PDF de programación - APUNTES FRAN PROGRAMACION ii

Estos apuntes son una recopilación y condensación de los apuntes de Jose Manuel
Carrillo, de algunos ejemplos del centro asociado de Vitoria y de algunos problemas
mas resueltos de los facilitados por el equipo docente.

No pretenden tener la profundidad de los creados por ejemplo por Jose Manuel Carillo
( sin los cuales yo no habría conseguido ni medio entender esta asignatura ) y mas son
un breve resumen, tocando solo las partes de creación de funciones recursivas e
iterativas, dejando en el tintero la conversión de recursivo a iterativo y sobre todo el
tema de coste de algoritmos, del que si consigo entender algo también haré un
resumencillo...

Lo que si he intentado es poner ejemplos de las demostraciones de los análisis por casos
y sobre todo de la verificación de funciones, que es lo que –aun sabiendo hacerlo de
manera mecánica – mas me costaba razonar y explicar, siendo esto parte fundamental en
el examen.

Probablemente estén llenos de erratas ( no soy ni mucho menos una autoridad en la
materia ), pero espero que al menos las demostraciones os sirvan de tanto como me ha
servido a mi realizarlas para aprender que además de poder desarrollar
Q(x)^Bnt(x)=>Q(s(x)) también puedes encontrarle un significado...

Como son bastante limitados ( no tenia intención ni de colgarlos, pero creo que pueden
ayudar para resolver alguna duda ) no tengo intención de ir ampliándolos ni nada así, así
que utilizar lo que os valga y lo que no pues ya sabéis que esta mal



1

Bnt(x)->c(f(s(x)),x)

caso Bt(x)->triv(x)
|
Fcaso

ESQUEMA DE UNA FUNCION RECURSIVA LINEAL: Final y No Final

{Q≡(x)}
Fun f(x:T1) dev (y:T2)



Ffun
{R≡(x,y)}

