Ciencias de la Computación (plan 2013) 2018-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

3. Estructuras de datos de gráficas planas.

a) Lista de aristas doblemente ligadas (DCEL)

b) Localización de puntos (Subdivisión trapezoidal, de cadenas monótonas y Algoritmo Kirkpatrick)

4. 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

5. 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

6. Transformaciones de Estructuras de Datos

a) Construcción de estructuras dinámicas

b) Construcción de estructuras persistentes

7. Estructuras de datos para cadenas

a) Tries

b) Diccionarios que permiten errores en las consultas

c) Árboles de sufijos

d) Arreglos de sufijos

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.

Mecanismos de Evaluación (los porcentajes pueden variar)

Tareas examen 50 %

Prácticas de laboratorio 25 %

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

Notas

1. Se requiere como asignaturas antecedentes Introducción a Ciencias de la Computación II y Análisis de Algoritmos I.

2. Una vez entregado el primer trabajo para evaluar, no se puede solicitar la calificación de NP.

3. No se reciben tareas y prácticas después de la fecha de entrega.

4. La entrega es al finalizar la clase.

5. Para acreditar el curso el alumno tiene que exponer.