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

Esteu aquí

Inici » Estudis » Màsters » Màster en Innovació i Recerca en Informàtica » Pla d'estudis » Assignatures » Mètodes Algorísmics per a Models Matemàtics
Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
DAC;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. 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.

Professorat

Responsable

  • Enric Rodriguez Carbonell ( )

Altres

  • Luis Domingo Velasco Esteban ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
7.12

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
    Competències relacionades: CG1, CG3, CEE2.1, CTR3, CTR6,
  2. Becoming familiar with state-of-the-art tools used to solve various mathematical models
    Competències relacionades: CG3, CEE2.1, CEE3.2, CTR3, CTR6,
  3. Understanding the basics of the algorithms used for solving various mathematical models
    Competències relacionades: CEE2.1, CEE3.2,

Continguts

  1. Programació lineal
    Conceptes bàsics de programació lineal. Exemples de modelatge. L'algorisme del símplex. Dualitat.
  2. Programació lineal entera
    Exemples de modelatge. Branch-and-bound, cuts i branch-and-cut.
  3. Programació no lineal
    Conceptes bàsics de programació no lineal. Exemples de modelatge.
  4. Metaheurístiques
    Procediments constructius. Cerca local. Metaheurístiques: GRASP, Simulated Annealing, Tabu Search, algorismes genètics, Ant Colony, Path Relinking, etc.

Activitats

Activitat Acte avaluatiu


Programació lineal


Objectius: 1 3
Continguts:
Teoria
12h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
11h

Programació lineal entera


Objectius: 1 3
Continguts:
Teoria
8h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

Laboratori de Programació Lineal


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

Programació no lineal


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

Metaheurístiques


Objectius: 1 3
Continguts:
Teoria
16h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

Laboratori de Metaheurístiques


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

Projecte


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

Examen


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

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. 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 eines per resoldre problemes computacionalment.

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) Un treball pràctic (projecte): 40%

B) Un examen final: 60%

Bibliografia

Bàsica:

Complementaria:

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.