Algoritmos y Estructuras de Datos

De Cuba-Wiki

Algoritmos y Estructuras de Datos (anteriormente Algoritmos y Estructuras de Datos II) es una materia donde se estudia la especificación formal de tipos de datos, y el diseño de los mismos para su posterior implementación. Tambien se ve, paralelamente, Teorema del invariante, complejidad y algoritmos de sorting.

Según el Plan de la Carrera (2023) es una materia a ser cursada en Primer año. Es correlativa de Introducción a la Programación y es necesaria para cursar Paradigmas De Programación, Técnicas De Diseño de Algorítmos y Lenguajes Formales, Autómatas y Computablildad.

Información general sobre la cursada

Algoritmos consiste de clases teóricas, prácticas y de laboratorio. Para aprobar la materia se deben rendir 2 exámenes parciales, 2 trabajos prácticos grupales y ademas, se deben entregar 5 talleres del laboratorio, los cuales son de programación en Java.

Contenidos

Cuando se habla de especificación formal de tipos de datos (también conocidos como TADs) se refiere a expresar el comportamiento que va a tener en función de las diferentes acciones que se le aplican. Para ésto es que se vale de la lógica algebraica, o por axiomas, la cual (intenta) eliminar la ambigüedad que se podría producir si se hace en lenguaje castellano.

En diseño lo que se hace es elegir la mejor manera (la mejor en términos de requerimientos de performance pero a su vez fácil de hacer) de representar los TADs en la "realidad" (principalmente, ésta realidad es un medio computacional). Para ésto es que se valen de estructuras de datos "básicas" mediante las cuales construir otras mas complejas que sirvan para otras aún más complejas, y así sucesivamente.

  • Especificación formal de software. Introducción a la validación y verificación.
  • Métodos de demostración formal de correctitud (ej. weakest precondition). Teorema del invariante.
  • Análisis básico de algoritmos: análisis asintótico, modelo RAM. Caso peor, promedio y mejor.
  • Impacto de la complejidad algorítmica en el diseño de estructuras de datos (Tipos Abstractos de Datos).
  • Algoritmos de búsqueda y ordenamiento básicos y avanzados (Sorting).
  • Estructuras para búsqueda y ordenamiento: árboles de búsqueda, árboles balanceados, árboles digitales, hashing, colas de prioridad. Tipos de datos inductivos

Guías prácticas

Las guías de ejercicios correspondientes al cuatrimestre en curso pueden encontrarse en la página oficial de la materia.

Guías prácticas de segundo cuatrimestre de 2017 resuelta

Guías prácticas de segundo cuatrimestre de 2019 resueltas

Guías prácticas de primer cuatrimestre de 2020 resueltas

Guías prácticas de primer cuatrimestre de 2022 resueltas

Trabajos Prácticos

Año Cuatrimestre Fecha Links
2023 Segundo Cuatrimestre 17/09/2023 Enunciado TP 1 (pdf)
2023 Segundo Cuatrimestre 11/11/2023 Enunciado TP 2 (pdf)

Parciales

Parciales Plan 2023

Primeros parciales

Año Cuatrimestre Fecha Instancia Links
2023 Segundo Cuatrimestre 10/10/2023 Parcial enunciado (jpg) enunciado + resolución (pdf)
2023 Segundo Cuatrimestre 7/10/2023 Parcial enunciado (pdf)
2023 Segundo Cuatrimestre 10/10/2023 Parcial Enunciado + Resolución (pdf)

Segundos parciales

Año Cuatrimestre Fecha Instancia Links
2023 Segundo Cuatrimestre 25/11/2023 Parcial enunciado (pdf) enunciado + resolución (pdf)
2023 Segundo Cuatrimestre 25/11/2023 Parcial Enunciado + Resolución (pdf)
2023 Segundo Cuatrimestre 12/12/2023 Recuperatorio enunciado (pdf) + Resolución

-|}

Parciales Plan 1993

Primeros parciales

