Saltar a contenido

Á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

Programa y cronograma (PDF)

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.

Corte 2

Grafos: representaciones, recorridos, orden topológico, conectividad, cortes y caminos más cortos.

Material de apoyo del corte, que no corresponde a una sesión:

Corte 3

Árboles y las estructuras que se construyen sobre ellos.

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.