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 (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) |
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
- Hoja de apunte para el primer parcial AED plan 23
- Excel 2.0 preguntas/respuestas finales (editable por cualquiera a conciencia, se agradece cualquier contribucion o mejora)
- "Resumen" para el final (2022). Repositorio en GitHub.
- Apunte teórico de la materia (2021)
- Balanceo de árboles y árboles AVL: Notas sobre balanceo de árboles en general, profundizando en la implementación de árboles AVL.
- Resumen bastante completo. Toca los 4 temas principales de la materia: especificación, diseño, algoritmos y estructuras. Código fuente del resumen en GitHub.
- Apunte de diseño de la materia subrayado
- Apunte de conceptos de especificación de la materia subrayado
- Apunte de Sorting. Código fuente en GitHub.
- Googlesheet con respuestas de alumnes para el final de algoritmos 2
- Apunte completo de Tomi 2023 (actualizado al plan nuevo)
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).
