Diferencia entre revisiones de «CSP»
| 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)
