Logo UAB
2022/2023

Optimización

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

Contacto

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

Uso de idiomas

Lengua vehicular mayoritaria:
inglés (eng)

Equipo docente

Albert Ruiz Cirera
Judit Chamorro Servent

Prerequisitos

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

  • 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 a los estudiantes 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 Dijstra 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.

Metodología

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.

Actividades

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

Evaluación

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, código y presentación oral.

Actividades de evaluación

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, 6, 7, 9, 8, 10
Proyectos de casos realistas de forma individual 40% 28 1,12 1, 2, 4, 3, 6, 7, 9, 8, 10
Proyectos en casos realistas en grupos de dos alumnos (excepcionalmente tres) 30% 21 0,84 1, 2, 4, 3, 5, 6, 7, 9, 8, 10

Bibliografía

  • David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
  • Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
  • 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.
  • 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