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.

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

Segundo parcial

Parciales

Primeros parciales

Año Cuatrimestre Fecha Instancia Links
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

Año Cuatrimestre Fecha Instancia Links
2018 Primer cuatrimestre 20/07/2018 Parcial 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

TPs

Apuntes

Bibliografía recomendada

Enlaces externos