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) }

Soluciones

a) El TAD no es correcto. El error se encuentra en que las operaciones podrían generar un frasco con diferentes observadores que el que genera el único generador que hay. Si se llama a aportar_calorías, por ejemplo, el observador volumen_agua del nuevo frasco debería tener como valor uno mayor al original, pero eso no se puede lograr con el único generador existente.

La forma de arreglarlo sería convertir una de las operaciones en generador.

b) El TAD podría estar mejor. En la operación empujar no hace falta que se pasen la distancia y el i, ya que una determina la otra inequívocamente. Lo arreglaría tener solo como parámetro uno de los dos.

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 menores que x o mayores 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.

Soluciones

a) Skip-list?

b) Skip-list?

Ejercicio 3

Se cuenta con n elementos que contienen una clave primaria y una secundaria. Hay m<<n claves secundarias distintas. Proponga dos formas eficientes y distintas que permitan ordenar los n elementos en base a las dos claves (primero la primaria, luego la secundaria) considerando que en una de ellas sólo puede utilizar arreglos.

Ejercicio 4

a) El invariante de representación suele escribirse de manera formal y eso permite utilizarlo para una serie de cosas. Si se escribiese en castellano, ¿cuáles de esas cosas se podrían seguir haciendo y cuáles no? Justifique.

b) Si el invariante de un tipo resultase programable, ¿lo haría? ¿para qué lo usaría? Justifique.

Ejercicio 5

Suponiendo que un programador tiene un error en una implementación de un diccionario con hashing doble, de modo que una de las dos funciones devuelve el mismo valor (distinto de 0), describir lo que sucede en cada situación (cuando es la primera función la que está mal y cuando lo es la segunda).

Solución

En el hashing doble, el hash se calcula como $h(k,i)=(h_{1}(k)+i*h_{2}(k))mod|T|$, con $k$ siendo la clave, $i$ siendo el número de intento, y $|T|$ siendo la longitud del arreglo de claves.

En el primer caso, la función de hash tendría colisiones siempre en el primer intento, ya que en ese caso, $h(k,0)=h_{1}(k)mod|T|$, y $h_{1}(k)$ siempre devolvería el mismo valor. Luego, si hay una colisión para $h(k,i)=c+i*h_{2}(k)$, siendo $h_{1}(k)=c$, se produciría aglomeración secundaria, ya que:

$\forall i,h_{1}(k1)==h_{1}(k2)\implies h(k1,i)==h(k2,i)$.

En el segundo caso, ni bien haya una colisión en $h_{1}$, habrá una colisión en la función de hash total, ya que $h(k,i)=(h_{1}(k)+i*constante)mod|T|$. Esto produciría aglomeración primaria.