5.19. CS210. Algoritmos y Estructuras de Datos (Obligatorio)

• Semestre: 4to Sem. Créditos: 4
• Horas del curso: Teoría: 2 horas; Práctica: 2 horas; Laboratorio: 2 horas;

• Prerrequisitos:

  • CS113. Programación Orientada a Objetos II (3er Sem)

5.19.1. Justificación

Este curso proporciona un estudio exhaustivo de las estructuras de datos y algoritmos fundamentales con énfasis en su implementación utilizando características avanzadas de C++. Basándose en conocimientos previos de C++, los estudiantes implementarán estructuras de datos genéricas usando plantillas y rasgos, asegurando flexibilidad de tipo y rendimiento. El curso cubre estructuras lineales (vectores, varias listas enlazadas), estructuras de árbol (binario, AVL, B-trees), montículos, tablas hash, tries y estructuras de datos concurrentes. Se pone especial atención en técnicas modernas de C++ incluyendo plantillas variádicas para operaciones genéricas y programación concurrente para estructuras de datos seguras en hilos.

5.19.2. Objetivos Generales

1.

Implementar estructuras de datos genéricas usando plantillas y rasgos.

2.

Dominar estructuras de árbol avanzadas y árboles balanceados.

3.

Comprender e implementar estructuras de datos concurrentes.

4.

Aplicar plantillas variádicas para operaciones genéricas en contenedores.

5.

Analizar la complejidad algorítmica de todas las estructuras implementadas.

6.

Diseñar estructuras de datos eficientes para restricciones de problemas específicas.

5.19.3. Contribución a los resultados (Outcomes)

AG-C08) Análisis de Problemas: Identifica, formula y analiza problemas complejos de computación. (Usage)

AG-C09) Diseño y Desarrollo de Soluciones: Diseña, implementa y evalúa soluciones para problemas complejos de computación. (Usage)

5.19.4. Contenido

5.19.4.1. Fundamentos avanzados para estructuras de datos (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Stroustrup, 2013, Vandevoorde et al., 2017a]

Temas

1.

Revisión de metaprogramación con plantillas y rasgos avanzados.

2.

Rasgos de tipos y SFINAE para compilación condicional.

3.

Plantillas variádicas y paquetes de parámetros.

4.

Reenvío perfecto y referencias universales.

5.

Expresiones lambda con capturas genéricas.

6.

Diseño basado en políticas y CRTP (Patrón de Plantilla Curiosamente Recursivo).

7.

Restricciones basadas en conceptos (conceptos C++20 si son aplicables).

Aprendizaje esperado (Learning Outcomes)

1.

Diseñar rasgos de tipos para personalizar el comportamiento de estructuras de datos [Usar].

2.

Implementar plantillas variádicas para operaciones genéricas de contenedores [Usar].

3.

Aplicar diseño basado en políticas para crear estructuras de datos configurables [Evaluar].

4.

Usar reenvío perfecto para implementar constructores eficientes [Usar].

5.19.4.2. Estructuras de Datos Fundamentales (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Cormen et al., 2009, Stroustrup, 2013]

Temas

1.

Tipo de Dato Abstracto (ADT) y operaciones sobre un ADT:

a)

Operaciones de diccionario (insertar, eliminar, encontrar)

2.

Arreglos:

a)

Numéricos vs no numéricos, cadenas de caracteres

b)

Unidimensionales (vector) vs multidimensionales (matriz)

3.

Registros/Estructuras/Tuplas y Objetos

4.

Listas enlazadas (por razones históricas):

a)

Simples vs Dobles y Lineales vs Circulares

5.

Pilas

6.

Colas y deques:

a)

Cola de prioridad basada en montículo

7.

Tablas/mapas hash:

a)

Resolución de colisiones y complejidad (por ejemplo, sondeo, encadenamiento, rehash)

8.

árboles:

a)

Binarios, n-arios y árboles de búsqueda

b)

Balanceados (por ejemplo, AVL, Rojo-Negro, Montículo)

9.

Conjuntos

Aprendizaje esperado (Learning Outcomes)

1.

