Esta versión de la guía docente es provisional hasta que no finalize el periodo de edición de las guías del nuevo curso.

Logo UAB

Optimización

Código: 42250 Créditos ECTS: 6
2024/2025
Titulación Tipo Curso
4313136 Modelización para la Ciencia y la Ingeniería / Modelling for Science and Engineering OB 0

Contacto

Nombre:
Albert Ruiz Cirera
Correo electrónico:
albert.ruiz@uab.cat

Equipo docente

Albert Ruiz Cirera
Judit Chamorro Servent

Idiomas de los grupos

Puede consultar esta información al final del documento.


Prerrequisitos

  • Conocimiento de matemáticas a nivel de un grado en ciencias o ingeniería.

  • Saber programar.


Objetivos y contextualización

El curso está dedicado a estudiar y practicar varios algoritmos de optimización heurística y combinatoria con especial énfasis en enrutamiento y optimización convexa. El curso también tratará otros temas de optimización.
Este curso pretende dar al alumnado el conocimiento necesario y las herramientas básicas para crear algoritmos con la finalidad de resolver problemas de la vida real.

Competencias

  • "Aplicar el pensamiento lógico/matemático: el proceso analítico a partir de principios generales para llegar a casos particulares; y el sintético, para a partir de diversos ejemplos extraer una regla general."
  • Analizar, sintetizar, organizar y planificar proyectos de su campo de estudio.
  • Aplicar la metodología de investigación, técnicas y recursos específicos para investigar en un determinado ámbito de especialización.
  • Aplicar las técnicas de resolución de los modelos matemáticos y sus problemas reales de implementación.
  • Comunicar en lengua inglesa los resultados de los trabajos del ámbito de estudio.
  • Concebir y diseñar soluciones eficientes, aplicando técnicas computacionales, que permitan resolver modelos matemáticos de sistemas complejos.
  • Extraer de un problema complejo la dificultad principal, separada de otras cuestiones de índole menor.
  • Formular, analizar y validar modelos matemáticos de problemas prácticos de distintos campos.
  • Usar métodos numéricos apropiados para solucionar problemas específicos.

Resultados de aprendizaje

  1. "Aplicar el pensamiento lógico/matemático: el proceso analítico a partir de principios generales para llegar a casos particulares; y el sintético, para a partir de diversos ejemplos extraer una regla general."
  2. Analizar, sintetizar, organizar y planificar proyectos de su campo de estudio.
  3. Aplicar técnicas de optimización para estudiar modelos asociados a problemas prácticos.
  4. Aplicar la metodología de investigación, técnicas y recursos específicos para investigar en un determinado ámbito de especialización.
  5. Comunicar en lengua inglesa los resultados de los trabajos del ámbito de estudio.
  6. Extraer de un problema complejo la dificultad principal, separada de otras cuestiones de índole menor.
  7. Identificar problemas que requieran aplicar técnicas de optimización para construir modelos asociados a problemas prácticos.
  8. Implementar las soluciones propuestas de forma fiable y eficiente.
  9. Implementar los algoritmos que constan en el programa
  10. Usar softwares específicos para la resolución de problemas de optimización.

Contenido

Contenidos principales:
  • Algoritmos combinatorios para grafos y enrutamientos: algoritmos Dijkstra y A *. Optimitzación sobre grafos.
  • Optimitzación determinista (problemas con y sin restricciones).
Posibles tópicos addicionales:
  • Algoritmos genéticos.
  • Simulated annealing.
  • Algoritmos de colonias de hormigas.
  • Otros.

Actividades formativas y Metodología

Título Horas ECTS Resultados de aprendizaje
Tipo: Dirigidas      
Asistir a las clases y actividades relacionadas 37,75 1,51 1, 2, 4, 3, 5, 6, 7, 9, 8, 10
Evaluación del profesorado y de la asignatura 0,25 0,01
Tipo: Autónomas      
Tareas (implementación de los algoritmos – actividad individual y en grupo) 42 1,68 1, 2, 4, 3, 6, 7

La metodología consiste en clases teóricas (presentaciones con transparencias y pizarra), y sesiones prácticas.

Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.


Evaluación

Actividades de evaluación continuada

Título Peso Horas ECTS Resultados de aprendizaje
Entrega y exposición del trabajo final (grupos de 4) 30% 21 0,84 1, 2, 4, 3, 5, 6, 7, 9, 8, 10
Proyectos de casos realistas de forma individual 30% 21 0,84 1, 2, 4, 3, 5, 6, 7, 9, 8, 10
Proyectos en casos realistas en grupos de 2 (excepcionalmente 3) 40% 28 1,12 1, 2, 4, 3, 5, 6, 7, 9, 8, 10

Hay tres tipos de evaluación:
  • Trabajos individuales: informe resumido y código solucionando el problema planteado.
  • Trabajos en grupos de dos: informe resumido y código solucionando el problema planteado.
  • Trabajo en grupos de cuatro: informe, (puede incluir código) y presentación oral.

Bibliografía

  • Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for industrial and applied mathematics. 
  • Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization. CMS Books in Mathematics. Springer, New York, NY.
  • Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
  • Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
  • Hansen, P. C. (2010). Discrete inverse problems: insight and algorithms. Society for Industrial and Applied Mathematics.
  • S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598,  671-680.
  • Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
  • Nocedal, J., & Wright, S. J. (2006). Quadratic programming. Numerical optimization, 448-492.
  • Nocedal, J., & Wright, S. J. (2006). Sequential Quadratic Programming. Numerical Optimization, 529-562.
  • Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
  • William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes in C. The Art of Scientific Computing (second edition), Cambridge University Press.
  • Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Numerical Mathematics, Texts in Applied Mathematics 37, Springer, 1991.

Software

Sofware recomendado:

  • C
  • MATLAB

Lista de idiomas

Nombre Grupo Idioma Semestre Turno
(TEm) Teoría (máster) 1 Inglés primer cuatrimestre tarde