Este curso es una introducción a algunos paradigmas avanzados para el diseño de algoritmos de búsqueda y optimización: búsqueda en grafos, programación dinámica (tanto exacta como aproximada), branch-and-bound y algunos métodos heurísticos de optimización global (por ejemplo algoritmos genéticos).

En el curso aprenderán en qué situaciones se aplican estos paradigmas así como algunos problemas importantes que pueden resolverse usándolos (encontrar caminos más cortos, topological sort, Knapsack, algunos problemas de logística y planeación, el problema del agente viajero, alineación de secuencias de ADN, etc.). También tendrán la oportunidad de trabajar con sus compañeros en un proyecto longitudinal para explorar alguno de estos algoritmos, así como su implementación y aplicación.

Textos: La referencia principal del curso seran las notas del instructor. Estas se basarán en los siguientes libros de referencia (altamente recomendados y complementarios entre si):

• [R2] Roughgarden Tim: Algorithms Illuminated Part 2: Graph Algorithms and Data Structures, Soundlikeyourself Publishing, LLC (2019).
• [R3] Roughgarden Tim: Algorithms Illuminated Part 3: Greedy Algorithms and Dynamic Programming, Soundlikeyourself Publishing, LLC (2019).
• [BaB] Notes on Branch-and-Bound (del curso ee364b en Stanford) [link]
• [PM] Poole David y Mackworth Alan: Artificial Intelligence: Foundations of Computational Agents, 2nd Edition, Cambridge University Press (2017). [link]
• [L] Lee Jon: A First Course in Combinatorial Optimization, Cambridge University Press (2004)

Metodología y Evaluación:

La mayor parte de lo que aprenderán en este curso será el resultado de su propio trabajo en tres aspectos de igual importancia: Reflexión posterior a cada clase sobre los resultados discutidos en ella, trabajo en los talleres Prácticos asignados clase a clase y un Proyecto longitudinal.

Los criterios de evaluación del curso son:

• El 45% de la nota será determinado por talleres prácticos clase a clase a ser realizados en grupos de a lo más tres estudiantes (ver fechas de entrega de los prácticos abajo, marcados con la letra [P]) y Quizzes individuales a ser realizados en clase (ver fechas abajo, marcadas con la letra [Q]). Todos los quizzes y prácticos tienen una participación igual en el 45% y la nota de cada taller práctico será la misma para todos los participantes de cada grupo.
• El 55% restante de la nota será determinado por un Proyecto Longitudinal en grupos (evaluado en tres entregas de 5%, 25% y 25% respectivamente a realizarse en las fechas de abajo). El proyecto deberá hacerse siguiendo las reglas descritas en este [link]

• Hay un 5% adicional (optativo) para todo estudiante que entregue al menos el 50% de sus prácticos en LaTex. LaTex es el lenguaje de la comunicación científica asi que vale la pena aprenderlo. Pueden encontrar un tutorial breve en este [link] ó en este [otro link].

• La nota final se decidirá calculando el promedio aritmético de las notas de los dos párrafos anteriores, redondeando al entero más cercano y convirtiéndolo a la escala oficial: S: 96-100 MB: 91-95, BMB: 83-90, B: 75-82, R: 41-74, D: 0-40.

Instructor:

• Mauricio Velasco (mauricio.velasco@ucu.edu.uy)