Profesor | Adriana Ramírez Vigueras | lu mi vi | 13 a 14 | P202 |
Ayudante | Ricardo López López | ma ju | 13 a 14 | P202 |
Ayud. Lab. | ma | 16 a 18 | Taller de Lenguajes de Programación |
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 de gráficas planas.
a) Lista de aristas doblemente ligadas (DCEL)
b) Localización de puntos
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
f) Árboles cuaternarios
g) Árboles R
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. Estructuras de datos para cadenas
a) Tries
b) Diccionarios que permiten errores en las consultas
c) Árboles de sufijos
d) Arreglos de sufijos
7. Transformaciones de Estructuras de Datos
a) Construcción de estructuras dinámicas
b) Construcción de estructuras persistentes
*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
[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.
[5] Elmar Langetepe, Gabriel Zachmann. Geometric data structures for computer graphics. A K Petters, 2006.
Mecanismos de Evaluación (los porcentajes pueden variar)
Tareas examen 75 %
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 (Plan 1994).
1'. Se requiere como asignaturas antecedentes 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 es al finalizar la clase.
5. Para acreditar el curso el alumno tiene que exponer.