Análisis de Algoritmos (COMP-420)
agosto - diciembre 2011
Profesor: Johan Van Horebeek Oficina: H-6, Ext: 49564 Prerequisitos: Haber aprobado los cursos obligatorios del segundo semestre de la licenciatura. Horario: lunes 15:00 a 16:30hrs (salon 2 cimat); jueves 8:00 a 9:30 (salon seminarios demat)
Descripción
Es un curso dirigido tanto a matemáticos como a computólogos con un interés no
solamente en aprender a disenar algoritmos para resolver problemas fundamentales en Ciencias de la
Computación sino también en analizar su comportamiento y complejidad.
El curso sirvirá al mismo tiempo como una aplicación de temas vistos en las materias de
matemáticas al área de Ciencias de la Computación.
Temario (preliminar)
Parte 1:
Técnicas de verificación de algoritmos,
Herramientas matemáticas para estudiar el comportamiento (asimptótica) de algoritmos,
Recursividad y backtracking,
Algoritmos randomizados y su análisis,
Algoritmos clásicos sobre grafos (Dijkstra, Prim, Kruskal y hermanos)
Parte 2:
Discusión y análisis de una selección de algoritmos clásicos de las siguientes áreas:
Geometría computacional,
Procesamiento de strings y bioinformática,
Minería de datos.
Tópicos selectos (por definir, en función de los intereses de los estudiantes)
Evaluación
Tareas, 2 exámenes y un proyecto
Referencias
Introduction to Algorithms, Thomas Cormen et al., MIT Press, 2009
Algorithm Design, Jon Kleinberg y Eva Tardos, Pearson-Addison Wesley, 2006.
Algorithms and Programming, Problems and Solutions, Alexander Shen, Birkhauser, 1997
Especificación, derivación y análisis de Algoritmos, Narciso Marti et al., Pearson 2006.
Probability and Computing: randomized algorithms and probabilistic analysis, Mitzenmacher et al., Cambridge, 2005
Algorithms on strings, trees and sequences, Gusfield, Cambridge, 1997
Liga al curso como fue dado por Claudia Esteves en 2010. Santo Patrón del curso.