$[/\]$

Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

CI-1303 Estructuras de Datos y Análisis de Algoritmos

Año 1996
I Semestre
II Semestre

Año 1997
I Semestre
II Semestre

Año 1998
I Semestre
II Semestre

Año 1999
I Semestre
II Semestre

REQUISITOS

CI-1201 Programación II	Horas:	4
CI-1104 Matemáticas Discretas I	Créditos:	4

OBJETIVO

El estudiante será capaz de seleccionar el objeto o modelo matemático más adecuado para la especificación formal y la posterior resolución de un problema. Además, podrá identificar las operaciones elementales y no elementales que se deberán aplicar al modelo escogido con el fin de resolver el problema. El estudiante será capaz de implementar el modelo mediante la escogencia de la estructura de datos apropiada, así como de implementar las operaciones mediante algoritmos específicos. Ambas implementaciones deberán hacerse tomando en cuenta, principalmente, criterios de eficiencia, tanto de espacio como de tiempo, para lo cual el estudiante deberá saber calcular el tiempo y orden de duración de un algoritmo, así como estimar la cantidad de espacio que utiliza.

OBJETIVOS ESPECIFICOS

Estudiar los modelos matemáticos básicos, sus diversas representaciones, sus operaciones básicas y sus algoritmos.
Estudiar las principales estructuras de datos para la organización eficiente de información.
Estudiar los principales algoritmos para ordenamiento, búsqueda, manejo de grafos, etc.
Estudiar las técnicas fundamentales para la resolución de problemas.
Estudiar un modelo para medir la complejidad espacio-tiempo de un algoritmo.

CONTENIDOS

Complejidad espacio-tiempo de un algoritmo.
Factores que afectan el tiempo de ejecución de un algoritmo.
Orden de duración y constantes de proporcionalidad.
Cálculo del tiempo de ejecución y orden de duración de algoritmos iterativos y de algoritmos recursivos
Método de sustitución y generalización
Método para resolución de relaciones de recurrencia lineales no homogéneas
Algoritmos O(n), O(log n), O(n log n), O(2ⁿ), O(n!)
Comparación de una implementación recursiva y una implementación iterativa, por ejemplo para calcular Fibonacci.
Modelos: lista, pila, cola, correspondencia o función, árbol n-ario, conjunto, diccionario, cola de prioridad, relaciones 1:N, relaciones N:M, grafo dirigido y grafo no dirigido, su definición, sus operadores básicos, las estructuras de datos para su implementación y sus algoritmos.
Estructuras de datos: arreglos (circular y lineal), diversas listas (por arreglos, por punteros o por cursores, ordenadas y no ordenadas, doblemente enlazadas, circulares, con cabeza y posición atrasada, etc.), lista de listas, multilista, vector de bits, árbol de búsqueda binaria, árbol parcialmente ordenado, árboles balanceados, tabla hash, vector heap, lista de adyacencia, matriz de adyacencia.
Algoritmos para la implementación de las operaciones y aplicaciones de los modelos: inserciones, borrados y búsquedas en diversos tipos de árboles y algoritmos para el manejo de grafos, tales como: Dijkstra, Floyd, Prim, Kruskal, recorrido en profundidad primero y ancho primero, etc.
Para cada estructura de datos estudiada, analizar sus ventajas y sus desventajas desde el punto de vista de su complejidad espacio-tiempo. Estudiar el orden de duración de los operadores básicos y de los algoritmos de acuerdo a la estructura de datos utilizada, estudiar su complejidad, el gasto de espacio extra y sus constantes de proporcionalidad.
Técnicas para la resolución de problemas de optimización: búsqueda greedy, búsqueda exhaustiva pura, búsqueda exhaustiva con ramificación y acotamiento y búsqueda local. Considerar ventajas y desventajas de cada técnica considerando su complejidad espacio-tiempo.
Resolución mediante técnicas de búsqueda de problemas de mochila, asignación, distribución de recursos y problemas de grafos tales como: circuito de Hamilton de menor costo y ruta de menor distancia en una red.
Backtracking como técnica para la implementación de la búsqueda exhaustiva. Ejemplos de las 8 Reinas, coloreo de mapas, árboles de juego, etc.
Algoritmos de ordenamiento interno: burbuja, selección, inserción, quicksort, heapsort, mergesort, binsort y radixsort. Para cada algoritmo estudiar su estabilidad, su orden de duración en el peor caso y en el promedio, número de comparaciones, número de intercambios, gasto de espacio extra, complejidad y constantes de proporcionalidad.

En todos los temas se incluye el análisis de tiempo de cada algoritmo y se estudia en términos de eficiencia las diferentes estructuras escogidas para la implantación de un TAD.

BIBLIOGRAFIA

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "The Design and Analysis of Computer Algorithms"; Addisson Wesley Publishing Co.; 1974.
Baase Sara: "Computer Algorithms".
Horowitz, E.; Sahni, S.: "Fundamentals of Data Structures"; Computer Science Press; 1982.
Knuth, Donald: "The Art of Computer Programming, Vol. 1 Fundamental Algorithms"; Addison-Wesley; 1968.
Knuth, Donald: "The Art of Computer Programming, Vol. 3 Sorting and Searching"; Adisson-Wesley; 1971.
Kronsjo, Lydia: "Algorithms: Their complexity and efficiency".
Sedgewick, Robert: "Algorithms". Addison-Wesley, 1995
Wirth, Niklaus: "Algoritmos y Estructura de Datos"; Prentice Hall Hispanoamericana; México 1982.

$[/\]$