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
erodri@cs.upc.edu
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

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
    0h

    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
    0h

    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
    0h

    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
    0h

    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àsic

    Complementari

    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.