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

Altres

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: CTR3, CTR6, CEE2.1, CG1, CG3,
    2. Becoming familiar with state-of-the-art tools used to solve various mathematical models
      Competències relacionades: CTR3, CTR6, CEE2.1, CEE3.2, CG3,
    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
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen


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

    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àsic

    Complementari

    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.