Ap

GUÍA PARA APROBAR EL EXAMEN DE PROGRAMACIÓN II Este texto se encuentra dirigido a aquellos que ya se han estrellado contra la asignatura. Los novatos pueden usarlo también, por supuesto. Vamos a suponer que el examen consiste básicamente en el desarrollo, como en la práctica, de un supuesto. Y que en dicho supuesto hay un vector.

RECURSIVIDAD Especificación de la función: Consiste en una terna QSR en la que: Q es la precondición. Lo que deben cumplir los datos de entrada. S es la definición (exclusivamente) de la función. Debe tener variables de entrada y de salida. R es la postcondición. Las condiciones que debe cumplir la (las) variables de salida. Q es Q(x) siendo x las variables de entrada. R es R(x,y) siendo x las variables de entrada e “y” la variable de salida. S puede ser: Función: (fun) si devuelve un valor. Acción: (accion) si existe alguna variable que sea de entrada Y salida. No pide nada más. Pero empiezan tus problemas: R debe ser exacto. Si te equivocas, por la regla del dominó, no vas a tener nada bien. Así que míralo bien y compruébalo dos veces antes de seguir. En primer lugar comprueba que el tipo de datos coincide con el especificado en la salida. Si es binario (CIERTO, FALSO), tienes que establecer unos criterios lógicos (algo es igual o distinto a otra cosa, Y/O etc.). Si es natural comprueba que haces cálculos en el ámbito de los naturales (div en lugar de /). También procura no mezclar enteros con naturales, y por supuesto, cuidado con mezclar ambos con los reales. Pero, como suponemos que hay un vector que recorrer, no es tan difícil: a) Encontrar algo. Responder cierto si... R(x,y)≡{b=(∃ α∈ [1..n]· α cumple la condición)} b es binario. b) Demostrar que se cumple algo. Responder cierto si... R(x,y)≡{b=(∀ α∈ [1..n]· α cumple la condición} b es binario. c) Contar los elementos que cumplen la condición. R(x,y)≡{s=Ν α (desde 1 hasta n) · α cumple la condición} s es natural. d) Sumar elementos del vector. R(x,y)≡{s=Σ α (desde 1 hasta n) } s depende del tipo de los datos del vector. e) Multiplicar elementos del vector. R(x,y)≡{s=Π α (desde 1 hasta n) } s depende del tipo de los datos del vector. Q debe ser lo menos restrictivo posible. Y ahí entran las opiniones. Si el equipo docente de la asignatura decide que has sido demasiado restrictivo, mal comienzas:

Si un número es natural, poner que es mayor o igual que cero es una tontería. Mejor no ponerlo. Si un número es natural, (CARDINAL) o entero (INTEGER), poner que tiene unos límites (MAXINT, MAXCARD) es demasiado apegado a la práctica y aquí somos muy teóricos. Prueba con “verdadero”. Y piensa en qué trampa vas a caer. ¿Realmente hay alguna condición que deben cumplir los parámetros de entrada?. ESQUEMA DE UN PROGRAMA RECURSIVO

Primera inmersión o inmersión no final: La especificación no vale para nada, y nadie le pide que haga nada, porque no es posible. Así que vamos a “sumergirla” (inmersión) para que aprenda a bucear. Es decir, vamos a convertirla en recursiva. Para eso necesitamos una variable que no está. Para ello necesitamos reforzar la poscondición (R) debilitándola. Oficialmente y para todos los efectos la estamos debilitando. Que el libro [Peña97] parezca contradecirse a sí mismo es sólo una circunstancia en la que no vamos a entrar (*). DEBILITAR. Y debilitar significa coger ese (“existe, para todo, conteo, suma o producto” desde el primero hasta el último) y convertirlo en otro desde el primero hasta una variable i. ¿Que usaste ya i precisamente en eso?. ¡Qué falta de previsión!. Vale. Usaremos c. Por tanto: R’≡(R debilitada) ∧ (c=n) Aunque R’ ,R y Rdebilitada son incomparables por lógica (según [Peña97]**), la lógica aquí vale poco. A todos los efectos R’ y R son equivalentes. ¿Qué pasa con S?. Debemos reescribir S incluyendo la variable c. ¿Qué pasa con Q?. Tenemos que reforzarla (esta vez sí) incluyendo una limitación a c. Pongamos que Q’ ≡ Q ∧ (c<=n). NO es la única solución. Pero al equipo docente de la asignatura le gusta esta. Tanto que muy pocos se atreven a hacerlo de otra manera. Por si acaso, vamos a hacerlo así.

¿Qué tipo le has dado a c?. ¿Natural?. Es natural que lo hagas. Pero no te confíes. En su momento puede que tengas que romperlo todo y empezar de nuevo.

Análisis por casos: En el análisis por casos tienes que hacer tres cosas. La primera es decidir qué es Bt. En castellano el caso trivial. En las prácticas, el rango de la matriz va desde 1 hasta n [1..n]. El caso trivial es cero (0). En los exámenes el rango de la matriz suele ir desde 0 hasta n. Así que el caso trivial es menor que cero. Lo que programando, si has definido c como natural te provoca un bonito código de error. Mejor define c como entero en lugar de natural. Pero cuidado con hacerlo al revés. Si has definido c<=n y pones como caso trivial c>n acabas de estrellarte contra la ruda realidad. Suspenso. Y eso que, te lo adelanto ya, no vas a detectar el error con la “famosa” verificación formal de programas recursivos. ¿Que porqué?. Porque aunque nadie te lo haya dicho, Bt y Q’ tienen que tener algo en común. Bt ∧ Q’ ≠ falso. Obligatoriamente. Cuando lleguemos a Bt aún debemos estar en Q’. Una vez que has decidido qué es Bt puedes ampliarlo a tu conveniencia. Con tal de que el Bt original esté en el rango que has creado para él. Si es cero, c=0 no hay ningún inconveniente en poner c<1. Por supuesto el caso trivial conduce al elemento neutro de la operación. 0 en conteo y suma, 1 en productos y potencias, falso (elemento neutro de la conjunción) si en R tenemos un ∀ o cierto (elemento neutro de la disyunción) si tenemos en R un ∃. Esto es triv(x). Lo segundo es decidir qué se hace en Bnt. Caso no trivial. Se supone que se examina el caso concreto. El momento c. Y se llama recursivamente a la función variando c por c-1 (lo habitual), o c+1 (invertido). Y lo tercero es decidir cual es la llamada correcta a la función. ¿Cual es el valor Cini?. “Evidentemente” es el otro extremo del vector. Si Bt es cero, Cini es n. ¿Está claro?. Repito: “c” recorre el vector hasta salirse. Y se tiene que salir, así que en Q tienes que dejarle espacio. Si el vector va desde 1 hasta n se sale en 0 o en n+1. Si el vector va desde 0 hasta n se sale en -1 o en n+1. COMPRUEBA Q. Y CAMBIA LO QUE SEA PRECISO. Así pues tenemos: Q’(x)≡Q(x) ∧ (c<=n)

S’≡ fun iLoQueSea (x variables de entradas, c entero (o natural)): dev resultado. Caso c<extremo inferior → elemento neutro de la operación c>=extremo inferior → “análisis para el momento c” (OP) iLoQueSea (x,c-1) R’(x,y) ≡ Rdebilitada ∧ (c=n) (El extremo inferior es el rango más pequeño del vector. Si va “desde 1 hasta n” el extremo inferior es 1. Por tanto Bt es c<1) Si en R tenemos un ∀ la operación OP es Y (∧). Si tenemos un ∃ la operación es O (∨). En el resto de los casos, habitualmente suma, producto. Verificación formal de la inmersión no final. Francamente, y ahora que no nos oye el equipo docente de la asignatura: esto tiene más agujeros que un queso Emmental (que es el de los agujeros. El gruyére es como el queso de barra, con unos agujeritos muy pequeños). En primer lugar unas consideraciones sobre ⇒. Significa que el segundo predicado es más débil que el primero. Es decir, que el primero es más restrictivo que el segundo (más fuerte). a∧b⇒a. Por supuesto, a∧b⇒b. (1) a⇒a∨b. Por supuesto, b⇒a∨b (2) Falso ⇒ cualquiercosa. Pero olvídalo. Si te sale falso vas bastante mal. Cualquiercosa ⇒ cierto. Y esto sí lo vamos a usar. (3) 1.- Completitud de la alternativa. Q(x) ⇒Bt ∨ Bnt. En Q(x) por (1) tomamos sólo la parte de c. Si te sale algo así como (cn) ∨ (c<=n ), es decir, (cn) no tienen un Bt común. Porque cuando llamas a c>n no se cumple la precondición. Sin embargo (c<=n) ⇒ (c<1)∨ (c>=1), es otra vez (c<=n)⇒cierto y apruebas. 2.- Satisfacción de la precondición para la llamada interna. Hay que demostrar que Q(x) Bnt(x) ⇒ Q(s(x)) En este caso hay que tener en cuenta que no sirven ni ciertos ni falsos. Q(x) Y Bnt(x) es, más o menos, Q(x). ¿Qué es Q(s(x))?. Pues es sólo Q(x) cuando sustituimos c por el valor de la siguiente llamada recursiva. Los casos posibles están contados. Más o menos cuatro. Supongamos que c varía entre n y 1. Hemos definido Q’(x) como Q(x) (c<=n) [y mayor o igual que cero, pero eso no lo ponemos si c es natural]. Entonces: Q(x) Bnt(x) ⇒ Q(s(x))

c<=n c>1 ⇒ c-1<=n c<=n c>1 ⇒ c-1<=n. Y podemos dejarlo ahí. Porque si c<=n entonces c-1<=n-1 lo que es más restrictivo que c1<=n En el caso alternativo, cuando c varía entre 1 y n entonces Q(x) Bnt(x) ⇒ Q(s(x)) c<=n+1 c<=n ⇒ c+1<=n+1 c<=n ⇒ c<=n Y basta. 3.- Base de la inducción. Hay que intentar demostrar que Q(x) Bt(x) ⇒ R(x, triv(x)) Lo cual es evidente, si lo hemos hecho bien. Q(x) Bt(x) es Bt(x) sin más o menos. Si nos da falso estamos en problemas, ya te lo he dicho. R(x, triv(x)) es cierto. Así que Bt(x) ⇒cierto. Lo que es indiscutible. Pero como los profesores nos van a calificar por lo que hagamos, vamos a hacerles creer que sabemos lo que estamos haciendo. R(x, triv(x)) es el resultado de R cuando ponemos en x el valor de Bt y en el resultado el resultado trivial. Es decir, si para Bt(x) devuelve 0 entonces: R(x, triv(x))0=(”en un rango imposible” de algo). (Desde 1 hasta 0 habitualmente. O desde n+1 hasta n). Si hemos cuidado en poner en triv(x) el elemento neutro de la operación será lo que salga (es lo que sale) cuando se hace un recorrido en un rango imposible. Como 0=0 es cierto, pues ya está. O 1=1 o falso=falso. Que son las alternativas habituales. Sólo recuerda que el elemento neutro de la disyunción es ‘falso’, pero el de la conjunción es ‘verdadero’. Es decir: R(x,triv(x)) es el resultado booleano de una igualdad. Y la igualdad debe ser cierta. Si no lo es, echa mano del tipex. O tacha, que hay que arreglar poco. 4.- Paso de inducción. Aquí tendrás problemas hasta que comprendas que este método es el método de inducción. Lo de noetheriana está solo para despistar. Si es válido para cero, para uno, (los dos neutros, así nos curamos en salud), y suponemos que es válido para n. ¿Es válido para n+1?. Vamos a hacer cuentas y veremos lo que sale. Q(x) Bnt(x) R(s(x), y’) ⇒ R(x,c(y’,x)) Puedes ignorar Q(x) Y Bnt(x). Están, pero ignóralos. R(s(x), y’) es lo que hace. R(x, c(y’,x)) es lo que debería de hacer. Y si las dos cosas no coinciden, entonces, a borrar. Un par de ejemplos: a) Supongamos un algoritmo que suma los elementos de un vector. Q(x){c<=n} fun iSuma (x:vector [1..n]de reales):dev s real;

caso c=0  0 c>0  x[c]+iSuma (x,c-1) fcaso ffun R(x,y){s=(desde i=1 hasta c) x[i]}

{c=n}

