Estructuras de Datos

Estructuras de Datos

Programa del curso

Objetivos, bibliografía, calendario y políticas.

Descargar sílabo oficial (PDF)Ver calendario

Estructuras de Datos — Programa del curso

Docente: Gerson Garrido

1. Descripción

En Introducción a la Programación ustedes aprendieron a manejar la memoria y a esconder detalles detrás de una interfaz. Este curso usa esas ideas para responder una pregunta práctica: ¿cómo se organizan los datos para que un programa siga siendo rápido cuando los datos crecen?

Ustedes van a construir las estructuras que las bibliotecas traen hechas, a predecir su costo y a medirlo. El curso se dicta en C++, y las dos primeras semanas enseñan lo que hace falta del lenguaje. Cada laboratorio es un programa real que necesita la estructura de la semana. Se organiza en cuatro partes:

  1. De C a C++ y costos — clases, ownership, templates, análisis asintótico y medición.
  2. Secuencias y ordenamiento — arreglos dinámicos, listas, pilas, colas y ordenamiento.
  3. Diccionarios — tablas hash, árboles de búsqueda, AVL y rojinegros.
  4. Prioridades y grafos — heaps, grafos, union-find y caminos mínimos.

Los apuntes son el texto del curso. Cada capítulo empieza con una ruta de lectura: qué leer antes de clase (15 a 20 minutos), qué se explica en clase y qué repasar después. Open Data Structures es la lectura gratuita de apoyo y CLRS es la referencia para quien quiera profundizar. Los términos técnicos siguen la guía de estilo, y el glosario reúne los principales.

2. Carga horaria

Componente Horas/semana Formato
Teoría 2 h Una sesión
Laboratorio 4 h Dos sesiones de 2 h

3. Resultados de aprendizaje

Al finalizar el curso, el estudiante será capaz de:

  1. Escribir clases y templates en C++ que administren su memoria con RAII, sin fugas ni accesos inválidos.
  2. Distinguir un tipo abstracto de datos de sus implementaciones, y elegir la adecuada según las operaciones que el problema necesita.
  3. Predecir el costo de un programa con análisis asintótico y costo amortizado, y contrastar la predicción con mediciones.
  4. Implementar y usar arreglos dinámicos, listas enlazadas, pilas, colas y deques.
  5. Implementar y comparar tablas hash con encadenamiento y con direccionamiento abierto.
  6. Implementar árboles binarios de búsqueda y mantenerlos balanceados con AVL y con árboles rojinegros.
  7. Implementar heaps y colas de prioridad, y representar y recorrer grafos.
  8. Declarar los invariantes de una estructura, comprobarlos en el código y probarla contra una implementación de referencia.
  9. Explicar cómo las bibliotecas y los lenguajes actuales aplican estas ideas, y por qué.

4. Bibliografía

Texto del curso: los apuntes, un capítulo por semana. No se requiere comprar ningún libro.

Lectura gratuita de apoyo: Pat Morin, Open Data Structures, edición en C++ (beta) o en pseudocódigo. Licencia CC BY.

Referencia: Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms, 4.ª edición, MIT Press, 2022.

5. Calendario

Este es el calendario oficial del curso. Cada semana enlaza a su guía con objetivos, temas y actividades de laboratorio. Los temas marcados con ✂️ se pueden comprimir o pasar a lectura autónoma si se pierden clases por feriados. Las semanas 8 y 16 son de exámenes y no tienen clases regulares.

Sem. Teoría (2 h) Laboratorio (4 h) Práctica
1 Presentación · De C a C++: referencias, clases, std::string, std::vector y pruebas Portar un módulo de C a C++
2 Ownership y RAII: destructor, copia y movimiento · Templates · Tipo abstracto e implementación, con la pila como ejemplo Una pila genérica sin fugas
3 Análisis asintótico · Medir tiempos Predecir el crecimiento y medirlo
4 Arreglos dinámicos y costo amortizado · Colas sobre un buffer circular Un Vector propio Práctica 1
5 Listas enlazadas e iteradores · Deques Un deque con dos representaciones (buffer circular y lista enlazada), medidas
6 Ordenamiento: mergesort y quicksort · Búsqueda binaria Autocompletado
7 Tablas hash: funciones hash y encadenamiento La tabla de variables, ahora como tabla hash Práctica 2
8 Examen parcial (semanas 1 a 7)
9 Direccionamiento abierto: linear probing y tombstones · Swiss Tables y el dict de CPython Corrector ortográfico: comparar diseños
10 Árboles binarios de búsqueda: recorridos y mapas ordenados Un mapa ordenado, probado contra std::map
11 Árboles AVL: rotaciones y altura Balancear el mapa con AVL Práctica 3
12 Árboles rojinegros: de los árboles 2-3-4 a la inserción · B-trees como idea · ✂️ Eliminación Inserción rojinegra · AVL, rojinegro y std::map, medidos
13 Heaps y colas de prioridad · Heapsort Compresión de Huffman
14 Grafos: representación, BFS y DFS · Union-find Generar y resolver laberintos Práctica 4
15 Dijkstra con un heap · ✂️ Tries · ✂️ Filtros de Bloom · Repaso Rutas sobre un mapa real
16 Examen final (todo el curso)

6. Prácticas

Hay cuatro prácticas individuales, en las semanas 4, 7, 11 y 14. Esa semana, una de las dos sesiones de laboratorio es para la práctica y la otra sigue con el laboratorio de la guía. El formato y las reglas están en practicas/README.md.

7. Políticas

  • Trabajo: individual. Se puede discutir ideas, pero cada estudiante escribe su propio código y debe poder explicarlo.
  • Herramientas e IA generativa: ver la sección siguiente.

8. Uso de herramientas e IA generativa

Las prácticas y los exámenes miden lo que cada estudiante sabe hacer solo, así que ahí no se usa IA generativa. En los laboratorios y para estudiar sí se puede, con las condiciones de la tabla.

Herramienta Laboratorios y estudio Prácticas
Mensajes del compilador, gdb, valgrind y sanitizers (ASan, UBSan) Sí Sí
Documentación oficial (cppreference, manuales de las herramientas) y búsqueda web Sí Sí, para consultar el lenguaje y la biblioteca, no para buscar soluciones
Autocompletado del editor que completa nombres y firmas, sin escribir soluciones enteras Sí Sí
Corrector ortográfico, traductores y herramientas de accesibilidad Sí Sí
Formateadores de código y linters Sí Sí
IA generativa para pedir explicaciones, sin que genere código Sí No
IA generativa que escribe código (chats, Copilot y similares) Sí, declarándolo No
  • Cómo se declara. Quien use IA generativa en un laboratorio lo dice en una línea al inicio del archivo o del informe que entrega: qué herramienta usó y para qué. Para estudiar no hace falta declararlo.
  • Revisión oral. Cualquier práctica o laboratorio puede incluir una revisión oral breve, en la que cada estudiante explica su código. Quien no pueda explicar lo que entregó no demuestra lo que la tarea pide, aunque el programa funcione.
  • Por qué. Los laboratorios preparan las prácticas. Si la IA escribe el código del laboratorio, la práctica es la primera vez que lo escriben ustedes.

9. Entorno de trabajo

Todo se hace en un mismo entorno, con el compilador de C++, gdb, valgrind, make y Git ya instalados. Se abre con GitHub Codespaces o con Docker. Instrucciones en labs/README.md.