AEDI
Especificación – Práctica 2
LENGUAJE DE ESPECIFICACIÓN
1
Algoritmos y Estructuras de Datos I
Especificación – Práctica 2
ESPECIFICACIÓN DE PROBLEMAS
AEDI
 Expresamos
 No



Especificación – Práctica 2
formalmente qué debe cumplir
una función para ser solución al problema
dado.
expresamos cómo solucionarlo
Puede 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.
2
ESPECIFICACIÓN DE PROBLEMAS
NOTACIÓN
AEDI
Especificación – Práctica 2
problema nombre(parámetros) = salida {
modifica: parámetro;
requiere: expresión1;
asegura: expresión2;
-- DEFINICIÓN DE AUX –
}
3
EJERCICIOS
Especificar el problema de, dados dos enteros,
devolver cualquiera de ellos.
Especificaión – Práctica 2

AEDI

Especificar el problema de, dados dos enteros,
devolver el máximo.
4
OPERACIONES CON SECUENCIAS
AEDI
long(a) ó |a|
 indice(s,i) ó s[i] ó si
 cab(s)
 cola(s)
 en(e,s) ó e en s ó e  s
 cons(e,s) ó e:s
 conc(s,t) ó s++t
 sub(s, e, f) ó s[e..f]
 cambiar (s, i, e)

Especificación – Práctica 2
5
OPERACIONES CON SECUENCIAS
AEDI
alguno(s)
 todos(s)
 sum(s) ó s
 prod(s) ó s

Especificación – Práctica 2
6
RECORDANDO


Equivale a
todos([propiedad | selectores, condiciones])
Existe:
( selectores, condiciones) propiedad

Especificación – Práctica 2
Para todo:
( selectores, condiciones) propiedad
AEDI

Equivale a
alguno([propiedad | selectores, condiciones])
Nota: cuando decimos “propiedad” nos referimos a
7
expresiones de tipo Bool.
SECUENCIAS POR COMPRENSIÓN
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

8
Especificación – Práctica 2

Notación:
[expresión | selectores, condiciones]
AEDI

RECORDANDO
AEDI

aux 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);
9
Especificación – Práctica 2
Contar cuántas veces aparece x en la secuencia a
ESPECIFICACIÓN DE PROBLEMAS
EJERCICIO – SOLUCIÓN
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;
}
Especificación – Práctica 2
Especificar el problema de, dados dos enteros,
devolver el máximo.
AEDI

10
ESPECIFICACIÓN DE PROBLEMAS
EJERCICIO – SOLUCIÓN
problema dameUno(a, b: Z) = result: Z{
asegura: (result == a) || (result == b);
}
Especificación – Práctica 2
Especificar el problema de, dados dos enteros,
devolver cualquiera de ellos.
AEDI

11
USANDO LISTAS POR COMPRENSIÓN

[x+y | x  a, y  b, x  y], qué indica esta expresión?


Por ejemplo: a = [1,2,3] y b = [1,2,3]

Especificación – Práctica 2
[x | x  [5,7,4,2,8,6,4,5,8,2,7,4], x4] = [4,2,4,2,4]
AEDI

[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]
12
MÁS EJERCICIOS CON SECUENCIAS
problema sumaCabezas (a, b: [Z]) = result : Z {
requiere : |a| > 0 && |b| > 0;
asegura : result == cab(a) + cab(b);
}
Especificaión – Práctica 2
Especificar el problema de, dadas dos listas de
enteros, devolver la suma de las cabezas de cada
una.
AEDI

13
MÁS EJERCICIOS CON SECUENCIAS
problema sumaPrimerosPares (a, b: [Z]) = result : Z {
requiere : existePar(a) && existePar(b);
asegura : result == primerPar(a) + primerPar(b);
Especificaión – Práctica 2
Especificar el problema de, dadas dos listas de
enteros, devolver la suma del primer elemento par
de cada una.
AEDI

aux existePar(a: [Z]) : Bool =
( x <- a) a mod 2 == 0;
aux primerPar(a: [Z]) : Z =
cab([ x | x <- a, a mod 2 == 0]);
}
14
MÁS EJERCICIOS CON SECUENCIAS
problema sumaListas (a, b: [Z]) = result : [Z] {
requiere : |a| == |b|;
asegura : result == [ a[i] + b[i] | i <- [0..|a|)];
}
Especificaión - Práctica 2
Especificar el problema de, dadas dos listas con
números enteros (que posean igual longitud),
devolver la suma elemento a elemento.
AEDI

15
MÁS EJERCICIOS CON SECUENCIAS
problema sumaListas (a, b: [Z]) = result : [Z] {
asegura :
result == [a[i] + b[i] | i <- [0..min(|a|,|b|))];
Especificaión - Práctica 2
Variante: no requerir que sean de igual longitud y
suponer que se devuelve la suma hasta que alguna se
acaba.
AEDI

aux min(a,b: Z) : Z =
if (a < b) then a else b;
}
16
MÁS EJERCICIOS CON SECUENCIAS
problema indiceMenorDistintos(a:[Float])=result:[Z]{
requiere noNegativos: (x <- a) x  0;
requiere distintos:
(i <- [0..|a|), j <- [0..|a|), i ≠ j) a[i] ≠ a[j];
Especificaión - Práctica 2
Encontrar el índice (la posición) del menor
elemento en una secuencia de números reales
distintos no negativos.
AEDI

asegura : 0 ≤ result < |a|;
asegura : (x <- a) a[result] ≤ x;
}
17
MÁS EJERCICIOS CON SECUENCIAS
problema ordenar(a:[Z])=result:[Z]{
asegura : mismos(result,a);
asegura :
(i <- [0..|a|-1)) result[i] ≤ result[i+1];
Especificaión - Práctica 2
Especificar el problema de, dada una lista de
enteros, devolver una que tenga los mismo elementos
pero ordenada.
AEDI

}
18
Descargar

problema