Habíamos quedado que R(s(x),y) es lo que hace: R(s(x),y)x[c]+((desde i=1 hasta c-1) x[i] ) (hemos supuesto hasta c-1 y evaluamos c) Y también habíamos quedado en que R(x,c(y’,x)) es lo que debería hacer: R(x,c(y’,x)){s=(desde i=1 hasta c) x[i]} ¿Lo ves?. Espero que sí. b) Supongamos un algoritmo que busca un determinado valor en un vector. Q(x){r>0 c<=n} fun iBusca (x:vector [1..n]de naturales):dev b boolean; caso c=0  falso c>0  b=(x[c]=r) iBusca (x, c-1) fcaso ffun R(x,y){b=(  [1..c]  x[i]=r)} {c=n} Lo que hace: R(s(x),y) b=(x[c]=r) {b=(∃ [1..c-1]  x[i]=r)} Lo que debería hacer: R(x,c(y’,x)){b=(  [1..c]  x[i]=r)} Y si no lo ves recuerda que el símbolo se puede sustituir por una concatenación de disyunciones ( ) y el símbolo por una concatenación de conjunciones ( ). Ya hemos pasado lo difícil. Continuamos: 4.- Elección de una estructura de preorden bien fundado. Formalmente debes encontrar t: Dt1  Z tal que Q(x) ⇒ t(x)>=0 Lo que no quiere decir nada porque no hay nada que demostrar. Si a estas alturas no sabes lo que es t, vas un poquitín despistado. Si c recorre desde n hasta 1 (alternativamente 0) entonces t=c Si c recorre desde 1 hasta n entonces t=n-c Lo escribes bonito y ya está. y 5.- Demostración del decrecimiento de los datos. NO es decrecimiento de los datos. Es decrecimiento de la t que acabamos de definir en cada llamada recursiva. Te piden demostrar que Q(x) Bnt (x) ⇒ t(s(x))
Y para que sea cierto, t del sucesor de x tiene que ser menor que t de x. Si t=c entonces c-1
Comenzamos de nuevo: Tenemos una función inútil. Es la siguiente: Q(x) fun LoQueSea (x:variables de entrada):dev y R(x,y) Vamos a sumergir esta función en el proceloso mar de la recursividad: 1.- Buscamos una variable c. Esta variable va a recorrer el vector desde el extremo superior (n) hasta el extremo inferior (1 ó 0). Definimos automáticamente t = c. Ya tenemos el preorden bien fundado. 2.- Le hacemos un sitio a c dentro de la función inútil. Para ello... a) “Debilitamos” R. R≡Rdébil (c=n). En Rdébil sustituimos cualquier referencia a n por c. b) Introducimos c dentro de las variables de entrada de la función. c) Reforzamos Q incluyendo una referencia a c. Pero ojo, dale suficiente espacio: cuando se salga del vector, y se tiene que salir, aún debe cumplir Q’ Ya tenemos la función recursiva. Para el equipo docente “inmersora no final”. Q’(x)=Q(x) (c<=n) fun iLoQueSea (x:variables de entrada, c:entero):dev y R’(x,y)=Rdebil(x,y) (c=n) 3.- Llamada inicial. La tenemos encima: c=n. Pero si lo recorres de abajo a arriba en ambos casos debes poner c=1 (ó c=0 dependiendo del rango del vector). 4.- Análisis por casos: a) El caso Bt es cuando c se sale del vector [c<1, c<0 ó c>n]. Dependiendo que el vector esté en [0..n] ó [1..n]. Y si lo recorremos hacia arriba o hacia abajo. b) El caso Bnt es cuando c está en el vector. Todo lo demás. Es decir: [c>=1; c>=0; c<=n] a2) El caso Bt conduce a triv(x). Que es el elemento neutro de la operación que vamos a poner debajo, dentro de un momento. b2) El caso Bnt conduce al examen del momento “c” OP (operado con) una llamada recursiva en la que c pasa a c-1 ó c+1. Podríamos decir que es (Rdébil para c) OP (Rdébil desde 1 hasta c-1) [llamada

recursiva]. Y ahora demostramos que es correcto. ¿Alguien te ha informado ya que a los programadores se los paga o clasifica por los miles de líneas de código al mes que pueden hacer?. Problemas: -Tu R(x,y) es un desastre. Ni se acerca a lo que te están pidiendo. Mala suerte. -Q(x) es demasiado optimista o pesimista. Es decir más débil o más fuerte de la cuenta, en opinión del equipo docente de la asignatura. Mala suerte. -Te has empeñado en que 0 es el elemento neutro del producto. O, lo que es más habitual, que cierto es el elemento neutro de la disyunción (∃). -Por un olvido estúpido la llamada recursiva va a c. Lo que hace que el ordenador entre en un ciclo infinito y tengas que apagarlo a lo bruto. -Por enésima vez: ‘falso⇒CualquierCosa’ es formalmente correcto. Pero no sirve. Inmersión final: Según uno de los dos posibles libros de texto de la asignatura, [Peña 97], la inmersión final crea código más compacto, eficiente y menos comprensible. Si has tenido que hacer X prácticas obligatorias, con X >=2 sabes que eso no es cierto. No es más eficiente. Menos comprensible, sí, por supuesto. Entonces, ¿para qué la inmersión final?. Incumpliendo las reglas que me he impuesto para hacer esta guía, te voy a contar una historia que puede que te aclare este concepto. Y voy a hacerlo porque creo que nadie se ha molestado en explicártelo. Por supuesto no va a servir para que apruebes, así que puedes saltártelo tranquilamente. Supongamos que te encuentras en lo alto de una escalera. No sabes los pisos que hay hasta la salida. Tampoco sabes si los pisos tienen todos la misma altura o no, si la escalera se subdivide en varias, ni si hay varias salidas. En resumen, sabes poco. Pero quieres poder salir del edificio en caso de necesidad, a oscuras, medio dormido. Así que coges un montón de miguitas de pan y dejas caer una en el suelo. Después bajas un escalón (PUSH) llamándote recursivamente a tí mismo. Es decir: (miguita, escalón), (miguita, escalón), etc. Cuando se acaba la escalera y/o vislumbras la salida te dices a tí mismo: “Vale”. Esto es triv(x). Te das media vuelta y comienzas a subir los escalones (POP) recogiendo las miguitas que has dejado caer. Cuando estás de vuelta en el origen, tienes un montón de miguitas que te dicen el número de escalones que tienes que descender. Además puedes haber recopilado otra mucha información: número de descansillos, escaleras alternativas, puertas, etc. Después de hacer esto un par de cientos de veces te dices a tí mismo: ¿Y porqué no llevo conmigo una bolsa donde guardar las miguitas?. Así cuando termine, puedo coger el ascensor. ¿Coger el ascensor?.

Sí. En informática después de un número indeterminado de PUSH (llamadas a subrutinas) no tiene porque haber igual número de POP (retornos). Un único POP puede devolverte al punto de origen, a la llamada original. Siempre que no hayas tocado la pila de datos. Es decir, siempre que no te hayas dejado miguitas por ahí. Una función recursiva final no se deja cálculos para después. Se los lleva dentro de la propia función, dentro de la llamada recursiva. Así que tiene su bolsa, real o virtual en la que guardar las miguitas. Esto exige un cambio de mentalidad: Estás en lo alto de la escalera y te dices a tí mismo: “De acuerdo. Supongamos que estoy en la salida. Me digo a mí mismo ‘Vale’ y cada vez que baje un escalón pienso que lo estoy subiendo y recogiendo la miguita, que voy a guardar en esta bolsa”. Y además tienes que estar seguro que el número de miguitas no va a cambiar por hacerlo así. Porque estás metiendo en la bolsa en primer lugar la última miga y eso puede ser importante. ¿Entonces es más eficiente?. NO. Y no lo es porque el conserje del edificio, el señor Compilador es muy serio y tiene responsabilidades ante el resto de los propietarios y, sobre todo, ante el presidente de la comunidad, Don Sistema Operativo. Así que cuando te ve haciendo PUSH con tu montón de miguitas se fía de tí lo justo y necesario, (es decir, nada) y te obliga a acompañarle escaleras arriba comprobando que no te has dejado ninguna miguita olvidada en la pila de datos. Que luego el ordenador se cuelga y nadie sabe porqué. En resumen: la posible mejor eficiencia de una función inmersora final depende del compilador. ¿Lo entiendes?. ¿Seguro?. Según [Peña97] en su página 62 el término inglés para “recursiva final” es ‘tail recursion’, es decir, recursividad de cola. Y las ‘funciones recursivas no finales” son en inglés ‘nontail recursive function’. Es decir, sin cola. VALE. Volvamos al principio de este apartado: Inmersión final: Vamos a crear una función en la que las operaciones que hasta ahora se hacían antes de la llamada recursiva, se hagan en la propia llamada recursiva. Una función inmersora final o recursiva final tiene una variable (una nueva variable) en la que se van acumulando los cálculos. Y el proceso de transformar una función recursiva final en otra final es automático y se llama “Desplegado y Plegado”. Que es lo que te van a poner en el examen. 1.- Hacer el árbol sintáctico de la operación. Queda muy bonito así que hazlo. Si lo haces a lápiz es más fácil arreglarlo. 2.- Defines ‘g’ como lo que ocurre en Bnt(x). Suele ser algo así: w OP iLoQueSea (x,c)

Por tanto: iiLoQueSea (x,c,w):=w OP iLoQueSea(x,c) Esto empieza a parecerse a eso de s:=s+t. 3.-En lugar de iLoQueSea(x,c) pones su análisis por casos. Y usas la propiedad distributiva. No te olvides, en algún momento, de poner que has usado la propiedad asociativa. Lo esperan de tí, no los defraudes. 4.- Como tu objetivo final es convertir el caso no trivial en una llamada a iiLoQueSea, busca la ocasión. Notas: No olvides que en el caso trivial nos llevamos la bolsita de migas. Eso es w. Si has utilizado correctamente la propiedad distributiva, no hay problema. La llamada inicial es triv(x). iiLoQueSea (x,c,triv(x))=iLoQueSea (x,c) Así que: Q’‘(x) fun iiLoQueSea (x:variables de entrada, c: entero, w:datos):dev s datos. caso Bt(x) → w Bnt(x) → iiLoqueSea (x,c-1, (w OP Rdébil para c)) ffun R(x,y) En el que, para bordarlo: R(x,y) es el original. No R’ sino el primero. Q’‘(x) es Q’(x) ∧ (w=R *hasta ahora*). *Hasta ahora* en descendente es desde c+1 hasta n. *Hasta ahora* en ascendente es desde 1 hasta c-1. Fin de la recursividad. Ejercicio para meditar: ¿Porqué no se verifican las funciones recursivas finales?. Parece un poco tonto hacer una cosa, comprobarla, modificarla y no comprobar la modificación. O como se dice en Informática: “Si funciona, no lo toques”. Así que, ¿porqué no se verifica después de obtener la función recursiva final?. [Peña 97] da un argumento: “No tiene interés optimizar un programa incorrecto”. Bien. ¿Qué opinas?.

ITERACIÓN Es posible que tengas la idea de que, si en lugar de desarrollar un supuesto recursivo en el examen fuera iterativo tendrías más probabilidades de aprobar. Que es más fácil. Yo también tuve esa idea en su momento. No es cierta. Las probabilidades de suspender son las mismas en ambos casos. Lo que sí es cierto es que puedes caer en los mismos errores. Así que manténte alerta. Verificación formal de programas iterativos. Una cosa buena que tienen los programas iterativos es que el proceso de verificación formal es idéntico al proceso de creación del programa. Es decir, la verificación formal puede utilizarse para crear un programa correcto. El esquema de un programa iterativo es el siguiente: Q(X) fun LoQueSea-it (x variables de entrada):dev s inicio (P)Mientras B hacer restablecer avanzar fmientras dev s ffun R(x,y) Suponemos, como ya hemos hecho con el caso recursivo que tenemos que recorrer un vector. El proceso de verificación formal de programas recursivos consta de 6 pasos, numerados, según [Peña97] del 1 al 6. El mismo autor establece 6 pasos para la verificación formal de programas iterativos, numerados del 0 al 5. ¿Puedes encontrar algún motivo por el que sea así?. Alguno habrá, así que procura recordarlo: En iterativo los pasos de verificación van del 0 al 5. 0.- Encontrar P, invariante y t función limitadora. Este paso 0 es, en su segunda parte, igual al paso 5 del proceso recursivo. Respecto a la primera parte, también tuvimos que hacer algo así cuando generamos la función recursiva no final. Y, realmente, también en ese momento se definía t. Tomemos R. Vamos a debilitarlo sustituyendo n por c, de tal manera que: R≡ Rdébil ∧ (c=n) Uno es el invariante. El otro ¬B. Nos estamos adelantando, pero no importa. Rdébil es el invariante. La función limitadora t es igual a (n-c).

1.- P ∧ ¬B ⇒ R Cae por su propio peso. Siempre que consideremos que el R original y el R descompuesto en una conjunción son equivalentes, aunque sean incomparables. Como ya lo había dicho para el caso recursivo, no insistiré en el tema. Escribes lo mismo en los dos lados de la ecuación lógica y ya está. Dado que ¬B es (c=n) entonces B ≡(c ≠ n) 2.- {Q}Inicio{P} ¿Esto qué es?. ¿Es una ecuación o inecuación lógica?. ¿Hay alguna manera de saber qué está en qué lado de la fórmula, igualdad, o lo que sea?. Para eso está esta guía, ¿no?. Para aclarártelo. Lo que ocurre es que te han cambiado la terminología. El primer capítulo tenía su terminología propia, el segundo capítulo se dedicaba a explicar la terminología del tercer capítulo, pero al llegar al cuarto era hora de cambiar. Que en esta asignatura la terminología tiene una fecha de caducidad muy inferior a la del pescado fresco. En dos capítulos huele mal y hay que tirarla. Después de una meditación profunda llegamos a que {Q}Inicio{P} puede ser interpretado como Q≡ P(inicio). Y en unos momentos sustituiremos ≡ por ⇒ . Vamos a ser más concretos. Necesitamos dos variables. Una ya la conocemos, c, y vamos a usarla en el control del bucle. Y la otra es una variable que al final será s. No podemos usar s porque no está definida (en Módula2, por ejemplo se define el tipo pero no el nombre de la variable que devuelve la función. Es la función llamante la que tiene un nombre (propio) para esa variable). Para mantener la terminología dentro de un orden será w, nuestra querida bolsita de migas de pan. Así pues: inicio: var c:entero; w:mismo tipo que s; fvar; c:=extremo inferior del rango del vector-1 (cero si el rango es [1..n]; -1 si el rango es [0..n]) w:=triv(x) finicio Te recuerdo que ¬B es (c=n) por decisión unilateral. Es decir que recorremos el vector desde el extremo inferior al superior. Puedes hacerlo al revés, si quieres. Al equipo docente le gusta así, lo que es un argumento importante. ¿Entonces porqué definimos c fuera de rango?. Porque esto, en el fondo, es equivalente a lo que poníamos en el punto 3 de la verificación de programas recursivos: base de inducción. P tiene que dar cierto. Y para eso, como hacíamos allí,

[0=Σ ”desde 1 hasta 0” de algo]. Sustituimos 0(w=triv(x)) por 1, cierto o falso y Σ por Π ,∀ ó∃. En el fondo no necesitamos Q. Porque P(inicio) tiene que ser cierto. Si estamos en paralelismos entre recursividad e iteración, y este punto es equivalente a la base de inducción. Entonces, ¿qué pasa con el anterior?. ¿No debería ser ese el equivalente?. También. Ten en cuenta que {P} es un predicado intermedio que vale de postcondición de la primera parte (inicio) y precondición de la segunda (restablecer, avanzar). Así que el punto anterior verifica “3" en la segunda parte y este en la primera. 3.- {P ∧ B} S {P} Ya que estamos buscando paralelismos que nos orienten, volvemos al caso recursivo. Esto es, terminologías aparte, igual que el punto 2 de la verificación recursiva. Allí decíamos que: Q(x) ∧ Bnt ⇒ Q(s(x)). Como acabamos de decir, {P} es precondición del bucle. Luego: {P ∧ B} S {P} ≡ P ∧ B ⇒ P(S). Que es lo mismo que en recursión. Lo cual nos da una idea bastante clara de lo que tenemos que hacer. Demostrar: Debemos calcular P(S). Dado que P es un invariante, es decir, una fórmula que no varía a lo largo del bucle, si todo es correcto entonces P ⇒ P. Construir: Para construir bien un algoritmo iterativo de entrada, necesitamos definir las dos subfunciones restablecer y avanzar. Avanzar, la última es fácil. Tenemos que asegurarnos que la función t recorre su camino hasta el final. Y como estamos hablando de vectores, y como lo estamos recorriendo desde el extremo inferior (1) al superior (n) y t=(n-c) entonces avanzar: c:=c+1 favanzar. Avanzar habitualmente destruye el invariante. Pero como es “invariante” la función restablecer debe arreglarlo. En este momento, en el libro de Peña aparece el error más grande. El predicado T. T ≡ P ∧B Dentro de poco va a volver a aparecer T con otro sentido. Teniendo tantas letras a su alcance, ¿porqué repetirla?. ¿Sólo para complicarnos la vida un poco más a los pobrecitos que queremos aprobarla?. Dado que B es c≠ n tenemos: [Rdébil hasta c] ∧ [c≠ n] ⇒ P(S). En S sólo hemos definido avanzar, que hace que c aumente en una unidad. Luego, [Rdébil hasta c] ∧ [c≠ n] ⇒ [Rdébil hasta c+1] Con lo cual parece claro la función de restablecer:

