Patiperros del DCC

Vigencia

En trámite (Otoño 1994).

Requisitos

CC20A

Objetivos

Estudiar métodos para el diseño de algoritmos y el desarrollo de programas. Conocer los principales algoritmos y estructuras de datos, incluyendo el análisis de su desempeño.

Programa

Métodos de programación

Nociones básicas de verificación de programas. Invariantes. Diagramas de estados. Recursión. Co-rutinas. Desarrollo de programas "top-down" y "bottom-up". Encapsulamiento y tipos de datos abstractos (TDAs).

Nociones de análisis de algoritmos

Como medir la eficiencia de los algoritmos: peor caso, caso promedio, costo amortizado. Notación "O". Técnicas para plantear y resolver ecuaciones de recurrencia.

Técnicas básicas para la estructuración de datos

Arreglos, punteros, árboles.

TDAs básicos

Listas, "stacks'' (con aplicaciones a eliminación de recursividad), colas.

TDA "diccionario"

Definición, variantes. Implementaciones en base a busqueda secuencial. Búsqueda binaria. "Skip lists". Árboles de búsqueda binaria. Árboles óptimos. Árboles balanceados: AVL, 2-3. "B-trees". "Splay trees". Árboles digitales. "Hashing''.

Métodos de ordenación

Cota inferior. Métodos cuadráticos. "Quicksort". "Heapsort". "Bucketsort". Ordenamiento externo.

Búsqueda en texto

Método de fuerza bruta. Knuth-Morris-Pratt. Boyer-Moore-Horspool.

Algoritmos en grafos

Representación de grafos. Recorridos. Árboles de costo mínimo. Distancias mínimas.

Algoritmos probabilísticos

Problemas NP-completos

Bibliografía

• H.R. Lewis y L. Denenberg, "Data Structures and Their Algorithms'', Harper Collins Publishers, 1991.

• Manber, U., "Introduction to Algorithms: A Creative approach'', Addison Wesley, 1989.

• T. Cormen, C. Leiserson y R. Rivest, "Introduction to Algorithms'', The MIT Press, 1990.

• R. Sedgewick, "Algorithms'', Addison Wesley, 1987.

• G. H. Gonnet y R. Baeza-Yates, "Handbook of Algorithms and Data Structures'', Addison-Wesley, 1991.

• D. E. Knuth, "The Art of Computer Programing'', vol. 1, "Fundamental Algorithms'', Addison-Wesley, segunda edicion, 1973.

• D. E. Knuth, "The Art of Computer Programming'', Vol. 3, "Sorting and Searching'', Addison-Wesley, 1973.