Matemàtica Discreta i Optimització

Esteu aquí

Inici » Estudis » Graus » Grau en Bioinformàtica » Pla d'estudis » Assignatures » Matemàtica Discreta i Optimització
Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits
Departament
MAT
Web
https://atenea.upc.edu/course/view.php?id=92262
Mail
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

  • Clément Requilé ( )

Altres

  • Richard Coll Josifov ( )
  • Tabriz Arun Avery Popatia ( )

Hores setmanals

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

Resultats d'aprenentatge

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àsica: