Resolució de Problemes i Programació amb Restriccions

Esteu aquí

Inici » Estudis » Màsters » Màster en Intel·ligència Artificial » Pla d'estudis » Assignatures » Resolució de Problemes i Programació amb Restriccions
Crèdits
4.5
Tipus
Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
Els problemes d'optimització discreta apareixen en un gran nombre de dominis que van des de l'enginyeria, la logística, la bioinformàtica, el raonament probabilístic, l'assignació de recursos, la programació, etc.

En aquest curs aprendrem a identificar, modelar i resoldre aquest tipus de problemes. Utilitzarem el famós enfocament declaratiu en què l'usuari modela el problema amb un llenguatge genèric i després utilitza una biblioteca genèrica de tècniques de resolució.

Per a aquest curs utilitzarem el llenguatge de modelització MiniZinc i presentarem tres paradigmes de resolució que es poden utilitzar amb ell: Satisfacció booleana, Programació de restriccions i Programació lineal enter. Per a cadascun d'ells tractarem el seu poder expressiu i les principals intuïcions darrere de les seves tècniques de resolució.

L'orientació del curs és essencialment pràctica. Aprendrem principalment a través d'exemples, tot i que també s'hi inclouran algunes idees teòriques.

Professorat

Responsable

  • Francisco Javier Larrosa Bondia ( )

Hores setmanals

Teoria
1
Problemes
1
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
5.65

Competències

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per a projectar, dissenyar i implantar productes, processos, serveis i instal·lacions en tots els àmbits de la Intel·ligència Artificial.

Competències Tècniques de cada especialitat

Acadèmiques

  • CEA1 - Capacitat de comprendre els principis bàsics de funcionament de les tècniques principals dels Sistemes Multiagents, i saber utilitzar-les en l'entorn d'un sistema o servei intel·ligent.
  • CEA13 - Capacitat de comprendre les tècniques avançades de Modelització, Raonament i Resolució de problemes, i saber dissenyar, implementar i aplicar aquestes tècniques en el desenvolupament d'aplicacions, serveis o sistemes intel·ligents.

Competències Transversals

Raonament

  • CT6 - Capacitat d'avaluar i analitzar de manera raonada i crítica sobre situacions, projectes, propostes, informes i estudis de caracter cientific-tecnic. Capacitat d'argumentar les raons que expliquen o justifiquen aquestes situacions, propostes, etc.

Objectius

  1. Capacitat per modelar de manera òptima un problema d'optimització discreta i resoldre'l utilitzant les eines mes adients.
    Competències relacionades: CEA1, CEA13, CG1, CT6,
    Subcompetences:
    • Traduir un problema d'optimització de la vida real en una especificació ben definida amb un lleguatge formal
    • Satisfactibilitat Booleana per resoldre problemes d'optimització discreta
    • Cerca Local
    • Programació Lineal Entera
    • Programació amb Restriccions

Continguts

  1. Modelat de problemes combinatoris
  2. Resolució amb Programació amb restriccions
  3. Resolució amb tècniques de Lògica Proposicional (SAT)
    .
  4. Resolució amb programació lineal entera
    .

Activitats

Activitat Acte avaluatiu


Modeling


Objectius: 1
Teoria
0h
Problemes
10h
Laboratori
13h
Aprenentatge dirigit
0h
Aprenentatge autònom
50h

Constraint Programming


Objectius: 1
Teoria
4h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Satisfactibilitat Booleana



Teoria
5h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Programació Lineal Entera



Teoria
4h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Metodologia docent

Per la part de modelatge es farà servir el sistema de "flipped classroom" on els estudiants hauràn de veure videos i fer petits projectes. Les hores lectives es faràn servir per resoldre dubtes i consolidar coneixements.

Per la part de tècniques de resolució es farà servir la metodologia clàssica de classe magistral i alguna classe de problemes.

Mètode d'avaluació

Al llarg del curs s'aniran fent petits projectes (al voltant de 6) amb un pes conjunt del 30% de la nota final. També es farà un quizz al començament del curs, un examen parcial i un examen final amb un pes total al voltant del 70% de la nota

Bibliografia

Bàsica:

Capacitats prèvies

Algorismia bàsica