Si no es necesario la función combinación en el caso no trivial ( c(f(s(x),x)) entonces la
función es Recursiva Final

Si para calcular la función recursiva hemos debilitado la Poscondición R entonces
obtendremos una función recursiva no final. Si actuamos fortaleciendo la precondición
Q obtendremos una función recursiva final.

ANALISIS POR CASOS Y COMPOSICION:
Realizaremos los siguientes pasos para realizar nuestra función recursiva de manera
directa:

- Buscamos la descomposición recursiva que reduzca más drásticamente el

tamaño del problema.

- Se analizan los casos que puedan darse, identificando los casos triviales y no
triviales, bajo que condiciones se puede considerar un caso trivial y como hay
que tratarlos.

- Asegurarse de que la reducción aplicada en Bnt conduce a problemas más

pequeños que nos conducirán al caso trivial Bt.

- Asegurarse de que entre los triviales Bt y no triviales Bnt se cubren todos los

estados previstos por la poscondición.

- En la etapa de composición asegurarse de que los condicionantes son

-

mutuamente excluyentes.
Introducir declaraciones locales para evitar calcular repetidas veces la misma
expresión.


TECNICAS DE INMERSION NO FINAL:
Si queremos obtener nuestra función mediante inmersión no final a partir de una
definición previa del problema actuaremos de la siguiente manera:
NOTA: En los siguientes ejemplos trabajamos con una poscondición:
R≡s=∑α €{1..N}v[ α]


- Debilitaremos la poscondición mediante sustitución de constantes por variables

de manera que: R=>R1^R2. Como hemos incluido una nueva variable
(habitualmente i ) en la función, habrá que incluirla en la Precondición. Como
buscamos la precondición más débil, ampliaremos el rango de i, aprovechando
así para obtener el caso trivial.
Ejemplo: R≡s=∑α €{1..N}v[ α] => R≡s=∑α €{1..i}v[ α] ^ i=N

R1 R2



2

- En el análisis por casos, como el caso trivial ya lo tenemos ( desarrollar que

tiene que devolverse en el caso trivial Bt: anulación del cuantificador, elemento
neutro, etc... )
Ejemplo: Si i=0 entonces s=∑α €{1..0}v[ α] en este caso al anularse el rango
del sumatorio ( al ser sumatorio de un conjunto vació ) obtenemos 0, siendo
este el elemento neutro del sumatorio.

- Para calcular el caso Bnt realizaremos los siguiente pasos:
-
- El resultado debe de cumplir la poscondición R y es la combinación de f(x)

Realizaremos una llamada recursiva pero con el tamaño del problema reducido.

y f(s(x))

f(v,i-1)=f(s(x))=s`=∑α €{1..i-1}v[ α]

f(v,i)=f(v,i-1)+v[i]
por lo tanto cuando Bnt -> c(f(s(x),x)=f(v,i-i)+v[i] o s=s`+v[i]
o mas exacto:
s`=∑α €{1..i-1}v[ α] ( llamada recursiva )
s=∑α €{1..i}v[ α] (poscondición R)
para que s`=s le falta el termino v[i] osea s=s`+v[i] lo que satisfacerla la
poscondición, siendo esta la solución en el caso no trivial. Demostración:
s=v[1]+v[2]...v[i-1]+v[i] s`=v[1]+v[2]...+v[i-1]
esta claro que a s` le falta v[i] para ser s y satisfacer la poscondición.

- Definiremos la llamada inicial y la relación entre la original y la sumergida

isuma(v,N)=suma(v)


TECNICAS DE INMERSION FINAL:
Básicamente en la precondición pediremos que parte del trabajo se de “de hecho”
mediante un parámetro acumulador y seguiremos con los siguientes pasos:
- Actuamos como antes, pero R1 lo pasamos a la precondición como parámetro

acumulador y mantenemos R como poscondición Ej:
{Q≡ (0<=i<=N ) ^ (r=∑α €{1..i}v[ α]) }
Fun iisuma (v:vector [1..N] de enteros;i:natural;r:entero) dev (s:entero)
{R≡ s=∑α €{1..N}v[ α])}

- Análisis por casos:

Caso trivial: Pues sencillo, en Bt devolveremos r ya que en dicho caso r será el
total de todas las operaciones anteriores.
Demostración:
Si i=N r= ∑α €{1..i=N}v[ α]) ya que r= v[1]+v[2]+..v[N-1]+v[N]
Caso no trivial: En el caso no trivial lógicamente tendremos que acercarnos
progresivamente al caso trivial, por lo que realizaremos llamadas recursivas
reduciendo el problema. En este caso por ejemplo mientras i<N entonces
devolveríamos i<N -> iisuma(v,i`,r`) donde si i`=i+1 ( acercándonos al caso
trivial ) lógicamente r`=r+v[i+1] ( acumulado anterior mas el de la ejecución
actual con lo que podemos verificar la Poscondición ) quedando la llamada en el
caso no recursivo i<N -> iisuma(v,i+1,r+v[i+1])
Demostración:
Al llamar a iisuma (v,i+1,...) tenemos que r en esta llamada es
∑α €{1..i+1}v[ α]
En la ejecución anterior por lo tanto habría que devolver
∑α €{1..i+1}v[ α]= ∑α €{1..i}v[ α]+v[i+1]. Como ∑α €{1..i}v[ α] =r entonces
r`=r+v[i+1]

- Definiremos la llamada inicial como isuma2(v,0,0)=suma(v)



3

PLEGADO Y DESPLEGADO:
Nos permite convertir una función recursiva no final en recursiva final:

PASOS:
GENERALIZACION: Definimos una función generalizadora g(x,w) como
expresión dependiente de f(x) y en la que fijamos un valor de (w) para los cuales
g(x,w) se comporta como f(x)

DESARROLLAMOS EL ARBOL SINTACTICO: Desarrollamos el árbol sintáctico
a partir del caso no trivial. Ej: caso i>0 -> isuma (v,i-1)+v[i]

PASO 1
+

Isuma v[i]


v i-1



PASO 3
+

IIsuma r


v i


+

Isuma



PASO 2



Donde en el paso 3: iisuma(v,i,r)=isuma(v,i)+r
Y donde la llamada inicial en este caso siendo una suma, el elemento neutro seria el
0 por lo que iisuma(v,i,0)=isuma(v,i)

DESPLEGAMOS: Una vez desarrollado el árbol sintáctico realizaríamos el º
desplegado, donde:


Sustituimos isuma por su desarrollo:
Iisuma(v,i,r)= caso i=0 -> 0



| i>0-> isuma(v,i-1)+v[i] +r

Desplegamos:
Iisuma(v,i,r)= caso i=0 -> 0 +r



| i>0-> isuma(v,i-1)+v[i] +r

Reducimos:
Iisuma(v,i,r)= caso i=0 -> r



| i>0-> isuma(v,i-1)+(v[i]+r)

Plegamos:
Iisuma(v,i,r)= caso i=0 -> r



| i>0-> iisuma(v,i-1,v[i]+r)

Y como habíamos dicho anteriormente la llamada inicial será:
Iisuma(v,N,0)=isuma(v,N) ya que 0 es el elemento neutro del sumatorio

4



CORRECCION DE PROGRAMAS RECURSIVOS:

Hay que verificar formalmente la corrección de la función desarrollada.
Para ello hay que seguir los siguientes 6 pasos:

1) COMPLETITUD DE LA ALTERNATIVA: Q(x)=>Bt(x) OR Bnt(x)

