CC40A: Diseño y Análisis de Algoritmos

Prof: Gonzalo Navarro

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

Nota = 2/3 NC + 1/3 NT, donde ambas NC y NT deben ser >= 4.0.
NC: formada por 3 controles y examen. Se exime del examen con 5.5 en controles. El examen reemplaza el peor control si eso conviene al alumno. Luego de eso se promedian los 3 controles y el examen para formar la NC.
Examen recuperativo para NC >= 3.7. El recuperativo se aprueba o desaprueba. En caso de aprobar la NC queda en 4.0.
NT: 1 proyecto semestral con tres entregas que se promedian para formar la NT. Se descuenta un punto por día de atraso en las entregas. La NT debe ser >= 4.0 o el alumno reprobará por tareas. Se puede quedar I por esta tarea, pero la tarea recuperativa incluirá las tres entregas y un trabajo extra.
Reclamos: se podrán reclamar los controles y, si el tiempo lo permite, el examen.

Programa

Introducción (3 horas)

Algoritmos y su complejidad. Cómo se mide la eficiencia de un algoritmo? Tiempo y Espacio. Peor caso, caso promedio. Modelo de un computador y sus medidas de complejidad.

Fundamentos Matemáticos (6 horas)

Notación. Medidas de Orden. Solución de Recurrencias. Funciones Generatrices. Cálculos asintóticos. Manipulación de big-O.

Paradigmas (9 horas)

Técnicas para el diseño de algoritmos: Búsqueda exhaustiva, heurísticas, algoritmos probabilísticos, algoritmos aproximados, avaricia (greedy), dividir para reinar, programación dinámica, inducción. En cada caso, revisión de problemas característicos y de un mismo problema resuelto con cada técnica.

Manipulación de Conjuntos (9 horas)

Breve repaso de técnicas básicas de ordenación (quicksort, mergesort, etc.) y de estructuras de datos para manipulación de conjuntos (árboles binarios, AVL, árboles 2-3, hashing). Algoritmos de selección: Max-Min, k-ésimo. Colas de Prioridad: heaps. Heapsort. Memoria secundaria: árboles B, hashing extendible. Union-find.

Algoritmos Paralelos (4.5 horas)

Modelos de máquinas paralelas: memoria compartida, pasaje de mensajes. El modelo PRAM: EREW, CREW, CRCW. Ejemplos de algoritmos para cada modelo. El modelo BSP para pasaje de mensajes. Ejemplos.

Algoritmos en Grafos (4.5 horas)

Definiciones. Propiedades básicas. Arboles cobertores de costo mínimo. Búsqueda en grafos. Caminos mínimos. Clausura transitiva.

Búsqueda en Texto (4.5 horas)

Búsqueda de strings: autómata finito, algoritmos de Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Shift-Or, BDM. Arboles digitales: tries, Patricia. Arboles de sufijos. Búsqueda aproximada.

Problemas NP-completos (4.5 horas)

Máquinas de Turing no determinísticas. Las clases P y NP. El problema de la satisfactibilidad (SAT). Otros problemas NP-Completos.

Bibliografía

"*" indica los textos más recomendados, "+" los recomendados como referencia pero no para aprender, "-" otros.

[+] A.V. Aho, J.E. Hopcroft y J.D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
[+] A.V. Aho, J.E. Hopcroft y J.D. Ullman, "Data Structures and Algorithms", Addison-Wesley, 1982.
[-] S. Baase, "Computer Algorithms: Introduction to Design and Analysis", Addison-Wesley 1988.
[-] Brassard, G. and Bratley, P., "Algorithmics: Theory and Practice", Prentice Hall, 1988. 1988.
[*] Cormen, Leiserson, Rivest, "Introduction 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.
[+] R. Sedgewick y P. Flajolet, "An Introduction to the Analysis of Algorithms", Addison-Wesley, 1996.
[*] R. Sedgewick, "Algorithms", Addison Wesley, 1987.