Algoritmos y Estructuras de Datos III
Información General sobre la Cursada
Algoritmos III consiste de clases de laboratorio, teóricas y prácticas. Para aprobar la materia se deben rendir 2 exámenes parciales y 3 trabajos prácticos, y se puede promocionar si tanto en las notas de los parciales como en las de los TPS se obtiene 7 de promedio.
Programa
1. Algoritmos Definición de algoritmo. Modelos de computación: modelo RAM, Máquina de Turing. Complejidad, definición, complejidad en el peor caso, en el caso promedio. Algoritmos de tiempo polinomial y no polinomial. Límite inferior. Ejemplo: análisis de algoritmos de ordenamiento. Algoritmos recursivos. Análisis de la complejidad de algoritmos recursivos. Técnicas de diseño de algoritmos: dividir y conquistar, backtracking, algoritmos golosos, programación dinámica.
2. Grafos Definiciones básicas: adyacencia, grado de un nodo, isomorfismos, caminos, conexión, etc. Grafos bipartitos. Arboles: caracterización, árboles orientados, árbol generador. Enumeración. Grafos eulerianos y hamiltonianos. Planaridad. Coloreo. Número cromático. Matching, conjunto independiente, recubrimiento. Recubrimiento de aristas y vértices.
3. Algoritmos en grafos y aplicaciones Representación de un grafo en la computadora: matrices de incidencia y adyacencia, listas. Algoritmos de búsqueda en grafos: BFS, DFS, A*. Mínimo árbol generador, algoritmos de Prim y Kruskal. Arboles ordenados: códigos unívocamente descifrables. Algoritmos para detección de circuitos. Algoritmos para encontrar el camino mínimo en un grafo: Dijkstra, Ford, Dantzig. Planificación de procesos: PERT/CPM. Algoritmos heurísticos: ejemplos. Nociones de evaluación de heurísticas y de técnicas metaheurísticas. Algoritmos aproximados. Heurísticas para el problema del viajante de comercio. Algoritmos para detectar planaridad. Algoritmos para coloreo de grafos. Algoritmos para encontrar el flujo máximo en una red: Ford y Fulkerson. Matching: algoritmos para correspondencias máximas en grafos bipartitos. Otras aplicaciones.
4. Problemas NP-completos Problemas tratables e intratables. Problemas de decisión. P y NP. Maquinas de Turing no determinísticas. Problemas NP-completos. Relación entre P y NP. Problemas de grafos NP-completos: coloreo de grafos, grafos hamiltonianos, recubrimiento mínimo de las aristas, corte máximo, etc.
Prácticas
- Primer Parcial
- Práctica 1 - Induccion
- Práctica 2 - Complejidad
- Práctica 3 - Tecnicas Algoritmicas
- Práctica 4 - Problemas de Grafos
- Práctica 5 - Clases de Grafos
- Práctica 6 - Arboles
- Práctica 7 - Camino Minimo / PERT
- Segundo Parcial
- Práctica 8 - Caminos Eulerianos y Hamiltonianos
- Práctica 9 - Planaridad / Coloreo
- Práctica 10 - Matching / Flujo Maximo
- Práctica 11 - Problemas P y NP
Parciales
Apuntes
- Resumen: Temas solamente para el 2do parcial
Bibliografía Recomendada
- Cormen, Introduction to Algorithms
