Edición de «Final 03/05/17 (Algoritmos II)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 48: | Línea 48: | ||
La forma de arreglarlo sería convertir una de las operaciones en generador. | 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. | 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. | ||
Línea 56: | Línea 54: | ||
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 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 | 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. | b) No se puede asumir que x e y están en el diccionario. | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Línea 82: | Línea 75: | ||
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: | 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, | <math>\forall i, h’(k1) == h’(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. | 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]] | [[Category: Finales]] |