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

De Cuba-Wiki
m (Agrego Parcial 2/7/2016)
(→‎Parciales: Reestructuración de parciales)
Línea 38: Línea 38:


== Parciales ==
== Parciales ==
'''Primeros Parciales'''
* [[Media:2016C1P1.pdf ‎|Parcial del 7/5/2016]]
* [[Media:2015C1R1.pdf ‎|Recuperatorio del 13/7/2015]]
* [[Parcial del 16/05/15 (Algoritmos III)|Parcial del 16/05/15]]
* [[Media:2014C2R1.pdf ‎|Recuperatorio del 12/12/2014]]
* [[Media:2014-1er-r.pdf  ‎|Recuperatorio del 21/7/2014]]
* [[Media:2013-2do.pdf  ‎|Parcial del 12/10/2013]]
* [[Media:2013C1R1.pdf ‎|Recuperatorio del 17/7/2013]]
* [[Media:2013C1P1.pdf ‎|Parcial del 18/5/2013]]
* [[Media:Primer_Parcial_13_10_2012_(Algoritmos_III).pdf|Parcial del 13/10/2012]]
* [[Media:Primer_Parcial_18_07_2012_(Algoritmos_III).pdf|Parcial del 18/07/2012]]
* [[Media:Primer_Parcial_12_12_2012_(Algoritmos_III).pdf|Parcial del 12/12/2012]]
* [[Media:Primer_Parcial_19_05_2012_(Algoritmos_III).pdf|Parcial del 19/05/2012]]
* [[Primer Recuperatorio 23/07/2010 (Algoritmos III)|Recuperatorio del 23/07/2010]] ([[Media:Primer Recuperatorio 23-07-2010 (Algoritmos III).pdf|enunciado]])
* [[Primer Parcial 22/06/2010 (Algoritmos III)|Parcial del 22/06/2010]] ([[Media:Primer Parcial 1c2010 (Algoritmos III).pdf|enunciado]])
* [[Primer Parcial 15/12/2006 (Algoritmos III)|Parcial del 15/12/2006]]
* [[Primer Parcial 20/05/2006 (Algoritmos III)|Parcial del 20/05/2006]]
* [[Primer Parcial 21/10/2006 (Algoritmos III)|Parcial del 21/10/2006]]
* [[Primer Parcial 15/10/2005 (Algoritmos III)|Parcial del 15/10/2005]]
* [[Primer Parcial 22/07/2005 (Algoritmos III)|Parcial del 22/07/2005]]
* [[Primer Parcial 22/05/2004 (Algoritmos III)|Parcial del 22/05/2004]]
* [[Primer Parcial 17/12/2003 (Algoritmos III)|Parcial del 17/12/2003]]
* [[Primer Parcial 18/07/2003 (Algoritmos III)|Parcial del 18/07/2003]]
* [[Primer Parcial 18/05/2002 (Algoritmos III)|Parcial del 18/05/2002]]


