Descripción del Curso
Aplicar técnicas clásicas como algoritmos voraces y programación dinámica para resolver problemas. Resolver problemas de optimización mediante el uso de meta-herísticos. Ajustar los parámetros de los meta-heurísticos para mejorar la calidad de las soluciones encontradas. Hacer uso del lenguaje matemático para especificar y modelar un problema. Modelar una situación como un problema de satisfacción de restricciones y resolverlo. Analizar el desempeño de diferentes técnicas comparando la calidad de las soluciones y el tiempo requerido para encontrarlas.
Información Básica
-
Profesor:
-
Créditos: 4
-
Horas de Clase: 3/semana
-
Horas de trabajo independiente: 9 / semana
-
Prerequisitos: Ninguno
Objetivos
Al finalizar el curso los participantes podrán:
-
Aplicar técnicas clásicas como algoritmos voraces y programación dinámica para resolver problemas.
-
Resolver problemas de optimización mediante el uso de meta-herísticos.
-
Ajustar los parámetros de los meta-herísticos para mejorar la calidad de las soluciones encontradas.
-
Hacer uso del lenguaje matemático para especificar y modelar un problema.
-
Modelar una situación como un problema de satisfacción de restricciones y resolverlo.
-
Analizar el desempeño de diferentes técnicas comparando la calidad de las soluciones y el tiempo requerido para encontrarlas.
Metodología
El curso contará con clases expositivas para explicar las técnicas y métodos de solución. El participante pondrá en práctica dichas técnicas por medio de diferentes tareas y proyectos que se asignarán a lo largo del semestre.
Contenido
| Sesión | Tema | Bibliografía |
|---|---|---|
| 1 | Introducción | [1,2] |
| 2 | Métodos tradicionales | [1,3,4] |
| 2 | Búsqueda exhaustiva | |
| 3 | Búsqueda local | |
| 4 | Algoritmos voraces | |
| 5 | Programación dinámica | |
| 6 | Meta heurísticos | [1,3,9] |
| 7 | Simulated annealing | |
| 8 | Búsqueda Tabu | |
| 8 | Algortimos evolutivos | |
| 11 | Programación por restricciones | [5,6,7,8] |
| 12 | Modelos de restricciones | |
| 12 | Propagación y Distribución | |
| 13 | Branch and bound | |
| 14-15 | Técnicas híbridas |
Evaluación
| Porcentaje | |
|---|---|
| Tareas | 25% |
| Proyecto I | 25% |
| Proyecto II | 25% |
| Proyecto III | 25% |
Bibliografía
-
Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer. 2004.
-
G. Polya. How to Solve It: A New Aspect of Mathematical Method. Princeton Science Library. 1988.
-
Roland Backhouse. Algorithmic Problem Solving. Wiley. 2011.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. The MIT Press. 3rd edition. 2009.
-
Krzystof R. Apt, Principles of Constraint Programming. Cambridge University Press, 2003.
-
Kim Marriott and Peter J. Stuckey, Programming with Constraints. An Introduction. The MIT Press, 1998.
-
Thom Frühwirth and Slim Abdennadher, Essentials of Constraint Programming. Springer-Verlag, 2003.
-
Philippe Baptiste, Claude Le Pape, and Wim Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic Publishers, 2001.
-
Sean Luke. Essentials of Metaheuristics. Lulu. 2011.