Para cada ADT/Estructura de Datos en esta unidad:

a)

Explicar su definición, propiedades, representación(es) y operaciones de ADT asociadas.

b)

Explicar paso a paso cómo las operaciones de ADT asociadas con la estructura de datos la transforman.

[Usar]

2.

Para cada algoritmo en esta unidad explicar paso a paso cómo opera el algoritmo [Usar]

3.

Implementar vector con política de asignación personalizable usando plantillas [Usar].

4.

Diseñar nodos de lista enlazada genéricos con gestión de memoria basada en rasgos [Usar].

5.

Comparar complejidad tiempo/espacio de diferentes estructuras lineales [Evaluar].

6.

Aplicar plantillas variádicas para inicializar contenedores con múltiples elementos [Usar].

5.19.4.3. Estructuras de Datos Fundamentales (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Cormen et al., 2009, Knuth, 1997a]

Temas

1.

árboles:

a)

Binarios, n-arios y árboles de búsqueda

b)

Balanceados (por ejemplo, AVL, Rojo-Negro, Montículo)

2.

Implementación de plantilla de árbol binario con soporte de iteradores.

3.

Árbol de búsqueda binaria con operadores de comparación basados en rasgos.

4.

Algoritmos de recorrido de árbol (iterativo y recursivo).

5.

Árboles de expresión y sus aplicaciones.

6.

Estructuras de nodo basadas en plantilla con carga útil configurable.

Aprendizaje esperado (Learning Outcomes)

1.

Dados los requisitos para un problema, desarrollar múltiples soluciones usando varias estructuras de datos y algoritmos. Posteriormente, evaluar la idoneidad, fortalezas y debilidades seleccionando un enfoque que satisfaga mejor los requisitos [Evaluar]

2.

Explicar factores más allá de la eficiencia computacional que influyen en la elección de algoritmos, como el tiempo de programación, la mantenibilidad y el uso de patrones específicos de la aplicación en los datos de entrada [Familiarizarse]

3.

Implementar árbol binario genérico con orden de recorrido configurable [Usar].

4.

Diseñar evaluador de árbol de expresión usando patrón visitante [Usar].

5.

Analizar complejidades de operaciones de árbol para diferentes estrategias de balanceo [Evaluar].

5.19.4.4. Balanced and Multi-way Trees (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Cormen et al., 2009, Knuth, 1997a, Sedgewick and Wayne, 2011]

Temas

1.

Implementación de árbol AVL con rasgo de balanceo basado en plantillas.

2.

Propiedades y operaciones de árbol rojo-negro.

3.

Implementación de plantilla de B-Tree para almacenamiento basado en disco.

4.

Estructuras de árbol 2-3 y árbol 2-3-4.

5.

Implementación de trie digital (árbol de prefijos).

6.

Árboles de sufijos y sus aplicaciones en procesamiento de cadenas.

7.

Estrategias de división/fusión de nodos para B-trees.

Aprendizaje esperado (Learning Outcomes)

1.

Implementar árboles auto-balanceados usando diseño basado en políticas [Usar].

2.

Diseñar B-tree para aplicaciones de índice de base de datos [Usar].

3.

Evaluar compensaciones entre diferentes estructuras de árbol balanceado [Evaluar].

4.

Implementar trie para coincidencia eficiente de prefijos de cadenas [Usar].

5.19.4.5. Estructuras de Datos Fundamentales (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Cormen et al., 2009, Sedgewick and Wayne, 2011]

Temas

1.

árboles:

a)

Binarios, n-arios y árboles de búsqueda

b)

Balanceados (por ejemplo, AVL, Rojo-Negro, Montículo)

2.

Implementación de montículo binario usando representación de arreglo.

3.

Variantes de montículo mínimo y montículo máximo.

4.

Algoritmos heapify y análisis de complejidad.

5.

Implementación de ADT de cola de prioridad.

6.

Visión general de montículo binomial y montículo de Fibonacci.

7.

Aplicaciones de montículos: algoritmo de Dijkstra, ordenamiento por montículo.

Aprendizaje esperado (Learning Outcomes)

