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

Optativas, Seminario de Programación

Estructuras de Datos Avanzadas

Semestre 2013 − I

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

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 tango

3. Estructuras de datos de gráficas planas.

a) Lista de aristas doblemente ligadas (DCEL)

b) Localización de puntos

c) El programa de disparo de rayos (ray shooting)

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. Transformaciones de Estructuras de Datos

a) Construcción de estructuras dinámicas

b) Construcción de estructuras persistentes

6. Estructuras de datos para cadenas

a) Tries

b) Diccionarios que permiten errores en las consultas

c) Árboles de sufijos

d) Arreglos de sufijos

7. Estructuras de datos cinéticas

a) Introducción

b) Predecedor cinético

c) Heap cinético

d) El problema de disparo de rayos (ray shooting)

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

Mecanismos de Evaluación (los porcentajes pueden variar)

Exámenes parciales 40 %

Trabajos y tareas fuera del aula 30%

Prácticas de laboratorio 20 %

Exposición por los alumnos 10 %

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 trabajos, tareas y prácticas después de la fecha de entrega.

4. La entrega de trabajos y tareas es al finalizar la clase.