Edición de «Final 03/05/17 (Algoritmos II)»

{{back|Algoritmos_y_Estructuras_de_Datos_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 <math>dm^2</math> 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 <code>aportar_calorías</code>, por ejemplo, el observador <code>volumen_agua</code> 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 <code>empujar</code> 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 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. 

== 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).
@@ Línea 48: / Línea 48: @@
 La forma de arreglarlo sería convertir una de las operaciones en generador.
-Además, las operaciones <code>disminuir hielo</code> y <code>incrementar_agua</code> no respetan el comportamiento automático que el enunciado da a entender.
 b) El TAD podría estar mejor. En la operación <code>empujar</code> 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:
+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 puede 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) Se ruede asumir que x e y están en el diccionario.
-a) Skip-list?
-b) Skip-list?
+b) No se puede asumir que x e y están en el diccionario.
 == Ejercicio 3 ==
@@ Línea 75: / Línea 68: @@
 == 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 <math>h(k,i) = (h_1(k) + i * h_2(k)) mod |T|</math>, con <math>k</math> siendo la clave, <math>i</math> siendo el número de intento, y <math>|T|</math> 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, <math>h(k,0) = h_1(k) mod |T|</math>, y <math>h_1(k)</math> siempre devolvería el mismo valor.
-Luego, si hay una colisión para <math> h(k, i) = c + i * h_2(k) </math>, siendo <math> h_1(k) = c </math>, se produciría aglomeración secundaria, ya que:
-<math>\forall i,  h_1(k1) == h_1(k2) \implies h(k1,i) == h(k2,i) </math>.
-En el segundo caso, ni bien haya una colisión en <math>h_1</math>, habrá una colisión en la función de hash total, ya que <math>h(k,i) = (h_1(k) + i * constante) mod |T|</math>. Esto produciría aglomeración primaria.
-[[Category: Finales]]