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.
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.
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.
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 | |
| Porcentaje |
Tareas | 25% |
Proyecto I | 25% |
Proyecto II | 25% |
Proyecto III | 25% |
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.