Diferencia entre revisiones de «CSP»

De OpenDataLab
Saltar a: navegación, buscar
Línea 6: Línea 6:
 
Autor: Álvaro Martín Boza
 
Autor: Álvaro Martín Boza
 
Tutor: Gonzalo A. Aranda Corral
 
Tutor: Gonzalo A. Aranda Corral
 +
 +
 +
== RESUMEN ==
 +
 +
Resumen
 +
En nuestro día a día tratamos de resolver diferentes actividades que presentan ciertas condiciones.
 +
La tarea de generar un horario para la universidad consta de una serie de especi�-
 +
caciones que se han de cumplir. Se pensar�a en distintos aspectos como que, por ejemplo, un
 +
mismo profesor no puede estar presente en dos aulas a la vez. A esto lo conoceremos como
 +
restricciones, que pueden entrar en con
 +
icto o necesitar de otras restricciones previas. Como
 +
puede pasar durante la generaci�on del horario, existen diferentes alternativas que pueden
 +
llevar a satisfacer m�as a unas restricciones que a otras, por ello es importante tener un buen
 +
rango de opciones que nos permita encontrar la �optima.
 +
Este problema lo podemos resolver f�acilmente mediante la programaci�on de restricciones
 +
(PR), la cual permite describir y solucionar problemas combinatorios y de optimizaci�on. La
 +
idea principal es resolver un problema sujeto a unas restricciones en el dominio del problema
 +
y encontrar distintas soluciones que satisfagan todas las restricciones y optimicen el
 +
resultado. Podemos encontrar aplicaciones de esta metodolog��a en distintos campos donde se
 +
realicen tomas de decisiones, plani�caciones, diagn�osticos, problemas de empaquetamiento,
 +
criptograf��as, razonamiento temporal, etc. Estos problemas suelen tener una complejidad
 +
bastante alta, normalmente de tipo NP [1]. Sin embargo, esto no impide que los podamos
 +
llevar a cabo como problemas de satisfacci�on de restricciones (Constraint Satisfaction Problems
 +
- CSP), donde en primer lugar realizar��amos un modelado del problema para despu�es
 +
pasar a su resoluci�on usando t�ecnicas CSP.
 +
En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo,
 +
desde su planteamiento hasta su resoluci�on.
 +
"Constraint Programming represents one of the closest approaches computer
 +
science has yet made to the Holy Grail of programming: the user states the
 +
problem, the computer solves it" (E. Freuder)

Revisión de 13:15 29 abr 2019

TRABAJO FIN DE GRADO Grado en Ingeniería Informática

Sistemas de Restricciones: Fundamentos y Aplicaciones.

Autor: Álvaro Martín Boza Tutor: Gonzalo A. Aranda Corral


RESUMEN

Resumen En nuestro día a día tratamos de resolver diferentes actividades que presentan ciertas condiciones. La tarea de generar un horario para la universidad consta de una serie de especi�- caciones que se han de cumplir. Se pensar�a en distintos aspectos como que, por ejemplo, un mismo profesor no puede estar presente en dos aulas a la vez. A esto lo conoceremos como restricciones, que pueden entrar en con icto o necesitar de otras restricciones previas. Como puede pasar durante la generaci�on del horario, existen diferentes alternativas que pueden llevar a satisfacer m�as a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la �optima. Este problema lo podemos resolver f�acilmente mediante la programaci�on de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimizaci�on. La idea principal es resolver un problema sujeto a unas restricciones en el dominio del problema y encontrar distintas soluciones que satisfagan todas las restricciones y optimicen el resultado. Podemos encontrar aplicaciones de esta metodolog��a en distintos campos donde se realicen tomas de decisiones, plani�caciones, diagn�osticos, problemas de empaquetamiento, criptograf��as, razonamiento temporal, etc. Estos problemas suelen tener una complejidad bastante alta, normalmente de tipo NP [1]. Sin embargo, esto no impide que los podamos llevar a cabo como problemas de satisfacci�on de restricciones (Constraint Satisfaction Problems - CSP), donde en primer lugar realizar��amos un modelado del problema para despu�es pasar a su resoluci�on usando t�ecnicas CSP. En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resoluci�on. "Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it" (E. Freuder)