Edición de «Algoritmos y Estructuras de Datos»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{Plan 2023|Algoritmos y Estructuras de Datos II}}
'''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.


{{Materia
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]]
  | 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 ==
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. Al menos hasta el segundo cuatrimestre 2016, en el que se cambió el TP0 por 5 talleres de C++ obligatorios que fueron presentando durante la cursada, teniendo una semana para entregar cada uno.


== Información general sobre la cursada ==
== Trabajos prácticos ==
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.
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 [[Lenguaje: Cpp|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 es 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 tienen 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 ==
== Contenidos ==
Línea 18: Línea 25:
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.
*[[Tipos Abstractos de Datos]] (TADs)
*Métodos de demostración formal de correctitud (ej. weakest precondition). Teorema del invariante.
*[[Inducción Estructural]]
*Análisis básico de algoritmos: análisis asintótico, modelo RAM. Caso peor, promedio y mejor.
*[[Sorting]]
*Impacto de la complejidad algorítmica en el [[diseño]] de estructuras de datos ([[Tipos Abstractos de Datos]]).
*[[Estructuras de Datos]]
*Algoritmos de búsqueda y ordenamiento básicos y avanzados (Sorting).
*[[Eliminación de la Recursión]]
*Estructuras para búsqueda y ordenamiento: árboles de búsqueda, árboles balanceados, árboles digitales, hashing, colas de prioridad. Tipos de datos inductivos
*[[Diseño]]
 
== Guías prácticas ==
Las guías de ejercicios correspondientes al cuatrimestre en curso pueden encontrarse en la página oficial de la materia.


== Prácticas ==
<!--[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-1/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]


== Trabajos Prácticos ==
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-2-1/at_download/file Practica 2]: Inducción estrutural.
{| class="wikitable sortable"
 
! Año  !! Cuatrimestre        !! Fecha    !! Links
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-3-1/at_download/file Practica 3]: Diseño -- invariante de representación y función de abstracción.
|-
 
|| 2023 || Segundo Cuatrimestre || 17/09/2023 || [[Medio:AED tp 2023-09-17 enunciado.pdf|Enunciado TP 1 (pdf)]]
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-4-1/at_download/file Practica 4]: Ordenes y complejidad algorítmica.
|-
 
|-
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-5-1/at_download/file Practica 5]: Diseño.
|| 2023 || Segundo Cuatrimestre || 11/11/2023 || [[Medio:TP2-Enunciado.pdf|Enunciado TP 2 (pdf)]]
 
|}
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-6-1/at_download/file Practica 6]: Divide and Conquer.
 
[http://dc.uba.ar/materias/aed2/2015/2c/descargas/practicas/practica-7-1/at_download/file Practica 7]: Ordenamiento.-->
 
=== Guías prácticas de segundo cuatrimestre de 2017 resuelta ===
 
*[[AED2_resumen_2C-17|Práctica 1]]


== Parciales ==
== Parciales ==


=== Primeros parciales ===
=== Primeros parciales ===
{| class="wikitable sortable"
 
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
*[[Medio:Algo2-1erParcial2014-2c-parte1.jpg|1er Parcial, 2do cuatrimestre 2014 (parte 1)]] [[Medio:Algo2-1erParcial2014-2c-parte2.jpg|(parte 2)]]
|-
*[[Medio:AED2_1parcial_23-04-16_resuelto.pdf|1er Parcial, 1er cuatrimestre 2016 (resuelto)]]
|| 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)]]
*[[Medio:AED2_1parcial_16-09-16_resuelto.pdf|1er Parcial, 2do cuatrimestre 2016 (resuelto)]]
|-
*[[Medio:Algo2-1erRecu-2docuatri-2016.pdf|1er Parcial - Recuperatorio, 2do cuatrimestre 2016 (Resueltos ej 1 y 2)]]
|-
*[[Medio:AED2_1parcial_03-05-17_resuelto.pdf|1er Parcial, 1er cuatrimestre 2017 (resuelto)]]
|| 2023 || Segundo Cuatrimestre || 7/10/2023 || Parcial || [[Medio:AyEDprimerparcial-7-10-2023.pdf|enunciado (pdf) ]]
*[[Medio:AED2_1parcial_30-09-17_resuelto.pdf|1er Parcial, 2do cuatrimestre 2017 (resuelto)]]
|-
*[[Medio:AED2_1Parcial_05-25-18_resuelto.pdf|1er Parcial, 1er cuatrimestre 2018 (resuelto)]]
|-
|| 2023 || Segundo Cuatrimestre || 10/10/2023 || Parcial || [[Medio:PrimerParcial2023-AED.pdf|Enunciado + Resolución (pdf)]]
|}


=== Segundos parciales ===
=== Segundos parciales ===
{| class="wikitable sortable"
 
! Año  !! Cuatrimestre        !! Fecha      !! Instancia    !! Links
*[[Medio:AED2_2parcial_14-06-14.pdf|2do Parcial (resuelto), 1er cuatrimestre 2014]]
|-  
*[[Medio:Algo2-2doParcial2014-2c-parte1.jpeg|2do Parcial, 2do cuatrimestre 2014 (parte 1)]] [[Medio:Algo2-2doParcial2014-2c-parte2.jpg|(parte 2)]]
|| 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)]]
*[[Recuperatorio_Segundo_Parcial_1C/2015_(Algoritmos_II)|Recuperatorio 2do Parcial, 1er cuatrimestre 2015]]
|-
*[[Medio:AED2_2parcial_08-06-16.pdf|2do Parcial, 1er cuatrimestre 2016]]
|-
*[[Medio:AED2_2parcial_02-11-16_Resuelto.pdf|2do Parcial, 2do cuatrimestre 2016 (resuelto)]]
|| 2023 || Segundo Cuatrimestre || 25/11/2023 || Parcial || [[Medio:SegundoParcial2023-AED.pdf|Enunciado + Resolución (pdf)]]
*[[Medio:AED2_2parcial_12-06-17_resuelto.pdf|2do Parcial, 1er cuatrimestre 2017 (resuelto)]]
|-
*[[Medio:AED2_2parcial_resuelto.pdf|2do Parcial, 2do cuatrimestre 2017 (resuelto)]]
|| 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 ]]
*[[Medio:AED2_2Parcial_23-06-18_resuelto.pdf|2do Parcial, 1er cuatrimestre 2018 (resuelto)]]
|-
|}


== Finales ==
== Finales ==
{| class="wikitable sortable"
*[[Final 1C/2006 (Algoritmos II)|Final del primer cuatrimestre de 2006]]
! Año  !! Mes        !! Fecha      !! Quién tomó/Quienes tomaron !! Links
*[[Final 2C/2006 (Algoritmos II)|Final del segundo cuatrimestre de 2006]]
|-
*[[Final 1C/2007 (Algoritmos II)|Final del primer cuatrimestre de 2007]]
|| 2024|| Marzo|| 05/03/2024|| Esteban Feuerstein || [[Final 05/03/24 (Algoritmos II)|enunciado (wikitexto) ]]
*[[Final 1/2C/2007 (Algoritmos II)|Final del segundo cuatrimestre de 2007 (1)]]
|-
*[[Final 2/2C/2007 (Algoritmos II)|Final del segundo cuatrimestre de 2007 (2)]]
|| 2024|| Febrero|| 26/02/2024|| Víctor Braberman || [[Final 26/02/24 (Algoritmos II)|enunciado (wikitexto) ]]
*[[Final 2/2C/2008 (Algoritmos II)|Final del primer cuatrimestre de 2008]]
|-
*[[Final 2/2C/2009 (Algoritmos II)|Final del segundo cuatrimestre de 2009 (1)]]
|| 2024|| Febrero|| 20/02/2024|| Víctor Braberman || [[Final 20/02/24 (Algoritmos II)|enunciado (wikitexto) ]]
*[[Final 2/2C/2009 (Algoritmos II) (2) |Final del segundo cuatrimestre de 2009 (2)]]
|-
*[[Final 1C/2010 (Algoritmos II)|Final del primer cuatrimestre de 2010]]
|}
*[[Final 1C/2011 (Algoritmos II)|Final del primer cuatrimestre de 2011]]
*[[Final 10/3/2011 (Algoritmos II)|Final del 10/3/11]]
*[[Final 2C/2012 (Algoritmos II)|Final del segundo cuatrimestre de 2012]]
*[[Final 1C/2013 (Algoritmos II)|Final del primer cuatrimestre de 2013 (1)]]
*[[Final 1C/2013 2 (Algoritmos II)|Final del primer cuatrimestre de 2013 (2)]]
*[[Final 2C/2013 (Algoritmos II)|Final del segundo cuatrimestre de 2013]]
*[[Final 1C/2014 (Algoritmos II)|Final del primer cuatrimestre de 2014]]
*[[Final 2C/2014 (Algoritmos II)|Final del segundo cuatrimestre de 2014]]
*[[Final 20/2/2015 (Algoritmos II)|Final del 20/2/15]]
*[[Final 27/2/2015 (Algoritmos II)|Final del 27/2/15]]
*[[Final 30/7/2015 (Algoritmos II)|Final del 30/7/15]]
*[[Final 10/12/2015 (Algoritmos II)|Final del segundo cuatrimestre de 2015 (1, 2 y 3)]]
*[[Final 15/02/2015 (Algoritmos II)|Final del 15/02/16]]
*[[Final 25/02/2016 (Algoritmos II)|Final del 25/02/16]]
*[[Final 13/12/2016 (Algoritmos II)|Final del 13/12/16]]
*[[Final 20/12/2016 (Algoritmos II)|Final del 20/12/16 (Resuelto)]]
*[[Final 10/03/17 (Algoritmos II)|Final del 10/03/17]]
*[[Final 03/05/17 (Algoritmos II)|Final del 03/05/17]]
*[[Final 20/09/17 (Algoritmos II)|Final del 20/09/17]]
*[[Final 13/12/17 (Algoritmos II)|Final del 13/12/17]]
*[[Final 22/02/18 (Algoritmos II)|Final del 22/02/18]]
*[[Final 01/03/18 (Algoritmos II)|Final del 01/03/18]]
*[[Final 20/07/18 (Algoritmos II)|Final del 20/07/18]]


== 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://github.com/guidotag/AVL/raw/master/documento/main.pdf Balanceo de árboles y árboles AVL]: Notas sobre balanceo de árboles en general, profundizando en la implementación de árboles AVL.
*[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.]
*[[Medio:AED2_apunte_final_2021.pdf|Apunte teórico de la materia (2021)]]
*[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.
*[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.]
*[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.]
*[[Medio:AED2_apunte_disenio_subrayado.pdf| Apunte de diseño de la materia subrayado]]
*[[Medio:AED2_apunte_disenio_subrayado.pdf| Apunte de diseño de la materia subrayado]]
*[[Medio:AED2_apunte_especificacion_subrayado.pdf| Apunte de conceptos de especificación de la materia subrayado]]
*[[Medio:AED2_apunte_especificacion_subrayado.pdf| Apunte de conceptos de especificación de la materia subrayado]]
*[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]
*[[Medio:AED_apunte_2023_Tomas-Lisazo.pdf| Apunte completo de Tomi 2023 (actualizado al plan nuevo)]]


== 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 ==
*[https://www.youtube.com/channel/UC4iUWhAWlMZkkJDCqyzz2hw/featured Canal de Youtube AED2 - DC - UBA]
*[http://www.dc.uba.ar/materias/aed2/ Página oficial de la materia]
*[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]


Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantillas usadas en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Algoritmos_y_Estructuras_de_Datos»