1. Educación

Grado en Ingeniería Informática
Ceuta, Curso 2014/2015
Estructuras de Datos.
Práctica 1.
Cálculo de eficiencia empírica y teórica de algoritmos.
Esta primera práctica consistirá en el análisis de la eficiencia de diversos algoritmos de búsqueda
y ordenación. El objetivo es determinar la implementación más eficiente para un determinado
algoritmo.
1. Implementación de algoritmos.
Cree un programa que permita evaluar la eficiencia de los distintos algoritmos de búsqueda y
ordenación. Para ellos se implementarán diversas algoritmos de búsqueda y ordenación en
forma de funciones. El programa generará un vector de enteros de forma aleatoria, y se
realizarán sobre él las siguientes operaciones:
a. Búsqueda secuencial: Busca un valor en el vector, comienza desde el inicio y termina
cuando lo encuentre. El vector no tiene porqué estar ordenado.
b. Búsqueda binaria: Busca un valor en el vector usando el algoritmo de búsqueda
binaria. El vector debe estar ordenado.
c. Ordenación burbuja: Ordenar el vector con el algoritmo de ordenación por el método
de la burbuja.
d. Ordenación por selección: Ordenar el vector con el algoritmo de ordenación por
selección.
e. Ordenación por inserción: Ordenar el vector con el algoritmo de ordenación por
inserción.
f.
Ordenación Quicksort: Ordena el vector con el algoritmo recursivo Quiscksort.
El programa, a partir de un valor que indicará el tamaño del problema, generará un vector
aleatorio de ese tamaño, y además se generará un valor aleatorio en el mismo rango de
valores que los enteros del vector.
Se buscará si el valor generado se encuentra dentro del vector usando búsqueda secuencial y
búsqueda binaria. El programa dará el valor de tiempo en segundos que ha tardado cada una
de las operaciones.
El programa también debe mostrar el tiempo que tarda en ejecutarse cada uno de los métodos
de ordenación.
Para el cálculo empírico del tiempo de ejecución puede consultar las funciones time() y
clock().
Para poder comprobar adecuadamente el funcionamiento de los algoritmos, todos deben usar
los mismos datos de entrada (el mismo vector de valores aleatorios).
Documente de forma adecuada las funciones utilizando Doxygen. Debe entregar como mínimo
1
la documentación HTML, se valorará la entrega de la documentación generada como un
fichero PDF.
Proporcione un fichero makefile para construir el programa. No debe proporcionar los ficheros
ejecutables, únicamente el código fuente y el fichero makefile correspondiente.
2. Implementación de algoritmos recursivos
Cree funciones recursivas que implementen los siguientes algoritmos:
a. Búsqueda secuencial.
b. Búsqueda binaria.
3. Implementación de otros algoritmos de ordenación
Busque información e implemente los siguientes algoritmos.
a. Ordenación Shell (ShellSort).
b. Ordenación por mezcla (MergeSort).
4. Cálculo de la eficiencia empírica.
Se realizará el cálculo de la eficiencia empírica para los algoritmos del programa creado en la
sección anterior.
Para ello debe realizar las siguientes tareas:
a. Usando distintos tamaños para el problema, tome los tiempos de ejecución de cada
uno de los algoritmos. Confeccione una tabla con los resultado obtenidos.
b. El programa debe generar un fichero de texto en el que se registren todos los datos de
las ejecuciones realizadas (Nombre de Algoritmo, Tamaño del Problema, Tiempo de
Ejecución). Organice la información de tal forma que pueda importarse desde una hoja
de cálculo.
c. Cree una gráfica (Excel, Calc,...) que muestre la evolución del tiempo de ejecución con
respecto al tamaño del problema, partiendo de los datos almacenados en el fichero.
5. Cálculo de la eficiencia teórica.
Realice el cálculo de la eficiencia teórica para los algoritmos iterativos. Inserte en el código de
los algoritmos comentarios para el análisis de la eficiencia teórica, determine el orden de
eficiencia para cada instrucción, bloque, y total, para cada una de las funciones siguientes:
a. Búsqueda secuencial (iterativa).
b. Búsqueda binaria (iterativa).
c. Ordenación burbuja.
d. Ordenación por selección.
e. Ordenación por inserción.
6. Análisis de resultados.
Elabore un documento en el que se describa cada uno de los algoritmos implementados, se
presenten y analicen las tablas y gráficas obtenidos para la eficiencia empírica, así como los
valores obtenidos de eficiencia teórica.
Determine y justifique el algoritmo de ordenación, y el de búsqueda más eficientes...
a. Analice los resultados, atendiendo a la eficiencia empírica.
a.i. ¿Cómo se comportan las versiones iterativas de los algoritmos frente a las
recursivas?. ¿A qué responde este comportamiento?.
b. Analice los resultados, atendiendo a la eficiencia teórica.
c. Analice los resultados, teniendo en cuenta ambas medidas de eficiencia.
2
Objetivos
•
•
Adquirir la capacidad para comprender cómo el uso de distintos tipos de datos afecta a la
eficiencia de los algoritmos que la usan.
Ser capaz de comparar implementaciones alternativas para un tipo de dato analizando los
factores que influyen en la eficiencia y el uso de memoria.
Evaluación de la práctica
La práctica se valorará con una calificación de 0 a 10 puntos, y supondrá 0,25 puntos de la nota
final de la asignatura.
Se valorará:
• Correcta implementación del programa, y los algoritmos.
• Cálculo correcto de la eficiencia teórica en los comentarios de los programas.
• Correcta generación de los datos para usarlos en hojas de cálculo.
• Documentación adecuada utilizando Doxygen.
• Documento de análisis completo y organizado.
◦ Tablas organizadas y correctamente explicadas.
◦ Gráficas correctas y explicadas claramente.
◦ Análisis correcto de los valores de eficiencia empírica y teórica.
Fecha y Forma de Entrega
La entrega se realizará a través de la plataforma de la asignatura, en una actividad creada a tal
efecto. Todos los ficheros que compongan la entrega deben subirse a la actividad creada en la
plataforma como un único fichero comprimido.
La fecha de entrega será hasta el día 15/10/2014 a las 23:59 horas.
Todas aquellas prácticas entregadas fuera de dicho plazo, tendrán como fecha límite de entrega el
día previo al examen de Febrero 03/02/2015 a las 23:59 horas, y se valorarán sobre un 70% de la
puntuación original de la práctica.
3