Solución de problemas con ccp

 

Código:

Profesor: Camilo Rueda

Créditos: 4

Lista de Correo del Curso:

Prerequisitos: Buen conocimiento de algún lenguaje de programación, lógica

Horario: Viernes, 5-8 PM

Objetivos

General

Estudiar los fundamentos del paradigma de programación por restricciones y aplicar el paradigma en la solución de problemas combinatorios.

Específicos

  • Estudiar las restricciones en programación como técnica para la solución de problemas combinatorios.
  • Estudiar el uso de las restricciones en programación como modelo formal de computación.
  • Construir una aplicación para resolver un problema de optimización usando las técnicas estudiadas.

Contenido

Tema Sesión Referencias Transparencias Notas de clase y ejemplos
Indroducción 25/07/2008 [ 1] cap. 1, [ 2] un ejemplo simple programa
Conceptos generales 01/08/2008 [ 1] cap. 2 conceptos ejemplos1 y 2 en gecode ejemplo2.oz
Modelar con restricciones 08/08/2008 [ 1] cap. 2 modelos cuadrado Mágico reinas tienda
Propagación: definiciones 15/08/2008 [ 1] cap. 3,4 CSP:especificar,implementar
Propagadores: propiedades 22/08/2008 [ 1] cap. 4,5 3] propagar: formalismo Ejercicios empaque en java azulejo
Búsqueda: propiedades 22/08/2008 [ 1] cap. 4,5 3] definiciones y propiedades domino(parcial)
dominio y límite consistencia 22/10/2008 [ 1] cap. 4,5 3] Implementar “element” y “distinct”
Propagar restricciones de canal 11/11/2008 [ 1] cap. 4,5 3] canal y planeamiento
Restricciones sobre conjuntos finitos 20/11/2008 [ 1] cap. 4,5 3] propagación de restricciones sobre conjuntos
Problemas de satisfacción de restricciones 21/11/2008 [ 1] cap. 4,5 3] arco consistencia

Evaluaciones

El curso supone trabajo adicional de 9 horas semanales
  • Trabajos sustentados : 60%
  • Presentacione orales : 30%
  • tareas : 10%

Software

– Gecode: http://www.gecode.org/

– Gecode/J: http://www.gecode.org/gecodej/

– Mozart: http://www.mozart-oz.org

Bibliografía

  1. Krzysztof R. Apt. Principles of constraint programming. 1st edition. Cambridge University Press. 2003.
  2. Kim Marriott and Peter Stuckey. Programming with constraints : an introduction. MIT Press. 1998.
  3. Peter Van Roy and Seif Haridi. Concepts, Techniques, and Models of Computer Programming. Edición Javeriana. 2005.
  4. Introducción:
    1. Smith conceptos generales
    2. Barták, WDS99 ideas básicas
  5. Propagación:
    1. Mecanismos: Schulte, Stuckey, TOPLAS 2008 procedimientos de propagación
    2. optimizar propagación. Schulte, Stuckey, ACM SIGPLAN 2008 eliminar variables