Algoritmos y Estructuras de Datos III
Algoritmos y Estructuras de Datos III (antes llamada Matemática Discreta) pertenece al area de Programación y, según el Plan de la Carrera es una materia a ser cursada en Tercer año. Es correlativa de Algoritmos y Estructuras de Datos II y es necesaria para cursar Ingeniería de Software I.
Información general sobre la cursada
La cursada 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: Inducción
- Práctica 2: Complejidad
- Práctica 3: Técnicas Algorítmicas
- Práctica 4: Problemas de Grafos
- Práctica 5: Clases de Grafos
- Práctica 6: Árboles
- Práctica 7: Camino Mínimo / PERT
- Segundo Parcial
- Práctica 8: Caminos Eulerianos y Hamiltonianos
- Práctica 9: Planaridad
- Práctica 10: Coloreo
- Práctica 11: Matching / Flujo Máximo
- Práctica 12: Problemas P y NP
Parciales
Primeros Parciales
- Parcial del 16/05/15
- Recuperatorio del 21/7/2014
- Parcial del 12/10/2013
- Recuperatorio del 17/7/2013
- Parcial del 18/5/2013
- Parcial del 13/10/2012
- Parcial del 18/07/2012
- Parcial del 12/12/2012
- Parcial del 19/05/2012
- Recuperatorio del 23/07/2010 (enunciado)
- Parcial del 22/06/2010 (enunciado)
- Parcial del 15/12/2006
- Parcial del 20/05/2006
- Parcial del 21/10/2006
- Parcial del 15/10/2005
- Parcial del 22/07/2005
- Parcial del 22/05/2004
- Parcial del 17/12/2003
- Parcial del 18/07/2003
- Parcial del 18/05/2002
Segundos Parciales
- Recuperatorio del 23/7/2014
- Recuperatorio del 5/8/2013
- Recuperatorio del 21/12/2013
- Recuperatorio del 19/12/2012
- Parcial del 5/12/2012
- Parcial del 11/07/2012
- Recuperatorio del 8/08/2012
- Parcial del 05/12/2011
- Recuperatorio del 21/12/2011
- Parcial del 14/07/2010 (enunciado)
- Parcial del 08/02/2010
- Parcial del 21/12/2009
- Recuperatorio del 26/08/2009
- Parcial del 06/12/2006
- Parcial del 06/12/2005
- Parcial del 08/08/2005
- Parcial del 15/07/2005
- Parcial del 17/12/2004
- Parcial del 09/08/2004
- Parcial del 14/07/2004
- Parcial del 10/12/2003
- Parcial del 04/08/2003
- Parcial del 11/07/2003
- Parcial del 10/07/2002
Finales
- Final del 17/03/2005
- Final del 11/08/2005
- Final del 12/03/2007
- Final del 12/02/10: Tomado por Paula Zabala.
- Final del 02/03/10: Tomado por Irene Loiseau.
- Final del 06/09/10: Tomado por Paula Zabala.
- Final del 21/02/13: Tomado por Irene Loiseau.
- Final del 22/12/14: Tomado por Paula Zabala y Javier Marenco.
- Final del 19/02/15: Tomado por Paula Zabala.
- Final del 27/02/15: Tomado por Javier Marenco.
- Final del 06/03/15: Tomado por Javier Marenco y Paula Zabala.
Apuntes
- Solución de LCS (Longest Common Subsequence) usando programación dinámica.
- Apunte sobre Kruskal y estructuras de datos union-find.
- Resumen de algoritmos típicos sobre grafos.
- Resumen: Temas para el segundo parcial.
- Apunte Teoremas Prácticos para el segundo parcial: para modificar el pdf (Repositorio de fuentes en GitHub)
- Apunte teórico: Contiene las demostraciones de los teoremas de casi toda la materia. Es ideal para preparar el final, junto con las slides resulta en un apunte casi autocontenido.
Bibliografía Recomendada
- Cormen, Introduction to Algorithms.
- Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen
- Graph theory and its applications, Gross J., and Yellen J.Google Books
