Algoritmos y Estructuras de Datos

De Cuba-Wiki
Revisión del 18:57 28 feb 2024 de JonnyQueso (discusión | contribs.) (Agregue Final 20/02/24, Estaba solo en la pagina de la materia del plan viejo, pero incluye version del plan nuevo.)
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 10 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

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)

Parciales

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)
2023 Segundo Cuatrimestre 12/12/2023 Recuperatorio enunciado (pdf) + Resolución

Finales

Año Mes Fecha Quién tomó/Quienes tomaron Links
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