Diferencia entre revisiones de «Algoritmos y Estructuras de Datos»

De Cuba-Wiki
Sin resumen de edición
 
(No se muestran 290 ediciones intermedias de 91 usuarios)
Línea 1: Línea 1:
'''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.
{{Plan 2023|Algoritmos y Estructuras de Datos II}}


Según el [[Plan de la Carrera]] es una materia a ser cursada en [[Plan de la Carrera#Segundo año|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]]
{{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]]
}}


== Información General sobre la Cursada ==
'''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.
Algoritmos II consiste de clases teóricas y prácticas. Para aprobar la materia se deben rendir 2 exámenes parciales y 4 trabajos prácticos.


== Trabajos Prácticos ==
== Información general sobre la cursada ==
La materia tiene 4 Trabajos Prácticos. El '''TP0''' es un trabajo corto cuyo objetivo es hacer que el alumno tome contacto y se acostumbre al desarrollo de estructuras de datos en [[Lenguaje: Cpp|C++]].
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.
 
Los otros 3 Trabajos Prácticos consisten 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 es promocionable. La condición de promoción del último cuatrimestre (2do Cuatri 2012) fue tener entre los 2 exámenes 4 ejercicios aprobados y ninguno insuficiente.


== Contenidos ==
== Contenidos ==
Cuando se habla de especificación formal de tipos de datos (tambien conocidos como TADs) se refiere a expresar el comportamiento que va a tener en funcion 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 ambiguedad que se podría producir si se hace en lenguaje castellano.
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 asi 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.


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


== Prácticas (2014) ==
== Prácticas ==
[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica1/at_download/file Practica 1]: Tipos algebraicos y especificación.
*[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]


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica2/at_download/file Practica 2]: Inducción estrutural.
== 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]


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica3/at_download/file Practica 3]: Diseño -- invariante de representación y función de abstracción.
== Trabajos Prácticos ==
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha    !! Links
|-
|| 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)]]
|}


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica4/at_download/file Practica 4]: Ordenes y complejidad algorítmica.
== Parciales ==


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica5/at_download/file Practica 5]: Diseño.
=== Primeros parciales ===
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
|-
|| 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) ]]
|-
|-
|}


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica6/at_download/file Practica 6]: Divide and Conquer.
=== Segundos parciales ===
{| class="wikitable sortable"
! 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)]]
|-
|-
|}


[http://www.dc.uba.ar/materias/aed2/2014/1c/descargas/practicas/practica7/at_download/file Practica 7]: Ordenamiento.
== Finales ==
{| class="wikitable sortable"
! 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) ]]
|-
|}


== Finales ==
== Apuntes ==
*[[Final 1C/2006 (Algoritmos II)|Final del primer cuatrimestre de 2006]]
*[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]
*[[Final 2C/2006 (Algoritmos II)|Final del segundo cuatrimestre de 2006]]
*[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)]
*[[Final 1C/2007 (Algoritmos II)|Final del primer cuatrimestre de 2007]]
*[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.]
*[[Final 1/2C/2007 (Algoritmos II)|Final del segundo cuatrimestre de 2007 (1)]]
*[[Medio:AED2_apunte_final_2021.pdf|Apunte teórico de la materia (2021)]]
*[[Final 2/2C/2007 (Algoritmos II)|Final del segundo cuatrimestre de 2007 (2)]]
*[https://github.com/CubaWiki/AED2-ApunteRotacionesAVL-gtagliavini/raw/master/main.pdf Balanceo de árboles y árboles AVL]: Notas sobre balanceo de árboles en general, profundizando en la implementación de árboles AVL.
*[[Final 2/2C/2008 (Algoritmos II)|Final del primer cuatrimestre de 2008]]
*[https://github.com/CubaWiki/AED2-ApunteFinal-Rama/releases/download/1.2/resumen.pdf Resumen bastante completo.] Toca los 4 temas principales de la materia: especificación, diseño, algoritmos y estructuras. [https://github.com/CubaWiki/AED2-ApunteFinal-Rama Código fuente del resumen en GitHub.]
*[[Final 2/2C/2009 (Algoritmos II)|Final del segundo cuatrimestre de 2009 (1)]]
*[[Medio:AED2_apunte_disenio_subrayado.pdf| Apunte de diseño de la materia subrayado]]
*[[Final 2/2C/2009 (Algoritmos II) (2) |Final del segundo cuatrimestre de 2009 (2)]]
*[[Medio:AED2_apunte_especificacion_subrayado.pdf| Apunte de conceptos de especificación de la materia subrayado]]
*[[Final 1C/2010 (Algoritmos II)|Final del primer cuatrimestre de 2010]]
*[https://github.com/FerFrassia/Algo2/files/2216488/Sorting.pdf Apunte de Sorting.] [https://github.com/FerFrassia/Algo2/ Código fuente en GitHub.]
*[[Final 1C/2011 (Algoritmos II)|Final del primer cuatrimestre de 2011]]
*[https://docs.google.com/spreadsheets/d/1k1LTX-qF_-eGeR3UwuvmAR4JsKLqk2vHsV6Bhmpen38/edit#gid=0 Googlesheet con respuestas de alumnes para el final de algoritmos 2]
*[[Final 2C/2012 (Algoritmos II)|Final del segundo cuatrimestre de 2012]]
*[[Medio:AED_apunte_2023_Tomas-Lisazo.pdf| Apunte completo de Tomi 2023 (actualizado al plan nuevo)]]
*[[Final 1C/2013 (Algoritmos II)|Final del primer cuatrimestre de 2013 (1)]]
*[https://github.com/nachodall/UBA-FCEN-AyED-AyED2 Repositorio de la materia (no oficial) de nachodall con guías y apuntes]
*[[Final 1C/2013 2 (Algoritmos II)|Final del primer cuatrimestre de 2013 (2)]]
*[https://github.com/tomihq/aed-2 Resumen de la materia (1er cuatrimestre 2024) con las guías resueltas y laboratorios]
*[[Final 2C/2013 2 (Algoritmos II)|Final del segundo cuatrimestre de 2013 (2)]]


== Bibliografía Recomendada ==
== 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]])
*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: [https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf]. 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 ==
== Enlaces externos ==
*[http://www.dc.uba.ar/materias/aed2/ Página oficial de la materia]
*[https://www.youtube.com/channel/UC4iUWhAWlMZkkJDCqyzz2hw/featured Canal de Youtube AED2 - DC - UBA]
*[http://www.sorting-algorithms.com Demostraciones graficas de los distintos algortimos de sorting]
*[http://www.sorting-algorithms.com Demostraciones graficas de los distintos algortimos de sorting]


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

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

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=17603»