restablecer Rdébil para c+1. frestablecer NOTA IMPORTANTE: Cualquiera acostumbrado a programar escribiría: “mientras B hacer c:=c+1; Rdébil para c; fmientras.” Lo cual parece correcto, bonito y fácilmente comprensible. Además es más lógico: avanzar destruye primero la invariancia y después restablecer cumple con su función. ¿Quieres aprobar?. Entonces escribe: “mientras B hacer R débil para c+1 c:=c+1 fmientras.” Sin discusiones. Simplemente hazlo. 4.- P ∧ B ⇒ t>=0 A t no se le pide que sea un preorden bien fundado. Se le pide que sea natural. Y los naturales, con la relación < es un orden estricto. Que es más estricto, más fuerte que los p.b.f. {P ∧ B} es, para estos efectos, {B} Es decir, en nuestro supuesto: (c ≠n) ⇒ (n-c)>=0 Lo cual es cierto si consideramos que c<=n. Que es como lo hemos definido. En Inicio. 5.- {P ∧ B ∧ (t=T)}S{t
(n-c) -1 < n-c. Lo cual es cierto. Hay una propiedad de la resta que dice que si sumamos un número al sustrayendo, restamos ese mismo número al resultado. Parece ser que hemos terminado. Y que el procedimiento era muy similar al de los programas recursivos. ¿Donde está entonces el núcleo de la inducción noetheriana, el paso de inducción?. En el punto 3. No te lo dije para no ponerte nervioso. Esta es la equivalencia entre recursividad e iteración: Recurs ividad 1 2 3 4 5 6

Iteració n ---3 1,2 3 0,4 5

Comentarios Innecesario. B∨¬ B≡cierto, por definición. P actúa como Q P actúa como Q en 1 y como R en 2 P actúa simultáneamente como Q y R. P actúa como Q P actúa como Q

De lo cual se deduce que es fácil convertir programas recursivos en iterativos, y viceversa. Lo cual forma parte de nuestro siguiente capítulo.

TRANSFORMACIÓN RECURSIVO-ITERATIVO. Como sabrás la transformación de inmersión no final a iterativo da un doble bucle, mientras la transformación de una función inmersora final a iterativo da un sólo bucle. Y si quieres saber porqué deberías leerte ese cuento sobre escaleras y miguitas que te dejaste atrás. La transformación es rápida y fácil. Veamos un esquema en el que pasamos de iterativo a recursivo rápidamente. Q(x) fun LoQueSea (x, variables de entrada):dev s inicioA: var c: entero (o natural); w:mismo tipo que s; inicioB: c:=extremo inferior -1 w:=triv(x); mientras c≠ n hacer restablecer:

w:=w OP Rdébil para c+1; avanzar: c:=c+1; fmientras dev w; ffun; R(x,y) ≡ Rdébil(desde 1 hasta c) ∧ (c=n) En el que B= (c≠ n) y P=Rdébil (desde 1 hasta c) Su equivalente recursivo final será: Q’‘(x) ≡ Q(x) ∧ (c<=n) ∧ (w=R débil desde 1 hasta c-1) fun iiLoQueSea (x, variables de entrada, inicioA): dev s caso ¬B → dev w B → iiLoQueSea (x,avanzar, restablecer); fcaso ffun R(x) Y su llamada inicial es iiLoQueSea (x,inicioB)

ESTUDIO DEL COSTE Si estamos repasando un vector para averiguar algo, las probabilidades de que el coste esté en el orden de Θ(n) son muy altas. El libro de [Peña97] no es mal libro en este sentido. Conviene memorizar las recurrencias por resta y por división. Las soluciones, por supuesto. Hay unos factores que hay que tener en cuenta: son k, b, a. k es el exponente del coste de Bt(x). Habitualmente 0 (coste unitario) salvo que haya algún bucle interno. En ese caso k puede ser 1, 2 o más. b es el número que restamos a t para cada llamada recursiva. Normalmente 1 a es el número de llamadas recursivas en Bnt. Si a es mayor que 1 entonces el problema es NP y su coste exponencial: a(n div b). Habitualmente 2n . Es decir, a=2, b=1. En este caso k es irrelevante. Si a es 1 entonces el problema es P y su coste polinómico. Es decir nk+1. Como generalmente el coste de Bt es constante (k=0) entonces T(n)=n. Salvo que haya uno o varios bucles internos. Y acaba de aparecer nuestro tercer T. Y el primero que aparece en el libro. ¡Qué manía de repetir la misma letra!.

Si nos dicen que un algoritmo tiene un coste de “n*log n” o mejor aún “log n” está claro que ese algoritmo trabaja por división y no por resta. Me refiero a “avanzar”. En el análisis de recurrencias por división nos encontramos con las mismas letras k, b y a. La diferencia está, como ya he dicho que en el primer caso se calcula (n-b) y en este (n/b). Comparamos a con bk. Como habitualmente k=0 comparamos a con 1. (No con b. b0=1). Si a < 1 (difícil. Muy difícil) el coste es Θ(n0) (1). Si a=1 entonces el coste está en Θ(logn). Si a>1 entonces el coste está en Θ(n logba). Considerando a=2 y b=2 entonces (n). Si k=1 (suponiendo un bucle interno de recurrencias por resta), y presuponemos b=2 entonces: Si ab (a>2) entonces Θ(n logba). Para a=4 Θ(n 2). Logba lo leemos como “Logaritmo en base b del número a”. FIN

(*) ¿Realmente se contradice a sí mismo?. No. Lo que pasa es que juega al despiste. Las páginas claves son 42-43, 86-87 y 134. La página 42 comienza con una definición “equivocada”. La definición 2.13. En ella se define como “más fuerte (resp. más débil)” entre predicados algo que no es exactamente “más fuerte”. Porque en castellano esas dos palabras tienen sentido estricto: excluyen la igualdad. Cosa que no ocurre en este caso. Por tanto la definición correcta debería ser “más fuerte o igual de débil que (resp. más débil o igual de fuerte que)”. A continuación en la misma página nos enteramos que un predicado siempre puede ser reforzado añadiendo una conjunción. Y eso es cierto incluso si el segundo predicado es una tautología (cierto), es decir, no modificamos el primer predicado. Igualmente puede ser debilitado añadiéndole una disyunción sea cual sea el segundo predicado. Pero también podemos debilitar un predicado expresándolo en forma conjuntiva. Después de desmontar todos nuestros esquemas de esa manera tan suave y sutil, después de un montón de horas pensándolo y sometiendo el ejemplo al tercer grado (lo que en mi caso fueron tres años, más o menos), se puede llegar al convencimiento de que, efectivamente, es más débil. Y más débil en sentido estricto. Pero hablando estrictamente ambos predicados son incomparables. Que es lo que nos dicen a continuación. Roberto Alonso Menlle, en su excelente trabajo (**)“Erratas y Escolios PeDos” (en Wainu) demuestra que no lo son; que son totalmente comparables y además que el segundo es más débil, estrictamente, que el primero.

Al final de este apartado nos enteramos que: falso ⇒P y que P⇒cierto. Pasemos a las páginas 86 y 87. No presumiré de comprender lo que pone en el apartado 2.b de la página 86. Sin embargo da la impresión que la implicación está equivocada. Si pasamos al ejemplo 3.3, en la página 87, después de la palabra “obviamente” aparece algo que sí parece comprensible. Y el símbolo ⇒ está al revés. El libro se contradice a sí mismo. PUES NO. No se contradice. Despiste 1: Las expresiones de las páginas 42 y 87 no son iguales. En la página 42 se pone un rango a la variable entre 0 y 10 mientras en la página 87 la variable tiene un único valor: n. Despiste 2: Rdébil (pág 87) es más débil que R. Pero ambas son incomparables, según hemos visto en la página 42. Despiste 3: Rdébil (a,b,s,i) ∧ (i=n) es equivalente a R. Por tanto no sólo es más débil que R sino también más fuerte que R. (en sentido no estricto, por supuesto). La oportunidad más clara que tiene el libro de contradecirse a sí mismo está en la palabra “obviamente”. Porque no es obvio que la implicación tenga que estar en ese sentido ni pasaría nada por ponerla en el otro sentido. Y sólo es obvio si comprendemos que las dos expresiones son equivalentes. Pero el libro no dice que no lo sean. Claro que tampoco dice en ningún momento que lo sean. Terminaré con la página 134. En principio es una repetición de las páginas 86-87, pero enfocado en el invariante P, que es equivalente al Rdébil. Incluso lo reconoce al hablar de la similitud del método con el presentado en la Sección 3.4. Pero cada vez que utiliza la expresión “débil” (más débil, debilitar, debilitada, debilitamiento. Hasta 6 veces aparecen términos que contienen “débil”) lo hace en sentido estricto. Lo que no ayuda nada en absoluto. Pero explica porqué en la página 87 se escribe la implicación al revés. Porque aquí se necesita que P ∧¬B⇒R. Lo que nos lleva al despiste fundamental que hace que uno se rompa la cabeza y no logre entender nada: Despiste 0: El término “más débil” tiene dos significados. Y el libro sólo lo utiliza en sentido estricto, que es el sentido habitual. Es cuando no utiliza el término cuando lo utiliza con sentido no estricto. Es decir, cuando nos encontramos la implicación pero el libro se cuida muy mucho de escribir en palabras la relación que existe entre ambos predicados. Veamos si podemos llegar a alguna conclusión: Tenemos cuatro predicados. Son R, Rdébil, Bt y Bnt. Alternativamente tenemos estos otros cuatro predicados: R, P, ¬B y B.

Tenemos que: R⇒Rdébil. (R⇒P). Rdébil ∧ Bt ⇒ R. Pero R⇒ Rdébil ∧ Bt. Por tanto R≡ Rdébil ∧ Bt. Alternativamente R≡P∧¬B. Y lo que nos lleva directamente al ejemplo de la página 42: R⇒ Rdébil ∧ Bnt (R⇒ P ∧ B). Por último, y sólo porque soy un pesado: El hecho de que en la página 43 se reconozca que falso⇒CualquierCosa no es una patente de corso. No puede ser utilizado en ningún caso. BIBLIOGRAFÍA: He utilizado un único libro, el primero de los dos alternativos que se citan en la guía del curso, y tal como es citado por el equipo docente del curso: [Peña97]: Ricardo Peña Marí.. Diseño de Programas. Formalismo y Abstracción. 2ª Edición. Prentice Hall, 1998 Recomiendo encarecidamente la lectura de “Erratas y Escollos en P2” de Roberto Alonso Menlle. Puede encontrarse en Wainu, en la página web de la asignatura. Carlos de la Cruz Gómez. [email protected]

APUNTES PROGRAMACIÓNII 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.

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. 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? De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 1.1.2 (Hallar 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).Apuntes Programación II U.N.E.D. – Curso 1999/2000 5 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 a n = a n-1 * a , podemos definir la función potencia de la siguiente forma: potencia(a,n) = potencia(a,n-1)*a Para calcular a n la función potencia calcula primero a n-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 a n-1 previamente la función deberá calcular el valor de a n-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

a 0 =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 5 3 : 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 a n 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).Apuntes Programación II U.N.E.D. – Curso 1999/2000 6 “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 a n-1 resolver el problema original a n 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 a n = 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)=a n y potencia(a,n-1)=a n-1 tendremos potencia(a,n)=potencia(a,n-1)*a luego para n>0 potencia(a,n)=potencia(a,n-1)*a.Apuntes Programación II U.N.E.D. – Curso 1999/2000 7 SINTAXIS • En el LR (lenguaje recursivo) no hay instrucciones en el sentido d órdenes que han de ser seguidas secuencialmente por un computador. En su lugar hay expresiones • La instrucción “condicional” de los lenguajes imperativos se convierte aquí en una expresión. Un condicional está formado por un conjunto de alternativas de la forma Bi à à Ei separadas entre sí por el símbolo [] • La ejecución de un condicional comienza evaluando todas las expresiones boolea-nas Bi. Si ninguna, o más de una, resultan ciertas, el resultado del condicional es indefinido y el programa aborta su ejecución. • Veamos pues el “aspecto” del programa que calcula la potencia n-ésima de un número escrito en LR: fun potencia(a:entero; n:natural) dev (p:entero) caso n=0 1 [] n>0 a*potencia(a,n-1) fcaso ffun. • En ocasiones una expresión E ha de aparecer repetidas veces como subexpresión de otra expresión más compleja E’ . Para evitar la escritura repetida y evitar tener que evaluar dicha expresión más de una vez, se introduce una declaración local. La sintaxis es “sea x = E en E’(x) “ e indica que la expresión E sólo se evalúa una vez, que llamamos x al resultado de su evaluación y que dicho valor puede aparecer repetidas veces en E’ Ejemplo: Supongamos que al escribir un programa en LR tenemos: caso xa+b … [] x=s … [] x>s … TERMINOLOGÍA: • Cuando una función recursiva genera a lo sumo una llamada interna por cada llamada externa, diremos que es una función recursiva lineal (recursiva simple) • Cuando genera dos o más llamadas internas por cada llamada externa diremos que es recursiva no lineal (recursiva múltiple)..Apuntes Programación II U.N.E.D. – Curso 1999/2000 8 • Podría ocurrir que en el texto de una función recursiva lineal aparecieran varias llamadas recursivas, una en cada alternativa diferente de una instrucción condicional. La recursividad sigue siendo lineal. ESQUEMA DE UNA FUNCIÓN RECURSIVA LINEAL Afortunadamente en los ejercicios de este curso todas las funciones con las que