Esto quiere decir que entre los casos triviales y no triviales se dan todos los casos
admitidos por la precondición.
EJEMPLO:
{Q≡ (0<=i<=N) } Bt=i=0 Bnt=i>0 sustituimos:
0<=i<=N => i=0 OR i>0 En este caso esta claro que todos los valores de i estan
contemplados.


2) SATISFACCION DE LA PRECONDICION EN LA LLAMADA INTERNA:

Q(x) ^ Bnt(x) => Q(s(x))
Esto quiere decir que verificamos que en el caso no trivial, la llamada recursiva se
realizara con parámetros que satisfagan la precondición.
EJEMPLO NO FINAL:
{Q≡ (0<=i<=N) } Bnt=i>0 {Q(s(x))= (0<=i-1<=N)}
(0<=i<=N} ^ i>0 =>(0<=i-1<=N)
Se puede afirmar que al ser i>0 i-1 será <=0 y también que i-1<N por lo tanto se
cumple la precondición en la llamada al estar i entre los valores admitidos.

EJEMPLO FINAL:
{Q≡ (0<=i<=N) ^(r=∑α €{i+1..N}v[ α])} Bnt=i>0 {Q(s(x)) ≡ (0<=i-1<=N) ^(r=∑α €{i..N}v[ α])}

Sustituimos:
(0<=i<=N) ^(r=∑α €{i+1..N}v[ α]) ^ i>0 =>(0<=i-1<=N) ^(r=∑α €{i..N}v[ α])



Por un lado comprobamos que se cumple la precondición en la siguiente

llamada a i siendo claro en este ejemplo que 0<=i-1 <=N



(0<=i<=N) ^(r=∑α €{i+1..N}v[ α]) ^ i>0 =>(0<=i-1<=N) ^(r=∑α €{i..N}v[ α])


Por otro lado comprobamos el acumulador donde podemos ver que:

r=∑α €{i+1..N}v[ α]) si sumamos v[i] en ambos lados obtenemos que:
r+v[i]= ∑α €{i+1..N}v[ α])+v[i] o r+v[i]= ∑α €{i..N}v[ α]) siendo este lado Q(s(x))
quedando demostrado que:


r+v[i]= ∑α €{i..N}v[ α])=v[i]+v[i+1]...v[N]=Q(s(x)) que es lo que queríamos
demostrar.



5


3) BASE DE INDUCCION: Q(x) ^ Bt(x) =>R(x,triv(x))

Se trata de comprobar que en el caso trivial el pred