Algoritmos y Estructuras de Datos

De Cuba-Wiki

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, eliminación de la recursión, inducción estructural, métodos algoritmicos y algoritmos de sorting.

Según el Plan de la Carrera es una materia a ser cursada en Segundo año. Es correlativa de Algoritmos y Estructuras de Datos I y es necesaria para cursar Algoritmos y Estructuras de Datos III, Lógica y Computabilidad y Sistemas Operativos

Información general sobre la cursada

Algoritmos II 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 4 talleres del laboratorio, los cuales son de programacion en C++. Los talleres pueden ser entregados en cualquier momento de la cursada.
(Modalidad 1C2022).

Historia de los Trabajos prácticos

La materia tenía 4 Trabajos Prácticos. El TP0 era un trabajo corto cuyo objetivo era hacer que el alumno tome contacto y se acostumbre al desarrollo de estructuras de datos en C++.

Los otros 3 Trabajos Prácticos consistían en las 3 etapas (Especificación, Diseño, Implementación) de un problema dado. Los trabajos prácticos por lo general son bastante largos, pero sirven de buena experiencia para ese tipo de actividades.

Algoritmos II era promocionable. La condición de promoción del último cuatrimestre (2do Cuatri 2014) fue tener el primer ejercicio de cada parcial muy bien, y el resto todos bien, además de los 3 TPs aprobados con Muy Bien.

Desde el segundo cuatrimestre de 2016, los trabajos prácticos se vieron reducidos a tres, correspondientes con las tres etapas de un problema, y se dividió el TP0 en cinco talleres obligatorios, con otros dos opcionales. (En orden: programar una pila, uso de templates, un ABB, un Trie, iteradores (opcional), un diccionario sobre Hash Tables y uno de sorting (opcional)).

Para promocionar la materia según esta modalidad, se tenian que tener los dos primeros trabajos prácticos Muy Bien, el primer ejercicio de cada parcial Muy Bien, y ningún Regular o Insuficiente en los otros ejercicios.

Actualmente, en el segundo cuatrimestre de 2017, se eliminó la opción de promoción.

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.

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

Parciales

Primeros parciales

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