PDF de programación - APUNTES PRGII

APUNTES

PROGRAMACIÓNII

Curso 1999 – 2000

© José Manuel Carrillo

Apuntes Programación II

U.N.E.D. – Curso 1999/2000

NOTA: El curso pasado (1999-2000) me enfrenté a esta asignatura con los mismos
prejuicios y reticencias que todos tenemos debido a los comentarios que hemos oído
acerca de su dificultad. Quizá la tomé como un desafío y por eso le dediqué muchas más
horas que a cualquier otra asignatura.

Como es lógico al principio no entendía nada. La primera luz apareció al consultar la
página de Jerónimo Quesada (http://www.bitabit.com). Es más que interesante que la
visitéis sobre todo a la hora de acometer la práctica.

Cuando conseguí entender de qué iba la asignatura volví sobre mis pasos y empecé a
estudiarla de nuevo.

Lo que tienes ahora en tus manos es el resultado de esas horas dedicadas a la asignatura.
He intentado plasmarlo más que como apuntes como guía para el estudio. Es decir, si yo
tuviera que volver a estudiar la asignatura lo haría siguiendo este orden. Al principio
todo te parecerá soporífero, pero si tienes paciencia, quién sabe, a lo mejor al final hasta
te resulta interesante. Por eso, es importante que al principio tengas un poco de
paciencia y te empeñes en llegar por lo menos hasta la página 17 de esta guía. Si al
llegar a este punto has entendido los ejemplos (páginas 10 a 17), quizá valga la pena
que vuelvas a empezar desde el principio, seguramente lo entenderás todo mucho mejor.

Que tengas mucha suerte.

José Manuel

2

Apuntes Programación II

U.N.E.D. – Curso 1999/2000

PRELIMINARES

ESPECIFICACIÓN DE PROBLEMAS

• La especificación ha de ser “precisa” y “breve” por lo que se requiere una

“especificación formal”

• Una técnica de especificación formal, basada en la lógica de predicados, se conoce

como técnica “pre/post” :

Si

S representa la función a especificar
Q es un predicado que tiene como variables libres los parámetros de
entrada de S
R es un predicado que tiene como variable libres los parámetros de
entrada y de salida de S

la especificación formal de S se expresa: {Q} S {R}

• Q se denomina PRECONDICIÓN y caracteriza el conjunto de estados iniciales para
los que está garantizado que S funciona (Se dice que la precondición describe las
obligaciones del usuario del programa).

• R se denomina POSTCONDICIÓN y caracteriza la relación entre cada estado inicial
y el estado final correspondiente. (Se dice que R describe las obligaciones del implementador).
• {Q} S {R} se lee como: “ Si S comienza su ejecución en un estado descrito por Q, S

termina, y lo hace en un estado descrito por R “.

(Si el usuario llama al algoritmo en un estado no definido por Q, no es posible afirmar
qué sucederá. La función puede no terminar, terminar con un resultado absurdo o
hacerlo con un resultado razonable).

• Emplearemos la siguiente notación para S:

a) Cuando las variables que aportan valores de entrada no pueden ser modificadas
por el algoritmo:

fun nombre (p1:t1;…;pn:tn) dev (q1:r1;…qm:rm)

Denominamos parámetros al conjunto de las variables que forman la interface
del algoritmo, distinguiendo entre parámetros de entrada (pi) y parámetros de
salida (qj)

Las ti representan los tipos de datos asociados a los parámetros de entrada

Las rj son los tipos de datos asociados a los parámetros de salida

3

Apuntes Programación II

U.N.E.D. – Curso 1999/2000

Como hemos comentado, la notación fun se empleará siempre que los
parámetros de entrada y de salida formen conjuntos disjuntos.

b) Cuando un algoritmo puede modificar una variable, la notación será:

accion nombre (p1:cf t1;…;pn:cf tn)

donde cf puede ser:

ent
si el parámetro es solo de entrada
sal si el parámetro es solo de salida
ent/sal si es un parámetro de entrada/salida

y ti representa los tipos de datos asociados a los parámetros.

EJEMPLOS Y EJERCICIOS:

Del Texto Base conviene entender los ejemplos: “Algoritmo que calcule el cociente por defecto y el
resto de la división entera”; “Máximo de un vector”; “Posición del primer máximo del vector” y ¿Cómo
especificar la moda?

la colección de problemas curso 1999-2000 conviene hacer los ejercicios 1.1.2 (Hallar
De
precondiciones); 1.3.1 (Especificación de funciones); 6.1 (Algoritmo que calcule cuántos elementos de un
vector son múltiplos de un natural k); 6.2 (Algoritmo que resuelve un sistema de ecuaciones lineales); 6.3
(La celebridad); 6.4 (Módulo de un vector); 6.5 (media y moda); 6.6 (Posición del primer máximo de un
vector); 6.7 (Producto escalar de dos vectores); 6.8 (desplazamiento circular de los elementos de un
vector); 6.9 (Descomposición de un cuadrado) y 6.10 (longitud del menor segmento de un vector que
contenga, al menos, k ceros)

LÓGICA DE PREDICADOS

