115112 Almacenamiento y Recuperación de la Información
Trimestre 2008 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
14 de enero a miércoles 4
de junio de 2008.
Grupo: CCT81 (lunes,
miércoles y viernes de 16:00
a
17:30).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: E-309.
Cupo: 35 estudiantes y 10
oyentes.
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.
- Grafos y sus aplicaciones.
- Estructuras de archivos.
- Ordenamiento externo.
- Índices.
- Árboles B y B+.
- Dispersión.
Evaluación
Habrá dos
exámenes y cinco
tareas. Cada examen
valdrá 30 puntos
y cada tarea valdrá 8
puntos. No
habrá examen global. Se
requiere obtener
- al menos 35 puntos en los exámenes, 25 puntos en las
tareas y un total de al menos 60 puntos para acreditar con S,
- al menos 40 puntos en los exámenes, 30 puntos en las
tareas y un total de al menos 73 puntos para acreditar con B y
- al menos 45 puntos en los exámenes, 35 puntos en las
tareas y un total de al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a
la cuenta ari en gabrijela.azc.uam.mx y
podrán estar escritas en C, C++, Java
o Pascal.
Su cuenta
está en la misma máquina, a la que se pueden conectar con
ssh y que tiene
dirección IP 148.206.67.155. Recuerden que, de acuerdo al Reglamento de
Alumnos de la UAM, es falta de los alumnos en contra de la
Institución el suplantar o permitir ser suplantado en la
realización de actividades académicas (Artículo 9)
y se impondrá desde amonestación escrita hasta
suspensión por dos trimestres (Artículo 13).
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
muestro abajo es tentativo e irá
apareciendo paulatinamente. He anotado los capítulos y secciones
correspondientes del Folk [F] y del Sedgewick [S] y los números
de página de las notas a la derecha
de cada
tema (A-B). Ya pueden bajar las notas completas
del curso.
- 14/01: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Estructuras de archivos [F1.1] (1-10).
- 16/01: Operaciones fundamentales
de archivos [F2.1-8] (11-30).
- 18/01: Hardware de
discos [F3.1] (31-42).
- 21/01: Hardware de
cintas [F3.2,3,7] (43-55).
- 23/01: Archivos y el sistema operativo [F3.8-9] (56-67).
- 25/01: Campos y registros en archivos [F4.1] (68-81).
- 28/01: Manipulación de archivos de registros [F5.1-2]
(82-95). Tarea 1 (para el 01/02).
- 30/01: Compresión de archivos [F6.1] (96-106).
- 01/02 a 04/04: Huelga.
- 07/04: Reinicio del curso.
- 09/04: Representación de
grafos no dirigidos y aplicaciones [S29] (129-149).
- 11/04: Representación de
grafos dirigidos y aplicaciones [S32] (150-164).
- 14/04: Búsqueda en profundidad y búsqueda en
amplitud [S29 y S32] (165-196). Tarea 2 (para el
28/04). Página
de prueba.
- 16/04: Conexidad, unión-pertenencia y ordenamiento
topológico [S30 y S32] (197-218).
- 18/04: Árboles abarcadores de costo mínimo (Kruskal
y
Prim) [S31] (219-239).
- 21/04: Caminos más cortos (Dijkstra y Floyd) [S31 y S32]
(240-256).
- 23/04: Árboles AVL y árboles 2-3-4
[S15] (257-276). Tarea 3 (para el 06/05). Página de prueba.
- 25/04: Árboles
AVL y árboles rojinegros [S15] (277-294).
- 28/04: Índices sencillos y grandes [F7.1-5] (295-309).
- 30/04: Índices secundarios
[F7.6-10] (310-324).
- 02/05: Primer examen
parcial (129-324).
- 05/05: Día feriado.
- 07/05: Operaciones cosecuenciales [F8.1-4] (325-337). Tarea 4 (para
el 23/05). Página de prueba.
- 09/05: Ordenamiento externo en discos [F8.5] (338-348).
- 12/05: Ordenamiento externo en cintas [F8.6] (349-360).
- 14/05: Introducción a los árboles B [F9.1-4]
(361-373).
- 16/05: Operaciones y propiedades de los árboles B
[F9.5-11] (374-387).
- 19/05: Borrado y otros detalles en árboles B [F9.12-16]
(388-405).
- 21/05: Introducción a los árboles B+ [F10.1-5]
(406-420). Tarea 5 (para el 06/06). Página de prueba.
- 23/05: Propiedades de los árboles B+ [F10.6-10]
(421-429).
- 26/05: Introducción a la dispersión [F11.1-4]
(430-447).
- 28/05: Técnicas de dispersión
[F11.5-8] (448-464).
- 30/05: Terminó el curso.
- 02/06: Terminó el curso.
- 04/06: Fin del curso.
- 06/06: Segundo
examen
parcial (325-464) (16:00
en el F208).
- 10/06: Hoy
entregué el acta.
- 20/06: Examen de recuperación (16:00).
- x/x: Reutilizando espacio en archivos [F6.2] (107-117).
- y/y: Ordenamiento y búsqueda interna de claves [F6.3-4]
(118-128).
Bibliografía
- Budd. Classic
Data Structures in Java.
Addison Wesley.
- Cormen, Leiserson, Rivest y Stein. Introduction to
Algorithms. Mc Graw Hill.
- Folk,
Zoellick y Riccardi. File Structures:
An Object-oriented Approach with
C++. Addison Wesley. [Libro de texto]
- Kleinberg
y Tardos. Algorithm Design.
Addison Wesley.
- Knuth.
The
Art
of Computer Programming: Vol. 3 Sorting and Searching. Addison
Wesley.
- Langsam, Augenstein y
Tenenbaum. Estructuras de datos con C y C++. Prentice Hall.
- Loomis. Data Management and File Structures. Prentice Hall.
- Parberry. Problems
on Algorithms.
Prentice Hall.
- Sedgewick.
Algoritmos en C++.
Pearson. [Libro de texto]
- Tharp. File
Organization and Processing. Wiley.
