CC40A: Diseño y Análisis de Algoritmos

Prof: Ricardo Baeza Yates
rbaeza@dcc.uchile.cl
www.dcc.uchile.cl/~rbaeza/cursos/cc40a.html

Motivación

Analizar la eficiencia de diversos algoritmos para resolver una variedad de problemas, principalmente no numéricos. Enseñar al alumno a diseñar y analizar nuevos algoritmos.

Reglas del Juego

• 2 controles y un examen. 2/3 de la nota y debe ser >= 4.
• Tareas (4). 1/3 de la nota y debe ser >= 4.
  Descuento por atraso: 1 punto por día hábil o fin de semana.

Programa

Introducción (3 horas)

Algoritmos y su complejidad. ¿Como se mide la eficiencia de un algoritmo? Tiempo y Espacio. Peor caso, caso promedio. Medidas de orden. Modelo de un computador y sus medidas de complejidad.

Fundamentos Matemáticos (6 horas)

Solución de Recurrencias (Números de Fibonacci). Funciones Generatrices. Cálculos asintóticos. Técnicas para cotas inferiores (teoría de la información, adversarios, complejidad de Kolmogorov).

Técnicas Básicas (9 horas)

Inducción: ejemplos simples. Otros paradigmas como casos particulares de inducción. Inducción doble y reforzada.

Dividir para reinar: quicksort, mergesort, algoritmos de selección, algoritmo de Strassen, árboles de búsqueda y otras estructuras de datos recursivas.

Programación dinámica. Arboles binarios de búsqueda. Algoritmos en grafos. Subsecuencia común más larga.

Algoritmos Competitivos (3 horas)

Algoritmos en línea vs. los que saben toda la información. Paginamiento. Búsqueda en el plano.

Aleatorización (6 horas)

Aleatorizar la entrada: hashing. Algoritmos aleatorios: listas saltadas, hashing perfecto. Algoritmos probabilisticos.

Uso de finititud (6 horas)

Búsqueda por interpolación, bucketsort, árboles digitales, búsqueda de strings.

Heurísticas (12 horas)

Heurísticas en estructuras de datos: auto-organizadas, splay trees. Análisis amortizado. Operaciones sobre conjuntos: Union-Find. Algoritmos golosos: algoritmo de Dijkstra, árboles de cobertura mínimos.

Algoritmos Aproximados (3 horas)

Resolución de problemas NP-completos: búsqueda exhaustiva, algoritmos con soluciones aproximadas acotadas.

Tópicos Avanzados (9 horas)

Algoritmos paralelos y distribuidos. Algoritmos genéticos. Algoritmos Geométricos (Convex Hull). Búsqueda multidimensional: k-d trees, grid files. Manejo de Memoria Dinámica.

Bibliografía

*

A.V. Aho, J.E. Hopcroft y J.D. Ullman, ``The Design and Analysis of Computer Algorithms'', Addison-Wesley, 1974.

**

Brassard, G. and Bratley, P., ``Algorithmics: Theory and Practice'', Prentice Hall, segunda edición, 1997.

*

Cormen, Leiserson, Rivest, ``Intr. to Algorithms", MIT Press, 1991.

-

Gonnet, G. y Baeza-Yates, R., ``Handbook of Algorithms and Data Structures'', Addison-Wesley, 2ed, 1991.

-

Harel, D. Algorithmics, the spirit of computing, Addison Wesley 1987.

-

D.E. Knuth, ``The Art of Computer Programing'', vol. 1, "Fundamental Algorithms", Addison-Wesley, segunda edición, 1973.

-

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

*

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

*

Rawlins, G., ``Compared to What? An Introduction to Analysis of Algorithms", Computer Science Press, 1991.

-

Reingold, Nievergelt, and Deo., Combinatorial algorithms, Prentice-Hall, 1977.

*

R. Sedgewick, ``Algorithms'', Addison Wesley, 1987.