Departamentos

Matemáticas

Grado y Doble Grado. Curso 2024/2025.

OPTIMIZACIÓN EN REDES - 800705

Curso Académico 2024-25

Datos Generales

SINOPSIS

COMPETENCIAS

Generales
- Desarrollar la capacidad de identificar y describir matemáticamente un problema de optimización que puede representarse sobre un Grafo o Red.
- Resolver problemas de Optimización en Redes, mediante técnicas algorítmicas adecuadas.
- Comunicar, tanto por escrito como de forma oral, conocimientos, procedimientos y resultados.
Específicas
Aunque en el módulo se desarrollan todas las competencias del grado (a excepción de la competencia específica 5), se especifican los siguientes resultados del aprendizaje indicando entre paréntesis la competencia o competencias con las que tienen una relación más directa.
Reconocer adecuadamente diversas situaciones como problemas de redes y discriminar el modelo adecuado. (CG1, CG3, CG4)
Conocer algoritmos apropiados para la resolución de problemas de redes. (CG3)
Implementar algoritmos para la resolución computacional de problemas en redes. (CE5)
Saber aplicar métodos heurísticos a problemas de optimización combinatoria que sean complejos. (CG3, CE1)

ACTIVIDADES DOCENTES

Clases teóricas
Si
Seminarios
No
Clases prácticas
Si

Presenciales

2,4

No presenciales

3,6

Semestre

6

Breve descriptor:

Estudio de problemas de Optimización que pueden modelizarse sobre un grafo o una red. Introducción a la Teoría de Grafos. Problemas de árboles soporte y arborescencias de mínimo peso. Problema del camino más corto. Problemas de flujos. Problemas de emparejamiento, recubrimiento y recorridos. Problema de coloración.

Requisitos

No hay

Objetivos

El alumno debe ser capaz de:
  • Identificar problemas de optimización que pueden modelizarse mediante grafos y redes y resolverlos con algoritmos adecuados.
  • Comprender los métodos matemáticos utilizados y las condiciones de aplicabilidad de los algoritmos desarrollados.

Contenido

  1. Grafos. Propiedades. Representación de grafos.
  2. Problemas de árboles y arborescencias de peso mínimo.
  3. Problemas de camino mínimo.
  4. Problemas de flujo.
  5. Problemas de emparejamiento y recubrimiento.
  6. Recorridos en grafos. Problema del Viajante. Problema del Cartero Chino. Problemas de Rutas.Complejidad algorítmica, heurísticas para el Problema del viajante.
  7. Problemas de coloración de grafos. Heurística.

Evaluación

Examen teórico-práctico: 80%
Entrega de problemas y trabajos: 20%


Observación
Para aprobar hay que obtener al menos 4 puntos (sobre 8) en el examen y un total de 5 puntos o más.

Bibliografía

BERGE, C. (1976). Graphs and Hypergraphs. North-Holland.
COOK, W.J., CUNNINGHAM, W.H., PULLEYBLANK, W.R., SCHRIJVER, A. (1998). Combinatorial Optimization. John Wiley.
GIBBONS, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
GROSS, J., YELLEN, J. (1999). Graph Theory and its Applications. CRC Press.
JUNGNICKEL, D. (2005). Graphs, Networks and Algorithms. Springer.
KORTE, B., VYGEN, J. (2006). ¿Combinatorial Optimization. Theory and Algorithms. Springer.

Otra información relevante

Se proporcionarán apuntes sobre los temas tratados.

La enseñanza de la asignatura es presencial.

Estructura

MódulosMaterias
No existen datos de módulos o materias para esta asignatura.

Grupos

Clases teóricas
GrupoPeriodosHorariosAulaProfesor
Grupo único20/01/2025 - 09/05/2025LUNES 13:00 - 14:00B03ELISENDA MOLINA FERRAGUT
MIÉRCOLES 13:00 - 14:00B03ELISENDA MOLINA FERRAGUT


Clases prácticas
GrupoPeriodosHorariosAulaProfesor
Grupo único20/01/2025 - 09/05/2025MARTES 13:00 - 14:00B03ELISENDA MOLINA FERRAGUT
JUEVES 13:00 - 14:00B03ELISENDA MOLINA FERRAGUT