Matemàtica Discreta i Optimització

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
MAT
Web
https://atenea.upc.edu/course/view.php?id=100753
Mail
clement.requile@upc.edu
Aquest curs introdueix les estructures matemàtiques discretes, incloent-hi les estructures de dades i els grafs, i les estudia des de les perspectives de la teoria de la probabilitat i de l'optimització. A continuació, se centra en l'optimització en un entorn continua, presentant tècniques fonamentals de la matemàtica numèrica tant per a problemes lineals com no lineals, incloent-hi l'algorisme del Símplex, el mètode de Newton¿Raphson i els mètodes d'optimització basats en gradients.

Professorat

Responsable

  • Clément Requilé (clement.requile@upc.edu)

Altres

  • Richard Coll Josifov (richard.coll@upc.edu)

Hores setmanals

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

Competències

Resultats d'aprenentatge

Coneixements

  • K2 - Identificar els mètodes estadístics i computacionals i els models matemàtics que permeten resoldre problemes en els camps de la biologia molecular, la genòmica, la investigació mèdica i la genètica de poblacions.
  • K3 - Identificar els fonaments matemàtics, les teories informàtiques, els esquemes algorísmics i els principis d'organització de la informació aplicables al modelat de sistemes biològics i a la resolució eficient de problemes bioinformàtics mitjançant el disseny d'eines computacionals.

    • Habilitats

  • S3 - Resoldre problemes en els camps de la biologia molecular, la genòmica, la investigació mèdica i la genètica de poblacions mitjançant l'aplicació de mètodes estadístics i computacionals i models matemàtics.

    • Competències

  • C3 - Comunicar-se de forma oral i escrita amb altres persones, en llengua anglesa, sobre els resultats de l'aprenentatge, de l'elaboració del pensament i de la presa de decisions.
  • C6 - Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per a ampliar aquest coneixement.

    • Objectius

    1. Adquisició dels coneixements bàsics de combinatòria, de programació lineal i d'anàlisi multivariant
      Competències relacionades: C3, C6, K3,
    2. Utilitzar la combinatòria, la programació lineal i l'anàlisi multivariant per a la resolució de problemes matemàtics i aplicar-la a problemes d'optimització discrets, lineals i no lineals, especialment en l'àmbit de la bioinformàtica.
      Competències relacionades: K2, K3, S3,

    Continguts

    1. Combinatòria enumerativa
      Comptatge bàsic. Permutacions, conjunts i paraules. Nombres combinatoris. Aplicacions a probabilitats discretes.
      Recurrències. Resolució de recurrències lineals amb coeficients constants.
    2. Teoria dels grafs i optimització discrete
      Grafs, dígrafs i les seves representacions. Arbres i DAGs (grafs acíclics dirigits).
      Mètodes greedy i optimització.
      El problema de l'arbre generadó mínima. Algorismes de Kruskal i de Prim.
      Flux màxim / tall mínim i l'algorisme de Ford-Fulkerson.
    3. Optimització lineal
      Programació lineal: modelització d'un problema mitjançant un programa lineal.
      El punt de vista geomètric i l'algoritme simplex.
    4. Optimització no lineal
      Record del càlcul multivariant i l'optimització convexa.
      Mètodes iteratius: mètode de Newton i Raphson, descens de gradient.

    Activitats

    Activitat Acte avaluatiu


    Lectures teòriques expositives i sessions de problemes


    Objectius: 1 2
    Continguts:
    Teoria
    30h
    Problemes
    30h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    90h

    Metodologia docent

    El curs es dividirà entre les classes magistrals, que seran de tipus expositiu, i sessions de problemes en grups més reduïts resolts conjuntament, amb un problema típic per resoldre individualment i a casa per a cada part del curs.

    Mètode d'avaluació

    L'assignatura s'avaluarà mitjançant elements d'avaluació obligatoris que consistiran en exàmens individuals, l'examen parcial i l'examen final, i dues proves obligatòries en forma de petits exàmens a classe de taller, amb l'objectiu de fer el seguiment i orientar el procés d¿aprenentatge de l'estudiantat.

    La qualificació final (G) es calcula de la següent manera. Tant la nota de l'examen parcial (P) com la de l'examen final (F) tenen un pes del 45 % de la qualificació final, mentre que la mitjana de les dues proves realitzades a classe (C) té un pes del 10 %. És a dir:

    G = 0,45*P + 0,45*F + 0,1*C.

    Es considera que un estudiant s'ha presentat a l'assignatura si fa l'examen final. En aquest cas, i si G < 5, l'estudiant pot fer l'examen de recuperació (R), i la nove qualificació final (G') esdevé la màxima entre G i 0,9*R + 0,1*C:

    G' = màx ( G, 0,9*R + 0,1*C ).

    En cas que el professorat ho cregui convenient, es podrà fer una prova oral per validar l'autoria de qualsevol de les proves d'avaluació.

    Bibliografia

    Bàsic

    Capacitats prèvies

    Àlgebra lineal.
    Càlcul diferencial i integral d¿una variable i de diverses variables.
    Teoria de les probabilitats discretes.