Diferencia entre revisiones de «Algoritmos y Estructuras de Datos»
De Cuba-Wiki
(enunciado primer parcial 7/10/2023) |
|||
| (No se muestran 59 ediciones intermedias de 21 usuarios) | |||
| Línea 1: | Línea 1: | ||
{{Plan 2023|Algoritmos y Estructuras de Datos II}} | |||
{{Materia | |||
| anoCursada=Primer año | |||
| cargaHoraria=15 horas semanales | |||
| correlativas=[[Álgebra I]] e [[Introducción a la Programación]] | |||
| correlativaDe=[[Paradigmas de Programación]], [[Técnicas de Diseño de Algoritmos]], [[Lenguajes Formales, Autómatas y Computabilidad]] y [[Álgebra Lineal Computacional]] | |||
}} | |||
'''Algoritmos y Estructuras de Datos''' es una materia obligatoria de la [[Licenciatura en Ciencias de la Computación]], incluida también en su título intermedio [[Bachiller Universitario en Computación]]. En ella se enseñan técnicas de especificación, validación y verificación formal de algoritmos, y se definen los tipos abstractos de datos fundamentales, diseñando estructuras de datos y algoritmos eficientes para su implementación, entendiendo cómo impactan las distintas decisiones estructurales en la complejidad de los algoritmos y en la interfaz de los tipos abstractos. | |||
== Información general sobre la cursada == | == Información general sobre la cursada == | ||
Algoritmos | 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 == | == Contenidos == | ||
| Línea 12: | Línea 18: | ||
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. | 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 | |||
[ | == Prácticas == | ||
*[https://gitlab.com/valn/uba/-/tree/main/Algoritmos%20y%20Estructuras%20de%20Datos%20(ex%20Algo%20II) Prácticas 4,5, y 7 resueltas + clases teóricas (PDFs) + primer parcial resuelto por valn / valnrms] | |||
*[https://github.com/tomihq/aed-2/tree/main/guias Guías resueltas (1er cuatrimestre 2024)] | |||
*[https://ubauba-my.sharepoint.com/:o:/g/personal/grunt_uba_ar/EsQDqzb7t5tLgmf0uQNlackBpWDsIE1o5EpdXBCtQt0LyA Cuaderno de Grunt con multiples ejercicios hechos de guías, parciales y finales] | |||
== Talleres de programación == | |||
*[https://github.com/laurabailleres/algo2 Talleres de programación 1C2024] | |||
*[https://github.com/tomihq/aed-2/tree/main/talleres Talleres Resueltos 1C2024] | |||
*[https://github.com/ | |||
*[https:// | |||
== Trabajos Prácticos == | == Trabajos Prácticos == | ||
| Línea 54: | Línea 38: | ||
! Año !! Cuatrimestre !! Fecha !! Links | ! Año !! Cuatrimestre !! Fecha !! Links | ||
|- | |- | ||
|| 2023 || Segundo Cuatrimestre || 17/09/2023 || [[Medio:AED tp 2023-09-17 enunciado.pdf| | || 2023 || Segundo Cuatrimestre || 17/09/2023 || [[Medio:AED tp 2023-09-17 enunciado.pdf|Enunciado TP 1 (pdf)]] | ||
|- | |- | ||
|| 2023 || Segundo Cuatrimestre || 11/11/2023 || [[Medio:TP2-Enunciado.pdf|Enunciado TP 2 (pdf)]] | |||
|- | |||
|| 2024 || Segundo Cuatrimestre || 15/09/2024 || [[Medio:AED_TP_150924.pdf|Enunciado TP 1 (pdf)]] | |||
|} | |} | ||
| Línea 61: | Línea 48: | ||
=== Primeros parciales === | === Primeros parciales === | ||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
! Año !! Cuatrimestre !! Fecha !! Instancia !! Links | ! Año !! Cuatrimestre !! Fecha !! Instancia !! Links | ||
|- | |- | ||
|| 2023 || Segundo Cuatrimestre || 7/10/2023 || Parcial || [[Medio:AyEDprimerparcial-7-10-2023.pdf|enunciado | || 2023 || Segundo Cuatrimestre || 7/10/2023 || Parcial || [[Medio:AyEDprimerparcial-7-10-2023.pdf|enunciado (pdf) ]] | ||
|- | |- | ||
|- | |- | ||
|| | || 2023 || Segundo Cuatrimestre || 7/10/2023 || Parcial || [[Medio:PrimerParcial2023-AED.pdf|Enunciado + Resolución (pdf)]] | ||
|- | |- | ||
|| | || 2023 || Segundo Cuatrimestre || 10/10/2023 || Parcial || [[Medio:AyEDprimerparcial-segundaMesa-10-10-2023.jpg|enunciado (jpg) ]] [[Medio:MOA - Primer Parcial de AED (2C-2023).pdf|enunciado + resolución (pdf)]] | ||
|- | |- | ||
|- | |- | ||
|| | || 2024 || Primer Cuatrimestre || 03/04/2024 || Parcial || [[Medio:AED2_1parcial_03-04-24v2.pdf|Enunciado + Resolución (pdf) ]] | ||
|- | |- | ||
|- | |- | ||
|| | || 2024 || Primer Cuatrimestre || 10/07/2024 || Recuperatorio || [[Medio:AED2_1recu_10-07-24.pdf |Enunciado + Resolución (pdf) ]] | ||
|- | |- | ||
|- | |- | ||
|} | |} | ||
| Línea 107: | Línea 70: | ||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
! Año !! Cuatrimestre !! Fecha !! Instancia !! Links | ! Año !! Cuatrimestre !! Fecha !! Instancia !! Links | ||
|- | |||
|| 2024 || Primer Cuatrimestre || 28/06/2024 || Parcial || [[Medio:segundo_parcial_AED.pdf|Enunciado + Resolución (por Magui) (pdf) ]] | |||
|- | |- | ||
|- | |- | ||
|| | || 2024 || Primer Cuatrimestre || 03/04/2024 || Parcial || [[Medio:AED2_2parcial_03-04-24.pdf|Enunciado + Resolución (pdf) ]] | ||
|- | |- | ||
|- | |- | ||
|| | || 2023 || Segundo Cuatrimestre || 25/11/2023 || Parcial || [[Medio:AyEDsegundoparcial-25-11-2023.pdf|enunciado (pdf) ]] [[Medio:MOA - Segundo Parcial de AED (2C-2023) compressed.pdf|enunciado + resolución (pdf)]] | ||
|- | |- | ||
|- | |- | ||
|| | || 2023 || Segundo Cuatrimestre || 25/11/2023 || Parcial || [[Medio:SegundoParcial2023-AED.pdf|Enunciado + Resolución (pdf)]] | ||
|- | |||
|| 2023 || Segundo Cuatrimestre || 12/12/2023 || Recuperatorio || [[Enlace:https://ubauba-my.sharepoint.com/:b:/g/personal/grunt_uba_ar/EYg6Ug2BltdEuwFKqzjy-JYB9UeqcgReWPZBPFC2MNVW3w?e=0OphAx|enunciado (pdf) + Resolución ]] | |||
|- | |- | ||
|| | || 2023 || Segundo Cuatrimestre || 12/12/2023 || Recuperatorio || [[Medio:12-12-2023_Thomas_compressed.pdf|enunciado + Resolución 2 (PDF)]] | ||
|- | |- | ||
|- | |- | ||
|} | |} | ||
== Finales == | |||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
! Año !! Mes !! Fecha !! Quién tomó/Quienes tomaron !! Links | ! Año !! Mes !! Fecha !! Quién tomó/Quienes tomaron !! Links | ||
|- | |- | ||
|| | || 2024|| Marzo|| 05/03/2024|| Esteban Feuerstein || [[Final 05/03/24 (Algoritmos II)|enunciado (wikitexto) ]] | ||
|- | |- | ||
|| | || 2024|| Febrero|| 26/02/2024|| Víctor Braberman || [[Final 26/02/24 (Algoritmos II)|enunciado (wikitexto) ]] | ||
|- | |- | ||
|| | || 2024|| Febrero|| 20/02/2024|| Víctor Braberman || [[Final 20/02/24 (Algoritmos II)|enunciado (wikitexto) ]] | ||
|- | |- | ||
|} | |} | ||
== Apuntes == | == Apuntes == | ||
*[https://github.com/igruntplay/apunte-primer-parcial-aed/blob/main/apunte_para_el_1er_parcial_AED.pdf Hoja de apunte para el primer parcial AED plan 23] | |||
*[https://docs.google.com/spreadsheets/d/1cs_Up3N2bc84l0cupEuzR8KOLdJ1d1V2Ml8gtkl1rnU/edit#gid=0 Excel 2.0 preguntas/respuestas finales (editable por cualquiera a conciencia, se agradece cualquier contribucion o mejora)] | *[https://docs.google.com/spreadsheets/d/1cs_Up3N2bc84l0cupEuzR8KOLdJ1d1V2Ml8gtkl1rnU/edit#gid=0 Excel 2.0 preguntas/respuestas finales (editable por cualquiera a conciencia, se agradece cualquier contribucion o mejora)] | ||
*[https://github.com/Sponja-/resumen-final-aed2/releases/latest/download/resumen-aed2.pdf "Resumen" para el final (2022).] [https://github.com/Sponja-/resumen-final-aed2 Repositorio en GitHub.] | *[https://github.com/Sponja-/resumen-final-aed2/releases/latest/download/resumen-aed2.pdf "Resumen" para el final (2022).] [https://github.com/Sponja-/resumen-final-aed2 Repositorio en GitHub.] | ||
| Línea 252: | Línea 112: | ||
*[https://github.com/FerFrassia/Algo2/files/2216488/Sorting.pdf Apunte de Sorting.] [https://github.com/FerFrassia/Algo2/ Código fuente en GitHub.] | *[https://github.com/FerFrassia/Algo2/files/2216488/Sorting.pdf Apunte de Sorting.] [https://github.com/FerFrassia/Algo2/ Código fuente en GitHub.] | ||
*[https://docs.google.com/spreadsheets/d/1k1LTX-qF_-eGeR3UwuvmAR4JsKLqk2vHsV6Bhmpen38/edit#gid=0 Googlesheet con respuestas de alumnes para el final de algoritmos 2] | *[https://docs.google.com/spreadsheets/d/1k1LTX-qF_-eGeR3UwuvmAR4JsKLqk2vHsV6Bhmpen38/edit#gid=0 Googlesheet con respuestas de alumnes para el final de algoritmos 2] | ||
*[[Medio:AED_apunte_2023_Tomas-Lisazo.pdf| Apunte completo de Tomi 2023 (actualizado al plan nuevo)]] | |||
*[https://github.com/nachodall/UBA-FCEN-AyED-AyED2 Repositorio de la materia (no oficial) de nachodall con guías y apuntes] | |||
*[https://github.com/tomihq/aed-2 Resumen de la materia (1er cuatrimestre 2024) con las guías resueltas y laboratorios] | |||
== Bibliografía recomendada == | == Bibliografía recomendada == | ||
Revisión actual - 02:47 31 oct 2024
Esta página es sobre la materia del plan de estudios 2023. Para ver la materia del plan 1993, consultar Algoritmos y Estructuras de Datos II.
Algoritmos y Estructuras de Datos
| Año | Primer año |
|---|---|
| Carga horaria | 15 horas semanales |
| Correlativas | Álgebra I e Introducción a la Programación |
| Correlativa de | Paradigmas de Programación, Técnicas de Diseño de Algoritmos, Lenguajes Formales, Autómatas y Computabilidad y Álgebra Lineal Computacional |
Algoritmos y Estructuras de Datos es una materia obligatoria de la Licenciatura en Ciencias de la Computación, incluida también en su título intermedio Bachiller Universitario en Computación. En ella se enseñan técnicas de especificación, validación y verificación formal de algoritmos, y se definen los tipos abstractos de datos fundamentales, diseñando estructuras de datos y algoritmos eficientes para su implementación, entendiendo cómo impactan las distintas decisiones estructurales en la complejidad de los algoritmos y en la interfaz de los tipos abstractos.
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
Prácticas
- Prácticas 4,5, y 7 resueltas + clases teóricas (PDFs) + primer parcial resuelto por valn / valnrms
- Guías resueltas (1er cuatrimestre 2024)
- Cuaderno de Grunt con multiples ejercicios hechos de guías, parciales y finales
Talleres de programación
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) |
| 2024 | Segundo Cuatrimestre | 15/09/2024 | Enunciado TP 1 (pdf) |
Parciales
Primeros parciales
| Año | Cuatrimestre | Fecha | Instancia | Links |
|---|---|---|---|---|
| 2023 | Segundo Cuatrimestre | 7/10/2023 | Parcial | enunciado (pdf) |
| 2023 | Segundo Cuatrimestre | 7/10/2023 | Parcial | Enunciado + Resolución (pdf) |
| 2023 | Segundo Cuatrimestre | 10/10/2023 | Parcial | enunciado (jpg) enunciado + resolución (pdf) |
| 2024 | Primer Cuatrimestre | 03/04/2024 | Parcial | Enunciado + Resolución (pdf) |
| 2024 | Primer Cuatrimestre | 10/07/2024 | Recuperatorio | Enunciado + Resolución (pdf) |
Segundos parciales
| Año | Cuatrimestre | Fecha | Instancia | Links |
|---|---|---|---|---|
| 2024 | Primer Cuatrimestre | 28/06/2024 | Parcial | Enunciado + Resolución (por Magui) (pdf) |
| 2024 | Primer Cuatrimestre | 03/04/2024 | Parcial | Enunciado + Resolución (pdf) |
| 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 |
| 2023 | Segundo Cuatrimestre | 12/12/2023 | Recuperatorio | enunciado + Resolución 2 (PDF) |
Finales
| Año | Mes | Fecha | Quién tomó/Quienes tomaron | Links |
|---|---|---|---|---|
| 2024 | Marzo | 05/03/2024 | Esteban Feuerstein | enunciado (wikitexto) |
| 2024 | Febrero | 26/02/2024 | Víctor Braberman | enunciado (wikitexto) |
| 2024 | Febrero | 20/02/2024 | Víctor Braberman | enunciado (wikitexto) |
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)
- Repositorio de la materia (no oficial) de nachodall con guías y apuntes
- Resumen de la materia (1er cuatrimestre 2024) con las guías resueltas y laboratorios
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).
