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

De Cuba-Wiki
m (Agrego apuntes teóricos)
 
(No se muestran 128 ediciones intermedias de 51 usuarios)
Línea 1: Línea 1:
'''Algoritmos y Estructuras de Datos III''' (antes llamada Matemática Discreta) pertenece al area de [[Programación (Area)|Programación]] y, según el [[Plan de la Carrera]] es una materia a ser cursada en [[Plan de la Carrera#Tercer año|Tercer año]]. Es correlativa de [[Algoritmos y Estructuras de Datos II]] y es necesaria para cursar [[Ingeniería de Software I]].
{{Plan 1993|Técnicas de Diseño de Algoritmos}}
 
'''Algoritmos y Estructuras de Datos III''' (antes llamada Matemática Discreta) pertenece al área de Algoritmos y, según el [[Plan de la Carrera]] es una materia a ser cursada en [[Plan de la Carrera#Tercer año|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 ==
== 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.
La cursada consiste de clases teóricas y prácticas-laboratorio. Para aprobar la materia se deben rendir 2 exámenes parciales y 2 trabajos prácticos. La materia no es promocionable.


== Programa ==
== Programa ==
Línea 15: Línea 17:
3. '''Algoritmos en grafos y aplicaciones'''
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.  
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. Árboles 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'''
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.
Problemas tratables e intratables. Problemas de decisión. P y NP. Máquinas 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 ==
== Guías prácticas con soluciones ==
Línea 40: Línea 42:
* [[Práctica 11: Matching - Flujo Máximo (Algoritmos III) | Práctica 11: Matching / Flujo Máximo]]
* [[Práctica 11: Matching - Flujo Máximo (Algoritmos III) | Práctica 11: Matching / Flujo Máximo]]
* [[Práctica 12: Problemas P y NP (Algoritmos III) | Práctica 12: Problemas P y NP]]
* [[Práctica 12: Problemas P y NP (Algoritmos III) | Práctica 12: Problemas P y NP]]
=== 2023 ===
* [https://github.com/honi/uba-aed3 Guías resueltas 1C2023]
* [https://github.com/IgnaOromendia/UBA_AED3 Guías resueltas 2C2023]


== Parciales ==
== Parciales ==
Línea 46: Línea 53:
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
|-
|2023 || Primer cuatrimestre || 12/05/2023 || Parcial || [[Media:AED3-12-05-23.pdf|enunciado (pdf)]], [[Media:2023c1p1_solucion.pdf |resuelto por Profesor (pdf)]]
|-
|2022 || Segundo cuatrimestre || 28/11/2022 || Recuperatorio || [[Media:2c_r1_2022.pdf|enunciado (pdf)]]
|-
|2022 || Segundo cuatrimestre || 30/09/2022 || Parcial || [[Media:AED32022_c2p1.pdf|enunciado (pdf)]]
|-
|2022 || Primer cuatrimestre || 01/07/2022 || Recuperatorio || [[Media:1c_r1_2022.pdf|enunciado (pdf)]]
|-
|2022 || Primer cuatrimestre || 29/04/2022 || Parcial || [[Media:2022c1p1.pdf|enunciado (pdf)]]
|-
|2021 || Segundo cuatrimestre (virtual)  || 17/11/2021 || Recuperatorio|| [[Media:AED3_1recu2021_2c.pdf|enunciado (pdf)]]
|-
|2021 || Segundo cuatrimestre (virtual)  || 22/09/2021 || Parcial|| [[Media:AED3_1parcial_2021_2c.pdf|enunciado (pdf)]]
|-
|2021 || Primer cuatrimestre (virtual)  || 25/06/2021 || Recuperatorio|| [[Media:AED3_1recu_25-06-21.pdf|enunciado (pdf)]]  [[Media:AED3_1recu_25-06-21_resolucion.pdf|resuelto (pdf)]]
|-
|2021 || Primer cuatrimestre (virtual)  || 14/05/2021 || Parcial|| [[Medio:AED3_1parcial_14-05-21.pdf|enunciado]], [[Media:.AED3_1parcial_1c_21_resolucion.pdf|resuelto por Profesor (pdf)]], [[Media:AED3_1parcial_1c_21_resolucion.pdf|resuelto (pdf)]]
|-
|2020 || Segundo cuatrimestre (virtual)  || 09/12/2020 || Recuperatorio  || [[Media:AED3_1recu_09-12-20.pdf|enunciado]]
|-
|2020 || Segundo cuatrimestre (virtual) || 07/10/2020 <br/> 14/10/2020|| Parcial      || [[Media:AED3_1parcial_07-10-20.pdf|parte domiciliaria]]<br/> [[Media:AED3_1parcial_14-10-20.pdf|parte presencial]]
|-
|2020 || Primer cuatrimestre* (virtual) || 03/08/2020 <br/> 10/08/2020 || Recuperatorio      || [[Media:AED3_1recu_03-08-20.pdf|primer recuperatorio]]<br/> [[Media:AED3_1recu_10-08-20.pdf|segundo recuperatorio]]
|-
|2020 || Primer cuatrimestre* (virtual) || 06/05/2020 <br/> 03/06/2020 || Parcial      || [[Media:AED3_1parcial_06-05-20.pdf|primer parcialito]]<br/> [[Media:AED3_1parcial_03-06-20.pdf|segundo parcialito]]
|-
|2019 || Segundo cuatrimestre  || 02/10/2019 || Parcial      || [[Media:AED3_1parcial_02-10-19.pdf|enunciado + resuelto (pdf)]]
|-
|2019 || Primer cuatrimestre  || 12/07/2019 || Recuperatorio      || [[Media:AED3_1recu_12-07-19.pdf|enunciado + resuelto (pdf)]]
|-
|2019 || Primer cuatrimestre  || 08/05/2019 || Parcial      || [[Media:AED3_1parcial_08-05-19.pdf|enunciado + resuelto (pdf)]]
|-
|2018 || Segundo cuatrimestre  || 03/10/2018 || Parcial      || [[Media:AED3_1parcial_03-10-18.png|enunciado]]
|-
|2018 || Primer cuatrimestre  || 13/07/2018 || Recuperatorio      || [[Media:AED3_1recu_13-07-18.pdf|enunciado + resuelto (pdf)]]
|-
|2018 || Primer cuatrimestre  || 09/05/2018 || Parcial      || [[Media:AED3_1parcial_09-05-18.pdf|enunciado (pdf)]] [[Media:AED3_1parcial_09-05-18_resolucion.pdf|resuelto (pdf)]]
|-
|2017 || Segundo cuatrimestre  || 15/12/2017 || Recuperatorio      || [[Media:AED3_1recu_15-12-17.pdf|enunciado + resuelto (pdf)]]
|-
|-
|2017 || Segundo cuatrimestre  || 04/10/2017 || Parcial      || [[Media:AED3_1parcial_04-10-17.pdf|enunciado + resuelto (pdf)]]
|2017 || Segundo cuatrimestre  || 04/10/2017 || Parcial      || [[Media:AED3_1parcial_04-10-17.pdf|enunciado + resuelto (pdf)]]
|-
|2017 || Primer cuatrimestre  || 14/07/2017 || Recuperatorio      || [[Media:AED3_1recu_14-07-17.pdf|enunciado (pdf)]]
|-
|-
|2017 || Primer cuatrimestre  || 13/05/2017 || Parcial      || [[Media:AED3_1parcial_13-05-17.pdf|enunciado + resuelto (pdf)]]
|2017 || Primer cuatrimestre  || 13/05/2017 || Parcial      || [[Media:AED3_1parcial_13-05-17.pdf|enunciado + resuelto (pdf)]]
|-
|2016 || Segundo cuatrimestre  || 12/12/2016 || Recuperatorio      || [[Medio:AED3_1recu_12-12-16.pdf|enunciado (pdf)]]
|-
|-
|2016 || Segundo cuatrimestre  || 01/10/2016 || Parcial      || [[Medio:AED3_1parcial_01-10-16.pdf|enunciado (pdf)]]
|2016 || Segundo cuatrimestre  || 01/10/2016 || Parcial      || [[Medio:AED3_1parcial_01-10-16.pdf|enunciado (pdf)]]
|-
|2016 || Primer cuatrimestre  || 11/07/2016 || Recuperatorio      || [[Media:2016C1R1.pdf‎|enunciado (pdf)]]
|-
|-
|2016 || Primer cuatrimestre  || 07/05/2016 || Parcial      || [[Media:2016C1P1.pdf‎|enunciado (pdf)]]
|2016 || Primer cuatrimestre  || 07/05/2016 || Parcial      || [[Media:2016C1P1.pdf‎|enunciado (pdf)]]
|-
|2015 || Segundo cuatrimestre  || 11/12/2015 || Recuperatorio || [[Media:2015C2R1.pdf‎|enunciado (pdf)]]
|-
|-
|2015 || Segundo cuatrimestre  || 03/10/2015 || Parcial || [[Media:2015C2P1.pdf‎|enunciado (pdf)]]
|2015 || Segundo cuatrimestre  || 03/10/2015 || Parcial || [[Media:2015C2P1.pdf‎|enunciado (pdf)]]
Línea 103: Línea 158:
|2002 || Primer cuatrimestre  || 18/05/2002 || Parcial      || [[Primer Parcial 18/05/2002 (Algoritmos III)|resolución]]
|2002 || Primer cuatrimestre  || 18/05/2002 || Parcial      || [[Primer Parcial 18/05/2002 (Algoritmos III)|resolución]]
|}
|}
<nowiki>*</nowiki> En el primer cuatrimestre de 2020, los temas que suelen ser del primer parcial se subdividieron en dos parcialitos/dos recuperatorios.


=== Segundos parciales ===
=== Segundos parciales ===
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
|-
|2023 || Primer cuatrimestre || 28/06/2023 || Parcial|| [[Media:Algo3_2023c1p2.pdf ‎|enunciado y resuelto profesor]]
|-
|2022 || Segundo cuatrimestre || 07/12/2022 || Recuperatorio|| [[Media:AED3-2r2c2022.pdf ‎|enunciado]]
|-
|2022 || Segundo cuatrimestre || 23/11/2022 || Parcial|| [[Media:AED3_2parcial_13-11-22_2c.pdf|enunciado]]
|-
|2022 || Primer cuatrimestre || 24/06/2022 || Recuperatorio|| [[Media:AED3-2r1c2022.pdf  ‎|enunciado]]
|-
|2022 || Primer cuatrimestre || 24/06/2022 || Parcial|| [[Media:AED3-2p1c2022.pdf  ‎|enunciado]]
|-
|2021 || Segundo cuatrimestre (virtual)  || 24/11/2021 || Recuperatorio|| [[Media:AED3_2recu2021_2c.pdf|enunciado]]
|-
|2021 || Segundo cuatrimestre (virtual)  || 10/11/2021 || Parcial|| [[Media:AED3_2parcial_2021_2c.pdf|enunciado]]
|-
| 2021 || Primer cuatrimestre (virtual)  || 02/07/2021 || Recuperatorio|| [[Media:AED3_2parcial_02-07-21.pdf |enunciado (pdf)]]
|-
| 2021 || Primer cuatrimestre (virtual)  || 18/06/2021 || Parcial || [[Media:AED3_2parcial_18-06-21.pdf |enunciado (pdf)]] [[Media:AED3_2parcial_18-06-21_resolucion.pdf |resolución (pdf)]]
|-
|2020 || Segundo cuatrimestre (virtual)  || 18/12/2020 || Recuperatorio      || [[Media:AED3_2recu_18-12-20.pdf|enunciado]]
|-
| 2020 || Segundo cuatrimestre (virtual)  || 30/11/2020 || Parcial || [[Media:AED3_2parcialConsigna_12-2020.pdf |enunciado (pdf)]] y [[Media:AED3_2parcial_12-2020.pdf |resolución (pdf)]]
|-
|2020 || Primer cuatrimestre* (virtual) || 29/07/2020 <br/> 05/08/2020 || Recuperatorio      || [[Media:AED3_2recu_29-07-20.pdf|tercer recuperatorio]], [[Media:AED3_2recu_03-08-20.pdf|bis]]<br/> [[Media:AED3_2recu_05-08-20.pdf|cuarto recuperatorio]]
|-
|2020 || Primer cuatrimestre* (virtual) || 06/07/2020 <br/> 24/07/2020 || Parcial      || [[Media:AED3_2parcial_06-07-20.pdf|tercer parcialito]]<br/> [[Media:AED3_2parcial_24-07-20.pdf|cuarto parcialito]]
|-
| 2019 || Primer cuatrimestre  || 05/07/2019 || Parcial|| [[Media:AED3_2parcial_05-07-19.pdf |enunciado + resuelto (pdf)]]
|-
| 2018 || Segundo cuatrimestre  || 03/12/2018 || Parcial|| [[Media:AED3_2parcial_03-12-18.gif |enunciado ]]
|-
| 2018 || Primer cuatrimestre  || 20/07/2018 || Recuperatorio|| [[Media:AED3_2recu_20-07-18.pdf |enunciado + semi-resuelto (pdf)]]
|-
| 2018 || Primer cuatrimestre  || 11/07/2018 || Parcial || [[Media:AED3_2parcial_11-07-18.pdf |enunciado (pdf)]] y [[Media:AED3_2parcial_11-07-18_resolucion.pdf |resolución (pdf)]]
|-
| 2017 || Segundo cuatrimestre  || 18/12/2017 || Recuperatorio || [[Media:AED3_2recuperatorio_18-12-17.pdf |enunciado (pdf)]]
|-
| 2017 || Segundo cuatrimestre  || 01/12/2017 || Parcial || [[Media:AED3_2parcial_06-12-17.pdf |resuelto (pdf)]]‎
|-
| 2017 || Primer cuatrimestre  || 21/07/2017 || Recuperatorio || [[Media:AED3_2recu_21-07-17.pdf |enunciado (pdf)]]‎
|-
|-
| 2017 || Primer cuatrimestre  || 07/07/2017 || Parcial || [[Media:AED3_2parcial_07-07-17.pdf |enunciado + resuelto (pdf)]]‎
| 2017 || Primer cuatrimestre  || 07/07/2017 || Parcial || [[Media:AED3_2parcial_07-07-17.pdf |enunciado + resuelto (pdf)]]‎
|-
|-
| 2016 || Segundo cuatrimestre  || 19/12/2016 || Recuperatorio || [[Media:AED3_2recu_19-12-16.pdf |enunciado (pdf)]]‎
| 2016 || Segundo cuatrimestre  || 19/12/2016 || Recuperatorio || [[Media:AED3_2recu_19-12-16.pdf |enunciado (pdf)]]
|-
| 2016 || Segundo cuatrimestre  || 30/11/2016 || Parcial || [[Media:AED3_2recu_30-11-16.pdf |enunciado (pdf)]]‎‎
|-
| 2016 || Primer cuatrimestre  || 15/07/2016 || Recuperatorio || [[Media:AED3_2recu_15-07-16.pdf |enunciado (pdf)]]‎
|-
|-
| 2016 || Primer cuatrimestre  || 02/07/2016 || Parcial || [[Media:AED3_2parcial_02-07-16.pdf |enunciado (pdf)]]‎
| 2016 || Primer cuatrimestre  || 02/07/2016 || Parcial || [[Media:AED3_2parcial_02-07-16.pdf |enunciado (pdf)]]‎
Línea 127: Línea 228:
|-
|-
| 2014 || Primer cuatrimestre  || 23/07/2014 || Recuperatorio || [[Media:2014C1R2.pdf |enunciado (pdf)]]‎
| 2014 || Primer cuatrimestre  || 23/07/2014 || Recuperatorio || [[Media:2014C1R2.pdf |enunciado (pdf)]]‎
|-
| 2014 || Primer cuatrimestre  || 07/07/2014 || Parcial || [[Media:2014C1P2.pdf |enunciado (pdf)]]‎
|-
|-
| 2013 || Segundo cuatrimestre || 21/12/2013 || Recuperatorio || [[Media:2013C2R2.pdf |enunciado (pdf)]]‎
| 2013 || Segundo cuatrimestre || 21/12/2013 || Recuperatorio || [[Media:2013C2R2.pdf |enunciado (pdf)]]‎
Línea 166: Línea 269:
| 2002 || Primer cuatrimestre  || 10/07/2002 || Parcial      || [[Segundo Parcial 10/07/2002 (Algoritmos III)|resolución]]
| 2002 || Primer cuatrimestre  || 10/07/2002 || Parcial      || [[Segundo Parcial 10/07/2002 (Algoritmos III)|resolución]]
|}
|}
<nowiki>*</nowiki> En el primer cuatrimestre de 2020, los temas que suelen ser del segundo parcial se subdividieron en dos parcialitos/dos recuperatorios.
=== Ambos ===
[https://drive.google.com/file/d/1Alaz5KHPlkgTlaIkKX3q8y0VWmgBs86h/view?usp=sharing Ejercicios v1.732 (439 enunciados - 419 soluciones)].


== Finales ==
== Finales ==
Línea 179: Línea 286:
* [[Final del 27/02/15 (Algoritmos III) | Final del 27/02/15]]: Tomado por Javier Marenco.
* [[Final del 27/02/15 (Algoritmos III) | Final del 27/02/15]]: Tomado por Javier Marenco.
* [[Final del 06/03/15 (Algoritmos_III) | Final del 06/03/15]]: Tomado por Javier Marenco y Paula Zabala.
* [[Final del 06/03/15 (Algoritmos_III) | Final del 06/03/15]]: Tomado por Javier Marenco y Paula Zabala.
* [[Final del 30/07/15 (Algoritmos_III) | Final del 30/07/15]]: Tomado por Min Chin Lin.
* [[Final del 30/07/15 (Algoritmos_III) | Final del 30/07/15]]: Tomado por Min Chih Lin.
* [[Medio:AED3_final_06-08-2015.jpg | Final del 06/08/15]]: Tomado por Irene Loiseau.
* [[Medio:AED3_final_06-08-2015.jpg | Final del 06/08/15]]: Tomado por Irene Loiseau.
* [[Medio:AED3_final_10-09-2015.png | Final del 10/09/15]]: Tomado por Irene Loiseau.
* [[Medio:AED3_final_10-09-2015.png | Final del 10/09/15]]: Tomado por Irene Loiseau.
* [[Final del 09/12/15 (Algoritmos_III) | Final del 09/12/15]]: Tomado por Javier Marenco.
* [[Final del 09/12/15 (Algoritmos_III) | Final del 09/12/15]]: Tomado por Javier Marenco.
* [[Final del 21/12/15 (Algoritmos_III) | Final del 21/12/15]]: Tomado por Javier Marenco.
* [[Final del 21/12/15 (Algoritmos_III) | Final del 21/12/15]]: Tomado por Javier Marenco.
* [[Final del 01/03/18 (Algoritmos_III) | Final del 01/03/18]]: Tomado por Paula Zabala.
* [[Final del 08/03/18 (Algoritmos_III) | Final del 08/03/18]]: Tomado por Paula Zabala.
* [[Final del 01/08/18 (Algoritmos_III) | Final del 01/08/18]]: Tomado por Paula Zabala.
* [[Final del 06/08/18 (Algoritmos_III) | Final del 06/08/18]]: Tomado por Paula Zabala.
* [[Final del 11/06/19 (Algoritmos_III) | Final del 11/06/19]]: Tomado por Flavia Bonomo.
* [[Final del 20/12/19 (Algoritmos_III) | Final del 20/12/19]]: Tomado por Min Chih Lin.
* [[Medio:Final_del_09-02-21_(Algoritmos_III).pdf | Final del 09/02/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_19-02-21_(Algoritmos_III).pdf | Final del 19/02/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_26-02-21_(Algoritmos_III).pdf | Final del 26/02/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_04-03-21_(Algoritmos_III).pdf | Final del 04/03/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_20-04-21_(Algoritmos_III).pdf | Final del 20/04/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_20-07-21_(Algoritmos_III).pdf | Final del 20/07/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_11-08-21_(Algoritmos_III).pdf | Final del 11/08/21]]: Tomado por Paula Zabala.
* [[Medio:Final_del_17-02-22_(Algoritmos_III).jpg | Final del 17/02/22]]: Tomado por Paula Zabala.
* [[Medio:AED3_final_24-02-22.jpeg | Final del 24/02/22]]: Tomado por Paula Zabala.
* [[Medio:Final_del_03-03-22_(Algoritmos_III).pdf | Final del 03/03/22]]: Tomado por Paula Zabala.
* [[Medio:AED3_final_20-07-22.jpg | Final del 20/07/22]]: Tomado por Javier Marenco y Juan Kamienkowski.
* [[Medio:AED3_final_03-08-22.jpg | Final del 03/08/22]]: Tomado por Javier Marenco y Juan Kamienkowski.
* [[Medio:AED3_final_10-08-22.jpg | Final del 10/08/22]]: Tomado por Javier Marenco y Juan Kamienkowski.
* [[Final_del_14/09/22_(AED3)|Final del 14/09/22]]: Tomado por Javier Marenco.
* [[Medio:AED3Final22-02-23.png | Final del 22/02/23]]: Tomado por Juan Kamienkowski.
* [[Medio:AED3Final01-03-23.png | Final del 01/03/23]]: Tomado por Juan Kamienkowski.
* [[Medio:AED3Final18-07-23.jpg | Final del 18/07/23]]: Tomado por Juan Kamienkowski.
* [[Medio:AED3Final28-07-23.jpg | Final del 28/07/23]]: Tomado por Juan Kamienkowski.
== TPs ==
* [[Medio:AED3_1tp_1cuat_2018.pdf | TP1 del primer cuatrimestre del 2018]]


== Apuntes ==  
== Apuntes ==  
Línea 192: Línea 326:
* [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])
* [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])
* [[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.
* [[Media:algo3-apunte-teorico.pdf|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.
* [https://drive.google.com/drive/folders/1V9tplU_ewsp7lFQoyQgbRRAUuD1U4G3s?usp=sharing Apuntes de los libros y teoricas para el final].
* [https://drive.google.com/drive/folders/1Wz8O_375lGLdw9Kf27KdeGIQffQ8a7Az?usp=sharing Apunte teórico oficial de 1c2020]: Conjunto de apuntes de toda la materia escritos por la profesora de la materia para dicho cuatrimestre.
* [[Media:AED3_apunte_algoritmos2doParcial.pdf|Resumen de algoritmos y complejidades para el segundo parcial o el final]].
* [https://docs.google.com/document/d/1YUVSyoBPO9bEJTNqL_MQX1bu7yPIPQASTzy5BYiQhm8/edit?usp=sharing Compilado de finales 2022/2023], incluye un [https://earthy-telephone-c18.notion.site/Compilado-de-Q-A-de-finales-49dcaf9382df4fb99cc56f2cc94a5c77?pvs=4 link] con con algunas respuestas a preguntas de finales.
* [https://github.com/sponja23/resumen-final-aed3/releases/latest/download/resumen-aed3.pdf Resumen teórico]. [https://github.com/sponja23/resumen-final-aed3 Link al repositorio] para agregar o corregir.


== Bibliografía recomendada ==
== Bibliografía recomendada ==
* Cormen, ''Introduction to Algorithms''.  
* Cormen, ''Introduction to Algorithms''. [http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf Link a la tercera edición]
* Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen  
* Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen  
* Graph theory and its applications, Gross J., and Yellen J.[http://books.google.com.ar/books?id=unEloQ_sYmkC&lpg=PP1&dq=gross%20yellen%20graph&pg=PP1#v=onepage&q=&f=false Google Books]
* Graph theory and its applications, Gross J., and Yellen J.[http://books.google.com.ar/books?id=unEloQ_sYmkC&lpg=PP1&dq=gross%20yellen%20graph&pg=PP1#v=onepage&q=&f=false Google Books]


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


Revisión actual - 23:19 4 feb 2024

Esta página es sobre la materia del plan de estudios 1993. Para ver la materia del plan 2023, consultar Técnicas de Diseño de Algoritmos.

Algoritmos y Estructuras de Datos III (antes llamada Matemática Discreta) pertenece al área de Algoritmos 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 teóricas y prácticas-laboratorio. Para aprobar la materia se deben rendir 2 exámenes parciales y 2 trabajos prácticos. La materia no es promocionable.

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. Árboles 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. Máquinas 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

2023

Parciales

Primeros parciales

Año Cuatrimestre Fecha Instancia Links
2023 Primer cuatrimestre 12/05/2023 Parcial enunciado (pdf), resuelto por Profesor (pdf)
2022 Segundo cuatrimestre 28/11/2022 Recuperatorio enunciado (pdf)
2022 Segundo cuatrimestre 30/09/2022 Parcial enunciado (pdf)
2022 Primer cuatrimestre 01/07/2022 Recuperatorio enunciado (pdf)
2022 Primer cuatrimestre 29/04/2022 Parcial enunciado (pdf)
2021 Segundo cuatrimestre (virtual) 17/11/2021 Recuperatorio enunciado (pdf)
2021 Segundo cuatrimestre (virtual) 22/09/2021 Parcial enunciado (pdf)
2021 Primer cuatrimestre (virtual) 25/06/2021 Recuperatorio enunciado (pdf) resuelto (pdf)
2021 Primer cuatrimestre (virtual) 14/05/2021 Parcial enunciado, resuelto por Profesor (pdf), resuelto (pdf)
2020 Segundo cuatrimestre (virtual) 09/12/2020 Recuperatorio enunciado
2020 Segundo cuatrimestre (virtual) 07/10/2020
14/10/2020		 Parcial parte domiciliaria
parte presencial
2020 Primer cuatrimestre* (virtual) 03/08/2020
10/08/2020		 Recuperatorio primer recuperatorio
segundo recuperatorio
2020 Primer cuatrimestre* (virtual) 06/05/2020
03/06/2020		 Parcial primer parcialito
segundo parcialito
2019 Segundo cuatrimestre 02/10/2019 Parcial enunciado + resuelto (pdf)
2019 Primer cuatrimestre 12/07/2019 Recuperatorio enunciado + resuelto (pdf)
2019 Primer cuatrimestre 08/05/2019 Parcial enunciado + resuelto (pdf)
2018 Segundo cuatrimestre 03/10/2018 Parcial enunciado
2018 Primer cuatrimestre 13/07/2018 Recuperatorio 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

* En el primer cuatrimestre de 2020, los temas que suelen ser del primer parcial se subdividieron en dos parcialitos/dos recuperatorios.

Segundos parciales

Año Cuatrimestre Fecha Instancia Links
2023 Primer cuatrimestre 28/06/2023 Parcial enunciado y resuelto profesor
2022 Segundo cuatrimestre 07/12/2022 Recuperatorio enunciado
2022 Segundo cuatrimestre 23/11/2022 Parcial enunciado
2022 Primer cuatrimestre 24/06/2022 Recuperatorio enunciado
2022 Primer cuatrimestre 24/06/2022 Parcial enunciado
2021 Segundo cuatrimestre (virtual) 24/11/2021 Recuperatorio enunciado
2021 Segundo cuatrimestre (virtual) 10/11/2021 Parcial enunciado
2021 Primer cuatrimestre (virtual) 02/07/2021 Recuperatorio enunciado (pdf)
2021 Primer cuatrimestre (virtual) 18/06/2021 Parcial enunciado (pdf) resolución (pdf)
2020 Segundo cuatrimestre (virtual) 18/12/2020 Recuperatorio enunciado
2020 Segundo cuatrimestre (virtual) 30/11/2020 Parcial enunciado (pdf) y resolución (pdf)
2020 Primer cuatrimestre* (virtual) 29/07/2020
05/08/2020		 Recuperatorio tercer recuperatorio, bis
cuarto recuperatorio
2020 Primer cuatrimestre* (virtual) 06/07/2020
24/07/2020		 Parcial tercer parcialito
cuarto parcialito
2019 Primer cuatrimestre 05/07/2019 Parcial enunciado + resuelto (pdf)
2018 Segundo cuatrimestre 03/12/2018 Parcial enunciado
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

* En el primer cuatrimestre de 2020, los temas que suelen ser del segundo parcial se subdividieron en dos parcialitos/dos recuperatorios.

Ambos

Ejercicios v1.732 (439 enunciados - 419 soluciones).

Finales

TPs

Apuntes

Bibliografía recomendada

Enlaces externos

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