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

Optativas, Seminario de Ciencias de la Computación B

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 75 %

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

Dinámica del Curso

Las sesiones del curso serán usando zoom.

Se compartirán en formato pdf las imagenes del pizarron virtual.

Se considera la posibilidad de grabar la clase.

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 al finalizar la clase.
5. Para acreditar el curso el alumno tiene que exponer.