View
269
Download
1
Category
Preview:
Citation preview
2.3. Derivacion de algoritmos
Metodologıa de la ProgramacionTema 2. Teorıa y practica de derivacion de asignaciones representado
usando LATEX
Igor Ruiz-Agundez1
DeustoTech Computing, Deusto Institute of Technology, University of Deusto
1http://paginaspersonales.deusto.es/igor.ira/
2.3. Derivacion de algoritmos
Teorıa 2.3.1. Derivacion de asignaciones
Practica Ejemplo 2. Intercambio de valores
Discusion Feed-back
2.3. Derivacion de algoritmos
Teorıa 2.3.1. Derivacion de asignaciones
Practica Ejemplo 2. Intercambio de valores
Discusion Feed-back
2.3. Derivacion de algoritmos
Teorıa 2.3.1. Derivacion de asignaciones
Practica Ejemplo 2. Intercambio de valores
Discusion Feed-back
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Analisis de la postcondicion
Los resultados a obtener influyen en el diseno mucho mas que los datosde los que se dispone.Es por eso por lo que el analisis de la postcondicion es un buen metodopara desarrollar algoritmos.
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Heurısticas derivadas del analisisde las postcondicion
Si en la postcondicionaparecen igualdades entrevariables del programa yexpresiones.
Podrıas satisfacerse mediante
Puede intentarsesatisfacerlas medianteasignaciones simples omultiples.
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Heurısticas derivadas del analisisde las postcondicion
Si aparecen disyunciones.
Podrıas satisfacerse mediante
Hay varias maneras desatisfacer la postcondicion.
Puede intentarse disenandouna alternativa, cada unade cuyas ramas obtenga lapostcondicion a base desatisfacer una de lasdisyunciones.
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Heurısticas derivadas del analisisde las postcondicion
Si aparecen conjunciones.
Podrıas satisfacerse mediante
Puede considerarse cadauna de ellas aisladamente eintentar satisfacerlas porseparado.
Es posible que al intentarsatisfacer una de ellas laotra se haga imposible desatisfacer.
Se puede crear alternativasen las cuales algunasconjunciones se satisfacenmediante la instruccionprotegida.
Las demas constan en laproteccion.
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Heurısticas derivadas del analisisde las postcondicion
Estas indicaciones noevitan...
Podrıas satisfacerse mediante
El empleo de “prueba yerror”.
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Requisitos
Hay que indicar en la especificacion que variables pueden cambiar devalor y cuales no.
Estrategia a seguir
La construccion de unprograma partenecesariamente de un parde asertos que constituyensu especificacion, porejemplo Prec y Post.
Ejemplo
{Prec}{Post}
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Estrategia a seguir
Es comun en el proceso dederivacion de los programaspensar en una instruccion Ique nos podrıa ayudar aestablecer la postcondiciony situarla como ultimainstruccion del programa.
Ejemplo
{Prec}?
I
{Post}
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Estrategia a seguir
En este caso habrıa quecontinuar el proceso haciaarriba, calculando el asertoB que deberıa cumplirseantes de la instrucciondisenada para que laejecucion de I lleve alcumplimiento de Post.
Ejemplo
{Prec}?
{B}I
{Post}
2.3. Derivacion de algoritmos
2.3.1. Derivacion de asignacionesTeorıa
Estrategia a seguir
A partir de este momento elobjetivo serıa derivar unprograma cuyasprecondicion ypostcondicion fueran Prec yB. El proceso se repitehasta que la precondicioncalculada para determinadainstruccion coincida conPrec, la precondicion de laespecificacion inicial.
Ejemplo
{Prec}?
{B}I
{Post}
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresEnunciado
Se pide
Derivar la siguiente especificacion que realiza un intercambio de valores.
Especificacion
var x , y : nat
{Prec : x = X ∧ y = Y }{Post : x = Y ∧ y = X}
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Analisis de la postcondicion
La postcondicion es una conjuncion de dos igualdades.
Opciones
Considerarse cada una de ellas aisladamente e intentar satisfacerlaspor separado. Pero es posible que al intentar satisfacer una de ellasla otra se haga imposible de satisfacer.
Crear alternativas en las cuales algunas conjunciones se satisfacenmediante la instruccion protegida y las demas constan en laproteccion.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Primera aproximacion
Podrıamos pensar en una asignacion multiple.
Instrucciones
{Prec : x = X ∧ y = Y }< x , y >:=< y , x >
{Post : x = Y ∧ y = X}
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Primera aproximacion
Podrıamos pensar en una asignacion multiple.
Instrucciones
{Prec : x = X ∧ y = Y }< x , y >:=< y , x >
{Post : x = Y ∧ y = X}
Reflexion
Sin embargo, la postcondicion es una conjuncion de dos igualdades.Tienen que cumplirse ambas simultaneamente. Ademas, no puedeverificarse.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Segunda aproximacion
Intentamos con una asignacion sobre la variable y . No podemos accederal valor inicial de X .
Instrucciones
{A1}y := x
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← x ]
≡ x = Y ∧ x = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Segunda aproximacion
Intentamos con una asignacion sobre la variable y . No podemos accederal valor inicial de X .
Instrucciones
{A1}y := x
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← x ]
≡ x = Y ∧ x = X
≡ X = Y
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Segunda aproximacion
Intentamos con una asignacion sobre la variable y . No podemos accederal valor inicial de X .
Instrucciones
{A1}y := x
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← x ]
≡ x = Y ∧ x = X
≡ X = Y
Reflexion
No podemos asegurarlo. No tenemos esa informacion.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Tercera aproximacion
Intentamos con una asignacion sobre la variable x . No podemos accederal valor inicial de Y .
Instrucciones
{A1}x := y
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[x ← y ]
≡ y = Y ∧ y = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Tercera aproximacion
Intentamos con una asignacion sobre la variable x . No podemos accederal valor inicial de Y .
Instrucciones
{A1}x := y
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[x ← y ]
≡ y = Y ∧ y = X
≡ X = Y
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Tercera aproximacion
Intentamos con una asignacion sobre la variable x . No podemos accederal valor inicial de Y .
Instrucciones
{A1}x := y
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[x ← y ]
≡ y = Y ∧ y = X
≡ X = Y
Reflexion
Ocurrirıa lo mismo. No podemos asegurarlo. No tenemos esainformacion.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional.
Instrucciones
var z : nat
{A1}y := z
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← z ]
≡ x = Y ∧ z = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional.
Instrucciones
var z : nat
{A1}y := z
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← z ]
≡ x = Y ∧ z = X
¿Podemos demostrar esto?
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional.
Instrucciones
var z : nat
{A1}y := z
{Post : x = Y ∧ y = X}
Buscamos {A1}{A1} ≡ Post[y ← z ]
≡ x = Y ∧ z = X
¿Podemos demostrar esto?
Reflexion
No podemos demostrarlo. Seguimos operando sobre {A1}.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.
Instrucciones
var z : nat
{A2}z := x ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[z ← x ]
≡ x = Y ∧ x = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.
Instrucciones
var z : nat
{A2}z := x ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[z ← x ]
≡ x = Y ∧ x = X
≡ X = Y
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.
Instrucciones
var z : nat
{A2}z := x ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[z ← x ]
≡ x = Y ∧ x = X
≡ X = Y
Reflexion
No podemos asegurarlo. No tenemos esa informacion.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.Segundo intento.
Instrucciones
var z : nat
{A2}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[x ← y ]
≡ y = Y ∧ z = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.Segundo intento.
Instrucciones
var z : nat
{A2}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[x ← y ]
≡ y = Y ∧ z = X
// Por la Prec
≡ z = X
¿Podemos demostrar esto?
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A1}.Segundo intento.
Instrucciones
var z : nat
{A2}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Buscamos {A2}{A2} ≡ A1[x ← y ]
≡ y = Y ∧ z = X
// Por la Prec
≡ z = X
¿Podemos demostrar esto?
Reflexion
No podemos demostrarlo. Seguimos operando sobre {A2}.
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A2}.
Instrucciones
{Prec : x = X ∧ y = Y }var z : nat
z := x
{A2 : z = X}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Verificamos z := x
{Prec} ⇒ A2[z ← x ]
≡ x = X
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A2}.
Instrucciones
{Prec : x = X ∧ y = Y }var z : nat
z := x
{A2 : z = X}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Verificamos z := x
{Prec} ⇒ A2[z ← x ]
≡ x = X
// Por la Prec
≡ True
2.3. Derivacion de algoritmos
Ejemplo 2. Intercambio de valoresSolucion
Cuarta aproximacion
Utilizamos una variable adicional y continuamos operando sobre {A2}.
Instrucciones
{Prec : x = X ∧ y = Y }var z : nat
z := x
{A2 : z = X}x := y ;
{A1 : x = Y ∧ z = X}y := z
{Post : x = Y ∧ y = X}
Verificamos z := x
{Prec} ⇒ A2[z ← x ]
≡ x = X
// Por la Prec
≡ True
Reflexion
Hemos terminado la derivacion.
2.3. Derivacion de algoritmos
Feed-backDiscusion
This slide is intentionally left blank
Recommended