Diferencia entre revisiones de «CSP»

De OpenDataLab
Saltar a: navegación, buscar
(RESUMEN)
Línea 9: Línea 9:
  
 
== RESUMEN ==
 
== RESUMEN ==
 
Resumen
 
 
En nuestro día a día tratamos de resolver diferentes actividades que presentan ciertas condiciones.
 
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 especificaciones 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.  
+
La tarea de generar un horario para la universidad consta de una serie de especificaciones que se han de cumplir. Se pensará 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 conflicto o necesitar de otras restricciones previas.  
+
 
 +
A esto lo conoceremos como restricciones, que pueden entrar en conflicto o necesitar de otras restricciones previas. Como puede pasar durante la generación del horario, existen diferentes alternativas que pueden llevar a satisfacer más a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la óptima. Este problema lo podemos resolver fácilmente mediante la programación de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimización.
 +
 
 +
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, planificaciones, diagnósticos, 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ón de restricciones (Constraint Satisfaction Problems
 +
- CSP), donde en primer lugar realizaríamos un modelado del problema para después pasar a su resolución usando técnicas CSP.
 +
 
 +
En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resolución.
  
Como puede pasar durante la generación del horario, existen diferentes alternativas que pueden
+
"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)
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:23 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

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 especificaciones que se han de cumplir. Se pensará 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 conflicto o necesitar de otras restricciones previas. Como puede pasar durante la generación del horario, existen diferentes alternativas que pueden llevar a satisfacer más a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la óptima. Este problema lo podemos resolver fácilmente mediante la programación de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimización.

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, planificaciones, diagnósticos, 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ón de restricciones (Constraint Satisfaction Problems - CSP), donde en primer lugar realizaríamos un modelado del problema para después pasar a su resolución usando técnicas CSP.

En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resolución.

"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)