LENGUAJE DE ESPECIFICACIÓNAlgoritmos y Estructuras de Datos I

Especificación – Práctica 2

AE

DI

Esp

ecifica

ción

– P

ráctica

2

1

ESPECIFICACIÓN DE PROBLEMAS

Expresamos formalmente qué debe cumplir una función para ser solución al problema dado.

No expresamos cómo solucionarloPuede no haber solución al problema que

planteamos.O tal vez, no sabemos escribirla.

Recordemos que lo que queremos especificar es el contrato que debe cumplir la función para ser considerada solución del problema planteado.

AE

DI

2

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS NOTACIÓN

problema nombre(parámetros) = salida {

modifica: parámetro;

requiere: expresión1;

asegura: expresión2;

-- DEFINICIÓN DE AUX –

}

AE

DI

3

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS NOTACIÓN

problema nombre(parámetros) = salida {

modifica: parámetro;

requiere: expresión1;

asegura: expresión2;

-- DEFINICIÓN DE AUX –

}

El formato de los parámetros de entrada es el siguiente:

(nombreParam1:Tipo1; nombreParam2,nombreParam3:Tipo2;…)

Esto es para cuando tenemos más de un parámetro con el mismo tipo.

AE

DI

4

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS NOTACIÓN

problema nombre(parámetros) = salida {

modifica: parámetro;

requiere: expresión1;

asegura: expresión2;

-- DEFINICIÓN DE AUX –

}

Puede no haber parámetro de salida del problema (por ejemplo si modifico los parámetros de entrada para devolver la solución).

De haber salida el formato es el siguiente: nombreSalida: Tipo

Notar que si hay más de un parámetro de salida entonces podemos usar una tupla para devolverlos todos:

nombreSalida:(TipoParam1,TipoParam2,…)

AE

DI

5

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS NOTACIÓN

problema nombre(parámetros) = salida {

modifica: parámetro;

requiere: expresión1;

asegura: expresión2;

-- DEFINICIÓN DE AUX –

}

El modifica es opcional, y lo colocamos sólo en el caso en que haya parámetro que deseamos alterar.

Si hay más de un parámetro que se modifica se repite la sentencia para cada parámetro que modifico o bien se separan los parámetros por comas.

AE

DI

6

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS NOTACIÓN

problema nombre(parámetros) = salida {

modifica: parámetro;

requiere: expresión1;

asegura: expresión2;

-- DEFINICIÓN DE AUX –

}

Tanto expresión1 como expresión2 son condiciones booleanas.

Puede haber más de un asegura y de un requiere consecutivos, y equivalen a la evaluación en el orden de las expresiones asociadas unidas con un && ( ‘y’ ).

AE

DI

7

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS EJEMPLO CONOCIDO…

o Supongamos que deseamos escribir la especificación al problema de hallar el cociente entre dos números:

problema cociente(a, b: Int) = result: Int{asegura: result == a div b;

}

o Notar que no pusimos ninguna condición sobre los parámetros de entrada. Eso es equivalente a tener como precondición:

require: true

Pero… está bien eso ???

AE

DI

8

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS PRECONDICIONES…

o Las precondiciones las utilizamos para poder poner restricciones que las variables de entrada deben cumplir para poder expresar lo que la solución al problema debe cumplir.

problema cociente(a, b: Int) = result: Int{requiere: b!=0;asegura: result == a div b;

}

o En este caso, para poder resolver el cociente entre ‘a’ y ‘b’, pedimos que el divisor no sea cero (pues no podemos realizar la división en caso contrario).

Nota: es importante que la pre no sea demasiado débil, sino obtenemos una especificación que no puede ser cumplida por ninguna función. Pues, no va a pasar que, para todo elemento posible de entrada, entonces la solución devuelta cumple la postcondición.

Con esto también evitamos, en algunos casos, que se indefinan las postcondiciones.

AE

DI

9

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS VARIANTE DEL COCIENTE

Podemos nombrar las precondiciones para aclarar su significado. Los nombres pueden usarse como predicados.

problema cociente(a, b: Int) = result: Int{requiere DivisorNoCero: b!=0;asegura: result == a div b;

}

AE

DI

10

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS VARIANTE DEL COCIENTE

Podemos modificar alguno de los parámetros (ejemplo b).

problema cociente (a, b: Int) { modifica: b; requiere: pre(b)!=0;

asegura: b == a div pre(b); }

Nos permite referirnos al valor de b al

momento de ingresar al problema.

Nota: no es necesario agregar un parámetro para dar la solución.

AE

DI

11

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS

No podemos usar problemas dentro de la especificación de otros problemas.

Si podemos usar aux.

AE

DI

12

Esp

ecifica

ción

– P

ráctica

2

ESPECIFICACIÓN DE PROBLEMAS EJERCICIO – SOLUCIÓN

Especificar el problema de obtener el máximo entre dos números a y b.

problema mayor(a, b: Int) = result: Bool{ asegura: result == (if (a > b) then a else b); }

problema mayor(a, b: Int) = result: Bool{ asegura: result ==

Beta(a > b)*a + Beta(a<=b)*b; }