trabajaremos son recursivas lineales. (Ojo para el test puede caer algo de recursividad múltiple). El esquema general es el siguiente: Donde:1.- Los parámetros x e y han de entenderse como tuplas “x1,…, xn” e “y1,…,yn” (parámetros de entrada y resultados respectivamente) 2.- Bt(x) representan los casos triviales (protección caso trivial); y Bnt(x) los casos no triviales (protección caso no trivial) Para todo (x) que satisfaga la precondición debe ser Bt (x) ^ Bnt(x) falso; es decir los casos triviales y no triviales han de ser conjuntos disjuntos. 3.- triv(x) representa el resultado de la función para el caso trivial 4.- Vallamos más despacio al analizar la expresión c(f(s(x)),x). Volvamos al ejemplo de la potencia n-ésima. En este caso tenemos: (x) {a,n} ; (y) {p} ; f(x) potencia(a,n) Bt(x) n=0 y triv(x) 1 Bnt(x) n>0 y c(f(s(x)),x) ≡ ¿? s(x) es la función “sucesor” que en nuestro ejemplo era s(x) n-1. f(s(x)) es la llamada recursiva a la función, pero con el parámetro sucesor. En el ejemplo f(s(x)) potencia(a,n-1). c(f(s(x)),x) es la función “combinar”. Para resolver el problema original (a n ) a partir del resultado devuelto por la llamada recursiva (a n-1 ) es preciso realizar una operación adicional que llamamos “combinar” (se combina el resultado devuelto con parte de los parámetros originales). En este caso, como a n = a * a n-1 se puede concluir que potencia(a,n) = a * potencia(a,n-1). Es decir; c(f(s(x)),x) a * potencia(a,n-1) {Q( x )} fun f( x : T1) dev ( y :T2) caso Bt( x ) triv( x ) [] Bnt( x ) c(f(s( x )), x ) fcaso ffun {R( x , y ).Apuntes Programación II U.N.E.D. – Curso 1999/2000 9 5.- Finalmente R(x,y) es la postcondición de la función f y establece la relación que ha de cumplirse entre los parámetros (x) y los resultados (y). [p = a n ] • Cuando la función “combinar” no es necesaria, es decir f(x) = f(s(x)) en el caso no trivial, diremos que f es recursiva final. En caso contrario, f es recursiva no final. • Las funciones recursivas finales son más eficientes en cuanto a tiempo y en orden de complejidad y su transformación a iterativo es más directa. ANALISIS POR CASOS Y COMPOSICIÓN No todos los problemas son tan sencillos como el ejemplo de la potencia n-ésima En esta fase tendremos que estudiar cómo se pueden descomponer recursivamente los datos de problema. No hay reglas ya que se trata de la etapa más creativa del diseño. • Hay que tener en cuenta que en general habrá más de una forma de hacerlo. La

solución más eficiente se alcanza casi siempre escogiendo la descomposición recursiva que más drásticamente reduce el tamaño del problema. • En esta etapa se analizan los casos que se pueden presentar a la función, identificando los que pueden considerarse no triviales, y qué solución hay que aplicar en estos casos, y bajo qué condiciones el problema ha de considerarse trivial y cómo se resuelve entonces. • Aunque después se estudiará cómo verificar formalmente la corrección del diseño, hay dos comprobaciones importantes que hacer en esta etapa: 1.- Asegurarse que la reducción aplicada al problema en el caso no trivial conduce a problemas cada vez más pequeños, (reducción del tamaño del problema), que necesariamente terminan en el caso trivial. 2.- Asegurarse de que entre los casos triviales y no triviales se han cubierto todos los estados previstos por la postcondición. • La etapa de composición consiste solo en expresar, en forma de programa LR, el resultado del análisis por casos. Hay dos consideraciones importantes: 1.- Asegurarse de que las condiciones de las instrucciones condicionales son mutuamente excluyentes. 2.- Introducir declaraciones locales para evitar calcular repetidas veces la misma expresión EJEMPLOS Y EJERCICIOS: Llegados a este punto es conveniente leer y entender los siguientes ejemplos del Texto Base: Algoritmo de Euclides para calcular el mcd de dos números. La división entera La potencia entera reconsiderada..Apuntes Programación II U.N.E.D. – Curso 1999/2000 10 TÉCNICAS DE INMERSIÓN • Sucede con frecuencia que no es posible abordar directamente el diseño recursivo de una función f. • Una técnica que puede solucionar el diseño consiste en: “Definir una función g, más general que f, es decir, con más parámetros y/o resultados que, para ciertos valores de los nuevos parámetros calcula lo mismo que f” • Diremos que hemos aplicado una inmersión de f en g g función Inmersora f función Sumergida generalmente usaremos para g con el mismo nombre que f precedido por una “i” • Para calcular la función original basta con establecer el valor inicial de los nuevos parámetros que hacen que la función inmersora se comporte como la sumergida. ¿Qué quiere decir todo esto?. Bueno, si has tenido paciencia y has llegado hasta este punto, creo que lo que viene a continuación puede aclararte bastante las ideas. Vamos a ver un par de ejemplos. El primero lo he tomado prestado del profesor Jerónimo Quesada a quien quiero agradecer públicamente la inestimable labor que realiza ya que sin sus ejercicios jamás habría llegado a entender de qué va esta asignatura, y cuya página web es visita obligada para cualquier estudiante de programación2. (http://www.bitabit.com) El segundo corresponde a la práctica del curso 99-00 (la que me ha tocado en suerte). A partir de este punto se hacen referencias continuamente a estos dos ejemplos a medida que avancemos en la teoría..Apuntes Programación II U.N.E.D. – Curso 1999/2000

11 EJEMPLO1: Dado un vector de enteros de dimensión N diseñar un algoritmo que calcule la suma de los elementos del vector. ESPECIFICACIÓN: {Q ≡ cierto} fun suma(v: vector[1..N] de enteros) dev (s: entero) {R ≡ s = ∑ α ∈ {1..N}. v[a]} (Confío que no tengas problema en escribir la especificación por ti mismo.) DISEÑO RECURSIVO: No parece fácil a primera vista encontrar una solución recursiva para esta función. Será preciso realizar una inmersión. ¿Qué es una inmersión?. Básicamente consiste en especificar un algoritmo en el que o bien se ha debilitado la postcondición (lo que dará lugar a una inmersión no-final) o bien se ha fortalecido la precondición (lo que dará lugar a una inmersión de tipo final) • Para obtener inmersiones la técnica más adecuada consiste en “manipular la postcondición” del algoritmo original. Consiste en introducir variables en lugar de constantes. En este ejemplo veamos qué ocurre si introducimos una variable “i” en sustitución de la constante “N” La postcondición original es: R ≡ s = ∑ α ∈ {1..N}. v[a] y al introducir la manipulación propuesta se obtiene R1 ≡ s’ = ∑ α ∈ {1..i}. v[a] Para obtener R a partir de R1 tendríamos que hacer i = N, luego se puede escribir: R ≡ ( ∑ α ∈ {1..i}. v[a] ) ^ (i = N); es decir: R ≡ R1 ^ R2 con R1 ≡ ∑ α ∈ {1..i}. v[a] y R2 ≡ i = N R1 es más débil que R en el sentido de que “pide menos” a la función. Mientras la postcondición original pedía a “s” que devolviera la suma de “todos” los elementos del vector, la nueva postcondición R1 “solo” exige que “s’” contenga la suma de los i-primeros elementos. Como hemos introducido un nuevo parámetro, la nueva precondición ha de incluir las condiciones que debe cumplir la variable incorporada. En este caso está claro que 1<=i<=N al tratarse de un índice que debe ser válido para el vector. Pero hay que tener en cuenta que se ha de intentar conseguir la precondición más débil. Por eso nos planteamos ampliar el rango de valores de i. ¿Qué ocurre si i=0?. En ese caso s = {1..0}. v[a] que, según convenio sobre cuantificadores, (ver Peña), sabemos que da como resultado s=0 al anularse el rango del sumatorio. Por tanto, podemos plantear 0<=i<=N que además nos “regala” una solución trivial al algoritmo: para i=0 s=0.Apuntes Programación II U.N.E.D. – Curso 1999/2000 12 Pero, vayamos un poco más despacio. En primer lugar escribamos la especificación de la función inmersora isuma: {Q 0<=i<=N} fun isuma(v: vector[1..N] de enteros; i: natural) dev (s: entero) {R s = {1..i}. v[a]} ANÁLISIS POR CASOS: (Trabajamos sobre valores de la nueva variable introducida) Como ya hemos comentado para i=0 s=0 (caso trivial) ¿ y para i>0 ? ¿? (caso no trivial) Para resolver el caso no trivial seguimos los siguientes pasos:

a) Realizamos una llamada recursiva a la función pero con el tamaño del problema reducido: isuma(v, i-1) b) El resultado de esa llamada debe cumplir la postcondición y por tanto, si llamamos s' al resultado de isuma(v, i-1) tendremos s' = {1..i-1}. v[a] c) Realizamos las operaciones adicionales necesarias para obtener un resultado que cumpla la postcondición para los parámetros originales a partir del valor devuelto por la llamada recursiva: Comparando el resultado de la llamada recursiva (s') y el de la llamada con los parámetros originales (s) s = v[1] + v[2] + ....+ v[i-1] + v[i] s' = v[1] + v[2] + …. + v[i-1] observamos que s = s' + v[i] En definitiva isuma(v,i) = isuma(v,i-1) + v[i] COMPOSICIÓN: El algoritmo completo correspondiente a la función isuma será: {Q 0<=i<=N} fun isuma(v: vector[1..N] de enteros; i: natural) dev (s: entero) caso i=0 0 [] i>0 isuma(v, i-1) + v[i] fcaso ffun {R s = {1..i}. v[a]} LLAMADA INICIAL: Finalmente, pero no menos importante, es saber bajo qué condiciones la nueva función isuma resuelve el problema original (llamada inicial). Es decir ¿qué parámetros hacen que la función isuma calcule la suma de los N elementos del vector? (éste era el problema original). En este caso es evidente que cuando i = N, la función isuma realizará el cálculo deseado. Por tanto suma(v) = isuma(v,N) La función obtenida es recursiva no-final; es decir, tras la llamada recursiva es necesario realizar una operación adicional antes de devolver el resultado [c(f(s(x)),x)].Apuntes Programación II U.N.E.D. – Curso 1999/2000 13 DISEÑO RECURSIVO FINAL: ¿Qué hubiera ocurrido si en lugar de "debilitar" la postcondición la mantenemos constante y lo que hacemos es "reforzar" la precondición? • En la precondición se pedirá que parte del trabajo "se dé hecho". En nuestro ejemplo podemos pedir en la precondición que se haya calculado previamente la suma de los i-primeros elementos. Estas sumas parciales se almacenan en un nuevo parámetro que llamamos parámetro acumulador. Así las cosas, nuestro algoritmo solo deberá preocuparse de "acumular" a dicho parámetro la suma de los elementos v[i+1]…v[n] del vector, ya que a la entrada al algoritmo el parámetro acumulador debe tener ya la suma de los elementos a[1]…a[i] . En definitiva, partimos, igual que antes de: R R1 ^ R2 con R1 {1..i}. v[a] y R2 i = N Pero con la diferencia de que ahora mantenemos como postcondición R y lo que hacemos es introducir un parámetro adicional, r = {1..i}. v[a] (acumulador). Pongamos entonces que la nueva precondición es: {Q 0<=i<=n ^ r = {1..i}. v[a]} (Observa que se han introducido dos parámetros adicionales i, r y que a r se le pide, a la entrada del algoritmo, que contenga la suma de los i primeros elementos del vector).

Pues bien, la especificación de la nueva función isuma2 será: {Q 0<=i<=n ^ r = {1..i}. v[a]} fun isuma2(v:vect[1..N] de entero; i:nat; r:entero) dev s:entero {R s = {1..n}. v[a]} ¿Cómo utilizar esta nueva función isuma2 para resolver el problema original?. Es decir, ¿cómo hacer que isuma2 devuelva la suma de todos los elementos del vector? Parece obvio que si i=0, entonces r=0, es decir que al llamar a la función con el valor del parámetro i=0 "se le pasa" la suma de 0 elementos y por tanto el trabajo a realizar por la función será la suma de todos los elementos. Esto es suma(v) = isuma2(v,0,0) será la llamada inicial. ANÁLISIS POR CASOS: • Casos triviales: Si la llamada se hace con i=n resultará que r ya tiene la suma de los n elementos del vector (r = {1..i}. v[a]) y por tanto la función se limitará a devolver el valor de r..Apuntes Programación II U.N.E.D. – Curso 1999/2000 14 ¿ Y cuando i0 isuma2(v, i+1,r+v[i+1]) fcaso ffun {R s = {1..n}. v[a]} obteniendo de esta forma una función recursiva final. No debemos caer en el error de pensar que estas soluciones son únicas. Más bien todo lo contrario. Por ejemplo, si a la hora de debilitar la postcondición, nos hubiéramos planteado: R R1 ^R2 con Rs = {i+1..N}. v[a] y R2 i=0 todo habría sido diferente: La inmersión no final sería: y la inmersión final sería: {Q ≡ 0<=i<=N} {Q ≡ 0<=i<=n ^ r = ∑ α ∈ {i+1..N}. v[a]}

fun isuma(v: vector[1..N] de ent; i: nat) dev (s: ent) fun isuma2(v:vect[1..N] de ent; i:nat; r:ent) dev s:ent caso i=N 0 caso i=0 r [] i0 isuma2(v, i-1,r+v[i]) fcaso fcaso ffun ffun {R ≡ s = ∑ α ∈ {i+1..N}. v[a]} {R ≡ s = ∑ α ∈ {1..N}. v[a]} llamada inicial: suma(v) = isuma(v,0) llamada inicial: suma(v) = isuma2(v ,N,0).Apuntes Programación II U.N.E.D. – Curso 1999/2000 15 EJEMPLO2: En el conocido juego del Tetris se dispone de una pantalla por donde caen las piezas que se codifica en una matriz de n filas por m columnas definida como sigue: t: vector[1..n, 1..m] de nat Siendo la primera coordenada de la matriz el número de la fila y la segunda coordenada el número de columna. Cada posición almacena un número natural que representa el código del color de la pieza que ocupa dicha casilla. El valor 0 representa una casilla vacía. Se pide diseñar una función que dada una matriz t con las características descritas y un número de fila f entre 1 y n nos diga si la fila f-ésima está completamente llena de piezas y, por tanto, representa una línea completada en el juego. ESPECIFICACIÓN: {Q 1<=f<=n} fun linea(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) {R b = {1..m}. t[f,a]>0} DISEÑO RECURSIVO: INMERSIÓN NO FINAL R R1 ^ R2 con R1 (b = {1..i}. t[f,a]>0) y R2 (i = m) Razonando de manera análoga a como se hizo en el ejemplo1 se obtiene el código: {Q (1<=f<=n) ^ (0<=i<=m)} fun ilinea(t: vector[1..n, 1..m] de nat; f,i: nat) dev (b: bool) caso i=0 cierto [] i>0 ilinea(t, f, i-1) ^ (t[f,i]>0) fcaso ffun {R b = {1..i}. t[f,a]>0} y la llamada inicial será: linea(t, f) = ilinea(t, f, m) Notas: 1.- Aunque inicialmente se piense en tomar 1<=i<=m se puede ampliar el rango con el valor i=0 ya que para dicho valor b = ∀α ∈ {1..0}. t[f,a]>0 ≡ "cierto" por convenio sobre cuantificadores. Además proporciona la solución para el caso trivial. 2.- Comparando ilinea(t, f, i) = t[f,1]>0 ^ t[f,2]>0 ^ … ^ t[f,i-1]>0 ^ t[f,i]>0 con ilinea(t, f, i-1) = t[f,1]>0 ^ t[f,2]>0 ^ … ^ t[f,i-1]>0 se llega a la conclusión: ilinea(t, f, i) = ilinea(t, f, i-1) ^ (t[f,i]>0) 3.- Cuando i=m la función ilinea comprobará que todos los elementos de la fila f-ésima son distintos de cero (línea completada); y por tanto calcula lo mismo que la función original linea. De ahí que la llamada inicial sea: linea(t, f) = ilinea(t, f, m).Apuntes Programación II U.N.E.D. – Curso 1999/2000 16

DISEÑO RECURSIVO FINAL {Q (1<=f<=n) ^ (0<=i<=m) ^ (bb = {1..i}. t[f,a]>0)} fun ilinea2(t: vector[1..n, 1..m] de nat; f,i: nat; bb: bool) dev (b: bool) caso i=m bb [] i<m ilinea2(t, f, i+1, bb ^ t[f,i+1]>0) fcaso ffun {R b = {1..m}. t[f,a]>0} y la llamada inicial será: linea(t, f) = ilinea2(t, f, 0, cierto) Notas: El razonamiento seguido es similar al del ejemplo1 con las particularidades siguientes: 1.- El parámetro bb comprueba si los i-primeros elementos de la fila f-ésima están o no ocupados. Cuando i=m al invocar la función el parámetro bb ya tendrá el valor de verdad correspondiente a la comprobación de todos los elementos de la fila f-ésima, por lo que la función devolverá el valor de bb. (caso trivial) 2.- En el caso no trivial, cuando i<m, y, dado que el caso trivial se da para i=m, lo lógico es pensar que el parámetro i se incremente (i' = i+1), con lo que la llamada interna será ilinea2(t, f, i+1, bb'). Esta llamada se hará con parámetros tales que se cumpla la precondición, y por tanto: bb' = {1..i+1}. t[f,a]>0 bb' = t[f,1]>0 ^ … ^ t[f,i]>0 ^ t[f,i+1]>0 como bb = {1..i}. t[f,a]>0 bb = t[f,1]>0 ^ … ^ t[f,i]>0 de la comparación de ambas se concluye que bb' = bb ^ t[f,i+1]>0 (solución para el caso no trivial) 3.- Respecto a la llamada inicial es obvio que cuando i=0 bb = "cierto" y la función ilinea2 tendrá que comprobar todos y cada uno de los elementos de la fila f-ésima, con lo cual "realizará el mismo trabajo" que la función linea. TEORIA, EJEMPLOS Y EJERCICIOS: Llegados a este punto es conveniente intentar entender las explicaciones teóricas de las técnicas de inmersión dadas en el Texto Base, intentando relacionar la teoría con lo puesto de manifiesto en estos ejemplos. Sería conveniente hacer el siguiente ejercicio: EJEMPLO3: Queremos una función que dados dos vectores a y b, cuyo tipo de datos es Tipovect = vector[1..n] de enteros (siendo n una constante) Calcule el producto escalar de a y b.Apuntes Programación II U.N.E.D. – Curso 1999/2000 17 EJEMPLO3: SOLUCIÓN ESPECIFICACIÓN: {Q ≡ cierto} fun prodesc(a,b: vector[1..n] de ent ) dev (p: ent) {R ≡ p = ∑α ∈ {1..n}. a[a] * b[a]} DISEÑO RECURSIVO: INMERSIÓN NO FINAL R R1 ^ R2 con R1 (p = {j..n}. a[a] * b[a]) y R2 (j = 1) {Q (1<=j<=n)} fun iprodesc(a,b: vector[1..n] de ent; j:nat) dev (p: ent)

caso j=n+1 0 [] j1 iprodesc2(a, b, j-1, s+a[j-1]*b[j-1]) fcaso ffun {R P = {1..n}. a[a] * b[a]} y la llamada inicial será: prodesc(a, b) = iprodesc2(a, b, n+1, 0).Apuntes Programación II U.N.E.D. – Curso 1999/2000 18 ) w , x g( r r 3) + isuma r vi TÉCNICAS DE DESPLEGADO Y PLEGADO Convierte programas recursivos no finales en recursivos finales. Se trata de transformar f, recursiva no final, en otra función g, recursiva final que calcule lo mismo que f. Los pasos a dar son los siguientes: 1.- Generalización: Se define una función como una expresión que depende de f y representa una generalización de la misma y se establece un valor inicial wini para el cual g se comporta como f - En la práctica se construye el árbol sintáctico de la operación c (combinar). A continuación se conserva el camino que va desde la raíz de árbol hasta la invocación a f y cada subárbol de éste camino se sustituye por un parámetro de inmersión diferente. - Si la función c tiene elemento neutro w0, entonces g es una generalización de f que se comporta igual que ella para el valor inicial w = w0. Volvamos a retomar nuestro ejemplo1 y dibujemos el árbol sintáctico de la operación c Las ramas laterales se rellenan con parámetros de inmersión y la ramas que parten de isuma se rellenan con los parámetros originales: La nueva función, que llamaremos iisuma será: iisuma(v, i, r) = isuma(v, i) + r Como el elemento neutro de la suma es el cero, tendremos: iisuma(v, i, 0) = isuma(v, i) 1) +

