1151012 Almacenamiento y Recuperación de la
Información
Trimestre 2005 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: Lunes
19 de septiembre a viernes 2 de diciembre.
Grupo: CCT81 (LMV de 16:00
a
17:30).
Asesorías: Lunes,
miércoles y viernes de 14:30 a 16:00 en la
oficina H-264.
Salón: E-306.
Laboratorio: Base de datos
"Edgar F. Codd" (H-253 a H-258).
Contenido
Se cubrirá el contenido
oficial del curso (el cual se detalla
abajo). Es posible que el temario se cubra en un
orden distinto al allí mencionado.
- Árboles AVL [C14, S14, S15].
- Grafos y sus aplicaciones [C23, L8, S29, S31].
- Estructuras de archivos [F2, F4].
- Ordenamiento externo [F8, K5, S13].
- Índices [F7].
- Árboles B y B+ [C19, F9, F10, S18].
- Dispersión [C12, F11, F12, S16].
Evaluación
La calificación del curso consta de 50 puntos obtenidos mediante
un proyecto, 30 puntos obtenidos mediante dos exámenes parciales
y 20 puntos obtenidos mediante tareas. No
habrá examen global. Además de obtener 18 puntos
en los exámenes y 30 puntos en el proyecto, se
requiere:
- obtener al menos un total de 60 puntos para acreditar con S,
- obtener al menos un total de 73 puntos para acreditar con B y
- obtener al menos un total de 87 puntos para acreditar con MB.
Calendario
El calendario de clases, de entrega de tareas y de
exámenes escritos que muestro abajo es tentativo e irá
apareciendo paulatinamente.
- 19/09: Presentación del curso y de las reglas de
evaluación
- 21/09: Grafos dirigidos y no dirigidos, estructuras de datos para
la representación de grafos [S29]
- 23/09: Búsqueda en profundidad, búsqueda a lo
ancho, aplicaciones [S29]
- 26/09: Árbol abarcador de costo mínimo (Kruskal y
Prim), camino de costo mínimo (Dijkstra) [S31]
- 28/09: Árboles binarios (de búsqueda) no
balanceados:
problemas y búsqueda de soluciones [S14]
- 30/09: Árboles binarios balanceados: árboles 2-3-4
[S15]
- 03/10: Árboles binarios balanceados: árboles
rojinegros [S15]
- 05/10: Estructuras de archivos [F1.1], operaciones fundamentales
de archivos [F2.1-4]
- 07/10: Otras operaciones de archivos [F2.5-8], hardware de discos [F3.1]
- 10/10: Hardware de
cintas [F3.2]
- 13/10: Archivos y el sistema operativo
[F3.8-10]
- 14/10: Campos y registros en archivos [F4.1]
- 17/10: Empleo de buffers
en archivos [F4.2-4]
- 19/10: Manipulación de archivos de registros [F5.1-2]
- 21/10: Compresión de archivos [F6.1]
- 24/10: Entrega de la tarea 1 en clase.
- 24/10: Primer examen parcial (sólo cubrirá el
material oficial: S14, S15, S29, S31, F2 y F4)
- 26/10: Reutilizando espacio en archivos [F6.2]
- 28/10: Ordenamiento interno, búsqueda binaria y
ordenamiento de claves [F6.3-4]
- 31/10: Índices sencillos [F7.1-4]
- 04/11: Índices grandes e índices secundarios
[F7.5-9]
- 07/11: Procesos cosecuenciales [F8.1-4]
- 09/11: Ordenamiento externo en discos [F8.5]
- 11/11: Ordenamiento externo en cintas [F8.6]
- 14/11: Fecha límite para propuesta
de proyecto.
- 14/11: Introducción a los árboles B [F9.1-4]
- 16/11: Búsqueda, inserción y otras propiedades de
los árboles B [F9.5-11]
- 18/11: Borrado y otros detalles en árboles B [F9.12-16]
- 21/11: Introducción a los árboles B+ [F10.1-5]
- 23/11: Propiedades de los árboles B+ [F10.6-10]
- 25/11: Introducción a la dispersión [F11.1-4]
- 28/11: Técnicas de dispersión [F11.5-8]
- 30/11: No habrá
clase. Además, por causas de fuerza mayor, se suspende la
asesoría programada para hoy.
- 01/12: Asesoría
adicional de 10:00 a 13:00 en mi oficina.
- 02/12: Entrega de la tarea 2 en clase.
- 02/12: Segundo examen parcial (sólo cubrirá el
material oficial: F7, F8, F9, F10 y F11)
- 05/12: Fecha límite para entrega del proyecto terminado.
- 07/12: Entrega de calificaciones finales
y acta.
- 02/01: Examen de recuperación a las 4 PM.
Bibliografía
- [B] Classic
Data Structures in Java, Budd,
Addison Wesley.
- [C] Introduction to
Algorithms, Cormen,
Leiserson, Rivest y Stein, Mc Graw Hill.
- [F] File Structures: An Object-oriented Approach with C++, Folk,
Zoellick y Riccardi, Addison Wesley.
- [K] The Art
of Computer Programming: Vol. 3 Sorting and Searching, Knuth, Addison
Wesley.
- [L] Estructuras de datos con C y C++, Langsam, Augenstein y
Tenenbaum, Prentice Hall.
- [P] Problems
on Algorithms, Parberry,
Prentice Hall.
- [S] Algoritmos en C++, Sedgewick,
Pearson.
- [T] File Organization and Processing, Tharp, Wiley.