'''Segundos Parciales'''
=== Primeros parciales ===
* [[Parcial del 04/07/15 (Algoritmos III)|Parcial del 04/07/15]]
{| class="wikitable sortable"
* [[Media:2014C1R2.pdf ‎|Recuperatorio del 23/7/2014]]
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
* [[Media:2013C1R2.pdf ‎|Recuperatorio del 5/8/2013]]
|-
* [[Media:2013C2R2.pdf ‎|Recuperatorio del 21/12/2013]]
|2016 || Primer cuatrimestre  || 07/05/2016 || Parcial      || [[Media:2016C1P1.pdf‎|enunciado (pdf)]]
* [[Media:2012C2R2.pdf ‎|Recuperatorio del 19/12/2012]]
|-
* [[Media:2012C2P2.pdf ‎|Parcial del 5/12/2012]]
|2015 || Primer cuatrimestre  || 13/07/2015 || Recuperatorio || [[Media:2015C1R1.pdf‎|enunciado (pdf)]]
* [http://freepdfhosting.com/d500d6d272.pdf Parcial del 11/07/2012]
|-
* [http://freepdfhosting.com/1309ae886e.pdf Recuperatorio del 8/08/2012]
|2015 || Primer cuatrimestre  || 16/05/2015 || Parcial      || [[Parcial del 16/05/15 (Algoritmos III)|enunciado]]
* [http://freepdfhosting.com/ec5dc89510.pdf Parcial del 05/12/2011]
|-
* [http://freepdfhosting.com/208434bbab.pdf Recuperatorio del 21/12/2011]
|2014 || Segundo cuatrimestre || 12/12/2014 || Recuperatorio || [[Media:2014C2R1.pdf‎|enunciado (pdf)]]
* [[Segundo Parcial 14/07/2010 (Algoritmos III)|Parcial del 14/07/2010]] ([[Media:Segundo Parcial 1c2010 (Algoritmos III).pdf|enunciado]])
|-
* [[Segundo Parcial 08/02/2010 (Algoritmos III)|Parcial del 08/02/2010]]
|2014 || Primer cuatrimestre  || 21/07/2014 || Recuperatorio || [[Media:2014-1er-r.pdf‎|enunciado (pdf)]]
* [[Segundo Parcial 21/12/2009 (Algoritmos III)|Parcial del 21/12/2009]]
|-
* [[Recuperatorio Segundo 26/08/2009 (Algoritmos III)|Recuperatorio del 26/08/2009]]
|2013 || Segundo cuatrimestre || 12/10/2013 || Parcial      || [[Media:2013-2do.pdf‎|enunciado (pdf)]]
* [[Segundo Parcial 06/12/2006 (Algoritmos III)|Parcial del 06/12/2006]]
|-
* [[Segundo Parcial 06/12/2005 (Algoritmos III)|Parcial del 06/12/2005]]
|2013 || Primer cuatrimestre  || 17/07/2013 || Recuperatorio || [[Media:2013C1R1.pdf‎|enunciado (pdf)]]
* [[Segundo Parcial 08/08/2005 (Algoritmos III)|Parcial del 08/08/2005]]
|-
* [[Segundo Parcial 15/07/2005 (Algoritmos III)|Parcial del 15/07/2005]]
|2013 || Primer cuatrimestre  || 18/05/2013 || Parcial      || [[Media:2013C1P1.pdf|enunciado (pdf)]]
* [[Segundo Parcial 17/12/2004 (Algoritmos III)|Parcial del 17/12/2004]]
|-
* [[Segundo Parcial 09/08/2004 (Algoritmos III)|Parcial del 09/08/2004]]
|2012 || Segundo cuatrimestre || 12/12/2012 || Recuperatorio || [[Media:Primer_Parcial_12_12_2012_(Algoritmos_III).pdf|enunciado (pdf)]]
* [[Segundo Parcial 14/07/2004 (Algoritmos III)|Parcial del 14/07/2004]]
|-
* [[Segundo Parcial 10/12/2003 (Algoritmos III)|Parcial del 10/12/2003]]
|2012 || Segundo cuatrimestre || 13/10/2012 || Parcial      || [[Media:Primer_Parcial_13_10_2012_(Algoritmos_III).pdf|enunciado (pdf)]]
* [[Segundo Parcial 04/08/2003 (Algoritmos III)|Parcial del 04/08/2003]]
|-
* [[Segundo Parcial 11/07/2003 (Algoritmos III)|Parcial del 11/07/2003]]
|2012 || Primer cuatrimestre  || 18/07/2012 || Recuperatorio || [[Media:Primer_Parcial_18_07_2012_(Algoritmos_III).pdf|enunciado (pdf)]]
* [[Segundo Parcial 10/07/2002 (Algoritmos III)|Parcial del 10/07/2002]]
|-
|2012 || Primer cuatrimestre  || 19/05/2012 || Parcial      || [[Media:Primer_Parcial_19_05_2012_(Algoritmos_III).pdf|enunciado (pdf)]]
|-
|2010 || Primer cuatrimestre  || 23/07/2010 || Recuperatorio || [[Media:Primer Recuperatorio 23-07-2010 (Algoritmos III).pdf|enunciado (pdf)]]
|-
|2010 || Primer cuatrimestre  || 22/06/2010 || Parcial      || [[Media:Primer Parcial 1c2010 (Algoritmos III).pdf|enunciado (pdf)]]
|-
|2006 || Segundo cuatrimestre || 21/10/2006 || Parcial      || [[Primer Parcial 21/10/2006 (Algoritmos III)|resolución]]
|-
|2006 || Primer cuatrimestre  || 20/05/2006 || Parcial      || [[Primer Parcial 20/05/2006 (Algoritmos III)|resolución]]
|-
|2005 || Segundo cuatrimestre || 15/10/2005 || Parcial      || [[Primer Parcial 15/10/2005 (Algoritmos III)|resolución]]
|-
|2005 || Primer cuatrimestre  || 22/07/2005 || Recuperatorio || [[Primer Parcial 22/07/2005 (Algoritmos III)|resolución]]
|-
|2004 || Primer cuatrimestre  || 22/05/2004 || Parcial      || [[Primer Parcial 22/05/2004 (Algoritmos III)|resolución]]
|-
|2003 || Segundo cuatrimestre || 17/12/2003 || Recuperatorio || [[Primer Parcial 17/12/2003 (Algoritmos III)|resolución]]
|-
|2003 || Primer cuatrimestre  || 18/07/2003 || Recuperatorio || [[Primer Parcial 18/07/2003 (Algoritmos III)|resolución]]
|-
|2002 || Primer cuatrimestre  || 18/05/2002 || Parcial      || [[Primer Parcial 18/05/2002 (Algoritmos III)|resolución]]
|}
 
=== Segundos parciales ===
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
|-
| 2015 || Primer cuatrimestre  || 04/07/2015 || Parcial      || [[Parcial del 04/07/15 (Algoritmos III)|enunciado]]
|-
| 2014 || Primer cuatrimestre  || 23/07/2014 || Recuperatorio || [[Media:2014C1R2.pdf |enunciado (pdf)]]‎
|-
| 2013 || Segundo cuatrimestre || 21/12/2013 || Recuperatorio || [[Media:2013C2R2.pdf |enunciado (pdf)]]‎
|-
| 2013 || Primer cuatrimestre  || 05/08/2013 || Recuperatorio || [[Media:2013C1R2.pdf |enunciado (pdf)]]‎
|-
| 2012 || Segundo cuatrimestre || 19/12/2012 || Recuperatorio || [[Media:2012C2R2.pdf |enunciado (pdf)]]‎
|-
| 2012 || Segundo cuatrimestre || 05/12/2012 || Parcial      || [[Media:2012C2P2.pdf |enunciado (pdf)]]‎
|-
| 2010 || Primer cuatrimestre  || 08/02/2010 || Recuperatorio || [[Segundo Parcial 08/02/2010 (Algoritmos III)|enunciado]]
|-
| 2010 || Primer cuatrimestre  || 14/07/2010 || Parcial      || [[Media:Segundo Parcial 1c2010 (Algoritmos III).pdf|enunciado (pdf)]]
|-
| 2009 || Segundo cuatrimestre || 21/12/2009 || Recuperatorio || [[Segundo Parcial 21/12/2009 (Algoritmos III)|enunciado]]
|-
| 2009 || Primer cuatrimestre  || 26/08/2009 || Recuperatorio || [[Recuperatorio Segundo 26/08/2009 (Algoritmos III)|enunciado + resolución]]
|-
| 2006 || Segundo cuatrimestre || 06/12/2006 || Parcial      || [[Segundo Parcial 06/12/2006 (Algoritmos III)|enunciado + resolución]]
|-
| 2005 || Segundo cuatrimestre || 06/12/2005 || Parcial      || [[Segundo Parcial 06/12/2005 (Algoritmos III)|resolución]]
|-
| 2005 || Primer cuatrimestre  || 08/08/2005 || Recuperatorio || [[Segundo Parcial 08/08/2005 (Algoritmos III)|enunciado + resolución]]
|-
| 2005 || Primer cuatrimestre  || 15/07/2005 || Parcial      || [[Segundo Parcial 15/07/2005 (Algoritmos III)|resolución]]
|-
| 2004 || Segundo cuatrimestre || 17/12/2004 || Recuperatorio || [[Segundo Parcial 17/12/2004 (Algoritmos III)|enunciado + resolución]]
|-
| 2004 || Primer cuatrimestre  || 09/08/2004 || Recuperatorio || [[Segundo Parcial 09/08/2004 (Algoritmos III)|enunciado + resolución]]
|-
| 2004 || Primer cuatrimestre  || 14/07/2004 || Parcial      || [[Segundo Parcial 14/07/2004 (Algoritmos III)|enunciado + resolución]]
|-
| 2003 || Segundo cuatrimestre || 10/12/2003 || Recuperatorio || [[Segundo Parcial 10/12/2003 (Algoritmos III)|enunciado]]
|-
| 2003 || Primer cuatrimestre  || 04/08/2003 || Recuperatorio || [[Segundo Parcial 04/08/2003 (Algoritmos III)|resolución]]
|-
| 2003 || Primer cuatrimestre  || 11/07/2003 || Parcial      || [[Segundo Parcial 11/07/2003 (Algoritmos III)|resolución]]
|-
| 2002 || Primer cuatrimestre  || 10/07/2002 || Parcial      || [[Segundo Parcial 10/07/2002 (Algoritmos III)|resolución]]
|}


== Finales ==
== Finales ==

Revisión del 23:31 18 dic 2016

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
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

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

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Algoritmos_y_Estructuras_de_Datos_III&oldid=10874»