CI2613: Algoritmos y Estructuras de Datos III (Pregrado)

Blai Bonet
Matemáticas y Sistemas, 215-A
Departamento de Computación
Universidad Simón Bolívar

bonet AT ldc DOT usb DOT ve
Tel: +58 (212) 906-3263
Web: http://www.ldc.usb.ve/~bonet (http://bonetblai.github.io)

Sinopsis

Tercer curso de la cadena de algoritmos y estructuras de datos. Se enfoca en algoritmos y estructuras de datos para grafos. Se cubren los temas de representación de grafos; búsqueda en amplitud y profundidad; árbol cobertor mínimo, algoritmos de Kruskal y de Prim; caminos de costo mínimo, algoritmos de Bellman-Ford, de Dijkstra, de Floyd-Warshall, y de Johnson; flujo en redes, algoritmos de Ford-Fulkerson y de Edmonds-Karp. También se estudian estructuras de datos para conjuntos disjuntos, heaps binomiales y Fibonacci, y nociones de análisis amortizado. En resumen, se estudian los capítulos 17, 19, 21 — 26 del libro de texto.

Evaluación

Examen 1 (50%) el 22/01/2015 sobre lo visto hasta el 15/01/2015 (inclusivo).
Examen 2 (50%) el 12/03/2015 sobre lo visto hasta el 05/03/2015 (inclusivo).

Objetivos y Cronograma

Semana	Día I (Martes 3-4 en AUL-020)	Día II (Jueves 3-4 en AUL-020)
I	9/12: Introducción. Notación asintótica. Complejidad en tiempo y espacio. Algoritmos eficientes.	11/12: Conceptos básicos y representación de grafos. Atributos. [§22.1 + apéndice + otros]
II	16/12: Análisis amortizado. [§17]	18/12: ED para cola de prioridad: heap binomial y Fibonacci. [§19 + otros]
III	6/1: Búsqueda en amplitud (BFS). [§22.2]	8/1: Búsqueda en profundidad (DFS). Ordenamiento topológico. [§22.3 + §22.4]
IV	13/1: Componentes fuertemente conectadas. [§22.5]	15/1: ED para conjuntos disjuntos. Componentes conexas. [§21]
V	20/1: Repaso para el examen.	22/1: Examen 1 (50%)
VI	27/1: No hay clases	29/1: No hay clases
VII	3/2: Árbol cobertor mínimo (MST). Algoritmos de Kruskal y de Prim. [§23]	5/2: Caminos de costo mínimo desde un vértice fuente fijo (SS/SP). [§24.0 + §24.5]
VIII	10/2: Algoritmo de Bellman-Ford. SS/SP en grafos dirigidos acíclicos (DAGs). PERT. [§24.1 + §24.2]	12/2: Algoritmo de Dijkstra. [§24.3]
IX	17/2: Feriado	19/2: Aplicaciones: clustering, arbitraje, sistemas de diferencias, y alineación de secuencias. [§24.4 + otros]
X	24/2: Caminos de costo mínimo para todos los pares de vértices (AP/SP). Programación dinámica y multiplicación de matrices. Algoritmo de Floyd-Warshall. Algoritmo de Johnson para grafos dispersos. [§25]	26/2: Redes y flujos. Problema de flujo máximo. Método de Ford-Fulkerson. Redes y capacidades residuales. Aumento de flujo. [§26.1 + §26.2]
XI	3/3: Caminos de aumento. Cortes y cortes mínimos. Teorema de flujo máximo — corte mínimo. Algoritmo básico de Ford-Fulkerson. Patologías de Ford-Fulkerson. [§26.2]	5/3: Algoritmo de Edmonds-Karp. Aplicaciones. [§26.2 + otros]
XII	10/3: Repaso para el examen.	12/3: Examen 2 (50%)

Bibliografía

T. H. Cormen, C. E. Leiserson, R. L. Rivest y C. Stein. Introduction to Algorithms. MIT Press. (3ra edición)
(Consulta) O. Meza y M. Ortega. Grafos y Algoritmos. Equinoccio. Universidad Simón Bolívar.
Clases: grafos, representación, análisis amortizado, heaps, bfs, dfs, ordenamiento topológico, scc, union/find, mst, ss-sp, Bellman-Ford, ss-sp-dags, Dijkstra, aplicaciones, ap-sp, Johnson, flujo, matching.

Last Modified 05 Mar 2015