Aunque se estudia mejor en la asignatura Lógica Matemática conviene estudiar con
detenimiento, sobre todo de cara al test, algunas definiciones como:
• Variables libres y ligadas
• Satisfactibilidad, consecuencia lógica y equivalencia
• Especificación con predicados y Convenios

sobre cuantificadores y

sustituciones

EJEMPLOS Y EJERCICIOS:

De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 1.1.1 (Expresar mediante la
lógica de predicados una serie de enunciados en lenguaje natural); 1.2.1 (Extensión de un conjunto de
estados); 1.2.2 (Intensión de un conjunto de estados); 1.2.3 (Potencia); 1.2.4 (Formalización de
enunciados) y 1.2.5 (Formalización de enunciados)

4

Apuntes Programación II

U.N.E.D. – Curso 1999/2000

DISEÑO RECURSIVO

CONEPTOS BÁSICOS, TERMINOLOGÍA Y NOTACIÓN
• La recursividad permite que un procedimiento o función hagan referencia a sí

mismos dentro de su definición.

- Ello conlleva que una invocación al programa recursivo genera una o más
llamadas al propio subprograma, cada una de las cuales genera nuevas
invocaciones y así sucesivamente.

- Si la definición está bien hecha, las cadenas de invocaciones así formadas

terminan felizmente en alguna llamada que no genera nuevas invocaciones

- Ejemplo: Cálculo de la potencia n-ésima de un número “a”

Como quiera que an = an-1 * a , podemos definir la función potencia
de la siguiente forma: potencia(a,n) = potencia(a,n-1)*a
Para calcular an la función potencia calcula primero an-1 mediante la
llamada recursiva a la función con los parámetros (a,n-1) y el resultado de
la llamada recursiva se multiplica por a para calcular el resultado de la
función. Pero, para calcular potencia(a,n-1) se produce una nueva llamada
recursiva: potencia(a,n-1)=potencia(a,n-2)*a ; por lo que para saber lo
que vale an-1 previamente la función deberá calcular el valor de an-2 y
multiplicar el resultado obtenido por a.
Pero el proceso no se puede repetir indefinidamente. Debe existir alguna
llamada que no genere nuevas llamadas recursivas. En este ejemplo como
a0=1 cuando tengamos que calcular potencia(a,0) en lugar de realizar una
nueva llamada recursiva, indicaremos a la función que directamente
devuelva el valor 1.
Veamos cómo se calcularía 53:
potencia(5,3) = potencia(5,2) * 5

potencia(5,2) = potencia(5,1) * 5

potencia(5,1) = potencia(5,0) * 5
potencia(5,0) = 1

potencia(5,3) = [(1*5)*5]*5 = 125

• El esfuerzo de razonamiento es menor trabajando en recursivo que en iterativo

- Veamos mediante el ejemplo de

la potencia n-ésima

la diferencia de

razonamientos recursivo e iterativo

- ITERATIVO: el problema P sería calcular an

Para resolverlo optamos por multiplicar n veces a por a por lo que
transformamos el problema original P en otro “p” que consiste en
multiplicar dos números (x,a)

5

Apuntes Programación II

U.N.E.D. – Curso 1999/2000

“x” irá acumulando los productos de a-es, por lo que se inicia a 1 y
a cada iteración su nuevo valor se obtendrá mediante la asignación
x := x*a
Repitiendo exactamente n veces el problema “p” se consigue
solucionar el problema original P

- RECURSIVO: tratamos de resolver el problema P suponiendo que P ya está
resuelto para otros datos del mismo tipo pero en algún sentido más
sencillos; es decir, suponiendo que ya sabemos calcular an-1
resolver el problema original an es inmediato.
En el razonamiento recursivo hay involucrado un solo problema P
y un solo tipo de datos

• Para que el razonamiento recursivo sea correcto se requiere que la sucesión de
invocaciones no sea infinita. Se llegará entonces a unos datos lo suficientemente
sencillo como para que el problema quede resuelto directamente. Diremos que se
trata de un caso trivial
En nuestro ejemplo n=0 es un caso trivial an = 1

ASPECTO DE UN PROGRAMA RECURSIVO
• Habrá una o más instrucciones condicionales dedicadas a separar los tratamientos
correspondientes al caso (casos) trivial(es) de los correspondientes al caso (o casos)
no trivial(es).

• El tratamiento de los casos no triviales será:
1.- Se calculará el “sucesor” (dato que reduce el tamaño del problema)“subproblema”
2.- A continuación se produce una llamada recursiva para obtener la solución al
subproblema
3.- Finalmente se opera sobre el resultado obtenido para el subproblema a fin de
calcular la solución para el problema inicial

En nuestro ejemplo: potencia(a,n) es el problema

Caso trivial: n=0 potencia(a,n)=1
Caso no trivial:

n>0

1.- sucesor: n-1
2.- llamada recursiva: potencia(a,n-1)
3.- como potencia(a,n)=an y potencia(a,n-1)=an-1
tendremos potencia(a,n)=potencia(a,n-1)*a

luego para

n>0 potencia(a,n)=potencia(a,n-1)*a

6

Apuntes