ELO 320 1er. Sem. 2002
2º Tarea de Programación: Hashing Cerrado.
Objetivos:
Aplicar uso de "makefile" para la compilación de progrmas.
Desarrollo de programas modulares y el manejo de proyectos de archivos multiples
Conocer y aplicar integracción y comunicación con módulos
externos, en particular gnuplot.
Medición de tiempos en procesos no deterministicos.
Programación de algoritmos de inserción y búsuqueda
en tablas de "hashing"
Comparar medidas teóricas con experimentales
Actividad:
Haga un programa que muestre dos tipos de gráficos:
A.- Este muestra la cantidad promedio de intentos en la inserción
de un elemento nuevo en la tabla hash versus el factor de carga de la tabla.
B.- Este muestra la cantidad promedio de intentos en la búsqueda exitosa
de un elemento de la tabla hash versus el factor de carga de la tabla.
Para ambos gráficos, pueble las tablas con palabras obtenidas de
este archivo de texto
.
Busque/proponga una función de hashing para convertir cada palabra
en un entero.
Use una función de hashing doble (o re-hashing) usando algún
método de multiplicación y en el mismo gafico muestre los valores
esperatos teóricamente (resultados vistos en clases).
En otros dos gaficos muestre los mismos casos A y B pero usando hashing lineal.
A Entregar:
Un archivo con implementación de los algoritmos de inserción
y busqueda.
Un archivo con implementación de la función de hashing.
Un archivo con implementación de la función de hashing doble
lineal.
Un archivo con implementación de la función de hashing usando
método de multiplicación.
Un programa que use los previos para resolver los gráficos A y B
para hashing lineal.
Un programa que use los previos para resolver los gráficos A y B
para hashing usnado multiplicación.
Si usted lo estima necesario, separe el problema en más archivos
aún.
Un archivo makefile.
Un archivo Readme.
Revisar el procedimiento de evaluación antes de entregar la tarea.