Resolució de Problemes Combinatoris

Esteu aquí

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
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.

Professors

Responsable

  • Enric Rodriguez Carbonell ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
1
Aprenentatge dirigit
0.6
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
2.2h
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
2.2h
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
2.2h
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
2.2h
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
Tipus: examen final
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
19h

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
Tipus: entrega
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
Tipus: entrega
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
Tipus: entrega
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.

Addenda

Continguts

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Metodologia docent

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Mètode d'avaluació

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Pla de contingència

En cas que no es pugui dur a terme la docència de forma presencial, les classes (de teoria i laboratori) s'impartiran de forma remota mitjançant Google Meet; els continguts, la metodologia docent i el mètode d'avaluació continuaran igual. In the circumstance where teaching cannot be carried out in person, the classes (theory and laboratory) will be taught remotely by means of Google Meet; the contents, the teaching methodology and the evaluation method will not change. En caso de que no se pueda llevar a cabo la docencia de forma presencial, las clases (de teoría y laboratorio) se impartirán de forma remota mediante Google Meet; los contenidos, la metodología docente y el método de evaluación continuarán igual.