AE

DI

13

Esp

ecifica

ción

– P

ráctica

2

FUNCIONES AUXILIARES

AE

DI

14

Esp

ecifica

ción

– P

ráctica

2

SECUENCIAS

Varios elementos del mismo tipo, posiblemente repetidos, en un cierto orden

Notación: [T]: Las secuencias de elementos de tipo T

AE

DI

15

Esp

ecifica

ción

–P

ráctica

2

SECUENCIAS

  Una forma de escribir un término de

este tipo:Varios términos de tipo T

separados por comas entre corchetes

[1,3,2][1,1+1,1+2,2*2] = [1,2,3,4][[1,2],[1],[2,3],[6,7]][[1,2],[1],2,3,[6,7]] está mal!

AE

DI

16

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES CON SECUENCIAS

long(a) ó |a| |[2]| = 1 |[3,4]| = 2 |[]| = 0

indice(s,i) ó s[i] ó si

[4,5,6]1 = 5

[]i = no se puede, recuerden que el índice 0 i < |s|, que en este caso es 0 i < 0

AE

DI

17

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES CON SECUENCIAS

cab(s) cab([4,5,6]) = 4 cab([]) = no se puede, recuerden que |s| > 0

cola(s) cola([4,5,6]) = [5,6] cola([6]) = [] cola([]) = no se puede, recuerden que |s| > 0

AE

DI

18

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES CON SECUENCIAS

en(e,s) ó e en s ó e s 5 [4,5,6] = True 2 [4,5,6] = False

cons(e,s) ó e:s 3:[4,5,6] = [3,4,5,6] 3:[] = [3] [3]:[4,5,6] = no se puede, recuerden que es concatenar un elemento a una lista

 

AE

DI

19

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES CON SECUENCIAS

conc(s,t) ó s++t [1,2,3]++[4,5,6] = [1,2,3,4,5,6] []++[4,5,6] = [4,5,6] []++[] = [] 1++[4,5,6] = no se puede, recuerden que es concatenar dos listas entre sí

sub(s, e, f) ó s[e..f] [1,2,3,4,5,6][2..4] = [3,4,5] [1,2,3,4,5,6][2..6] = [] recuerden que 0 e

f < |s| [1,2,3,4,5,6][2..6) = [3,4,5,6]

AE

DI

20

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES CON SECUENCIAS

cambiar (s, i, e) cambiar([3,4,5], 1, 20) = [3,20,5] cambiar([3,4,5], 3, 20) = no se puede, recuerden que 0 i < |s|

 

AE

DI

21

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES DE COMBINACIÓN

alguno(s) alguno([]) = False alguno([True, False]) = True alguno([False, False]) = False

todos(s) todos([]) = True todos([True, True]) = True todos([True, False]) = False

AE

DI

22

Esp

ecifica

ción

– P

ráctica

2

OPERACIONES DE COMBINACIÓN

sum(s) ó s [1,2,3,4,5,6] = 21 [] = 0 [‘a’, ‘b’, ‘c’] = no se puede, recuerden que s debe ser de tipo numérico

prod(s) ó s [1,2,3] = 6 [] = 1 [‘a’, ‘b’, ‘c’] = no se puede, recuerden que s debe ser de tipo numérico

AE

DI

23

Esp

ecifica

ción

– P

ráctica

2

SECUENCIAS POR COMPRENSIÓN Notación: [expresión | selectores, condiciones]

selectores: variable secuencia (o <-) variable va tomando el valor de cada elemento de

secuencia en orden. condiciones: expresiones de tipo Bool

Resultado Secuencia

el valor de la expresión calculado para los elementos seleccionados por los selectores que cumplen las condiciones

AE

DI

24

Esp

ecifica

ción

– P

ráctica

2

INTERVALOS

  Ejemplos:

[1..3] = [1,2,3] [1..1] = [1] [1..3) = [1,2] (1..3] = [2,3] (1..3) = [2] [3..1] = [] (1..2) = []

Parecido a lo que vimos en matemática, no?

AE

DI

25

Esp

ecifica

ción

– P

ráctica

2

USANDO LISTAS POR COMPRENSIÓN

  [x | x [5,7,4,2,8,6,4,5,8,2,7,4], x4] = [4,2,4,2,4]

[x+y | x a, y b, x y], qué indica esta expresión? Por ejemplo: a = [1,2,3] y b = [1,2,3] [3,4,3,5,4,5] 

Sea a una secuencia, obtener la secuencia inversa de a: aux reverso(a:[T]):[T] =

[x[|a|-i-1] | i<-[0..|a|)]

Sea a una secuencia y n un natural, obtener la secuencia que queda de eliminar los primeros n elementos de s:

aux quitarN(n:Int, a:[T]) =

[a[i] | i<-[0...|a|), i>=n]

AE

DI

26

Esp

ecifica

ción

– P

ráctica

2

RECORDANDO

  Para todo: ( selectores, condiciones) propiedad

Equivale a todos([propiedad | selectores, condiciones])

Existe: ( selectores, condiciones) propiedad

