Matemática Discreta y Optimización

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
MAT
Web
https://atenea.upc.edu/course/view.php?id=100753
Mail
clement.requile@upc.edu
Esta asignatura introduce las estructuras matemáticas discretas, incluidas las estructuras de datos y los grafos, y las estudia desde las perspectivas de la teoría de la probabilidad y la optimización. A continuación, se centra en la optimización en un entorno continuo, presentando técnicas fundamentales de la matemática numérica tanto para problemas lineales como no lineales, como el algoritmo del Símplex, el método de Newton¿Raphson y los métodos de optimización basados en gradientes.

Profesorado

Responsable

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

Otros

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

Horas semanales

Teoría
2
Problemas
2
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Resultados de aprendizaje

Conocimientos

  • K2 - Identificar los métodos estadísticos y computacionales y los modelos matemáticos que permiten resolver problemas en los campos de la biología molecular, la genómica, la investigación médica y la genética de poblaciones.
  • K3 - Identificar los fundamentos matemáticos, las teorías informáticas, los esquemas algorítmicos y los principios de organización de la información aplicables al modelado de sistemas biológicos y a la resolución eficiente de problemas bioinformáticos mediante el diseño de herramientas computacionales.

    • Habilidades

  • S3 - Resolver problemas en los campos de la biología molecular, la genómica, la investigación médica y la genética de poblaciones mediante la aplicación de métodos estadísticos y computacionales y modelos matemáticos.

    • Competencias

  • C3 - Comunicarse de forma oral y escrita con otras personas, en lengua inglesa, sobre los resultados del aprendizaje, de la elaboración del pensamiento y de la toma de decisiones.
  • C6 - Detectar deficiencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento.

    • Objetivos

    1. Adquisición de los conocimientos básicos de combinatoria, de programación lineal y de análisis multivariado
      Competencias relacionadas: K3, C3, C6,
    2. Utilizar la combinatoria, la programación lineal y el análisis multivariante para la resolución de problemas matemáticos y aplicarlos a problemas de optimización discretos, lineales y no lineales, especialmente en el campo de la bioinformática.
      Competencias relacionadas: K2, K3, S3,

    Contenidos

    1. Combinatoria enumerativa
      Conteo básico. Permutaciones, conjuntos y palabras. Números combinatorios. Aplicaciones a probabilidades discretas.
      Recurrencias. Resolución de recurrencias lineales con coeficientes constantes.
    2. Teoría de grafos i optimización discreta
      Grafos, dígrafos y sus representaciones. Árboles y DAGs (grafos acíclicos dirigidos).
      Mètodes greedy i optimización.
      El problema del árbol generador mínima. Algoritmos de Kruskal y de Prim.
      Flujo máximo / corte mínimo y el algoritmo de Ford-Fulkerson.
    3. Optimización lineal
      Programación lineal: modelado de un problema mediante un programa lineal.
      El punto de vista geométrico y el algoritmo símplex.
    4. Optimización no lineal
      Recordatorio de cálculo multivariante y optimización convexa.
      Métodos iterativos: método de Newton y Raphson, descenso de gradiente.

    Actividades

    Actividad Acto evaluativo


    Lecturas teóricas expositivas y sesiones de problemas.


    Objetivos: 1 2
    Contenidos:
    Teoría
    30h
    Problemas
    30h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    90h

    Metodología docente

    El curso se dividirá entre clases expositivas, que serán de tipo expositivo, y sesiones de problemas en grupos reducidos resueltos entre todos, con un problema típico a resolver individualmente y en casa para cada parte del curso.

    Método de evaluación

    La asignatura se evaluará mediante pruebas obligatorias, que consistirán en exámenes individuales, el examen parcial y el examen final, además de dos pruebas obligatorias en formato de pequeños exámenes presenciales realizados en clase, con el objetivo de realizar el seguimiento y orientar el proceso de aprendizaje del estudiantado.

    La calificación final (G) se calcula de la siguiente manera. Tanto la nota del examen parcial (P) como la del examen final (F) tienen un peso del 45 % de la calificación final, mientras que la media de las dos pruebas realizadas en clase (C) tiene un peso del 10 %. Es decir:

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

    Se considera que un alumno ha cursado la asignatura si se presenta al examen final. En ese caso, y si G < 5, puede presentarse al examen de recuperación (R), y la nueva calificación final (G') será la máxima entre G y 0,9*R + 0,1*C:

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

    En caso de que el profesorado lo considere conveniente, se podrá realizar una prueba oral para validar la autoría de cualquiera de las pruebas de evaluación.

    Bibliografía

    Básico

    Capacidades previas

    Álgebra lineal.
    Cálculo diferencial e integral univariable y multivariable.
    Teoría de las probabilidades discretas.