Matemàtica Discreta i Optimització

Esteu aquí

Inici » 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 analitza les eines d'optimització principals utilitzades en matemàtiques numèriques, des del punt de vista de problemes tant continus com discrets. Això requereix una comprensió profunda dels grafs i problemes combinatoris en el context discret, així com dels problemes lineals i no lineals en el marc continu.

Professorat

Responsable

  • Clément Requilé ( )

Altres

  • Jorge Delgado Rodríguez ( )
  • 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: K3, C3, C6,
  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
    Recompte bàsic. Seleccions, conjunts i paraules. Nombres combinatoris. Recurrencies. Resolució de recurrències lineals amb coeficients constants.
  2. Teoria dels grafs
    Grafs, dígrafs i les seves representacions. Arbres i codis Prüfer. Exploració de grafs amb cerca en amplitud i profunditat.
  3. Optimització discreta
    El problema del arbre d'expansió mínim spanning tree. Els algorismes de Kruskal i Prim. El problema del venedor ambulant.
  4. Optimització lineal
    Programació lineal: modelització d'un problema mitjançant un programa lineal (LP). El punt de vista geomètric i l'algorisme simplex. Dualitat i maneig d'excepcions.
  5. Anàlisi multivariada
    El gradient i el Hessian. Extrem de funcions. Convexitat.
  6. Optimització no lineal
    Optimització convexa. Mètodes iteratius: mètode de Newton i Raphson, descens del 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ó obligatòria que consistiran en exàmens individuals, l'examen parcial (P) i l'examen final (F), i sis proves obligatòries en forma de deures (H) per comprovar i orientar els aprenentatges. procés dels alumnes. La nota final (G) es calcula de la següent manera. Cada un dels dos exàmens pesa el 35% de la nota final, i la mitjana dels deures pesa el 30% de la nota final. Això és:

G = 0,35*P + 0,35*F + 0,3*H.

Es considera que un estudiant ha cursat l'assignatura si fa l'examen final. Si l'estudiant ha cursat l'assignatura però ha suspès, llavors l'estudiant pot fer l'examen d'avaluació (R). En aquest cas, la qualificació de l'examen de reavaluació substituirà tant la qualificació de l'examen parcial com la de l'examen final. Això és:

G* = 0,70*R + 0,3*H.

Bibliografia

Bàsica: