Ciencias de la Computación (plan 1994) 2020-2
Optativas, Análisis de Algoritmos II
Grupo 7007, 20 lugares. 8 alumnos.
Objectivo del curso.
Conocer y aplicar técnicas de análisis y diseño de algoritmos para resolver problemas reales, usando un enfoque geométrico.
Nota. Es necesario que hayan aprobado la materia Análisis de Algoritmos para llevar el curso.
Índice temático oficial
I. Algoritmos voraces
II. Divide y vencerás
III. Programación dinámica
IV. Análisis amortizado
V. Algoritmos de aproximación
VI. Algoritmos aleatorios
Además del temario oficial agregaremos un enfoque geométrico
VII. Aplicaciones de flujos en redes y emparejamientos
VIII. Clasificación
IX. Iluminación
X. Programación lineal
XI. Dualidad
XII. Algunos resultados clásicos y recientes de geometría computacional y discreta
Bibliografía.
1. Michael Mitzenmacher and Eli Upfal. Probability and Computing, Cambridge University Press, 2005.
2. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms, Cambridge University Press, 2000.
3. Jon Kleinber and Eva Tardos. Algorithm Design, Addison-Wesley, 2006.
4. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 2nd edition, 2001.
5. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry (3rd ed.), Springer Verlag, Berlin, 2008.
6. S. Ghosh. Visibility Algorithms in the Plane. Cambridge: Cambridge University Press, 2007.
7. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985.
También artículos de investigación que se proporcionarán en el transcurso del semestre.
Sistema de calificaciones:
Exposiciones 70 %
Tareas: 30 %
No hay extraordinarios largos. Las tareas se entregan a la hora de clase. Las exposiciones son obligatorias para acreditar el curso.