Ciencias de la Computación (plan 2013) 2025-1

Optativas, Seminario de Ciencias de la Computación A

ESTRUCTURAS DE DATOS AVANZADAS

Las estructuras de datos juegan un papel central en el área de las ciencias de la computación. El desarrollo de las estructuras de datos hoy en día es tan frecuente y complicado como el diseño de algoritmos. Este curso ofrece profundizar y conocer una serie de estructuras de datos avanzadas, con el fin de obtener información suficiente y detallada, para la implementación de las mismas. Al finalizar el curso el alumno habrá adquirido los conocimientos necesarios, sobre una serie de estructuras de datos, para utilizarlas como una de sus herramientas principales para el diseño e implementación de programas.

1. Estructuras de datos elementales

a) Estructuras basadas en arreglos

b) Pilas

c) Colas

d) Árboles binarios de búsqueda

e) Heaps

f ) Tablas Hash

g) Skip List

2. Árboles balanceados de búsqueda

a) Características y Propiedades

b) Árboles AVL

c) Árboles Rojo-Negro

d) Árboles treaps

e) Árboles splay

f) Árboles B

3. Estructuras de datos geométricas

a) Árboles Kd

b) Árboles de búsqueda ortogonal

c) Árboles de intervalos

d) Árboles de segmentos

e) Árboles para suma de intervalos

f) Árboles cuaternarios

g) Árboles R

4. Heaps

a) Características y propiedades

b) Árboles balanceados de búsqueda como heaps

c) Heaps basados en arreglos

d) Heaps sesgados

e) Heaps binomiales

f) Heaps de Fibonacci

5. Estructuras de datos para cadenas

a) Tries

b) Diccionarios que permiten errores en las consultas

c) Árboles de sufijos

d) Arreglos de sufijos

6. Transformaciones de Estructuras de Datos

a) Construcción de estructuras dinámicas

b) Construcción de estructuras persistentes

7. Estructuras de datos compactas

a) Entropía y codificación

b) Bitvectors

c) Permutaciones y secuencias

d) Árboles, gráficas y mallas

8. Estructuras de datos cinéticas

a) Introducción

b) Predecedor cinético

c) Heap cinético

9. Miscelánea de Aplicaciones

a) Estructuras de datos para manejo de imágenes

b) Estructuras de datos para bases de datos

c) Minería de datos

d) Estructuras de proximidad

Referencias

[1] Peter Brass. Advanced Data Structures. Cambridge University Press, 2008.

[2] Dinesh P. Mehta, Sartaj Sahni, editores. Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2005.

[3] Hanan Samet. Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006

[4] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications (3rd ed.), Springer Verlag, Berlin, 2008.

[5] Elmar Langetepe y Gabriel Zachmann . Geometric data structures for computer graphics.A K Petters, 2006.

[6] J. Basch, L. J. Guibas and J. Hershberger. Data Structures for Mobile Data. Journal of Algorithms, 31(1), pp. 1–28, 1999.

[7] Maxime Crochemore, Christophe Hancart, Thierry Lecroq. Algorithms on Strings. Cambridge University Press 2007.

[8] Guillaume Damiand, Pascal Lienhardt. Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing 2014.

[9] Gonzalo Navarro. Compact Data Structures: A Practical Approach 2016.

[10] Cormen, Thomas H. and Stein, Clifford and Rivest, Ronald L. and Leiserson, Charles E. Introduction to Algorithms, third edition. 2009.

[11] Goodrich, Michael T. and Tamassia, Roberto and Goldwasser, Michael H. Data Structures and Algorithms in Python. 2013.

[12] Marcello La Rocca. Advanced Algorithms and Data Structures. 2021.

Mecanismos de Evaluación

Tareas Examen 70%

Prácticas 15 %

Exposición por los alumnos (temas 9) 15 %

Dinámica del Curso

Se compartirá material usando Google Classroom.

Las tareas se entregarán usando Google Classroom en formato pdf.

Favor de verificar su correo registrado en el sistema de la facultad, porque usaremos la lista de correos que la facultad proporciona a los profesores para crear el Classroom.

Notas

1. Se requiere como asignaturas antecedentes Introducción a Ciencias de la Computación II y Análisis de Algoritmos I (Plan 1994 si es el caso) o Estructuras de Datos y Análisis de Algoritmos (Plan 2013).
2. Una vez entregado el primer trabajo para evaluar, no se puede solicitar la calificación de NP.
3. No se reciben tareas después de la fecha de entrega.
4. La entrega de tareas es hasta las 23:59 del día de entrega
5. Para acreditar el curso el alumno tiene que exponer y obtener al menos 6 en tareas examen.