5.23.5.1 Algoritmos de Grafos y Optimización Combinatoria (20 horas)

Resultados de la carrera Outcomes: AG-Ci09,AG-Ci11

Temas

1. Representación de grafos y recorrido (BFS, DFS)
2. Algoritmos de camino más corto (Dijkstra, Bellman-Ford)
3. Árboles de expansión mínima (Prim, Kruskal)
4. Flujo en redes y emparejamiento
5. NP-completitud y algoritmos de aproximación

Objetivos de Aprendizaje (Learning Outcomes)

1. Implementar algoritmos de recorrido de grafos [Usar (Usage)]
2. Resolver problemas de camino más corto usando algoritmos apropiados [Usar (Usage)]
3. Construir árboles de expansión mínima [Usar (Usage)]
4. Analizar complejidad de algoritmos de grafos [Evaluar (Assessment)]
5. Diseñar algoritmos de aproximación para problemas NP-difíciles [Usar (Usage)]

Bibliografía: [Bondy and Murty, 2008,West, 2001]