Source: https://www.cubawiki.com.ar/index.php?title=Algoritmos_y_Estructuras_de_Datos_III&amp;action=info
Timestamp: 2019-08-23 22:14:13+00:00

Document:
Algoritmos y Estructuras de Datos III - Cuba-Wiki
Algoritmos y Estructuras de Datos III
De Cuba-Wiki
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.
1 Información general sobre la cursada
2 Programa
3 Guías prácticas con soluciones
3.1 Primer parcial
3.2 Segundo parcial
4 Parciales
4.1 Primeros parciales
4.2 Segundos parciales
5 Finales
6 TPs
7 Apuntes
8 Bibliografía recomendada
Información general sobre la cursada[editar]
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[editar]
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[editar]
Primer parcial[editar]
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[editar]
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[editar]
Primeros parciales[editar]
Cuatrimestre
2019 Primer cuatrimestre 08/05/2019 Parcial enunciado + resuelto (pdf)
2018 Primer cuatrimestre 09/05/2018 Parcial enunciado (pdf) resuelto (pdf)
2017 Segundo cuatrimestre 15/12/2017 Recuperatorio enunciado + resuelto (pdf)
2017 Segundo cuatrimestre 04/10/2017 Parcial enunciado + resuelto (pdf)
2017 Primer cuatrimestre 14/07/2017 Recuperatorio enunciado (pdf)
2017 Primer cuatrimestre 13/05/2017 Parcial enunciado + resuelto (pdf)
2016 Segundo cuatrimestre 12/12/2016 Recuperatorio enunciado (pdf)
2016 Segundo cuatrimestre 01/10/2016 Parcial enunciado (pdf)
2016 Primer cuatrimestre 11/07/2016 Recuperatorio enunciado (pdf)
2016 Primer cuatrimestre 07/05/2016 Parcial enunciado (pdf)
2015 Segundo cuatrimestre 11/12/2015 Recuperatorio enunciado (pdf)
2015 Segundo cuatrimestre 03/10/2015 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 Segundo cuatrimestre 11/10/2014 Parcial enunciado (pdf)
2014 Primer cuatrimestre 21/07/2014 Recuperatorio enunciado (pdf)
2014 Primer cuatrimestre 17/05/2014 Parcial 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[editar]
2018 Primer cuatrimestre 20/07/2018 Recuperatorio enunciado + semi-resuelto (pdf)
2018 Primer cuatrimestre 11/07/2018 Parcial enunciado (pdf) y resolución (pdf)
2017 Segundo cuatrimestre 18/12/2017 Recuperatorio enunciado (pdf)
2017 Segundo cuatrimestre 01/12/2017 Parcial resuelto (pdf)‎
2017 Primer cuatrimestre 21/07/2017 Recuperatorio enunciado (pdf)‎
2017 Primer cuatrimestre 07/07/2017 Parcial enunciado + resuelto (pdf)‎
2016 Segundo cuatrimestre 19/12/2016 Recuperatorio enunciado (pdf)
2016 Segundo cuatrimestre 30/11/2016 Parcial enunciado (pdf)‎‎
2016 Primer cuatrimestre 15/07/2016 Recuperatorio enunciado (pdf)‎
2016 Primer cuatrimestre 02/07/2016 Parcial enunciado (pdf)‎
2015 Segundo cuatrimestre 18/12/2015 Recuperatorio 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)‎
2014 Primer cuatrimestre 07/07/2014 Parcial 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[editar]
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.
Final del 01/03/18: Tomado por Paula Zabala.
Final del 08/03/18: Tomado por Paula Zabala
Final del 01/08/18: Tomado por Paula Zabala
Final del 06/08/18: Tomado por Paula Zabala
TPs[editar]
TP1 del primer cuatrimestre del 2018
Apuntes[editar]
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.
Apunte teórico: Apunte teórico de grafos y complejidad con casi todas las demostraciones de la teórica y con algunos resultados de las prácticas.
Bibliografía recomendada[editar]
Cormen, Introduction to Algorithms. Link a la tercera edición
Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen
Graph theory and its applications, Gross J., and Yellen J.Google Books
Pagina Oficial de la Materia
Ejercicios resueltos de programación dinámica.
Obtenido de «https://www.cubawiki.com.ar/index.php?title=Algoritmos_y_Estructuras_de_Datos_III&oldid=12604»
Se editó esta página por última vez el 2 jul 2019 a las 15:40.

References: resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución 
 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución

 resolución