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

Professors

Responsable

  • Enric Rodriguez Carbonell ( )

Altres

  • Luis Domingo Velasco Esteban ( )

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
    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
Teoria
11.5h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

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
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

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

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.