Árboles y Grafos¶
Curso de Árboles y Grafos de la Pontificia Universidad Javeriana Cali, semestre 2026-II, grupos A y B. Los dos grupos llevan el mismo cronograma y el mismo material.
El curso arranca con las herramientas para razonar sobre eficiencia (orden asintótico, propiedades de la función O e invariantes de ciclo) y con ellas analiza las primeras técnicas de diseño: dividir y conquistar, búsqueda binaria y bisección. La parte central es de grafos: representaciones, recorridos DFS y BFS con sus propiedades formales, orden topológico, conectividad, componentes fuertemente conexos, puntos de articulación y puentes, y los algoritmos clásicos de caminos más cortos (Bellman-Ford, Dijkstra y Floyd-Warshall). El cierre es sobre árboles y las estructuras que se construyen encima: diámetro, radio y centro, árboles de segmentos, Union-Find, árboles de cubrimiento mínimo, árboles de Fenwick y arreglos de sufijos. Se programa en Python y el texto guía es CLRS.
Las sesiones de refuerzo de algoritmia y lógica repasan en dieciséis horas los arreglos, las estructuras con su costo, la búsqueda binaria y la lógica que el curso da por vista, con problemas de juez y sus soluciones en Python y C++.
Programa del curso¶
Notas de clase¶
Las notas de cada sesión se publican aquí, organizadas por corte, a medida que avanza el semestre. Hay una nota por sesión y sirve para los dos grupos. Las de las semanas en que los grupos estuvieron en puntos distintos del tema traen las dos rutas, y ahí conviene entrar por la del grupo propio. Las del semestre anterior, que cubren los mismos temas, siguen disponibles en Árboles y Grafos 2026-I.
Corte 1¶
Complejidad, invariantes de ciclo, dividir y conquistar, búsqueda binaria y bisección.
- Clase 1. Repaso de estructuras de datos y notación asintótica — 31 de julio
- Clase 2. Invariantes de ciclo y divide y vencerás — 21 de agosto
- Clase 3. Búsqueda binaria y bisección — 28 de agosto
- Clase 4. Invariantes: acumuladores, listas y ciclos anidados — 4 de septiembre
Corte 2¶
Grafos: representaciones, recorridos, orden topológico, conectividad, cortes y caminos más cortos.
- Clase 5. Introducción a grafos — semana del 7 de septiembre
- Clase 6. Representaciones de grafos y recorridos — 11 de septiembre
- Clase 7. Grafos implícitos — 18 de septiembre
- Clase 8. Orden topológico — semana del 21 de septiembre
- Clase 9. Conectividad — 25 de septiembre
- Clase 10. Orden topológico con la profundidad y el valor low — 2 de octubre
- Clase 11. Problemas de cortes — 9 de octubre
- Clase 12. Caminos más cortos: generalidades y la idea de Bellman-Ford-Moore — 16 de octubre
- Clase 13. Implementaciones de Bellman-Ford-Moore y grafos de estado — 16 de octubre
- Clase 14. Grafos de estado, 23 de octubre
- Clase 15. Caminos más cortos en DAG y Dijkstra, 23 de octubre
Material de apoyo del corte, que no corresponde a una sesión:
Corte 3¶
Árboles y las estructuras que se construyen sobre ellos.
- Clase 16. Generalidades de los árboles, 30 de octubre
- Clase 17. El centro de un árbol, 6 de noviembre
- Clase 18. Árboles de cubrimiento mínimo, 13 de noviembre
Clases en video¶
Las grabaciones de cada sesión están en la lista de reproducción del curso, ordenada por clase: la sesión más reciente queda al final y la lista se va llenando a medida que avanza el semestre. Es una sola lista para los grupos A y B, y cada sesión se parte en varios videos cortos, para volver a un tema puntual sin recorrer la clase entera. El reproductor de abajo va sobre la lista completa; la barra que lo encabeza la abre en YouTube, en una pestaña nueva.