Métodos Algorítmicos para Modelos Matemáticos

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
DAC;CS
La tarea de construir modelos matemáticos que representen problemas del mundo real y usar herramientas para solucionar estos modelos es una tarea ubicua a la informática. Tener conocimientos sobre estas herramientas y algoritmos permite sopesar el equilibrio entre cómo de precisa es la formalización del problema y cómo de tratable es el modelo resultante.

Este curso revisará algunos de estos modelos y algoritmos matemáticos, poniendo especial énfasis en su aplicación en problemas concretos de la informática. Primero, revisaremos los contenidos básicos de programación lineal y no lineal. Más tarde, los algoritmos metaheurísticos serán presentados como alternativa a los métodos vistos previamente para los problemas de optimización combinatoria.

Profesorado

Responsable

Otros

Horas semanales

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

Competencias

Competencias Técnicas de cada especialidad

Computer networks and distributed systems

  • CEE2.1 - Capacidad para entender los modelos, problemas y algoritmos relacionados con los sistemas distribuidos, así como poder diseñar y evaluar algoritmos y sistemas que traten la problemática de la distribución y ofrezcan servicios distribuidos

    • Advanced computing

  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Transversales

    Trabajo en equipo

  • CTR3 - Ser capaz de trabajar como miembro de un equipo, ya sea como un miembro más, o realizando tareas de dirección con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.

    • Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Objetivos

    1. Modelar en varios formalismos matemáticos los problemas que surjan en las distintas disciplinas de la informática.
      Competencias relacionadas: CG1, CG3, CEE2.1, CTR3, CTR6,
    2. Familiarizarse con las herramientas actuales para solucionar varios modelos matemáticos.
      Competencias relacionadas: CG3, CEE2.1, CEE3.2, CTR3, CTR6,
    3. Entender los conceptos básicos de los algoritmos usados para resolver varios modelos matemáticos.
      Competencias relacionadas: CEE2.1, CEE3.2,

    Contenidos

    1. Programación lineal
      Conceptos básicos de programación lineal. Ejemplos de modelaje. El algoritmo simplex. Dualidad.
    2. Programación lineal entera
      Ejemplos de modelaje. Branch-and-bound, cuts y branch-and-cut.
    3. Programación no lineal
      Conceptos básicos de programación no lineal. Ejemplos de modelaje.
    4. Metaheurísticas
      Procedimientos constructivos. Búsqueda local. Metaheurísticas: GRASP, Simulated Annealing, Tabu Search, algoritmos genéticos, Ant Colony, Path Relinking, etc.

    Actividades

    Actividad Acto evaluativo


    Programación lineal


    Objetivos: 1 3
    Contenidos:
    Teoría
    12h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    11h

    Programación lineal entera


    Objetivos: 1 3
    Contenidos:
    Teoría
    8h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Laboratorio de programación lineal


    Objetivos: 2
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    9h

    Programación no lineal


    Objetivos: 1 3
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    3h

    Metaheurísticos


    Objetivos: 1 3
    Contenidos:
    Teoría
    16h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Laboratorio de metaheurísticos


    Objetivos: 2
    Contenidos:
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    6h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    9h

    Proyecto


    Objetivos: 1 2
    Semana: 16
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen


    Objetivos: 1 2 3
    Semana: 18
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    Ya que el objetivo del curso es proveer a los alumnos con la experiencia necesaria para usar distintos formalismos y herramientas para solucionar problemas concretos, la metodología docente tendrá esto en cuenta. Las clases de teoría siempre usarán ejemplos motivadores. En estas sesiones, los estudiantes tendrán que resolver ejercicios simples que serán los ingredientes básicos de los algoritmos más complicados.

    En las sesiones de laboratorio los estudiantes se familiarizarán con herramientas para la resolución de problemas computacionalmente.

    Durante el desarrollo del proyecto los estudiantes tendrán la supervisión de los profesores.

    Método de evaluación

    La nota final del curso tendrá en cuenta:

    A) Un trabajo práctico (proyecto): 40%

    B) Un examen final: 60%

    Bibliografía

    Básico

    Complementario

    Capacidades previas

    Los estudiantes deben estar familiarizados con los conceptos básicos de álgebra lineal: vector, matriz, rango, matriz inversa y resolución de sistemas de ecuaciones lineales.