CI2612: Algoritmos y Estructuras de Datos II (Pregrado)

Blai Bonet
Matemáticas y Sistemas, 215-A
Departamento de Computación
Universidad Simón Bolívar

bonet AT ldc DOT usb DOT ve
Tel: +58 (212) 906-3263
Web: http://www.ldc.usb.ve/~bonet

Sinopsis

Segundo curso de la cadena de algoritmos y estructuras de datos. Se estudian los temas de ordenamiento y cálculo de estadísticos así como estructuras de datos fundamentales. Se hacen análisis peor caso y caso promedio de algoritmos y del desempeño de operaciones sobre estructuras de datos. Se estudia ordenamiento por inserción, heapsort, quicksort, y los algoritmos lineales count sort, radix sort y bucket sort. Se estudia cotas inferiores para ordenamiento basado en comparaciones y la optimalidad asintótica de heapsort y quicksort con selección de mediana. Se estudian las estructuras de datos elementales de pila, cola, y lista enlazada. Otras estructuras de datos estudiadas son diccionarios (tablas de hash), árboles binarios de búsqueda y árboles rojo negro.

Evaluación (tentativo)

Objetivos y Cronograma (tentativo)

Semana  Día I (Lunes 7-8 en ENE-104) Día II (Miércoles 7-8 en ENE-110)
I 23/04: Introducción al curso. Contenido. Evaluación. Bibliografía. Nociones básicas. Algoritmos. Modelo computacional. Complejidad en tiempo y espacio. Crecimiento de funciones. Notación asintótica. Búsqueda lineal y binaria. Ordenamiento por inserción. [§2.1 + §3.1] 25/04: Recurrencias. Solución de recurrencias por substitución y Teorema Maestro. Dividir y conquistar. Mergesort. Multiplicación de matrices. Algoritmo de Strassen. Algoritmo de Karatsuba. [§4.1 + §4.2 + §4.3 + §4.4 + §4.5]
II 30/04: Introducción a ordenamiento y estadísticos de orden. Heaps. Representación. Heapsort. Colas de prioridad. [Intro. Part II + §6.1 + §6.2 + §6.3 + §6.4 + §6.5] 02/05: Probabilidad. Análisis probabilístico. [§5.2 + §5.4 + §C.2 + §C.3]
III 07/05: Algoritmos aleatorizados (randomized algorithms). Algoritmo de Freivalds. [§5.1 + §5.2 + §5.4] 09/05: Quicksort. Partition. Desempeño de quicksort. Quicksort randomizado. Análisis de peor caso, tiempo esperado y caso promedio. [§7.1 + §7.2 + §7.3 + §7.4]
IV 14/05: Solución de problemas. 16/05: Cotas inferiores para ordenamiento basado en comparaciones. Optimalidad asintótica de mergesort y heapsort. Cotas para tiempo esperado para ordenamiento basado en comparaciones. Optimalidad asintótica de quicksort. Cotas para mezclar listas ordenadas. [§8.1]
V 21/05: Ordenamiento en tiempo lineal. Counting sort. Radix sort. Bucket sort. [§8.2 + §8.3 + §8.4] 23/05: Cálculo de mediana y estadísticos. Máximos y mínimos. Selección del k-ésimo en tiempo lineal esperado. Selección del k-ésimo en tiempo lineal peor caso. [§9.1 + §9.2 + §9.3]
VI 28/05: Repaso. 30/05: Examen.
VII 04/06: Conjuntos dinámicos. Estructuras de datos elementales. Pilas y colas. Listas enlazadas. Implementación de apuntadores y objetos. Representación de árboles enraizados. [§10.1 + §10.2 + §10.3 + §10.4] 06/06: Tablas de hash (diccionarios). Operaciones. Direccionamiento directo. Hashing. Resolución de colisiones por encadenamiento. Funciones de hash. [§11.1 + §11.2]
VIII 11/06: Tablas de hash (diccionarios). Direccionamiento abierto. Funciones de hash para direccionamiento abierto. [§11.3 + §11.4] 13/06: Hashing universal. Hashing perfecto. [§11.5]
IX 18/06: Solución de problemas. 20/06: Hashing cuco (cuckoo). Filtro de Bloom.
X 25/06: No hay clases. 27/06: Árboles binarios de búsqueda. [§12.1 + §12.2 + §12.3]
XI 02/07: Árboles rojo negro. [§13.1 + §13.2 + §13.3 + §13.4] 04/07: Repaso. Resolución de problemas.
XII 09/07: Examen. 11/07: No hay clases.

Bibliografía

Last Modified 15 Jul 2018