Final 03/05/17 (Algoritmos II)

Tomado por Esteban Feuerstein, corregido por Fernando Schapachnik.

Para aprobar: como mínimo 3 ejercicios BIEN

Ejercicio 1

A continuación se muestran unos breves enunciados junto a fragmentos de su especificación como TADs. Indicar si dichos fragmentos son correctos o presentan errores, y si es así cuáles y por qué.

a) En un frasco aislado en un laboratorio se cuenta con una cantidad de hielo, que al ser sometido a calor se transforma en agua, a razón de un $dm^{2}$ por caloría. Como el frasco está aislado, ésa es la única transformación posible.

   TAD frasco
   generadores:
   nuevo_frasco: tamaño -> frasco
   observadores:
   volumen_hielo: frasco -> nat
   volumen_agua: frasco -> nat
   operaciones:
   aportar_calorías: frasco x nat -> frasco
   disminuir_hielo: frasco x nat -> frasco
   incrementar_agua: frasco x nat -> frasco
   Fin TAD

b) Una bolita se desplaza sobre una recta a medida que recibe impulsos. Los impulsos se miden en kilos, y la relación entre ambos es que por cada kilo la bolita avanza dos metros.

   [...]
   observadores:
   posición: bolita -> nat
   operaciones:
   empujar: bolita x nat i x distancia d -> bolita { d = 2i }
   [...]

c) Se desea modelar una pila que siempre permite aplicar la operación top(), pero indica cuando no hay ningún elemento válido.

   observadores:
   top: pila -> <elem, bool>

d) Ídem anterior:

   top: pila -> indicador
   hay_elem?: indicador -> bool
   elem: pila x indicador i -> elem { hay_elem?(i) } 

Ejercicio 2

Supongamos que extendemos el TAD Diccionario agregándole una operación RestricciónDeRango(x,y), con x<=y, que elimina del diccionario todos los valores que son mayores que x o menores que y. Por ejemplo, si las claves son reales, luego de una operación RestricciónDeRango(x,y) el diccionario contendría solamente las claves en el intervalo cerrado [x,y]. Proponga una estructura de datos para implementar eficientemente tanto las operaciones tradicionales de diccionario como la nueva operación, considerando los siguientes casos:

a) Se ruede asumir que x e y están en el diccionario.

b) No se puede asumir que x e y están en el diccionario.