isuma v[i] vi-1 2) + isuma.Apuntes Programación II U.N.E.D. – Curso 1999/2000 19 2.- Desplegado: Para poder aplicar el desplegado y posterior plegado, la función c (combinar) ha de poseer elemento neutro y ser asociativa 2.1.- Partiendo de la igualdad iisuma(v, i, r) = isuma(v, i) + r , sustituimos la función isuma por su desarrollo: 2.2.- Trasladamos la operación adicional a cada uno de los casos (desplegado) 2.3.- Aplicando las propiedades, elemento neutro al caso trivial y asociativa al no trivial 3.- La expresión del caso no trivial de iisuma tiene el mismo aspecto de su definición; es decir, es igual a la función isuma, (con unos determinados parámetros), mas un sumando adicional (v[i] + r). Es decir isuma( ) + ( ) tiene el aspecto de isuma(v, k) + p = isuma(v, k, p); por tanto, si hacemos k=i-1 y p=v[i]+r tenemos: isuma(v, i-1) + (v[i] + r) = iisuma(v, i-1, v[i]+r) es decir: que resulta ser recursiva final (se ha eliminado la función combinar). La función recursiva final obtenida será: La llamada inicial de esta función, es decir, aquella que calcula lo mismo que la función original suma será: iisuma(v, N, 0) = isuma(v, N) = suma(v) [ ] r i v -1) i isuma(v, i • 0 i r) i, iisuma(v, +    χασο + → >0 → =0 = [ r v -1) i isuma(v, i • r i r) i, iisuma(v,    χασο ι]+ + → >0 0+ → =0 = [ +→> → = r) i]+ (v -1) i isuma(v, 0 i • r =0 i ìcaso r) i, iisuma(v, [ →> → = r) i]+ v -1, i iisuma(v, 0 i • r =0 i ìcaso r) i, iisuma(v, []

[] ffun r) i v -1, i iisuma(v, 0 i • r i caso :ent) (s dev :ent) r nat, : i ent; de 1..n vect : iisuma(v fun +→> → =0.Apuntes Programación II U.N.E.D. – Curso 1999/2000 20 La postcondición de esta función será la misma que la de la función isuma para el caso i=N; es decir la original de la función suma: R   s =    Î{1..N}. v[ a] La precondición deberá incluir condiciones adecuadas para el nuevo parámetro "r". Estas condiciones se pueden deducir del hecho de que iisuma = isuma(v, i) + r la función iisuma(v, i, r) devuelve åaÎ{1..N}. v[a] y la función isuma(v, i) devuelve åaÎ{1..i}. v[a] luego: iisuma = isuma(v, i) + r åaÎ{1..N}. v[a] = åaÎ{1..i}. v[a] + r , por tanto, podemos concluir que r =   Î{i+1..N}. v[ a] La precondición será: {Q º(0<=i<=N) ^ (r = åaÎ{i+1..N}. v[a])} Para finalizar reescribimos el algoritmo completo: {Q º(0<=i<=N) ^ (r = åaÎ{i+1..N}. v[a])} {R s = åaÎ{1..N}. v[a]} y como se puede comprobar, la llamada inicial iisuma(v, N, 0) = isuma(v, N) = suma(v) cumple la precondición ya que para i=N y r=0 tendremos: Q ≡ (00 tfi-1 ^ ilinea bb tfi [] [] ffun r) i v -1, i iisuma(v, 0 i • r i caso :ent) (s dev :ent) r nat, : i ent; de 1..n vect : iisuma(v fun +→> → =0.Apuntes Programación II U.N.E.D. – Curso 1999/2000 21 [ bb ^ 0 f, t ^ -1) i f, ilinea(t, i • cierto 0 i bb) i, f, iilinea(t,    χασο ι]> → >0 →==

[ bb ^ 0 f, t ^ -1) i f, ilinea(t, i • bb ^ cierto 0 i bb) i, f, iilinea(t,    χασο ι]> → >0 →== [ ] bb) ^ 0 f,i (t ^ -1) i f, ilinea(t, i • bb 0 i bb) i, f, iilinea(t,    χασο > → >0 →== iilinea(t, f, i, bb) = ilinea(t, f, i) ^ bb La operación ^ tiene como elemento neutro "cierto" y es asociativa. Desplegado: 1.2.3.Plegado: Como el elemento neutro de la operación "^" es cierto; iilinea(t, f,i,cierto) = ilinea(t,f,i) y, la llamada inicial será: iilinea(t, f, m, cierto) = ilinea(t, f, m) = linea(t, f) Las condiciones adecuadas para bb se deducen de iilinea(t, f, i, bb) = ilinea(t, f, i) ^ bb obteniéndose la siguiente: bb =    Î{i+1..m}. t[f, a]>0 (parámetro acumulador) Por tanto, la precondición será: {Q º(1<=f<=n) ^ (0<=i<=m) ^ (bb = "aÎ{i+1..m}. t[f,a]>0) } y el código para la función recursiva final obtenida por desplegado-pleagado: {Q º(1<=f<=n) ^ (0<=i<=m) ^ (bb = "aÎ{i+1..m}. t[f,a]>0) } {R b = "aÎ{1..m}. t[f,a]>0} [ bb) ^ 0 f, t -1, i f, iilinea(t, i • bb i bb) i, f, iilinea(t,    χασο ι]> → >0 → =0 = [] [] ffun bb) ^ 0 f,i t -1, i f, iilinea(t, 0 i • bb 0 i caso :bool) (b dev bool) : bb nat; : i nat; de 1..m 1..n, vect : iilinea(t fun >→> → =.Apuntes Programación II U.N.E.D. – Curso 1999/2000 22 EJEMPLO3: SOLUCIÓN PROPUESTA

El algoritmo de la función recursiva final obtenido por desplegado-plegado de la función iprodesc será: {Q (1 <= j <= n) ^ (pp = {1..j-1}. a[a] * b[ a]} fun iiprodesc(a,b: vector[1..n] de ent; j, pp: ent) dev (p: ent) {R p = {1..n}. a[a] * b[a]} y la llamada inicial: iiprodesc(a, b, 1, 0) = iprodesc(a, b, 1) = prodesc(a, b) [][] fcaso )) j b * j (a pp 1, j b, a, iiprodesc( n j • pp n j caso + + → <= → =.Apuntes Programación II U.N.E.D. – Curso 1999/2000 23 {Q( x )} fun f( x : T1) dev ( y :T2) caso Bt( x ) triv( x ) [] Bnt( x ) c(f(s( x )), x ) fcaso ffun {R( x , y ) ) x B ) x B ) x Q( nt t ( ( ∨ ⇒ )) x Q(s( ) x B ) x Q( nt ⇒ ∧ ( )) x triv( , x R( ) x B ) x Q( t ⇒ ∧ ( )) x , ' y c( , x R( ) ' y ), x R(s( ) x B ) x Q( nt ⇒ ∧ ∧ ( CORRECCION DE PROGRAMAS RECURSIVOS Una vez obtenido el código de la función recursiva, hemos de verificar formalmente su corrección. Sea la función recursiva lineal: los puntos a demostrar para verificar la corrección de la función f son: 1.- Completitud de la Alternativa: Se debe demostrar en este punto que entre los casos triviales y no triviales se cubren todos los casos posibles (todos los valores admitidos como parámetros en la precondición). 2.- Satisfacción de la Precondición par la llamada interna : Se ha de demostrar que las llamadas recursivas se realizan con parámetros que cumplen la precondición 3.- Base de la inducción: Se trata de comprobar que para el caso trivial, y con parámetros que cumplan la precondición, la solución que se devuelve cumple la postcondición. En definitiva: "las soluciones para los casos triviales han de cumplir la postcondición" 4.- Paso de inducción: Este suele ser el paso mas complicado en el caso de la inmersión no final. Hay que probar que se cumple la postcondición para los casos recursivos, (no triviales), a partir de la suposición de que la postcondición se satisface para los datos de la llamada interna. A la expresión R(s( x ), y ') se le llama Hipótesis de Inducción y se interpreta como que el valor devuelto por la llamada recursiva ( y ' = f(s( x ))) cumple la postcondición R Pues bien, suponiendo R(s( x ), y ') cierto y que se cumple Q( x ) para el caso no trivial

Bnt( x ), debemos deducir que tras la operación "combinar", se sigue cumpliendo la postcondición R.Apuntes Programación II U.N.E.D. – Curso 1999/2000 24 0 x) Q( ≥ Þh(x) B x) Q( nt <η(ξ) ∧ (x) Þh(s(x)) 5.- Elección de una estructura de preorden bien fundado (p.b.f.): Hay que encontrar una función h: DT1 Z tal que Es decir, se trata de encontrar una función de los parámetros de entrada en los enteros no negativos. Como el pbf más conocido son los naturales, en muchas ocasiones es posible dotar a un conjunto de una relación de pbf estableciendo una aplicación con el conjunto de los natutares N 5.- Demostración del decrecimiento de los datos: Se ha de demostrar que en cada llamada recursiva la operación previa que se realiza sobre los parámetros de entrada hace decrecer estrictamente los datos en relación al pbf previamente definido. La función que determina el pbf ha de disminuir estrictamente el valor en cada llamada. Lo que garantizan estos dos últimos puntos (5 y 6) es que la sucesión de llamadas recursivas conducen al caso trivial. Vamos a comprobar la corrección de las funciones obtenidas en los Ejemplos 1 y 2 Ejemplo1 1.A) Recursiva no final: {Q º0<=i<=N} fun isuma(v: vector[1..N] de enteros; i: natural) dev (s: entero) caso i=0 0 [] i>0 isuma(v, i-1) + v[i] fcaso ffun {R s = åaÎ{1..i}. v[a]} 1.- Completitud de la Alternativa: ) (x B ) (x B ) x Q( nt t rrr ∨⇒ (0<=i<=N) Þ(i=0) (i>0) lo que resulta evidente. "Todos los valores admitidos para i en la precondición se encuentran contemplados, bien en el caso trivial, bien en el no trivial. 2.- Satisfacción de la Precondición par la llamada interna: )) Q(s(x ) (x B ) x Q( nt rrr ⇒∧ En este caso: (0<=i<=N) ∧ (i>0) ⇒ 0<=i-1<=N ; es decir 0<=N Þ0<=i-1<=N Al ser i>0 entonces i-1>=0 y, por otro lado, como i<=N será i-1
el rango del sumatorio (convenio sobre cuantificadores). 4.- Paso de inducción: x)) ', c(y , R(x ') y ), R(s(x ) (x B ) x Q( nt rrrrrrr ⇒∧∧ En este caso: Q(x) (0<=i<=N) (1) Bnt(x) (i>0) (2) R(s(x),y') ºs' = åaÎ{1..i-1}. v[a] (3) c(y', x) ºs' + v[i] R s = åaÎ{1..i}. v[a] tenemos que comprobar que, cumpliéndose (1), (2) y(3); y teniendo en cuenta los valores de c(y', x) y R, resulta ser s = s' + v[i] Como s = ∑αÎ{1..i}.v[a] = v[1]+…+v[i-1]+v[i] = (∑αÎ{1..i-1}.v[a]) + v[i] = s' + v[i] 5.- Elección de una estructura de preorden bien fundado (p.b.f.): 0 ) h(x ) x Q( ≥ ⇒ r r Si elegimos h(v, i) = i está claro que como 0<=i<=N, para cualquier valor de i de los admitidos por la precondición será h(v, i) >= 0 5.- Demostración del decrecimiento de los datos: ) h(x )) ) B ) x Q( nt r r r r < ⇒ ∧ h(s(x (x En este caso: (0<=i<=N) (i>0) Þh(v, i-1) < h(v, i). Como h(v, i-1) = i-1 y h(v, i) = i; para i>0 resulta evidente que i-1 → =0.Apuntes Programación II U.N.E.D. – Curso 1999/2000 26 1.- Completitud de la Alternativa: ) (x B ) (x B ) x Q( nt t rrr ∨⇒ (0<=i<=N) Þ(i=0) (i>0) lo que resulta evidente. 2.- Satisfacción de la Precondición en la llamada interna: )) Q(s(x ) (x B ) x Q( nt rrr ⇒∧ Este es el paso más importante a verificar en el caso de la solución recursiva final ya que se debe garantizar que las llamadas recursivas cumplen la precondición. En este caso: (0<=i<=N) ^ (r = ∑αÎ{i+1..N}.v[a]) ^ (i>0) ⇒ (0<=i-1<=N) ^ (r + v[i]= ∑αÎ{i..N}.v[a]) Q(x ) Q(s( x )) (llamada iisuma(v, i, r)) (llamada iisuma(v, i-1, r+v[i])) [(0<=i<=N) ^ (i>0)] ^ (r = ∑αÎ{i+1..N}.v[a])⇒ (0<=i-1<=N) ^ (r + v[i]= ∑αÎ{i..N}.v[a]) Evidente De r = v[i+1] + … + v[N] , sumando v[i] a las dos partes de la igualdad se tiene: r + v[i] = v[i] + v[i+1] + … + v[N] = Î{i..N}.v[a]) ; que es lo que se quería

demostrar. 3.- Base de la inducción: )) x triv( , R(x x) ( B ) x Q( t rrrr ⇒∧ (0<=i<=N) ^ (r = Î{i+1..N}.v[a]) ^ (i=0) Þs = Î{1..N}.v[a]) = r Para el caso trivial (i=0) tendremos r = Î{1..N}.v[a] = s ; luego bastará que la función iisuma devuelva el valor "r" como solución que evidentemente cumple la postcondición. 4.- Paso de inducción: )) x y', c( , R(x ') y ), R(s(x ) (x B ) x Q( nt rrrrrrr ⇒∧∧ En el caso de la recursividad final prácticamente no hay nada que demostrar en este punto ya que si la llamada interna devuelve el valor y' que cumple la postcondición R, y puesto que no existe función "combinar", el valor devuelto cumple la postcondición. 5.- Elección de una estructura de preorden bien fundado (p.b.f.): 0 ) h(x ) x Q( ≥ ⇒ r r Si elegimos h(v, i) = i está claro que como 0<=i<=N, para cualquier valor de i de los admitidos por la precondición será h(v, i) >= 0 5.- Demostración del decrecimiento de los datos: ) h(x )) ) B ) x Q( nt r r r r < ⇒ ∧ h(s(x (x En este caso: (0<=i<=N) (i>0) Þh(v, i-1) < h(v, i). Como h(v, i-1) = i-1 y h(v, i) = i; para i>0 resulta evidente que i-10 ilinea(t, f, i-1) ^ (t[f,i]>0) fcaso ffun {R b = "aÎ{1..i}. t[f,a]>0} 1.- Completitud de la Alternativa: ) (x B ) (x B ) x Q( nt t rrr ∨⇒ (1<=f<=n) ^ (0<=i<=m) Þ(i=0) (i>0) lo que resulta evidente. 2.- Satisfacción de la Precondición par la llamada interna: )) Q(s(x ) (x B ) x Q( nt rrr ⇒∧ En este caso: (1<=f<=n) ^ (0<=i<=m) ∧ (i>0) ⇒ (1<=f<=n) ^ (0<=i-1<=m) ; es decir (0<=m) Þ(0<=i-1<=m) Al ser i>0 entonces i-1>=0 y, por otro lado, como i<=m será i-1<m por tanto, se puede afirmar que 0<=i-1<=m 3.- Base de la inducción: )) x triv( , R(x x) ( B ) x Q( t rrrr ⇒∧ (1<=f<=n) ^ (0<=i<=m) ∧ (i=0) ⇒ R(t, f, 0) En palabras, se trata de comprobar que la solución para el caso trivial cumple la postondición, es decir que cuando i=0, entonces, el valor "cierto" devuelto por la función, cumple la postondición b = ∀α ∈ {1..0}. t[f,a]>0 = cierto, lo cual resulta evidente al anularse el rango del cuantificador universal.

4.- Paso de inducción: )) x ', c(y , R(x ') y ), R(s(x ) (x B ) x Q( nt rrrrrrr ⇒∧∧ En este caso: Q(x ) ≡ (1<=f<=n) ^ (0<=i<=m) (1) Bnt( x ) ≡ (i>0) (2) R(s( x ), y ') ≡ b' = ∀α ∈ {1..i-1}. t[f,a]>0 (3) c( y ', x ) ≡ b' ^ t[f,i]>0 R ≡ b = ∀α ∈ {1..i}. t[f,a]>0 tenemos que comprobar que, cumpliéndose (1), (2) y(3); y teniendo en cuenta los valores de c(y', x) y R, resulta ser b = b' ^ t[f, i]>0 Como R ≡ b = (∀ α ∈ {1..i}. t[f,a]>0) = (t[f, 1]>0) ^…^ (t[f, i-1]>0) ^ (t[f,i]>0) = (∀αÎ{1..i-1}.t[f,a]>0 ^ (t[f, i]>0) = b' + t[f,i]>0.Apuntes Programación II U.N.E.D. – Curso 1999/2000 28 5.- Elección de una estructura de preorden bien fundado (p.b.f.): 0 ) h(x ) x Q( ≥ ⇒ r r Si elegimos h(t, f, i) = i está claro que como 0<=i<=m por precondición, para cualquier valor de i de los admitidos será h(t, f, i) >= 0 6.- Demostración del decrecimiento de los datos: ) h(x )) ) B ) x Q( nt r r r r < ⇒ ∧ h(s(x (x En este caso: (0<=i<=m) ∧ (i>0) ⇒ h(t, f, i-1) < h(t, f, i). Como h(t, f, i-1) = i-1 y h(t, f, i) = i; para i>0 resulta evidente que i-10} 1.- Completitud de la Alternativa: ) (x B ) (x B ) x Q( nt t rrr ∨⇒ En este caso planteamos: (0<=i<=m) Þ(i=m) (i<m) lo que resulta evidente. 2.- Satisfacción de la Precondición en la llamada interna: )) Q(s(x ) (x B ) x Q( nt rrr ⇒∧ En este caso: (1 ≤ f £n) ∧ (0 ≤ i ≤ m) ∧ (bb = ∀α ∈ {1..i}.t[f,a] > 0) ^ (i < m) Q(x ) (llamada ilinea2(t, f, i, bb))  (1 ≤ f ≤ n) ∧ (0 ≤ i+1 ≤ m) ∧ [(bb ∧ t[f, i+1] > 0) = ∀αÎ{1..i+1}.t[f, a]>0] Q(s( x )) (llamada iisuma(v, i-1, r+v[i])) a) [(0≤ i £m) ^ (i<m)] ⇒ (0≤ i+1 ≤ m) resulta evidente b) (bb ∧ t[f, i+1] > 0) ⇒ (∀αÎ{1..i}.t[f, a]>0) ^ t[f, i+1] > 0 ⇒ ∀αÎ{1..i+1}.t[f, a]>0 que es lo que se quería demostrar. 3.- Base de la inducción: )) x triv( , R(x x) ( B ) x Q( t rrrr ⇒∧ (1 ≤ f ≤ n)Ù(0 ≤ i ≤ m)Ù(bb=∀αÎ{1..i}.t[f,a]>0)^(i=m)  b=∀αÎ{1..m}.t[f,a]>0 = bb Para el caso trivial (i=m) tendremos bb = ∀αÎ{1..m}.t[f,a]>0 por precondición; pero si observamos la postcondición, bastará que la función ilinea2 devuelva el valor "bb"

como solución, (se han comprobado todos los valores de la fila f completa), que evidentemente cumple la postcondición..Apuntes Programación II U.N.E.D. – Curso 1999/2000 29 4.- Paso de inducción: )) x y', c( , R(x y') ), R(s(x ) (x B ) x Q( nt rrrrrrr ⇒∧∧ Si por hipótesis de inducción se cumple R(s( x ), y '), al no existir operación adicional, el resultado cumple la postcondición 5.- Elección de una estructura de preorden bien fundado (p.b.f.): 0 ) h(x ) x Q( ≥ ⇒ r r Si elegimos h(t, f, i, bb) = m - i está claro que como 0<=i<=m, para cualquier valor de i de los admitidos por la precondición será h(t, f, i, bb) >= 0 6.- Demostración del decrecimiento de los datos: ) h(x )) ) B ) x Q( nt r r r r < ⇒ ∧ h(s(x (x En este caso: (0<=i<=m) ∧ (i<m) ⇒ h(t, f, i+1, bb ^ t[f, i+1]>0) < h(t, f, i, bb). Como h(t, f, i+1, bb) = m – (i+1) = (m-i) - 1 y h(t, f, i, bb) = m - i; para 0<=i<m resulta evidente que (m-i) - 1< m - i y por tanto h(t, f, i+1, bb ^ t[f, i+1]>0) < h(t, f, i, bb) EJEMPLOS Y EJERCICIOS: De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 2.2.1, 7.3, 8.2, 8.3, 8.4, 9.1, 9.2, 9.3, 9.4, 9.5 Todo lo que caiga en tus manos sobre ejercicios relacionados con el diseño y verificación de algoritmos recursivos..Apuntes Programación II U.N.E.D. – Curso 1999/2000 30 DISEÑO ITERATIVO SEMÁNTICA DEL LENGUAJE En el lenguaje imperativo dado un estado inicial, la ejecución de un programa es determinista en el sentido de que la secuencia de estados por la que pasa, incluido el propio estado final, están completamente determinados por el estado de partida. Al conjunto de estados alcanzados por el algoritmo en un punto intermedio de su ejecución se les llama “aserciones o asertos” Consideramos un programa de la forma S = s1;…sn cuya especificación es {Q} S {R}. Al introducir asertos intermedios obtenemos {ΘºP}s1{P1}s2{P2}…{Pn-1}sn{PνºR} Las reglas del lenguaje imperativo se darán de la forma E m n ...,E' , E' ,...,E 1 1 con n>=0 y m>=1 y se lee: “De la veracidad de las expresiones E1,…En se infiere la veracidad de las expresiones E1,…Em AXIOMAS 1.- Una precondición siempre se puede reforzar. Q Q' {Q}S{R}

{Q}S{R}, ⇒ Si Q define un conjunto de estados admisibles como precondición de un algoritmo, también será admisible cualquier subconjunto suyo En particular, “falso” siempre es una precondición admisible aunque carece de interés ya que, al definir el conjunto vacío de estados, el algoritmo será inútil. 2.- Una postcondición siempre se puede debilitar. R {Q}S{R'} R' {Q}S{R}, ⇒ Si R define un conjunto de estados admisibles como postcondición de un algoritmo, cualquier “superconjunto” suyo también será admisible En particular, cierto siempre es una postcondición admisible si el programa termina. 3.- Las precondiciones admisibles para un algoritmo pueden componerse mediante las conectividades  y  siempre que se haga lo mismo en las respectivas postcondiciones RQR1111 2211 } }S{R {Q }, }S{R {Q } }S{R {Q }, }S{R {Q 2 2 2 2 ∨ ∨ ∧ ∧Θ.Apuntes Programación II U.N.E.D. – Curso 1999/2000 31 INSTRUCCIONES Nada: Los conjuntos inicial y final de estados coinciden, es decir, la instrucción nada siempre termina y su efecto sobre el estado del cómputo es nulo {Q}nada{Q} RQ {Q}nada{Q} ⇒ ≡ cualquiera que sea Q Abortar: No existe ningún estado de partida que garantice que la instrucción abortar termina en un estado definido { falso}abortar {Q}cualquiera que sea Q Asignación: Para cualquier postcondición R: E{R} }x R {Dom(E) E x := ∧ E x R se construye sustituyendo en R todas las apariciones libres de x por la expresión E Dom(E) es el conjunto de todos los estados en los que la expresión E está definida. La regla permite calcular una precondición admisible a partir de una postcondición. Ejemplo: En la especificación {Q} x:=x+1 {R}, calqular Q para distintas postcondiciones R: a) Ρ≡ x=7 {Q} x := x+1 Q ≡ x+1 x R ≡ x+1=7 ≡ x=6 {Ρ≡ x=7}

b) Ρ≡ x+y>0 Q ≡ x+1 x R ≡ x+1+y>0 ≡ x+y>=0 c) Ρ≡ y=2k Q ≡ x+1 x R ≡ y=2k (la expresión no contiene x) d) Ρ≡ ($x>=0. y=2x) Q ≡ x+1 x R ≡ ($x>=0. y=2x) (x no es libre) Cuando aparezcan en la expresión E componentes de un vector o cualquier tipo de operaciones parciales, se hará constar expresamente en la precondición el dominio de E Se admiten asignaciones múltiples, esto es, la asignación “simultánea” de una lista de expresiones a una lista de variables de los tipos adecuados. Por ejemplo <x, y> := permuta los viejos valores de x e y evitando sobreespecificar el orden en que han de tener lugar el conjunto de asignaciones. Así si x=6 e y=4 la asignación múltiple provoca que x=4 e y=6 que no es el mismo resultado que x:= y; y:= x secuencialmente ya que esto daría como resultado 4 tanto para x como para y. En general: } 1 1 {R} ,...E E ,...x x {R n n E 1...En x1...xn > >:=< <.Apuntes Programación II U.N.E.D. – Curso 1999/2000 32 Composición secuencial de instrucciones: {R} ;S {Q}S {R} {P}S {P}, {Q}S 21 21 Si S1 y S2 son asignaciones se calculan precondiciones en sentido inverso al del flujo del programa: partiendo de R, se calcula P mediante la regla de asignación y, tomando P como postcondición de S1, se aplica de nuevo la regla de asignación para calcular Q Ejemplo: Hallar Q en el algoritmo siguiente: (Calcular la precondición conocida la postcondición) {Q} {Q} x:= x+y; x:= x+y; y:= x-y; escribimos {P} x:= x-y; y:= x-y; {Ρ≡ (x=A) ∧ (y=B) {S} x:= x-y; {Ρ≡ (x=A) ∧ (y=B) y calculamos en sentido inverso {S} ≡ y> y> R <x-y, <x, ≡ (x-y=A) ∧ (y=B) ≡ (x=A+B) ∧ (y=B) {P} ≡ S <x,x-y> <x,y> ≡ (x=A+B) ∧ (x-y=B) ≡ (x=A+B) ∧ (y=A) {Q} ≡

y> y> P <x+y, <x, ≡ (x+y=A+B) ∧ (y=A) ≡ (x=B) ∧ (y=A) INSTRUCCIONES CONDICIONALES A.- Si B entonces S1 sino S2 fsi S sino S entonces B si fsi{R} Dom(B)} {Q {R} {Q {R}; B}S {Q 21 21 ∧ ∧¬Β}Σ ∧ La regla obliga a que se demuestre que se satisfacen las dos especificaciones del antecedente de la regla. Se puede partir también de la postcondición R, calculando hacia atrás las precondiciones. Es decir, partiendo de R se calcula Q1 para B y Q2 para ØB. Obtenidas ambas se calcula la precondición de “Si B entonces…” como: {Dom(B) ((Q1 B) (Q2 ØB))} Ejemplo: {Q} si x<0 entonces x:=x+1 sino x:=x-1 fsi {Ρ≡ x>=0} Para x<0 tenemos {Q1} x:= x+1 {Ρ≡ x>=0} luego hacia atrás calculamos Q1 x+1>=0 ≡ x>=-1.Apuntes Programación II U.N.E.D. – Curso 1999/2000 33 Para x>=0 tenemos {Q2} x:= x-1 {Ρ≡ x>=0} luego hacia atrás calculamos Q2 x-1>=0 ≡ x>=1 entonces: Q º(x>=-1 ∧ x<0) ∨ (x>=1 ∧ x>=0) ≡ (x=-1) (x>=1) B.- La segunda forma de instrucción condicional es la versión imperativa de la expresión “caso”: “caso B1à àS1 …. casoBnà àSn fcaso”; (ver en el libro las reglas) INSTRUCCIONES ITERATIVAS: INVARIANTES A.- “mientras B hacer S fmientras” Comienza evaluando la condición booleana B: • si B es falsa, el bucle equivale a la instrucción nada • en otro caso se ejecuta el cuerpo S de la iteración No es práctico dar una regla que permita calcular la precondición a partir de la postcondición. Invariante: Es un predicado que describe todos los estados por los que atraviesa el cómputo realizado por el bucle, observado justo antes de evaluar la condición B de terminación. El invariante se satisface antes de la primera iteración, después de cada una de ellas y, en particular, después de la última, es decir, a la terminación del bucle.

1.- Si el bucle termina, lo hace satisfaciendo el invariante P y la negación de la condición B Por tanto, R    ÙØB 2.- Además, el invariante P es a la vez precondición y postcondición del cuerpo S de la iteración (se debe cumplir antes de la primera iteración y después de cada una de ellas). En consecuencia se puede enunciar la siguiente regla: “Comenzando la ejecución del bucle en estados que cumplen P, si el bucle termina, lo hace cumpliendo P ØB : REGLA: S hacer B mientras fmientas{P {P} B}S{P} {P ¬Β} ∧ ∧ Pero la regla es incompleta ya que al exigir tan sólo que S mantenga la invarianza de P no garantizamos que el bucle termina, sólo afirmamos que si termina lo hace….Apuntes Programación II U.N.E.D. – Curso 1999/2000 34 Para resolver el problema debemos encontrar una función t: estados Z (función limitadora) que se mantenga no negativa mientras se realiza el cuerpo S y que decrezca cada vez que se ejecuta éste: 1.- P B t>=0 2.- {ÙB Ùt=T} S {t
mientras B hacer {P} S fmientras {R}.Apuntes Programación II U.N.E.D. – Curso 1999/2000 35 “El invariante P ha de ser lo suficientemente fuerte para que, junto con ØB conduzca a la postcondición R, y lo suficientemente débil para que las instrucciones Inic de inicialización, hagan que se satisfaga antes de la primera iteración, y, además, el cuerpo del bucle lo mantenga invariante”. Una técnica para “adivinar” invariantes consiste en tabular, para unas cuantas iteraciones, los valores de las variables modificadas por el bucle. De esta forma se clarifican las relaciones entre ellas. Algunas de estas relaciones formarán parte del invariante. El resto de condiciones (relaciones) para el invariante se irán descubriendo después a medida que se necesiten propiedades para completar las demostraciones de su verificación formal. VERIFICACIÓN FORMAL Puntos a demostrar: 0.- Inventar un invariante P y una función limitadora t 1.- ØB R 2.- {Q} Inic {P} 3.- {ÙB} S {P} 4.- ÙB t 0 5.- {Ùt=T} S {t
instrucción a derivar {R ≡ a=Adiv2 ∧ b=2B ∧ AB=u+ab } Ensayamos := y obtenemos: B Adiv baR 2,2 , ≡ (Adiv2=Adiv2) ∧ (2B=2B) ∧ (AB = u + (Adiv2)2B) ≡ AB = u + (Adiv2)2B ¿Es cierto que Q ⇒ Dom(E) ∧ E xR? (a=A) ∧ (b=B) ∧ (AB=u+ab) ⇒ AB = u + (Adiv2)2B , es decir u+AB = u+ (Adiv2)2B Esto será cierto sólo si A es par pero no si es impar. Si A es impar (Adiv2)*2 = A-1 y por tanto u+ (Adiv2)2B = u+(A-1)B = u+AB-B La instrucción resultante debe ser: caso par(n) := caso impar(n) := fcaso B.- DERIVACIÓN DE BUCLES Si hubiera necesidad de bucles anidados, se deriva cada uno por separado y se procede en sentido descendiente, es decir, derivando primero el más externo y progresivamente los internos. B1.- Derivación de bucles a partir de invariantes: 1.- Conociendo P y R determinar cuál ha de ser ØB para que P ØB R A partir de ØB se obtiene B 2.- Conociendo P se determinamos las instrucciones de Inicialización que hacen {Q} Inic {P} Estas instrucciones serán lo más simple posibles. Es posible que tengamos que hacer algunos ajustes a la precondición Q.Apuntes Programación II U.N.E.D. – Curso 1999/2000 37 3.- Hasta el momento, hemos derivado {Q} Inic; mientras B hacer {P} ¿? fmientras {R} • Para derivar el cuerpo del bucle S: a) Incluimos al final de S, una instrucción “Avanzar” que haga progresar el bucle hacia su terminación. La instrucción Avanzar ha de hacer decrecer la función limitadora t b) Normalmente, la instrucción Avanzar rompe la invarianza de P por lo que es necesario incluir otra instrucción “Restablecer” para que se siga cumpliendo {P B} S {P} Si comprobamos que {P ∧ B} ⇒ T entonces Restablecer sería “nada” B.2.- Derivación del invariante a partir de la postcondición • La idea de partida es que el invariante es un predicado más débil que la

postcondición. Sólo algunos estados de P son también estados de R (los que cumplen además ØB) • Como conocemos R, y deseamos conocer P, hemos de proceder a debilitar R. ¿Hasta dónde?. Hasta que R debilitada sea P, es decir, hasta que P sea tan débil para que alguno de sus estados pueda establecerse fácilmente con unas simples asignaciones • Las técnicas para debilitar un predicado son las que ya vimos al estudiar las técnicas de inmersión: a) Elminar una conjunción: Si R es de la forma R1 R2, una de las dos conjunciones (la que más fácil sea de establecer al comienzo del bucle) se tomará como P. La otra será directamente ØB y de esta forma P ØB conducirá obviamente a R b) Incorporar una variable: Sustituir en R cierta expresión por una nueva variable. Así R se escribirá como una conjunción. • Normalmente, el invariante delimita los valores permitidos para todas las variables que intervienen en el bucle. Ejemplo1 Es hora de retomar el ejemplo del algoritmo que calculaba la suma de los elementos de un vector, cuya especificación era: {Q cierto} fun suma(v: vector[1..n] de ent) dev (s: ent) {R s = {1..N}. v[a]}.Apuntes Programación II U.N.E.D. – Curso 1999/2000 38 Vamos a derivar un programa iterativo que resuelva el problema. • Iniciamos el proceso debilitando la postcondición. Para ello introducimos una variable que sustituya la expresión constante N. Tendremos: R º(s = Î{1..i}. v[a]) (i = N). De esta forma R R1 R2. Si tomamos {P º(s = Î{1..i}. v[a])} y ØB º(i = N) es obvio que ØÞR Lógicamente B i ¹N • Hasta ahora tenemos: {Q ºcierto} fun sumait(v: vector[1..n] de ent) dev (s: ent) Inicializar; mientras i ¹N hacer {P º(s = Î{1..i}. v[a])} Restablecer; Avanzar; fmientras ffun {R s = åaÎ{1..N}. v[a]} • Tenemos que diseñar los términos Inicializar, Avanzar y Restablecer Inicializar supone declarar las dos variables implicadas en el invariante: “s” e “i” asignándole valores que hagan que antes de iniciarse el bucle se cumpla P. Esto último se puede lograr fácilmente en nuestro caso si damos el valor 0 a la variable i ya que sabemos que en ese caso s también valdrá 0. Por tanto Inicializar ≡ var i: nat, s: ent fvar <s, i>:= <0, 0> El término Avanzar ha de modificar las variables (o alguna de ellas) para que se

acerque el bucle a su condición de finalización. En este caso i parte del valor 0 y la condición de finalización es i = N . Parece lógico que hagamos: Avanzar i:= i+1 El paso “más complicado” es establecer el término Restablecer. Como queremos que {P B} S {P}, planteamos {P B}  ',i+1 s s,i P por un lado {P B} será (s = Î{1..i}. v[a]) (i ¹N) y por otro ',i+1 s s,i P ºs’ = Î{1..i+1}. v[a] = Î{1..i}. v[a]) +v[i+1] = s + v[i+1] Se deduce por tanto que la instrucción Restablecer ha de consistir en sumar a s el término v[i+1], luego tendremos: Restablecer s:= s+v[i+1].Apuntes Programación II U.N.E.D. – Curso 1999/2000 39 Con esto habremos terminado el diseño formal y tendremos: {Q cierto} fun sumait(v: vector[1..n] de ent) dev (s: ent) var i: nat, s: ent fvar <s, i>:= <0, 0> mientras i N hacer {P (s = Î{1..i}. v[a])} s:= s+v[i+1]; i:= i+1; fmientras dev s ffun {R s = {1..N}. v[a]} VERIFICACIÓN FORMAL: 0.- Fijar invariante y función limitadora: El invariante se ha obtenido en la fase de diseño luego no tenemos que hacer nada . La función limitadora puede ser t(v, s, i) = N-i que cumple t 0 (0 i N) 1.-   ØB  R Es cierto por construcción 2.- {Q} Inic {P} 0 = {1..0}. v[a] Evidente. 3.- {  B} S {P} “Teniendo en cuenta que a la entrada del bucle se cumple el invariante (P) y la condición de bucle (B), tras las operaciones interiores al bucle se ha de cumplir el invariante para los nuevos valores de las variables” Precisamente para calcular el término Restablecer hemos utilizado esta propiedad. Por tanto cuando empleemos este método de derivación la propiedad será cierta y no tendremos que demostrar nada aquí. 4.-  ÙB  t  0 “Verficar que la función limitadora se mantiene no negativa durante la ejecución del bucle”. Cuestión ya comentada en el punto 0. 5.- {  B  t=T} S {t
Ejemplo 2 ESPECIFICACIÓN: {Q º1<=f<=n} fun linea(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) {R b = "aÎ{1..m}. t[f,a]>0} • Partiendo de la postcondición, la debilitamos introduciendo un parámetro variable i en sustitución de la constante m R ºR1 ÙR2 CON R1 º(b = "aÎ{1..i}. t[f,a]>0) y R2 º(i = m) Tomamos la primera como invariante del bucle y la segunda como ØB y tendremos {Q º1<=f<=n} fun lineait(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) Inicializar; mientras i ¹m hacer {Pº(b = "aÎ{1..i}. t[f,a]>0)} Restablecer; Avanzar; fmientras ffun {R b = "aÎ{1..m}. t[f,a]>0} • Inicializar: Cuando i=0 sabemos que b = "aÎ{1..0}. t[f,a]>0 es “cierto”; luego Inicializar := <0, cierto> • Avanzar: Si i comienza tomando el valor 0 y debe alcanzar el valor n, el termino Avanzar podría ser: Avanzar i:= i+1 • Restablecer: Tendrá que cumplirse {P B} S {P}, planteamos {P B}  ',i+1 b b,i P Por un lado {P B} º(b = "aÎ{1..i}. t[f,a]>0) (i < m) (ι≠ m lo hemos cambiado por i<m ya que en este caso es equivalente) Por otro ',i+1 b b,i P b’ = "aÎ{1..i+1}. t[f,a]>0 ºb’=(Î{1..i}. t[f,a]>0) (t[f, i+1]>0)  b’ = b (t[f, i+1]>0) Si hacemos b’:= b (t[f, i+1]>0) se tiene {P B}  ',i+1 b b,i P ; por tanto Restablecer ºb:= b (t[f, i+1]>0) • El algoritmo iterativo: {Q º1<=f<=n} fun lineait(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) var i: nat; b: bool fvar; := <0, cierto>.Apuntes Programación II U.N.E.D. – Curso 1999/2000 41 mientras i < m hacer {(b = {1..i}. t[f,a]>0)} b:= b (t[f, i+1]>0); i:= i+1; fmientras; dev b

ffun {R b = {1..m}. t[f,a]>0} Esta sería una solución válida, no obstante vamos a plantearnos un par de mejoras respecto al algoritmo obtenido. 1.- Si en la especificación de la función: {Q 1<=f<=n} fun linea(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) {R b = {1..m}. t[f,a]>0} introducimos el predicado auxiliar lcompleta(t, f, i) = {1..i}. t[f,a]>0), el diseño iterativo que tendríamos ahora sería: P b = lcompleta(t, f, i) B i < m R b = lcompleta(t, f, m) En principio el rango de i sería 1 i m, pero se puede ampliar con i = 0 ya que para dicho valor sabemos que lcompleta(t, i, 0) = cierto. En este caso incluiremos en P el rango de i con lo que tendremos P b = lcompleta(t, f, i) (0 i m). Los términos Inicializar, Avanzar y Restablecer no sufrirán variación por lo que el algoritmo quedará: {Q 1<=f<=n} fun lineait2(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) var i: nat; b: bool fvar; := <0, cierto> mientras i < m hacer { P b = lcompleta(t, f, i) (0 i m)} b:= b (t[f, i+1]>0); i:= i+1; fmientras; dev b ffun {R b = lcompleta(t, f, m)} 2.- Por otra parte, en el momento en que se detecta que un elemento t[f, a] es cero se puede afirmar que b será falso y no se debería seguir iterando. Esto equivale a poner una condición de finalización de bucle que compruebe a cada paso del bucle si b sigue siendo cierto..Apuntes Programación II U.N.E.D. – Curso 1999/2000 42 La función modificada sería: {Q º1<=f<=n} fun lineait3(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) var i: nat; b: bool fvar; := <0, cierto> mientras ((i < m) b) hacer { P b = lcompleta(t, f, i) (0 £i £m)} b:= b (t[f, i+1]>0); i:= i+1; fmientras; dev b

ffun {R ºb = lcompleta(t, f, m)} VERIFICACIÓN: 1.-  ÙØB  R Tanto para lineait como lineait2, por construcción, es evidente. Para lineait3 tendremos: b = lcompleta(t, f, i) (0 £i £m) ((i = m) Øb) Þb = lcompleta(t, f, m) a) b = lcompleta(t, f, i) (i = m) b = lcompleta(t, f, m) resulta evidente. b) b = lcompleta(t, f, i) falso b = lcompleta(t, f, m) falso ¿? siempre se cumple. 2.- {Q} Inic {P} cierto = lcompleta(t, f, 0) en cualquier caso 3.- {  B} S {P} Se trata del punto más conflictivo en el proceso de verificación En el caso de lineait se tiene: {ÙB} º(b = "aÎ{1..i}. t[f,a]>0) (0 £i < m) ',i+1 b b,i P º(b’=Î{1..i+1}.t[f,a]>0) Ù(0£i+1£m)  (b’=Ù(t[f, i+1>0]) (0£i+1£m) Tenemos que (0£i< m)Þ(0£i+1£m) y (b=Î{1..i}.t[f,a]>0)Þ(b’=Ù(t[f, i+1>0]) luego {ΠÙB} ⇒ ',i+1 b b,i P Para lineait2 tenemos: {ÙB} º(b = lcompleta(t, f, i)) (0 £i < m) ',i+1 b b,i P (b’=lcompleta(t, f, i+1)) (0 £i+1 £m) º(b’= b t[f, i+1>0])Ù(0£i+1£m) razonando como antes {ÙB}  ',i+1 b b,i P , y esto equivale a {ÙB} S {P}.Apuntes Programación II U.N.E.D. – Curso 1999/2000 43 Finalmente en el caso de lineait3 tenemos: {ÙB}(b=lcompleta(t,f,i))Ù(m) ((i< m)Ùb) (b=lcompleta(t,f,i))Ù(i<m)Ùb 1,' , +ib i b P (b’ = lcompleta(t, f, i+1)) (0 i+1 m) Ùb’  (b’= lcompleta(t, f, i) t[f, i+1>0])Ù(i+m) b’  (b’= b t[f, i+1>0])Ù(i+m) (b t[f, i+1>0]) a cada paso del bucle, tras las instrucciones Restablecer y Avanzar := <Ùt[f, i+1]>0; i+1> se cumple el invariante P, luego podemos concluir que {ÙB} S {P} es cierto 4.-  ÙB  t  0 Si tomamos l(t, f, i) = m–i, puesto que el valor inicial de i es 0 y a cada paso del bucle se incrementa en 1 hasta alcanzar el valor m, se tiene l(t, f, i) 0 5.- {  t=T} S {t l(t, f, i+1) por ser m-i-1 < m-i EJEMPLOS Y EJERCICIOS:

De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 3.2.1, 11.1, 11.2, 11.3 Exámenes de años anteriores TRANSFORMACIONES RECURSIVO-ITERATIVO El diseño recursivo puede utilizarse como técnica para el descubrimiento de invariantes Las razones para desear transformar a iterativo una función recursiva son: • El lenguaje iterativo disponible no soporta la recursividad • No se quiere pagar el coste adicional en tiempo del mecanismo de llamada a procedimiento y del paso de parámetros • No se quiere pagar el coste adicional de memoria que lleva implícita la implementación de la recursividad. Conviene tener en cuenta que la versión iterativa siempre será menos legible y modificable..Apuntes Programación II U.N.E.D. – Curso 1999/2000 44 A) TRANSFORMACIÓN RECURSIVA FINAL – ITERATIVA donde ) ) (x) f x f( x) Q( P(x,x ini ini = ∧ ≡ B) TRANSFORMACIÓN RECURSIVA NO FINAL – ITERATIVA donde s -1 es la inversa de la función sucesor texto libro en ver x SUC( R( x P x P x SUC( x P ini ini ini ini ≡ ∧≡ ∧ ≡Θ( ) x, y); x, ) (x, y) (x, ); x, x) ) (x, 1 ini, 2 1 )} ; )} y)} , x {R( ffun x) triv( dev fmientras x) s( x hacer x) Bnt( mientras x x, {P( xx fvar :T x var ) :T y dev( ) :T x f( fun x {Q( ini

ini ini 1 2 1 ini ini := := )} y , x {R( ffun fcaso )) x f(s( ) x Bnt( triv Bt( caso ) T y ( dev ) T x f( fun 2 1 → → = x) ( x) :: x)} ( {Q , )} ; )} y)} , x {R( ffun y dev fmientras x) y, c( y (x); s x hacer x x mientras y)} x x, ( {P x) triv( y fmientras; x) s( x hacer x) Bnt( mientras x x, ( {P xx fvar :T x var ) :T y dev( ) :T x f( fun x {Q( ini -1 ini ini 2 ini 1 ini 1

2 1 ini ini := = ≠ := := := )} y x, {R( ffun fcaso )), x f(s( ) x Bnt( Bt( caso ) y dev( ) x f( fun 2 1 x) c( triv(x) x) :T :T {Q(x)} → → =.Apuntes Programación II U.N.E.D. – Curso 1999/2000 45 Ejemplo 1.- Transformación recursiva final a iterativa En nuestro ejemplo1 una solución recursiva final es: {Q º0<=i<=n ^ r = åaÎ{1..i}. v[a]} fun isuma2(v:vect[1..N] de entero; i:nat; r:entero) dev s:entero caso i=n r [] i>0 isuma2(v, i+1,r+v[i+1]) fcaso ffun {R s = åaÎ{1..n}. v[a]} y la llamada inicial era isuma2(v, 0, 0) Su equivalente iterativo dará lugar a un bucle, (uno solo por ser final), en el que: a) La inicialización de variables consistirá en asignar a las variables involucradas los mismos valores que se utilizan en la llamada inicial en la función recursiva: Inicialización := <0, 0> b) La condición de bucle será el caso no trivial en el algoritmo recursivo: i < n c) Se devolverá tras el bucle el mismo valor que devuelve en el caso trivial el algoritmo recursivo: r d) El invariante será el predicado dado por la igualdad entre la conjunción de la precondición del algoritmo recursivo y de la función aplicada a los valores iniciales, y la propia función para valores genéricos, es ) ) (x) f x f( x) Q( decir:P(x,x ini ini = ∧ ≡ en este caso: P(r, i, 0, 0) º(0 i £n) r = åaÎ{1..i}. v[a] isuma2(v, 0, 0) = isuma2(v, i, r) En la práctica esto conduce al predicado dado por la precondición de la función recursiva ya que la postcondición no depende de los parámetros, luego:

P º(0<=i<=n) ^ (r = åaÎ{1..i}. v[a]) e) La precondición de la función iterativa será el predicado utilizado en la precondición de la recursiva en el que se sustituyen las variables genéricas por sus valores iniciales: [ ] [ ] ( [ ] ( ) cierto v v r n) i (0 i ≡ = ν)∧ ≤ ≤ ≡ = ∧ ≤ ≤ = 0 i,r 0,0 0 0 0 Q(xini)  El algoritmo iterativo será: {Q ºcierto} fun suma_iter1(v: vect[1..n] de ent) dev (s: ent) var i: nat; r: ent fvar := <0, 0>; mientras i < n hacer {P (0<=i<=n) ^ (r = åaÎ{1..i}. v[a])} r:= r + v[i + 1]; i:= i + 1; fmientras dev r ffun {R ºs = åaÎ{1..n}. v[a]}.Apuntes Programación II U.N.E.D. – Curso 1999/2000 46 Ejemplo 2.- Transformación recursiva final a iterativa {Q (1<=f<=n) ^ (0<=i<=m) ^ (bb = {1..i}. t[f,a]>0)} fun ilinea2(t: vector[1..n, 1..m] de nat; f,i: nat; bb: bool) dev (b: bool) caso i=m bb [] i<m ilinea2(t, f, i+1, bb ^ t[f,i+1]>0) fcaso ffun {R b = {1..m}. t[f,a]>0} y la llamada inicial era: ilinea2(t, f, 0, cierto) aplicando los mismos preceptos anteriores tendremos: {Q 1<=f<=n } fun ilinea2(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) var i: nat; bb:bool fvar; := <0, cierto>; mientras i < m hacer {P (0<=i<=m) ^ (bb = {1..i}. t[f,a]>0)} := 0)> fmientras dev bb ffun {R b = {1..m}. t[f,a]>0} Ejemplo 1.- Transformación recursiva no final a iterativa La solución recursiva no final del ejemplo 1 era: {Q 0<=i<=N} fun isuma(v: vector[1..N] de enteros; i: natural) dev (s: entero)

