Programa de la Asignatura

Revisión de Algoritmos elementales en grafos: Conceptos básicos. Algoritmo de Dijkstra
Árboles abarcadores mínimos: Algoritmo de Kruskal. TAD Conjunto Disjunto. Corrección de los algoritmos de Prim y Kruskal.
Grafos de tareas: Grafos dirigidos acíclicos. Hitos. Holgura. Caminos críticos.
Aplicaciones de Búsqueda en Profundidad: Introducción. Grafos biconexos. Circuitos eulerianos. Circuitos hamiltonianos y el Problema del Viajante
Flujos en grafos: Introducción. Algoritmo de Ford-Fulkerson. Cortes mínimos y flujos máximos. Algoritmo de Edmonds-Karp.
Programación dinámica: El problema de la suma y la criptografía de clave pública. Ordenación óptima en el producto de matrices. Problemas resolubles por programación dinámica. Árboles binarios de búsqueda óptimos. Distancias mínimas sobre todos los vértices en grafos densos (opcional). Búsquedas aproximadas en cadenas (opcional). 2.
Recursividad: El problema de Selección. Problemas resolubles mediante recursividad. Multiplicación de matrices. La Transformada Rápida de Fourier. Distancias mínimas entre conjuntos (opcional).
Algoritmos codiciosos Secuenciación lineal en colas de trabajos. Problemas resolubles mediante algoritmos codiciosos. Codificación Hufman. Algoritmos codiciosos y de programación dinámica.

Última modificación: 15/09/2011 17:28