Solución de Problemas con CCP

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

Sesión Tema Descripción
1 Introducción Presentación del profesor, objetivos, contenido, metodología y formas de evaluación del curso. Conceptos fundamentales de la programación por restricciones. Aplicaciones de la programación por restricciones. Mozart: Lenguaje para la Propgramación por Restricciones
2 Problemas de Satisfacción de Restricciones. Problemas de Satisfacción de Restricciones en los enteros, reales y booleanos.
3 Mozart: Lenguaje para la Programación por Restricciones Modelo Declarativo. Técnicas declarativas. Concurrencia
6 La Programación por Restricciones: Teoría y práctica Equivalencia de los CSPs. La estructura básica de la programación con restricciones. Algoritmos de propagación de restricciones. Programación por restricciones en Mozart: Ejemplos básicos de propagación y distribución Eliminación de simetrías Restricciones redundadntes.
10 Taller práctico
11 Presentación de una Aplicación Modelo del problema, implementación del modelo, implementación de estrategias de distribución, arquitectura de una apliación CCP.
12 Completitud de algunos Solvers de Restricciones Marcos de pruebas teóricas. Derivaciones. Problemas de unificación.
13 Consistencia Local Nodo consistencia. Arco Consistencia. k-consistencia.
14 Incompletitud de algunos Solvers de Restricciones Igualdad y desigualdad de restricciones. Reglas de transformación. Reglas de reducción de dominios.
15 Algoritmos de Propagación de Restricciones Algoritmos de iteracciones genéricos. Algoritmos para un orden parcial arbitrario. Algoritmos de nodo consistencia.
16 Búsqueda. Árbol de búsqueda. Árbol de etiquetado. Completitud de los árboles de etiquetado.

Evaluación

  • Parcial: 40 %
  • Proyecto: 40 %
  • Talleres, Tareas, Quices: 20 %

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.

Material Adicional

Software

Diapositivas

 
materias/restricciones.txt · Última modificación: 2013/06/08 02:20 por caolarte
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki