Resolución de Problemas y Programación con Restricciones

Usted está aquí

Inicio » Estudios » Grados » Grado en Inteligencia Artificial » Plan de estudios » Asignaturas » Resolución de Problemas y Programación con Restricciones
Créditos
4.5
Tipos
Optativa
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
Los problemas de optimización discreta aparecen en una gran cantidad de dominios que van desde ingeniería, logística, bioinformática, razonamiento probabilístico, asignación de recursos, programación, etc.

En este curso aprenderemos a identificar, modelar y resolver este tipo de problemas. Usaremos el famoso enfoque declarativo en el que el usuario modela el problema con un lenguaje genérico y luego usa una biblioteca genérica de técnicas de resolución.

Para este curso usaremos el lenguaje de modelado MiniZinc y presentaremos tres paradigmas de resolución que se pueden usar con él: satisfacibilidad booleana, programación de restricciones y programación lineal entera. De cada uno cubriremos su poder expresivo y las principales intuiciones detrás de sus técnicas de resolución.

La orientación del curso es esencialmente práctica. Aprenderemos principalmente a través de ejemplos, aunque también se incluirán algunas ideas teóricas.

Profesorado

Responsable

  • Francisco Javier Larrosa Bondia ( )

Horas semanales

Teoría
1
Problemas
1
Laboratorio
1
Aprendizaje dirigido
0
Aprendizaje autónomo
5.65

Competencias

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para proyectar, diseñar e implantar productos, procesos, servicios e instalaciones en todos los ámbitos de la Inteligencia Artificial.

Competencias Técnicas de cada especialidad

Académicas

  • CEA1 - Capacidad de comprender los principios básicos de funcionamiento de las técnicas principales de los Sistemas Multiagentes, y saber utilizarlas en el entorno de un sistema o servicio inteligente.
  • CEA13 - Capacidad de comprender las técnicas avanzadas de Modelización, Razonamiento y Resolución de problemas, y saber diseñar, implementar y aplicar estas técnicas en el desarrollo de aplicaciones, servicios o sistemas inteligentes.

Competencias Transversales

Razonamiento

  • CT6 - Capacidad de evaluar y analizar de manera razonada y critica sobre situaciones, proyectos, propuestas, informes y estudios de caracter cientifico-tecnico. Capacidad de argumentar las razones que explican o justifican tales situaciones, propuestas, etc.

Objetivos

  1. Capacidad para modelar problemas de optimización discreta y resolverlos con las herramientas más apropiadas
    Competencias relacionadas: CEA1, CEA13, CG1, CT6,
    Subcompetences:
    • Traducir un problema de optimización real a una especificación bien definida con un lenguaje formal
    • Satisfactibilidad Booleana para resolver problemas de optimización discreta
    • Búsqueda Local
    • Programación Lineal Entera
    • Programación con restricciones

Contenidos

  1. Modelado de problemas combinatorios
  2. Resolucion con programacion con restricciones
  3. Resolución con técnicas de Lógica Proposicional (SAT)
    .
  4. Resolución con programación lineal entera
    .

Actividades

Actividad Acto evaluativo


Modelado


Objetivos: 1
Teoría
0h
Problemas
10h
Laboratorio
13h
Aprendizaje dirigido
0h
Aprendizaje autónomo
50h

Programacion con restricciones


Objetivos: 1
Teoría
4h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Satisfactibilitat Booleana



Teoría
5h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Programación Lineal Entera



Teoría
4h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Metodología docente

Para la parte de modelado se utilizará el sistema de "flipped classroom" donde los estudiantes tendrán que ver videos y realizar pequeños proyectos. Las horas lectivas se utilizarán para resolver dudas y consolidar conocimientos.

Por la parte de técnicas de resolución se utilizará la metodología clásica de clase magistral y alguna clase de problemas.

Método de evaluación

A lo largo del curso se irán realizando pequeños proyectos (alrededor de 6) con un peso conjunto del 30% de la nota final. También se hará un quizz al inicio del curso, un examen parcial y un examen final con un peso total en torno al 70% de la nota

Bibliografía

Básica:

Capacidades previas

Algorítmica básica