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 lo básico 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. Otros elementos matemáticos con un gran impacto en la informática, como los grafos o la computación y uso de valores propios/vectores, también serán cubiertos durante el curso.

Profesores

Responsable

  • Antoni Lozano Boixadors ( )

Otros

  • Albert Atserias Peri ( )
  • Enric Rodriguez Carbonell ( )
  • Luis Domingo Velasco Esteban ( )

Horas semanales

Teoría
3
Problemas
0
Laboratorio
0.9
Aprendizaje dirigido
0.1
Aprendizaje autónomo
4

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. Valores propios y vectores propios
    Conceptos básicos del álgebra lineal. Valores propios, vectores propios y su interpretación. Aplicaciones en la informática (clustering, representación de grafos, análisis de componentes principales, page rank, ...)
  2. Programación lineal (entera)
    Conceptos básicos de programación lineal. Ejemplos de modelaje. El algoritmo simplex. Dualidad. Programación entera: branch-and-bound, cuts y branch-and-cut.
  3. Programación no lineal
    Convexidad. Programación separable. Optimización de una dimensión. Algoritmo Frank-Wolfe.
  4. Grafos: Problemas y algoritmos
    Camino más corto. Algoritmo max-flow min-cut. Minimum spanning trees.
  5. Metaheurística
    Procedimientos constructivos. Búsqueda local. Metaheurísticos: GRASP, Simulated Annealing, Tabu Search, algoritmos genéticos, Ant colony, Path Relinking, etc.

Actividades

Actividad Acto evaluativo


Valores y vectores propios


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

Programación lineal (entera)


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

Laboratorio de programación lineal


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

Programación no lineal


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

Grafos: Problemas y Algoritmos


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

Metaheurísticos


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

Laboratorio de metaheurísticos


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

Proyecto


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

Examen


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

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 provenientes de aplicaciones informáticas, poniendo especial interés en los aspectos prácticos. 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 los sistemas que serán usados en el proyecto. 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) Trabajo práctico: los estudiantes, en grupos pequeños, desarrollarán un proyecto. Los profesores sugerirán una variedad de proyectos para que todas las especialidades estén representadas. El objetivo del proyecto será solucionar un problema concreto usando técnicas de programación (no) lineal y metaheurística. La evaluación será de la siguiente forma:

* Técnicas de programación (no) lineal (20%)
* Metaheurística (20%)

B) Exámenes:

* 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.