Resolució de Problemes Combinatoris

Esteu aquí

Inici » Estudis » Màsters » Màster en Innovació i Recerca en Informàtica » Pla d'estudis » Assignatures » Resolució de Problemes Combinatoris
Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
Web
http://www.cs.upc.edu/~erodri/cps.html
Mail
Un problema combinatori consisteix en, donada una col·lecció finita d'objectes i un conjunt de restriccions, trobar un objecte de la col·lecció que satisfà totes les restriccions (i possiblement que optimitzi una funció objectiu). Els problemes combinatoris són omnipresents i tenen una gran importància pràctica. En aquest curs estudiarem tres paradigmes generals diferents per resoldre problemes combinatoris: programació lineal, satisfactibilitat proposicional i programació amb restriccions. Per a cadascun d'ells, n'estudiarem els fonaments algorítmics, així com les tècniques de modelització.

Pla d'estudis del curs (resum).
Exemples de problemes combinatoris. Paradigmes generals: programació lineal entera, SAT i extensions, programació amb restriccions. Tècniques de modelització i llenguatges.

Professorat

Responsable

  • Enric Rodriguez Carbonell ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
6.4

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.
  • CEE3.3 - Capacitat per entendre les necessitats computacionals de problemes de disciplines diferents de la informàtica i efectuar contribucions significatives en equips multidisciplinaris que facin servir la computació.

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.

Competències Transversals

Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.

Objectius

  1. Modelar problemes derivats de la informàtica i altres disciplines en els paradigmes de resolució que es consideren en el curs: programació amb restriccions, programació lineal entera, satisfactibilitat proposicional.
    Competències relacionades: CB6, CTR6, CEE3.3, CG1, CG3,
  2. Familiaritzar-se amb les eines de l'estat de l'art dels paradigmes de resolució considerats al curs: programació amb restriccions, programació lineal entera, satisfactibilitat proposicional.
    Competències relacionades: CTR6, CEE3.2, CG3,
  3. Comprendre els fonaments algorísmics de cadascun dels paradigmes de resolució considerats en el curs: programació amb restriccions, programació lineal entera, satisfactibilitat proposicional.
    Competències relacionades: CEE3.2,

Continguts

  1. Problemes Combinatoris.
    Definició informal. Problemes NP-complets vs. problemes de temps polinòmic. Alguns exemples i aplicacions: satisfactibilitat proposicional, coloració de grafs, motxilla, empaquetament de contenidors, etc. Enfocaments per a la resolució de problemes.
  2. Programació amb Restriccions.
    Definicions bàsiques. Problemes de satisfacció de restriccions. Exemples. Consistència local: consistència d'arc, consistència d'arc direccional, consistència de límits. Propagació de restriccions per a restriccions globals: all different. Algorismes de cerca: retrocés bàsic, verificació anticipada, cerca parcial / completa. Heurístiques d'ordre de variable i de valor. Problemes d'optimizació de restriccions. Modelat i resolució de problemes amb CP.
  3. Programació Lineal.
    Revisió de programació lineal: l'algorisme del símplex. Dualitat i símplex dual. Modelatge i resolució de problemes amb programació lineal. Programació lineal entera mixta. Branch & bound, plans de tall, branch & cut. Matrius totalment unimodulars. Algorisme del símplex per a xarxes. Modelatge i resolució de problemes amb programació lineal entera mixta.
  4. Resolució de SAT i extensions.
    Lògica proposicional. El problema de la satisfactibilitat (SAT). Algorisme DPLL. Resolució. Resolvedors de SAT amb aprenentatge de clàusules guiat per conflictes. Modelatge i resolució de problemes amb SAT: restriccions de cardinalitat, restriccions pseudo-booleanes. Satisfactibilitat mòdul teories.

Activitats

Activitat Acte avaluatiu


Introducció als Problemes Combinatoris

Introducció als Problemes Combinatoris
Objectius: 1 2 3
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Programació amb Restriccions

Modelatge i resolució amb programació amb restriccions
  • Aprenentatge autònom: Review of the material given in theory sessions. Resolution of exercises.
Objectius: 1 2 3
Continguts:
Teoria
8h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
12.8h

Programació Lineal

Modelatge i resolució amb programació lineal
  • Teoria: Understanding of the materials given in theory sessions.
  • Laboratori: Resolution of the practical exercises of each laboratory session.
  • Aprenentatge autònom: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
Objectius: 1 2 3
Continguts:
Teoria
10h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
20.6h

SAT i Extensions

Modelatge i resolució amb SAT i extensions
  • Teoria: Understanding of the materials given in theory sessions.
  • Laboratori: Resolution of the practical exercises of each laboratory session.
  • Aprenentatge autònom: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
Objectius: 1 2 3
Continguts:
Teoria
8h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
12.8h

Examen Final

L'examen cobreix els temes de modelatge i resolució amb programació amb restriccions, programació lineal i satisfactibilitat proposicional.
Objectius: 1 2 3
Setmana: 16
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
19.8h

Treball Pràctic de Programació amb Restriccions

El projecte consisteix en el modelatge i resolució d'un problema combinatori amb programació amb restriccions
Objectius: 1 2 3
Setmana: 8
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Treball Pràctic de Programació Lineal

El projecte consisteix en el modelatge i resolució d'un problema combinatori amb programació lineal
Objectius: 1 2 3
Setmana: 12
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Treball Pràctic de SAT

El projecte consisteix en el modelatge i resolució d'un problema combinatori amb SAT
Objectius: 1 2 3
Setmana: 16
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Metodologia docent

La principal característica de la metodologia docent és l'ús de
materials accessibles a través de la web, dissenyats específicament per
a un curs d'autoaprenentatge. Aquests materials permeten reformular
l'ensenyament de manera que el tradicional model de classes
desapareix en gran mesura.

Així:

1. Considera la classe com a base de treball, que l'estudiant ha de
continuar i aprofundir pel seu propi compte.

2. Es basa en materials d'alta qualitat (diapositives, llistes de
problemes, problemes resolts, exemples de treballs pràctics de
laboratori, software LP / SAT / CP, referències bibliogràfiques).

3. Pretén motivar els estudiants, amb exemples, debats, comentaris,
etc ... Les intuïcions darrere de les definicions, propietats i Les
tècniques es discuteixen en grup.

El laboratori fomentarà el treball independent dels estudiants. El
paper del professor serà principalment per ajudar i avaluar els
estudiants, que haurien de treballar majorment de forma autònoma.

Mètode d'avaluació

El 50% de la nota final correspon a teoria. Aquesta nota s'obtindrà mitjançant un examen escrit al final del curs.

L'altre 50% de la nota final correspon a laboratori. Aquesta nota s'obtindrà com la mitjana de tres projectes successius (un per CP, un altre per LP, i encara un altre per SAT) que els estudiants hauran hagut d'entregar.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Coneixements bàsics del sistema operatiu Linux i del llenguatge de programació C++.
Coneixements bàsics d'àlgebra lineal, algorismes de grafs i lògica.