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.

Guías prácticas con soluciones

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

Año	Cuatrimestre	Fecha	Instancia	Links
2017	Segundo cuatrimestre	04/10/2017	Parcial	enunciado + resuelto (pdf)
2017	Primer cuatrimestre	13/05/2017	Parcial	enunciado + resuelto (pdf)
2016	Segundo cuatrimestre	01/10/2016	Parcial	enunciado (pdf)
2016	Primer cuatrimestre	07/05/2016	Parcial	enunciado (pdf)
2015	Primer cuatrimestre	13/07/2015	Recuperatorio	enunciado (pdf)
2015	Primer cuatrimestre	16/05/2015	Parcial	enunciado
2014	Segundo cuatrimestre	12/12/2014	Recuperatorio	enunciado (pdf)
2014	Primer cuatrimestre	21/07/2014	Recuperatorio	enunciado (pdf)
2013	Segundo cuatrimestre	12/10/2013	Parcial	enunciado (pdf)
2013	Primer cuatrimestre	17/07/2013	Recuperatorio	enunciado (pdf)
2013	Primer cuatrimestre	18/05/2013	Parcial	enunciado (pdf)
2012	Segundo cuatrimestre	12/12/2012	Recuperatorio	enunciado (pdf)
2012	Segundo cuatrimestre	13/10/2012	Parcial	enunciado (pdf)
2012	Primer cuatrimestre	18/07/2012	Recuperatorio	enunciado (pdf)
2012	Primer cuatrimestre	19/05/2012	Parcial	enunciado (pdf)
2010	Primer cuatrimestre	23/07/2010	Recuperatorio	enunciado (pdf)
2010	Primer cuatrimestre	22/06/2010	Parcial	enunciado (pdf)
2006	Segundo cuatrimestre	21/10/2006	Parcial	resolución
2006	Primer cuatrimestre	20/05/2006	Parcial	resolución
2005	Segundo cuatrimestre	15/10/2005	Parcial	resolución
2005	Primer cuatrimestre	22/07/2005	Recuperatorio	resolución
2004	Primer cuatrimestre	22/05/2004	Parcial	resolución
2003	Segundo cuatrimestre	17/12/2003	Recuperatorio	resolución
2003	Primer cuatrimestre	18/07/2003	Recuperatorio	resolución
2002	Primer cuatrimestre	18/05/2002	Parcial	resolución

Segundos parciales

Año	Cuatrimestre	Fecha	Instancia	Links
2017	Primer cuatrimestre	07/07/2017	Parcial	enunciado + resuelto (pdf)‎
2016	Segundo cuatrimestre	19/12/2016	Recuperatorio	enunciado (pdf)‎
2016	Primer cuatrimestre	02/07/2016	Parcial	enunciado (pdf)‎
2015	Segundo cuatrimestre	30/11/2015	Parcial	enunciado (pdf)‎
2015	Primer cuatrimestre	17/07/2015	Recuperatorio	enunciado (pdf)‎
2015	Primer cuatrimestre	04/07/2015	Parcial	enunciado
2014	Segundo cuatrimestre	19/12/2014	Recuperatorio	enunciado (pdf)‎
2014	Segundo cuatrimestre	01/12/2014	Parcial	enunciado (pdf)‎
2014	Primer cuatrimestre	23/07/2014	Recuperatorio	enunciado (pdf)‎
2013	Segundo cuatrimestre	21/12/2013	Recuperatorio	enunciado (pdf)‎
2013	Primer cuatrimestre	05/08/2013	Recuperatorio	enunciado (pdf)‎
2012	Segundo cuatrimestre	19/12/2012	Recuperatorio	enunciado (pdf)‎
2012	Segundo cuatrimestre	05/12/2012	Parcial	enunciado (pdf)‎
2010	Primer cuatrimestre	08/02/2010	Recuperatorio	enunciado
2010	Primer cuatrimestre	14/07/2010	Parcial	enunciado (pdf)
2009	Segundo cuatrimestre	21/12/2009	Recuperatorio	enunciado
2009	Primer cuatrimestre	26/08/2009	Recuperatorio	enunciado + resolución
2006	Segundo cuatrimestre	06/12/2006	Parcial	enunciado + resolución
2005	Segundo cuatrimestre	06/12/2005	Parcial	resolución
2005	Primer cuatrimestre	08/08/2005	Recuperatorio	enunciado + resolución
2005	Primer cuatrimestre	15/07/2005	Parcial	resolución
2004	Segundo cuatrimestre	17/12/2004	Recuperatorio	enunciado + resolución
2004	Primer cuatrimestre	09/08/2004	Recuperatorio	enunciado + resolución
2004	Primer cuatrimestre	14/07/2004	Parcial	enunciado + resolución
2003	Segundo cuatrimestre	10/12/2003	Recuperatorio	enunciado
2003	Primer cuatrimestre	04/08/2003	Recuperatorio	resolución
2003	Primer cuatrimestre	11/07/2003	Parcial	resolución
2002	Primer cuatrimestre	10/07/2002	Parcial	resolución

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.
• Final del 30/07/15: Tomado por Min Chin Lin.
• Final del 06/08/15: Tomado por Irene Loiseau.
• Final del 10/09/15: Tomado por Irene Loiseau.
• Final del 09/12/15: Tomado por Javier Marenco.
• Final del 21/12/15: Tomado por Javier Marenco.

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

Enlaces externos

• Pagina Oficial de la Materia
• Ejercicios resueltos de programación dinámica.