Año Cuatrimestre Fecha Instancia Links
2023 Primer Cuatrimestre 06/05/2023 Parcial enunciado (pdf)
2022 Segundo Cuatrimestre 19/07/2022 Parcial enunciado + resolución (pdf)
2022 Primer Cuatrimestre 29/04/2021 Parcial enunciado + resolución (pdf)
2022 Primer Cuatrimestre 29/04/2021 Parcial enunciado + resolución (pdf)
2021 Segundo Cuatrimestre 04/12/2021 Recuperatorio enunciado TADs (pdf)
2021 Segundo Cuatrimestre 11/09/2021 Parcial enunciado TADs (pdf) , resolución (pdf)
2021 Primer Cuatrimestre 07/07/2021 Recuperatorio enunciado (pdf)
2021 Primer Cuatrimestre 17/04/2021 Parcial enunciado TADs (pdf) , resolución (pdf)
2019 Primer Cuatrimestre 06/07/2019 Recuperatorio enunciado (pdf) , resolución (pdf)
2019 Primer Cuatrimestre 04/05/2019 Parcial enunciado + resolución (pdf)
2018 Primer Cuatrimestre 05/05/2018 Parcial enunciado + resolución (pdf)
2017 Segundo Cuatrimestre 30/09/2017 Parcial enunciado + resolución (pdf)
2017 Primer Cuatrimestre 03/05/2017 Parcial enunciado + resolución (pdf)
2016 Segundo Cuatrimestre 16/09/2016 Parcial enunciado + resolución (pdf)
2016 Segundo Cuatrimestre 16/09/2016 Parcial enunciado + resolución (pdf)
2016 Primer Cuatrimestre 23/04/2016 Parcial enunciado + resolución (pdf)
2014 Segundo Cuatrimestre 27/09/2014 Parcial enunciado parte 1 (pdf) , enunciado parte 2 (pdf)

Segundos parciales

Año Cuatrimestre Fecha Instancia Links
2023 Primer Cuatrimestre 24/06/2023 Parcial enunciado (pdf)
2022 Primer Cuatrimestre 08/07/2022 Recuperatorio enunciado + resolución (pdf)
2022 Primer Cuatrimestre 10/06/2022 Parcial enunciado + resolución (pdf)
2021 Segundo Cuatrimestre 18/12/2021 Recuperatorio enunciado Sorting y D&C (pdf), resolución D&C (pdf)
2021 Segundo Cuatrimestre 11/12/2021 Recuperatorio enunciado elección de estructuras (pdf)
2021 Segundo Cuatrimestre 27/11/2021 Parcial enunciado Sorting y D&C (pdf) , resuelto sorting, resuelto D&C
2021 Segundo Cuatrimestre 30/10/2021 Parcial enunciado elección de estructuras (pdf) , resolución (pdf)
2021 Primer Cuatrimestre 14/07/2021 Recuperatorio enunciado (pdf)
2021 Primer Cuatrimestre 26/06/2021 Parcial enunciado Sorting y D&C (pdf)
2021 Primer Cuatrimestre 05/06/2021 Parcial enunciado elección de estructuras (pdf) , resolución (pdf)
2021 Primer Cuatrimestre 15/05/2020 Parcial enunciado complejidad y rep/abs (pdf)
2020 Segundo Cuatrimestre ??/??/2020 Parcial enunciado elección de estructuras (pdf)
2020 Segundo Cuatrimestre 19/10/2020 Parcial enunciado complejidad y rep/abs (pdf)
2020 Primer Cuatrimestre ??/??/2020 Parcial enunciado Sorting y D&C + resolución (pdf)
2019 Primer Cuatrimestre 22/06/2019 Parcial enunciado + resolución (pdf)
2018 Segundo Cuatrimestre 24/11/2018 Parcial enunciado + resolución (pdf)
2018 Primer Cuatrimestre 23/06/2018 Parcial enunciado + resolución (pdf)
2017 Segundo Cuatrimestre ??/??/2017 Parcial enunciado + resolución (pdf)
2017 Primer Cuatrimestre 12/06/2017 Parcial enunciado + resolución (pdf)
2016 Segundo Cuatrimestre 02/11/2016 Parcial enunciado + resolución (pdf)
2016 Primer Cuatrimestre 08/06/2016 Parcial enunciado (pdf)
2014 Segundo Cuatrimestre 15/11/2014 Parcial enunciado parte 1 (pdf) , enunciado parte 2 (pdf)
2014 Primer Cuatrimestre 14/06/2014 Parcial enunciado + resolución (pdf)

Compilado de parciales

Finales

