Ciencias de la Computación (plan 1994) 2021-2
Optativas, Análisis de Algoritmos II
Grupo 7007, 60 lugares. 4 alumnos.
Cambiaremos el horario del curso a su horario habitual de 12:00 a 13:00.
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, incluyendo los de exposición.
Dinámica del curso:
Las sesiones del curso serán usando zoom.
https://cuaed-unam.zoom.us/j/85102661776
Todos los días a la hora de clase.
No se grabarán las sesiones, pero se enviarán las notas que se generen durante la clase.
Las tareas se entregarán usando Google Classroom.
Favor de verificar su correo registrado en el sistema de la facultad, porque el viernes 26 de febrero se escribirá directamente a la lista de correos que la facultad proporciona a los profesores la información para conectarse a la clase el lunes 01 de marzo de 2021.
Sistema de calificaciones:
Exposiciones 90 %. Dependiendo del número de estudiantes, serán dos exposiciones en el semestre y en equipo.
Tareas 10%
No hay extraordinarios largos.