Métodos Algorítmicos para Modelos Matemáticos

Usted está aquí

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

  • Enric Rodriguez Carbonell ( )

Otros

  • Luis Domingo Velasco Esteban ( )

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: CTR3, CTR6, CEE2.1, CG1, CG3,
  2. Familiarizarse con las herramientas actuales para solucionar varios modelos matemáticos.
    Competencias relacionadas: CTR3, CTR6, CEE2.1, CEE3.2, CG3,
  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
3h
Aprendizaje autónomo
24h

Examen


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

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

Complementaria:

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.