Técnicas para el diseño de soluciones computacionales

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

  1. Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer. 2004.
  2. G. Polya. How to Solve It: A New Aspect of Mathematical Method. Princeton Science Library. 1988.
  3. Roland Backhouse. Algorithmic Problem Solving. Wiley. 2011.
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. The MIT Press. 3rd edition. 2009.
  5. Krzystof R. Apt, Principles of Constraint Programming. Cambridge University Press, 2003.
  6. Kim Marriott and Peter J. Stuckey, Programming with Constraints. An Introduction. The MIT Press, 1998.
  7. Thom Frühwirth and Slim Abdennadher, Essentials of Constraint Programming. Springer-Verlag, 2003.
  8. Philippe Baptiste, Claude Le Pape, and Wim Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic Publishers, 2001.
  9. Sean Luke. Essentials of Metaheuristics. Lulu. 2011.
 
materias/tecnicassoluciones.txt · Última modificación: 2016/03/08 21:00 por juancmartinez
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki