Mètodes Algorísmics per a Models Matemàtics

Esteu aquí

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
La tasca de construir models matemàtics que representin problemes del món real i fer servir eines per solucionar aquests models és una tasca ubiqua a la informàtica. Tenir coneixements sobre aquestes eines i algorismes permet sospesar l'equilibri entre com de precisa és la formalització del problema i com de tractable és el model resultant.

Aquest curs revisarà alguns d'aquests models i algorismes matemàtics, posant especial èmfasi en la seva aplicació en problemes concrets de la informàtica. Primer, revisarem continguts bàsics de programació lineal i no lineal. Més tard, els algoritmes metaheurístics seran presentats com a alternativa als mètodes vistos prèviament per als problemes d'optimització combinatòria. Altres elements matemàtics amb un gran impacte en la informàtica, com els grafs o la computació i ús de valors propis / vectors, també seran coberts durant el curs.

Professors

Responsable

  • Albert Oliveras Llunell ( )

Altres

  • Luis Domingo Velasco Esteban ( )
  • Marc Ruiz Ramírez ( )

Hores setmanals

Teoria
3
Problemes
0
Laboratori
0.9
Aprenentatge dirigit
0.1
Aprenentatge autònom
4

Competències

Competències Tècniques de cada especialitat

Xarxes de computadors i sistemes distribuïts

  • CEE2.1 - Capacitat per a entendre els models, problemes i algoritmes relacionats amb els sistemes distribuïts, així com poder dissenyar i avaluar algoritmes i sistemes que tractin la problemàtica de la distribució i ofereixin serveis distribuïts.

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.

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

Treball en equip

  • CTR3 - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.

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ó.

Objectius

  1. Modelling in various mathematical formalisms the problems arising in different computer science disciplines
    Related competences: CG1, CG3, CEE2.1, CTR3, CTR6,
  2. Becoming familiar with state-of-the-art tools used to solve various mathematical models
    Related competences: CG3, CEE2.1, CEE3.2, CTR3, CTR6,
  3. Understanding the basics of the algorithms used for solving various mathematical models
    Related competences: CEE2.1, CEE3.2,

Continguts

  1. Valors i vectors propis
    Conceptes bàsics d'àlgebra lineal. Valors i vectors propis i la seva interpretació. Aplicacions a la informàtica (clustering, representació de grafs, anàlisi de components principals, page rank, ...)
  2. Programació lineal i programació lineal entera
    Conceptes bàsics de programació lineal. Exemple de modelatge. L'algorisme del símplex. Dualitat. Programació entera: branch-and-bound, cuts i branch-and-cut.
  3. Programació no-lineal
    Convexitat. Programació separable. Optimitzación en una dimensió. Algorisme Frank-Wolfe.
  4. Problemes i Algorismes sobre grafs
    Camí més curt. Algorisme max-flow min-cut. Arbres d'expansió mínims.
  5. Metaheurístiques
    Procediments constructius. Cerca local. Meta-heurístiques: GRASP, Simulated Annealing, Tabu Search, algorismes genètics, Ant colony, Path Relinking, etc.

Activitats

Activitat Acte avaluatiu


Vectors i valors propis


Objectius: 1 3
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Programació lineal (entera)


Objectius: 1 3
Continguts:
Teoria
13h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
9h

Laboratori de Programació Lineal


Objectius: 2
Continguts:
Teoria
0h
Problemes
0h
Laboratori
7h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Programació no-lineal


Objectius: 1 3
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Problemes i Algorismes sobre Grafs


Objectius: 1 3
Continguts:
Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Metaheurístiques


Objectius: 1 3
Continguts:
Teoria
14h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
9h

Laboratori de Metaheurístiques


Objectius: 2
Continguts:
Teoria
0h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Projecte


Objectius: 1 2
Setmana: 16
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
1h
Aprenentatge autònom
16h

Examen


Objectius: 1 2 3
Setmana: 18
Tipus: examen final
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Metodologia docent

Ja que l'objectiu del curs és proveir als alumnes amb l'experiència necessària per utilitzar diferents formalismes i eines per solucionar problemes concrets, la metodologia docent tindrà això en compte. Les classes de teoria sempre faran servir exemples motivadors provinents d'aplicacions informàtiques, posant especial interès en els aspectes pràctics. En aquestes sessions, els estudiants hauran de resoldre exercicis simples que seran els ingredients bàsics dels algoritmes més complicats.

A les sessions de laboratori els estudiants es familiaritzaran amb els sistemes que seran usats en el projecte. Durant el desenvolupament del projecte els estudiants tindran la supervisió dels professors.

Mètode d'avaluació


La nota final del curs tindrà en compte:

A) Treball pràctic: els estudiants, en grups petits, desenvoluparan un projecte. Els professors suggeriran una varietat de projectes perquè totes les especialitats estiguin representades. L'objectiu del projecte serà solucionar un problema concret utilitzant tècniques de programació (no) lineal i metaheurística. L'avaluació serà de la següent manera:

* Tècniques de programació (no) lineal (20%)
* Metaheurística (20%)

B) Exàmens:

* Un examen final (60%)

Bibliografia

Bàsica:

Complementaria:

  • Model building in mathematical programming - Williams, H. P, Wiley & Sons , 1999. ISBN: 0471997889
    http://cataleg.upc.edu/record=b1358490~S1*cat
  • How to solve it : modern heuristics - Michalewicz, Zbigniew; Fogel, David B, Springer , cop. 2004. ISBN: 3540224947
    http://cataleg.upc.edu/record=b1295094~S1*cat
  • Elementary Linear Algebra. - Larson, R; Falvo, D.C, Houghton Mifflin Harcourt , 2009.
  • Applied Mathematical Programming - Bradley, S.P; Hax, A.C; Magnanti, T.L., Addison-Wesley , 1977.

Capacitats prèvies

Els estudiants han d'estar familiaritzats amb els conceptes bàsics d'àlgebra lineal: vector, matriu, rang, matriu inversa i resolució de sistemes d'equacions lineals.