Dades generals

Curs acadèmic:
2018
Descripció:
Introducció als problemes d'alta complexitat. Característiques. Exemples: distribució de recursos, planificació i programació de tasques, confecció d'horaris i calendaris. Especificació i modelització. Diferents tècniques de resolució: Programació amb restriccions. Mètodes lògics. SAT. Programació lineal. Mètodes híbrids. SMT, Lazy_fd. Altres propostes. Casos pràctics: Especificació dels problemes. Modelitzacions. Utilització de diferents tècniques
Crèdits:
3

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:
MATEU VILLARET AUSELLE
Idioma de les classes:
Català (100%)

Competències

  • CB02 Aplicar els coneixements adquirits i la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contextos més amplis (o multidisciplinaris) relatius al seu camp d'estudi.
  • CB05 Posseir habilitats d'aprenentatge que permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.
  • CTI07 Capacitat per a comprendre i poder aplicar coneixements avançats de computació d'altes prestacions i mètodes numèrics o computacionals a problemes d'enginyeria.

Continguts

1. Presentació, problemes combinatoris i complexitat.

2. CSPs i Modelització.

          2.1. Timetabling, Scheduling i planning

3. CSP solvers

          3.1. Propagadors

          3.2. Constraints Globals

4. SAT i SMT

          4.1. MiniSat com a exemple de "Conflict-Driven Clause Learning (CDCL) SAT solver

          4.2. Max-SAT

          4.3. PseudoBooleans i Cardinality Constraints

          4.4. Theory Solvers

5. Programació lineal entera

          5.1. Simplex

          5.2. Cutting Planes

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Total
Anàlisi / estudi de casos 8 16 24
Classes participatives 22 26 48
Total 30 42 72

Bibliografia

  • Biere, A., Heule, M., Van Maaren, H., Walsh, T. (2009). Handbook of Satisfiability. IOS Press.
  • Rossi, Francesca, 1962- Van Beek, Peter Walsh, Toby (cop. 2006 ). Handbook of constraint programming . Amsterdam: Elsevier. Catàleg
  • Rossi, Francesca, 1962- (2006 ). Handbook of constraint programming. Amsterdam: Elsevier. Recuperat 15-07-2015, a http://www.sciencedirect.com/science/book/9780444527264 Catàleg

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Classes presencials Tema 1 10
Classes presencials Tema 2 10
Classes presencials Tema 3 10
Classes presencials Tema 4 10
Classes presencials Tema 5 10
Realizació i presentació de treballs pràctics 50

Qualificació

Es valorarà el seguiment de l'assignatura amb exercicis proposats a classe. (Si algun dia no es pot assistir a classe, s'acordaran mètodes alternatius). (50%)

L'altra 50% correspondrà a la realizació de treballs pràctics proposats i temes a exposar a classe.

Criteris específics de la nota «No Presentat»:
No presentar els treballs proposats.

Observacions

Cal tenir ganes d'afrontar reptes i d'aprendre.