Equivale a alguno([propiedad | selectores, condiciones])

Nota: cuando decimos “propiedad” nos referimos a expresiones de tipo Bool.

AE

DI

27

Esp

ecifica

ción

– P

ráctica

2

RECORDANDO

  Contar cuántas veces aparece x en la secuencia aaux cuenta(x: T, a: [T]): Int = long([y | y <- a, y == x]);

Determinar si dos secuencias tienen los mismos elementos (sin importar el orden)

aux mismos(a, b: [T]): Bool = |a| == |b| && ( c a) cuenta(c,a) ==

cuenta(c,b);

AE

DI

28

Esp

ecifica

ción

– P

ráctica

2

ACUMULACIÓN Construye un valor a partir de una o más

secuencias

acum(expresión | inicialización, selectores, condición)

inicialización: nombreAcum: tipoAcum = valorInicial El valor inicial debe de ser del tipo: tipoAcum

expresión: Puede (y suele) contener el acumulador

Significado El valor inicial del acumulador es valorInicial Por cada valor de los selectores, se calcula la expresión Ese es el nuevo valor del acumulador El resultado de acum es el resultado final del acumulador (de

tipo tipoAcum)

AE

DI

29

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS

  Escribir un auxiliar que, dada una secuencia s,

devuelva la cantidad de elementos pares de la secuencia.

Algunas soluciones posibles:aux cantPares(s:[Int]) : Int =

cuenta(True, [x mod 2 ==0 | x<- s])

aux cantPares(s:[Int]) : Int =long([x| x s , x mod 2 == 0 ])

aux cantPares(a:[Int]) : Int =

acum(s+1| s:Int = 0, x a , x mod 2 == 0)

AE

DI

30

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS

 Escribir un auxiliar que, dada una secuencia s, determine si hay algún elemento par en ella.

Algunas soluciones posibles:aux existePar(s:[Int]) : Bool =

cantPares(s) > 0

aux existePar(s:[Int]) : Bool =( x s ) x mod 2 == 0

aux existePar(s:[Int]) : Bool =

alguno([x mod 2 == 0| x s])

AE

DI

31

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS

  Escribir un auxiliar que, dada una secuencia s,

determine si todos sus elementos de posiciones pares son pares.

Algunas soluciones posibles:aux todosPares(s:[Int]) : Bool =

( i [0..|s|), i mod 2 == 0 ) si mod 2 == 0

aux todosPares (s:[Int]) : Bool =

todos([si mod 2 == 0| i [0..|s|), i mod 2 == 0])

AE

DI

32

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS

 Dada una secuencia s de enteros, modificarla para obtener una secuencia que contenga los mismos elementos que ella en las posiciones pares, pero multiplicados por 2. Además devolver una secuencia que posea los mismos, elementos que s en las posiciones impares. Ejemplo:

Dada la secuencia s = [1,2,3,4] , una posible solución sería que s quedara como [3*2,1*2] y result como [2,4]

OJO: el orden de los elementos de las secuencias resultantes no importa.

AE

DI

33

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS SOLUCIÓN TENTATIVA…

problema problemaRaro(s: [Int]) = result: [Int]{

modifica: s;asegura: s == paresX2(pre(s));asegura: result == impares(pre(s)); aux paresX2 (s:[Int]) : [Int] =

[xi*2 | i [0..|s|), i mod 2 == 0]; aux impares (s:[Int]) : [Int] =

[xi | i [0..|s|), i mod 2 != 0];}

 Está bien eso?? NO!!!

 Estamos sobreespecificando… Estamos imponiendo un orden tanto en la

secuencia que devolvemos como en la que modificamos… Una solución al problema que es válida (como la del ejemplo inicial) no verifica la postcondición de la especificación propuesta.

AE

DI

34

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS USEMOS MISMOS… problema problemaRaro(s: [Int]) = result: [Int]{

modifica: s;asegura: mismos(s, paresX2(pre(s)));asegura: mismos(result, impares(pre(s))); aux paresX2 (s:[Int]) : [Int] =

[xi*2 | i [0..|s|), i mod 2 == 0]; aux impares (s:[Int]) : [Int] =

[xi | i [0..|s|), i mod 2 != 0];}

  Tampoco estaría bien colocar alguna restricción al parámetro de

entrada…  

AE

DI

35

Esp

ecifica

ción

– P

ráctica

2

EJERCICIOS USEMOS MISMOS… problema problemaRaro(s: [Int]) = result: [Int]{

modifica: s;asegura: mismos(s, paresX2(pre(s)));asegura: mismos(result, impares(pre(s))); aux paresX2 (s:[Int]) : [Int] =

[xi*2 | i [0..|s|), i mod 2 == 0]; aux impares (s:[Int]) : [Int] =

[xi | i [0..|s|), i mod 2 != 0];}

  Nota: las funciones auxiliares las puedo poner dentro o fuera de

la especificación del problema. Si las especifico dentro del problema, sólo podrán ser usadas dentro de la especificación de ese problema y nada más.

AE

DI

36

Esp

ecifica

ción

– P

ráctica

2