1.

Explicar la propiedad de montículo y el uso de montículos como una implementación de una cola de prioridad [Familiarizarse]

2.

Implementar montículo genérico con rasgo de comparación configurable [Usar].

3.

Diseñar cola de prioridad que soporte múltiples estrategias de actualización de prioridad [Usar].

4.

Analizar complejidad de operaciones de montículo para diferentes tipos de montículo [Evaluar].

5.

Aplicar montículo en implementaciones de algoritmos de grafos [Usar].

5.19.4.6. Estructuras de Datos Fundamentales (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Cormen et al., 2009, Knuth, 1997a]

Temas

1.

Tablas/mapas hash:

a)

Resolución de colisiones y complejidad (por ejemplo, sondeo, encadenamiento, rehash)

2.

Diseño de función hash y propiedades.

3.

Implementación de encadenamiento separado con listas enlazadas.

4.

Direccionamiento abierto: sondeo lineal, sondeo cuadrático, doble hashing.

5.

Hashing perfecto y hashing perfecto mínimo.

6.

Hashing cuco y hashing de rayuela.

7.

Estrategias de redimensionamiento de tabla hash y gestión de factor de carga.

Aprendizaje esperado (Learning Outcomes)

1.

Explicar cómo se maneja la evitación de colisiones y la resolución de colisiones en tablas hash [Familiarizarse]

2.

Diseñar tabla hash genérica con resolución de colisiones configurable [Usar].

3.

Implementar funciones hash personalizadas para tipos definidos por el usuario [Usar].

4.

Evaluar rendimiento de diferentes esquemas de hashing [Evaluar].

5.

Aplicar tablas hash en la implementación de tabla de símbolos del compilador [Usar].

5.19.4.7. Concurrent Data Structures (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Herlihy and Shavit, 2012, Williams, 2019]

Temas

1.

Principios de diseño de estructuras de datos seguras para hilos.

2.

Listas enlazadas concurrentes basadas en bloqueos.

3.

Algoritmos sin bloqueo y libres de espera.

4.

Tablas hash concurrentes con bloqueo de grano fino.

5.

Operaciones atómicas y ordenamiento de memoria.

6.

Colas concurrentes (limitadas e ilimitadas).

7.

Pilas concurrentes y técnicas de eliminación.

Aprendizaje esperado (Learning Outcomes)

1.

Diseñar estructuras de datos seguras para hilos usando mutex y guardas de bloqueo [Usar].

2.

Implementar lista enlazada sin bloqueo usando operaciones atómicas [Usar].

3.

Analizar rendimiento de estructuras de datos concurrentes vs secuenciales [Evaluar].

4.

Aplicar colas concurrentes en patrones productor-consumidor [Usar].

5.19.4.8. Specialized Structures and Applications (8 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Okasaki, 1999, Sedgewick and Wayne, 2011]

Temas

1.

Estructuras de datos persistentes.

2.

Unión-búsqueda de conjuntos disjuntos (union-find) con compresión de trayectoria.

3.

Filtros de Bloom y sus propiedades probabilísticas.

4.

Listas por niveles para búsqueda balanceada probabilística.

5.

Árboles de segmentos y árboles de Fenwick para consultas de rango.

6.

Estructuras de datos espaciales: árboles k-d, quadtrees.

7.

Estructuras de datos inconscientes de la caché.

Aprendizaje esperado (Learning Outcomes)

1.

Implementar estructuras de datos persistentes con compartición estructural [Usar].

2.

Diseñar union-find con unión por rango y compresión de trayectoria [Usar].

3.

Aplicar estructuras especializadas para resolver problemas específicos de dominio [Evaluar].

4.

Evaluar compensaciones espacio-tiempo en estructuras de datos probabilísticas [Evaluar].

5.19.5. Referencias Bibliográficas

[Stroustrup, 2013]

[Vandevoorde et al., 2017a]

[Cormen et al., 2009]

[Knuth, 1997a]

[Sedgewick and Wayne, 2011]

[Herlihy and Shavit, 2012]

[Williams, 2019]

[Okasaki, 1999]