Estructuras de Datos

Back.png Volver a TPI | LIDS

Estructuras de Datos es una materia fundamental, por dos razones. Primero porque los conocimientos impartidos son esenciales para el resto de la carrera (y para que seas un buen programador) y segundo porque tiene una carga horario bastante grande, lo que genera que se complique cursar otras materias. Con lo cual, cuando te anotes es muy importante que le dediques todo el tiempo y el esfuerzo que puedas.

Cursada

Esta materia suele sufrir cambios de días y horarios. Probablemente curses 3 días por semana, 3 horas por día.

Se suelen tomar dos parciales y un trabajo práctico individual. Como todas las materias de la carrera, es promocionable. En caso de no promocionar hay una etapa de Integrador.

Hay una sola etapa para recuperar UN parcial. El trabajo práctico no se puede recuperar, no obstante se desarrolla a lo largo de varias semanas y hay muchas etapas de corrección.

Se utiliza Haskell como lenguaje de programación para los parciales y C++ para el trabajo práctico. Para la parte de Haskell se utiliza Hugs/WinHugs como REPL y un editor de código a elección (Sublime Text, Visual Studio Code, Vim, Notepad++, Atom, etc.). Para la parte de C++ se puede usar cualquier editor de código o entorno de desarrollo, siempre y cuando pueda compilar. Se propone usar Codeblocks, aunque no es obligatorio, y se puede descargar acá: http://www.codeblocks.org/downloads/binaries.

Página de la materia: https://sites.google.com/site/tpiedunq.

Hugs

Un REPL es una consola interactiva para testear código a medida que lo vamos creando. Lo usamos durante la cursada para probar todos los ejercicios.

Para instalarlo en distros basadas en Debian (Ubuntu, Mint, etc.). basta con escribir en la consola:

sudo apt-get install hugs

Para usarlo, primero nos movemos desde la terminal usando cd a la carpeta donde tenemos nuestros ejercicios (o abrimos la terminal desde esa carpeta), y escribimos hugs.

Para instalarlo en Windows se utiliza el instalador de WinHugs disponible en la siguiente página: https://www.haskell.org/hugs/pages/downloading-May2006.htm

Durante la instalación podríamos encontrarnos con el siguiente error:

Winhugs-error.png


Esto pasa porque el instalador no reconoce la carpeta de destino. Para solucionarlo, basta con cambiarla:

Winhugs-solucion.png

Si por algún motivo no podemos instalar Hugs, podemos probar usando GHCi como REPL, funciona de manera similar a Hugs (con la diferencia de que es mucho más pesado). También podemos utilizar la página Repl.it de forma online: https://repl.it/languages/haskell .

Temas

Distribución de los temas actualizada al primer cuatrimestre de 2019.

Primera Parte (Haskell):

  • Prácticas 1, 2 y 3:
  • Introducción a Haskell. Definiciones, expresiones básicas. Inferencia de tipos.
  • Listas.
  • Recursión sobre listas.
  • Tipos algebraicos (Maybe, Either, Nothing, enumerativos, registros, recursivos).
  • Árboles binarios. Árboles ternarios. Recursión sobre árboles.
  • Prácticas 4 y 5:
  • Tipos Abstractos de Datos. Conjuntos (Set). Pilas (Stack). Colas (Queue).
  • Nociones de interfaz, representación e invariante de representación/precondición. Roles.
  • Nociones básicas de eficiencia: peor caso y notación big-O (O(1), O(n), O(n2)).
  • Maps/Dict. y sus implementaciones (con listas en varias versiones, BSTs, AVLs).
  • Binary Heaps.

Segunda Parte (C++):

  • Modelo de memoria imperativa (Stack/Heap, alocación de memoria, punteros, variables por referencia).
  • Linked lists (destructivas).
  • Árboles con punteros.
  • Recorridos iterativos sobre árboles.
  • Arrays.
  • Binary Heaps con Arrays.
  • Sorting.
  • Hashing.

Ejercicios

Ejercicios resueltos.

Bibliografía e información útil

En esta página está disponible la bibliografía recomendada de la materia. No es obligatorio leer todo pero puede resultar útil para buscar algo muy específico.

Por otro lado, nosotros recomendamos fuertemente que leas éste libro:

Es lo mejor que te puede pasar para entender tanto esta materia como programación funcional.

Nota: el libro recomienda utilizar GHCi como REPL, pero nosotros recomendamos usar Hugs (funciona de manera similar y es mucho más liviano).

También puede resultar útil la siguiente página:

Tener en cuenta que en esta página se enseñan algunos temas que en clase no se verán ni se evaluarán (Guardas, por ejemplo).