|
PROBLEMAS Objetivo: Estudio comparativo de algoritmos sencillos y caracterización de sus costes temporales medidos en pasos. Se considerarán en esta práctica 3 algoritmos de búsqueda en vectores ordenados: búsqueda lineal, dicotómica y dicotómica modificada. Habría que implementar los tres algoritmos como funciones que toman un valor , un vector y una talla y devuelven un índice entre 0 y ( significa que el elemento x no se encuentra en v ). Habría que hacer un programa principal que genere un vector ordenado y al que se pueda dar un valor x. El programa tendría que dejar claro que los algoritmos implementados funcionan correctamente. El algoritmo de búsqueda lineal no merece ningún comentario. La versión de la búsqueda dicotómica que se ha estudiado en teoría es:
El algoritmo anterior recibe el nombre de búsqueda dicotómica de tres vías ya que en cada paso se pueden tomar tres decisiones: izquierda, derecha o acabar (Figura 1). Una alternativa es la llamada búsqueda dicotómica de dos vías (modificada). El algoritmo consiste en continuar la búsqueda por la izquierda o por la derecha incluyendo en una de las dos opciones también la posición central independientemente de si contiene o no el elemento (Figura 2). Aunque este algoritmo no tiene un mejor caso como el anterior, es evidente que requiere una comparación menos en cada iteración. (Cuidado con la posibilidad de entrar en un bucle infinito con este algoritmo!) Estudio comparativo Se trata de evaluar los costes de los tres algoritmos anteriores. La instrucción crítica considerada será la comparación sobre elementos del vector (no las comparaciones de índices). Habría que añadir contadores de comparaciones dentro de los algoritmos. Para calcular el coste medio, habría que repetir búsquedas aleatorias ( rand() ) sobre un mismo vector y calcular el promedio. Para cada talla, el vector será fijo y contendría enteros impares (1,3,5,...). Consideraremos dos casos a) generación y búsqueda de enteros aleatorios entre 0 y 2n . (50% de probabilidad de éxito) y b) generación aleatoria de índices entre 0 y n-1 y búsqueda del valor x=v [ i ] (100% de probabilidad de éxito). Se podrá considerar un único vector de la talla máxima y considerar la parte correspondiente para cada (cuidado con los índices fuera de rango). Para unificar las diferentes tallas a considerar habría que usar un bucle de la forma for (n=10; n<10000; n = n*3/2). Para cada talla, el número de búsquedas deberá ser de al menos 5 veces n. Si el programa escribe en un fichero los resultados en dos columnas (para n y para T(n), respectivamente) entonces se puede mostrar la función coste gráficamente mediante el programa gnuplot. Algunos comandos de éste son:
Documentación a entregar 1) ficheros de programas (pro.cpp y cost.cpp) desarrollados correspondientes a la comprobación y al estudio comparativo. Hay que adjuntar información suficiente para compilar, ejecutar y comprobar que los programas funcionan bien. 2) funciones coste obtenidas en ficheros separados con el formato anteriormente descrito. El nombre será ALG-P.dat , donde ALG puede ser lin, bin , o bim y P puede ser 50 ó 100 (probabilidad de éxito). 3) ficheros de gráficas de gnuplot donde se comparen los diferentes algoritmos. Concretamente binlin-P.plt, bin23-P.plt donde P es la probabilidad de éxito. 4) fichero de tipo texto en el que tendrás que comentar los resultados obtenidos en el estudio comparativo. Comenta si te parecen o no lógicos, si eran esperables, etc.¿ Qué crees que pasará con el coste "real" medido como tiempo de ejecución?
Solución |
