5.34. CS312. Estructuras de Datos Avanzadas (Obligatorio)

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

• Prerrequisitos:

  • CS212. Análisis y Diseño de Algoritmos (5to Sem)

5.34.1. Justificación

Los algoritmos y estructuras de datos son una parte fundamental de la Ciencia de la Computación que nos permite organizar información de manera eficiente. Para cualquier profesional en el campo, una base sólida en esta área es crucial. Este curso se enfoca en estructuras avanzadas como Métodos de Acceso Multidimensional, Métodos de Acceso Espacio-Temporales y Métodos de Acceso Métrico, que son esenciales para aplicaciones de alto rendimiento en motores de búsqueda, sistemas de información geográfica (SIG) y procesamiento de big data.

5.34.2. Objetivos Generales

1.

Comprender, diseñar e implementar estructuras de datos innovadoras para datos multidimensionales.

2.

Aplicar técnicas de búsqueda por similitud e indexación métrica a tipos de datos complejos.

3.

Analizar la "Maldición de la Dimensionalidad 2 su impacto en la eficiencia de búsqueda.

4.

Investigar y presentar métodos de indexación contemporáneos para Big Data en inglés.

5.34.3. Contribución a los resultados (Outcomes)

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

AG-C12) Aplica la teoría de la ciencia de la computación y los fundamentos de desarrollo de software para producir soluciones basadas en computadora. (Usage)

5.34.4. Contenido

5.34.4.1. Programación Orientada a Objetos II: Encapsulación, Subtipado y Reflexión (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cuadros-Vargas et al., 2004, Knuth, 1997b, Gamma et al., 1994b, Vandevoorde et al., 2018]

Temas

1.

Técnicas de implementación estáticas y dinámicas.

2.

Abstracción y encapsulación de datos.

3.

Tipos Abstractos de Datos (TAD).

4.

Polimorfismo en tiempo de compilación vs. en tiempo de ejecución.

5.

Estructuras de datos genéricas y Plantillas de C++.

6.

Componentes reutilizables y patrones de diseño para estructuras de datos.

Aprendizaje esperado (Learning Outcomes)

1.

Evaluar el impacto de las técnicas estáticas y dinámicas en el diseño de estructuras de datos [Evaluar].

2.

Implementar estructuras de datos genéricas y reutilizables usando paradigmas de programación avanzados [Usar].

3.

Analizar las compensaciones de rendimiento entre diferentes estrategias de implementación [Evaluar].

5.34.4.2. Métodos de acceso multidimensional (Parte I) (8 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Gaede and Günther, 1998, Samet, 2006]

Temas

1.

Introducción a datos multidimensionales.

2.

Representación en espacios vectoriales.

3.

La Maldición de la Dimensionalidad: fundamentos teóricos.

4.

Impacto de la alta dimensionalidad en la indexación tradicional.

5.

Aplicaciones en el mundo real en motores de búsqueda y reconocimiento de patrones.

Aprendizaje esperado (Learning Outcomes)

1.

Explicar la importancia de la representación de datos multidimensionales [Familiarizarse].

2.

Analizar la complejidad y degradación del rendimiento en espacios de alta dimensión [Usar].

3.

Discutir escenarios del mundo real donde el impacto de la dimensionalidad es crítico [Usar].

5.34.4.3. Métodos de acceso multidimensional (Parte II) (20 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Samet, 2006]

Temas

1.

Estructuras de datos espaciales: Quadtree y Octree.

2.

Métodos de Acceso a Puntos: Kd-Tree.

3.

Métodos de Acceso a Regiones: R-Tree (Guttman), R+ tree, R* tree.

4.

Variaciones de R-trees y su relación con la paginación y el tamaño de bloque.

5.

Estructuras avanzadas: X-tree y SS-tree.

Aprendizaje esperado (Learning Outcomes)

1.

Implementar estructuras de datos espaciales para indexación de datos de alto volumen [Usar].

2.

Evaluar las limitaciones de las estructuras espaciales basadas en árboles en dominios específicos [Evaluar].

3.

Implementar búsqueda por rango y estrategias de Vecino Más Cercano (k-NN) [Usar].

5.34.4.4. Métodos de acceso métrico (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Samet, 2006, Zezula et al., 2007]

Temas

1.

Espacios Métricos: definiciones y propiedades.

2.

Búsqueda por similitud vs. Búsqueda exacta.

3.

Árbol de Punto de Vista (VP-Tree).

4.

Slim-Tree y M-Tree.

5.

Indexación basada en pivotes.

Aprendizaje esperado (Learning Outcomes)

1.

Modelar problemas de búsqueda por similitud usando propiedades de espacios métricos [Usar].

2.

Comparar métodos de acceso métrico contra métodos multidimensionales para datos no vectoriales [Evaluar].

5.34.4.5. Comunicación Técnica y Profesional (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Navarro, 2016, Traina Jr et al., 2000]

Temas

1.

Seminario sobre artículos de investigación recientes (SIGMOD, VLDB, ICDE).

2.

Indexación para Big Data y datos en flujo.

3.

Estructuras de datos compactas y representaciones sucintas.

4.

Tendencias futuras en búsqueda por similitud.

Aprendizaje esperado (Learning Outcomes)

1.

Investigar nuevos métodos para indexar grandes volúmenes de datos complejos [Usar].

2.

Presentar y dirigir discusiones técnicas en inglés sobre métodos de vanguardia [Evaluar].

3.

Identificar posibles temas de tesis dentro del dominio de estructuras de datos avanzadas [Familiarizarse].

5.34.5. Referencias Bibliográficas

[Cuadros-Vargas et al., 2004]

[Knuth, 1997b]

[Gamma et al., 1994b]

[Vandevoorde et al., 2018]

[Gaede and Günther, 1998]

[Samet, 2006]

[Zezula et al., 2007]

[Navarro, 2016]

[Traina Jr et al., 2000]