caso i=0 0 [] i>0 isuma(v, i-1) + v[i] fcaso ffun {R s = {1..i}. v[a]} y la llamada inicial: isuma(v, n) Su transformación a iterativa dará lugar a dos bucles Antes del primer bucle se inicializan las variables con los mismos valores utilizados en la llamada inicial: Inicialización i:= n El primer bucle consiste en realizar la operación de modificación de parámetros realizada en la llamada recursiva utilizando como condición de bucle la del caso no trivial de la función recursiva: mientras i > 0 hacer i:= i – 1 fmientras (el bucle se utiliza para alcanzar el valor inicial de i (caso trivial) para iniciar el segundo bucle).Apuntes Programación II U.N.E.D. – Curso 1999/2000 47 Antes del segundo bucle se ha de inicializar la variable que contenga finalmente el resultado con el valor del caso trivial de la función recursiva: s:= 0 (como hemos llevado el valor de i hasta 0 (caso trivial), s se inicializa con triv(x)) El segundo bucle consiste en aplicar sucesivamente: a) la función inversa de la aplicada en la modificación de parámetros en la llamada recursiva: i:= i + 1 b) La operación adicional del algoritmo recursivo sobre las variables de salida y entrada (combinación): s:= s + v[i] El bucle termina cuando las variables alcanzan de nuevo sus valores iniciales: mientras i n hacer i:= i + 1; s:= s + v[i] fmientras. El algoritmo resultante será: {Q cierto} fun suma_iter2(v: vect[1..n] de ent) dev (s: ent) var i: nat; s: ent fvar i:= n; mientras i > 0 hacer {P1} i:= i – 1; fmientras s:= 0; mientras i n hacer {P2} i:= i + 1; s:= s + v[i]; fmientras dev s ffun {R s = {1..n}. v[a]}

