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 79: | Línea 72: | ||
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 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 | En el primer caso, la función de hash fallaría casi 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. | ||
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> | 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>. | ||
[[Category: Finales]] | [[Category: Finales]] |