Diferencia entre revisiones de «Algoritmos y Estructuras de Datos III»

De Cuba-Wiki
mSin resumen de edición
Línea 158: Línea 158:


== Apuntes ==  
== Apuntes ==  
* [[Media:lcs_tagliavini.pdf|Solución de LCS (Longest Common Subsequence) usando programación dinámica]].
* [[Media:lcs_tagliavini.pdf|Solución de LCS (Longest Common Subsequence) usando programación dinámica]].
* [[Media:union-find_tagliavini.pdf|Apunte sobre Kruskal y estructuras de datos union-find]].
* [[Media:union-find_tagliavini.pdf|Apunte sobre Kruskal y estructuras de datos union-find]].
* [[Resumen algoritmos grafos (Algoritmos III) | Resumen de algoritmos típicos sobre grafos]].
* [[Resumen algoritmos grafos (Algoritmos III) | Resumen de algoritmos típicos sobre grafos]].
* [[Resumen (Algoritmos III) | Resumen]]: Temas para el segundo parcial.
* [[Resumen (Algoritmos III) | Resumen]]: Temas para el segundo parcial.
* [https://github.com/CubaWiki/AED3-Apunte-sacamacho/releases/download/1.0/apunte.pdf Apunte Teoremas Prácticos para el segundo parcial]: para modificar el pdf ([https://github.com/CubaWiki/AED3-Apunte-
* [https://github.com/CubaWiki/AED3-Apunte-sacamacho/releases/download/1.0/apunte.pdf Apunte Teoremas Prácticos para el segundo parcial]: para modificar el pdf ([https://github.com/CubaWiki/AED3-Apunte-
sacamacho Repositorio de fuentes en GitHub])
sacamacho Repositorio de fuentes en GitHub])
* [[Media:Algo3_teoria_arjovsky.pdf|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.
* [[Media:Algo3_teoria_arjovsky.pdf|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 ==
== Bibliografía recomendada ==
* Cormen, ''Introduction to Algorithms''.  
* Cormen, ''Introduction to Algorithms''.  
* Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen  
* Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen  
Línea 178: Línea 172:


== Enlaces externos ==
== Enlaces externos ==
*[http://www.dc.uba.ar/materias/aed3/ Pagina Oficial de la Materia]
* [http://www.dc.uba.ar/materias/aed3/ Pagina Oficial de la Materia]
* [https://people.cs.clemson.edu/~bcdean/dp_practice/ Ejercicios resueltos de programación dinámica].


[[Category:Materias]]
[[Category:Materias]]
[[Category:Computación]]
[[Category:Computación]]
[[Category:Programación]]
[[Category:Programación]]

Revisión del 00:39 25 ene 2017

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
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
2015 Primer cuatrimestre 04/07/2015 Parcial enunciado
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

Apuntes

sacamacho 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