En este ejemplo es evidente, como ya se ha comentado, que el primer bucle puede ser eliminado asignando simplemente a i el valor cero. Esto ocurrirá en todos los casos en que la operación de modificación de parámetros en la llamada recursiva sea muy simple. En este caso existe la operación inversa de la aplicada en la modificación de parámetros en la llamada recursiva, pero esto no es siempre posible. En algunos casos la función inversa no puede expresarse por medio de una operación matemática. En estos casos los valores obtenidos en el primer bucle en cada operación de modificación han de ser acumulados en una estructura tipo pila. En el segundo bucle la operación inversa se sustituye por la extracción de esos valores desde la pila (ver manual Peña). Queda por establecer P1 y P2, pero como de lo que uno no entiende es mejor no hablar dejo que cada uno busque su solución..Apuntes Programación II U.N.E.D. – Curso 1999/2000 48 Ejemplo 2.- Transformación recursiva no final a iterativa Partiendo de la función recursiva no final ilinea {Q (1<=f<=n) ^ (0<=i<=m)} fun ilinea(t: vector[1..n, 1..m] de nat; f,i: nat) dev (b: bool) caso i=0 cierto [] i>0 ilinea(t, f, i-1) ^ (t[f,i]>0) fcaso ffun {R b = {1..i}. t[f,a]>0} cuya llamada inicial era: ilinea(t, f, m) Su transformación a iterativo será: {Q 1<=f<=n } fun ilinea_it2(t: vector[1..n, 1..m] de nat; f: nat) dev (b: bool) var i: nat; fvar; i:= m; mientras i > 0 hacer {P1} i:= i – 1 fmientras b:= cierto mientras i m hacer {P2} := 0)> fmientras dev b ffun {R b = {1..m}. t[f,a]>0} Como siempre, falta determinar P1 y P2 (suerte) EJEMPLOS Y EJERCICIOS: De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 10.1, 10.2, 10.3, 11.3 Ejercicios de transformación recursivo-iterativo de exámenes de años anteriores.Apuntes Programación II U.N.E.D. – Curso 1999/2000 49 EFICIENCIA DE ALGORITMOS Pues efectivamente, yo os recomiendo dejar para el final este tema que es el primero de

la asignatura. Es muy recomendable que antes de abordar el tema en el libro de texto visitéis la página de Jerónimo Quesada y estudies sus apuntes sobre el tema. En este tema no tengo nada que aportar, solo os recomendaría que os aprendáis las fórmulas ya que siempre caen cuestiones relacionadas con este tema en la parte de test, además de que en el estudio de los algoritmos también os pueden pedir el coste. EJEMPLOS Y EJERCICIOS: De la colección de problemas curso 1999-2000 conviene hacer los ejercicios 5.1, 5.2, 5.3, 5.4 Exámenes de años anteriores. Espero que estas orientaciones os sirva de ayuda para el estudio de la asignatura. Mucha suerte. José Manuel.