Práctica 4: Especificación de Problemas (Algoritmos I)
De Cuba-Wiki
Ejercicio 1
Las siguientes especificaciones no son correctas. Indicar por qué y corregirlas para que describan correctamente el problema.
I) problema arcoSeno(x, ε : R) = res : R{
requiere : ε > 0;
asegura : | sin(res) − x| ≤ ε;
}
II)
III)
IV)
V)
VI)
Ejercicio 2
La siguiente no es una especificación válida, ya que para ciertos valores de entrada que cumplen la precondición, no existe una salida que cumpla con la postcondición
problema subListaQueSume(lista : [Z], suma : Z) = sublista : [Z]{
asegura Incluida: (∀x ← sublista)cant(sublista, x) ≤ cant(lista, x);
asegura SumaJusta: sublista == suma;
aux cant(l : [Z], n : Z) : Z = |[x|x ← l, x == n]|;
}
Ejercicio 3
Para los siguientes problemas, dar todas las soluciones posibles a las entradas dadas.
i) problema raizCuadrada(x : R) = res : R{
requiere : x ≥ 0;
asegura : res2 == x;
}
a) x = 0
b) x = 1
c) x = 27
ii) problema indiceDelMaximo(l : [R]) = res : Z{
requiere : |l| > 0;
asegura : 0 ≤ res < |l|;
asegura : (∀i ← [0.. |l|))li ≤ lres ;
}
a) l = [1, 2, 3, 4]
b) l = [15.5, −18, 4.215, 15.5, −1]
c) l = [0, 0, 0, 0, 0, 0]
iii) problema indiceDelPrimerMaximo(l : [R]) = res : Z{
requiere : |l| > 0;
asegura : 0 ≤ res < |l|;
asegura : (∀i ← [0.. |l|))(li < lres ∨ (li == lres ∧ i ≥ res));
}
a) l = [1, 2, 3, 4]
b) l = [15.5, −18, 4.215, 15.5, −1]
c) l = [0, 0, 0, 0, 0, 0]
