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=92262
Mail
clement.requile@upc.edu
Aquest curs introdueix l'estudi d'estructures discretes en matemàtiques, com ara estructures de dades o grafs, en els marcs de la teoria de la probabilitat i l'optimització. A continuació, en l'entorn continu, discutim algunes de les principals eines d'optimització utilitzades en matemàtiques numèriques, des del punt de vista de problemes lineals i no lineals.

Professorat

Responsable

Altres

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
      Grafs, dígrafs i les seves representacions. Arbres i DAGs. Exploració de grafs.
    3. Optimització discreta
      El problema del camí més curt. El problema de l'arbre d'expansió mínim. Introducció al problema del viatjant de comerç.
    4. Optimització lineal
      Programació lineal: modelització d'un problema mitjançant un programa lineal.
      El punt de vista geomètric i l'algoritme simplex.
    5. 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 (P) i l'examen final (F), i quatre proves obligatòries en forma de petits exàmens a classe (H) per comprovar i orientar el procés d'aprenentatge dels estudiants. La nota final (G) es calcula de la següent manera. Cadascun dels dos exàmens pondera el 45% de la nota final, i la mitjana dels deures pondera el 10% de la nota final. És a dir:

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

    Es considera que un estudiant ha superat 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 nota final esdevé la màxima entre G i 0,9*R + 0,1*H:

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

    Bibliografia

    Bàsic