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
Modelling in various mathematical formalisms the problems arising in different computer science disciplines
Competències relacionades:
CTR3,
CTR6,
CEE2.1,
CG1,
CG3,
Becoming familiar with state-of-the-art tools used to solve various mathematical models
Competències relacionades:
CTR3,
CTR6,
CEE2.1,
CEE3.2,
CG3,
Understanding the basics of the algorithms used for solving various mathematical models
Competències relacionades:
CEE2.1,
CEE3.2,
Continguts
Programació lineal
Conceptes bàsics de programació lineal. Exemples de modelatge. L'algorisme del símplex. Dualitat.
Programació lineal entera
Exemples de modelatge. Branch-and-bound, cuts i branch-and-cut.
Programació no lineal
Conceptes bàsics de programació no lineal. Exemples de modelatge.
Metaheurístiques
Procediments constructius. Cerca local. Metaheurístiques: GRASP, Simulated Annealing, Tabu Search, algorismes genètics, Ant Colony, Path Relinking, etc.
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.
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.