Tema 2. teoría y práctica de derivación de asignaciones representado

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/

http://paginaspersonales.deusto.es/igor.ira/


Teorıa 2.3.1. Derivacion de asignaciones

Practica Ejemplo 2. Intercambio de valores

Discusion Feed-back




Discusion Feed-back




Discusion Feed-back


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.



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.




Si aparecen disyunciones.


Hay varias maneras desatisfacer la postcondicion.

Puede intentarse disenandouna alternativa, cada unade cuyas ramas obtenga lapostcondicion a base desatisfacer una de lasdisyunciones.




Si aparecen conjunciones.


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.




Estas indicaciones noevitan...


El empleo de “prueba yerror”.



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}



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}



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}



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}


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}


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.



Primera aproximacion

Podrıamos pensar en una asignacion multiple.

Instrucciones

{Prec : x = X ∧ y = Y }< x , y >:=< y , x >

{Post : x = Y ∧ y = X}



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.



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





Instrucciones

{A1}y := x

{Post : x = Y ∧ y = X}


≡ x = Y ∧ x = X

≡ X = Y





Instrucciones

{A1}y := x

{Post : x = Y ∧ y = X}


≡ x = Y ∧ x = X

≡ X = Y

Reflexion

No podemos asegurarlo. No tenemos esa informacion.



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





Instrucciones

{A1}x := y

{Post : x = Y ∧ y = X}


≡ y = Y ∧ y = X

≡ X = Y





Instrucciones

{A1}x := y

{Post : x = Y ∧ y = X}


≡ y = Y ∧ y = X

≡ X = Y

Reflexion

Ocurrirıa lo mismo. No podemos asegurarlo. No tenemos esainformacion.



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



Cuarta aproximacion


Instrucciones

var z : nat

{A1}y := z

{Post : x = Y ∧ y = X}


≡ x = Y ∧ z = X

¿Podemos demostrar esto?



Cuarta aproximacion


Instrucciones

var z : nat

{A1}y := z

{Post : x = Y ∧ y = X}


≡ x = Y ∧ z = X


Reflexion

No podemos demostrarlo. Seguimos operando sobre {A1}.



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



Cuarta aproximacion


Instrucciones

var z : nat

{A2}z := x ;

{A1 : x = Y ∧ z = X}y := z

{Post : x = Y ∧ y = X}


≡ x = Y ∧ x = X

≡ X = Y



Cuarta aproximacion


Instrucciones

var z : nat

{A2}z := x ;

{A1 : x = Y ∧ z = X}y := z

{Post : x = Y ∧ y = X}


≡ x = Y ∧ x = X

≡ X = Y

Reflexion

No podemos asegurarlo. No tenemos esa informacion.



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



Cuarta aproximacion


Instrucciones

var z : nat

{A2}x := y ;

{A1 : x = Y ∧ z = X}y := z

{Post : x = Y ∧ y = X}


≡ y = Y ∧ z = X

// Por la Prec

≡ z = X




Cuarta aproximacion


Instrucciones

var z : nat

{A2}x := y ;

{A1 : x = Y ∧ z = X}y := z

{Post : x = Y ∧ y = X}


≡ y = Y ∧ z = X

// Por la Prec

≡ z = X


Reflexion

No podemos demostrarlo. Seguimos operando sobre {A2}.



Cuarta aproximacion


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



Cuarta aproximacion


Instrucciones


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



Cuarta aproximacion


Instrucciones


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.


Feed-backDiscusion

This slide is intentionally left blank

Education

Tema 2. teoría y práctica de derivación de asignaciones representado