Á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.
Programa del curso¶
Notas de clase¶
Las notas de cada sesión se publican aquí, organizadas por corte, a medida que avanza el semestre. Los grupos A y B ven la misma sesión el mismo viernes, así que hay una sola nota por clase. Las del semestre anterior, que cubren los mismos temas, siguen disponibles en Árboles y Grafos 2026-I.
Corte 1¶
- 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
Clases en video¶
Las grabaciones de cada sesión se publican en la lista de reproducción del curso, en orden cronológico (la sesión más reciente queda al final). La lista es común a los grupos A y B y se irá llenando a medida que avanza el semestre.