Año Mes Fecha Quién tomó/Quienes tomaron Links
2023 Marzo 08/03/2023 Esteban Feuerstein enunciado (pdf)
2023 Marzo 01/03/2023 Pablo Brusco enunciado (wikitexto)
2023 Febrero 23/02/2023 Nicolás D'Ippolito enunciado (wikitexto) , resolución (pdf)
2022 Agosto 12/09/2022 Ariel Bendersky enunciado (wikitexto)
2022 Agosto 03/08/2022 Ariel Bendersky enunciado (wikitexto) , resolución (pdf)
2021 Agosto 11/08/2021 enunciado (wikitexto)
2021 Abril 21/04/2021 enunciado (pdf) , resolución (pdf)
2021 Marzo 04/03/2021 enunciado (pdf) , resolución (pdf)
2021 Febrero 25/02/2021 enunciado (pdf)
2019 Diciembre 20/12/2019 Nicolás D'Ippolito enunciado (wikitexto)
2019 Diciembre 06/12/2019 Nicolás D'Ippolito enunciado (wikitexto)
2018 Julio 20/07/2018 Francisco Soulignac enunciado (wikitexto)
2018 Marzo 01/03/2018 Francisco Soulignac enunciado (wikitexto)
2018 Febrero 22/02/2018 Carlos Gustavo Lopez Pombo enunciado (wikitexto)
2017 Diciembre 13/12/2017 Carlos Gustavo Lopez Pombo enunciado (wikitexto)
2017 Septiembre 20/09/2017 Carlos Gustavo Lopez Pombo enunciado + resolución (wikitexto)
2017 Mayo 03/05/2017 Esteban Feuerstein enunciado + resolución (wikitexto)
2017 Marzo 10/03/2017 Esteban Feuerstein enunciado + resolución (wikitexto)
2016 Diciembre 20/12/2016 enunciado + resolución (pdf)
2016 Diciembre 13/12/2016 enunciado (wikitexto)
2016 Febrero 25/02/2016 Fernando Schapachnik enunciado (wikitexto)
2015 Febrero 15/02/2015 Charlie enunciado (wikitexto)
2015 Diciembre 10/12/2015 Esteban Feuerstein, Charlie y Fernando Schapachnik enunciado (wikitexto)
2015 Julio 30/07/2015 Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik enunciado (wikitexto)
2015 Febrero 27/02/2015 Esteban Feuerstein y Flavia Bonomo enunciado (wikitexto)
2015 Febrero 20/02/2015 enunciado (wikitexto)
2014 Diciembre ??/12/2014 Charlie enunciado (wikitexto)
2014 Julio ??/07/2014 Esteban Feuerstein y Chapa enunciado (wikitexto)
2013 Diciembre ??/12/2021 enunciado (wikitexto)
2013 Diciembre ??/12/2013 Esteban Feuerstein y Fernando Schapachnik enunciado (wikitexto)
2013 Diciembre ??/12/2013 Esteban Feuerstein y Fernando Schapachnik enunciado (wikitexto)
2012 Diciembre ??/12/2012 Esteban Feuerstein y Fernando Schapachnik enunciado (wikitexto)
2011 Julio ??/07/2011 enunciado (wikitexto)
2011 Marzo 10/03/2011 enunciado (wikitexto)
2009 Diciembre ??/12/2009 enunciado (wikitexto)
2008 Julio ??/07/2008 enunciado (wikitexto)
2007 Diciembre ??/12/2007 Esteban Feuerstein y Fernando Schapachnik enunciado (wikitexto)
  • Compilado de finales resueltos PDF

Apuntes

Bibliografía recomendada

  • R. Sedgewick, Algorithms in C Partes I-IV (1998). Addison Wesley. Toca casi todos los temas de la materia.
  • Bratley P. Brassard G. Fundamental of Algorithmics. International series of monographs on physics.Prentice Hall, 1995. Explica bastante bien la parte de complejidad.
  • Thomas Cormen; Charles Leirserson; Ronald Rivest y Clifford Stein, Introduction to algorithms, MIT Press, 2001 (Circulante 681 332 Cormen en la Biblioteca Central)
  • ACM Vol. 32.3 (Julio de 1985), pags. 652--686. link: [1]. Es el paper que desarrolla los Splay Trees.
  • Ronald Fagin et al. Extendible Hashing—a Fast Access Method for Dynamic Files. ACM Transactions on Database Systems 4.3 (sep. de 1979), págs. 315-344. issn: 0362-5915. doi:10.1145/320083.320092. Es el paper que desarrolla el método de Hashing Extensible (o Hashing Dinámico).

Enlaces externos
Obtenido de «https://www.cubawiki.com.ar/index.php?title=Algoritmos_y_Estructuras_de_Datos&oldid=15547»