115112 Almacenamiento y Recuperación de la Información
Trimestre 2009 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
19 de enero a viernes 3 de abril de 2009.
Grupo: CCT01 (lunes,
miércoles y viernes de 10:00
a
11:30).
Asesorías: lunes,
miércoles y viernes de 16:00 a 17:30 en la
oficina H-264.
Salón: E-309.
Cupo: 40 estudiantes incluyendo
a los
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á tres exámenes y seis tareas. Cada examen
valdrá 25 puntos
y cada tarea valdrá 5 puntos. No
habrá examen global. Se
requiere obtener
- al menos 35 puntos en los exámenes, 15 puntos en las
tareas y un total de al menos 60 puntos para acreditar con S,
- al menos 40 puntos en los exámenes, 20 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, 25 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.
Su cuenta
está en la misma máquina, a la que se pueden conectar con
ssh y que tiene
dirección IP 148.206.75.15.
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).
- 19/01: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Estructuras de archivos [F1.1] (1-10).
- 21/01: Operaciones fundamentales
de archivos [F2.1-8] (11-30).
- 23/01: Hardware de
discos [F3.1] (31-42).
- 26/01: Hardware de
cintas [F3.2,3,7] (43-55). Primera tarea (para
el 02/02). Calificación promedio: 4 de 5.
- 28/01: Archivos y el sistema operativo [F3.8-9] (56-67).
- 30/01: Campos y registros en archivos [F4.1] (68-81).
- 02/02: Manipulación de archivos de registros [F5.1-2]
(82-95).
- 04/02: Compresión de archivos [F6.1] (96-106). Segunda
tarea (para el 18/02).
Calificaciones.
- 06/02: Reutilizando
espacio en archivos [F6.2] (107-117).
- 09/02: Ordenamiento y búsqueda interna de claves [F6.3-4]
(118-128).
- 11/02: Primer examen
parcial (1-128). Calificación promedio: 56 de 75.
- 13/02: Representación de
grafos no dirigidos y aplicaciones [S29] (129-149).
- 16/02: Representación de
grafos dirigidos y aplicaciones [S32] (150-164). Ya está instalado alpine y ya
revisé que funciona.
- 18/02: Búsqueda en profundidad y búsqueda en
amplitud [S29 y S32] (165-196).
- 20/02: Conexidad, unión-pertenencia y ordenamiento
topológico [S30 y S32] (197-218). Tercera
tarea (para el 05/03). Calificaciones.
- 23/02: Árboles abarcadores de costo mínimo (Kruskal
y
Prim) [S31] (219-239).
- 25/02: Caminos más cortos (Dijkstra y Floyd) [S31 y S32]
(240-256).
- 27/02: Árboles AVL y árboles 2-3-4
[S15] (257-276).
- 02/03: Árboles
AVL y árboles rojinegros [S15] (277-294). Cuarta
tarea (para el 11/03). Calificaciones.
- 04/03: Día feriado.
- 06/03: Segundo examen
parcial (129-294).
- 09/03: Índices sencillos y grandes [F7.1-5] (295-309).
- 11/03: Índices secundarios
[F7.6-10] (310-324).
- 13/03: Operaciones cosecuenciales [F8.1-4] (325-337).
- 16/03: Ordenamiento externo en discos [F8.5] (338-348). Quinta tarea (para el 25/03). Calificaciones.
- 18/03: Ordenamiento externo en cintas [F8.6] (349-360).
- 20/03: Introducción a los árboles B [F9.1-4]
(361-384).
- 23/03: Propiedades de los árboles B
[F9.5-11] (385-405).
- 25/03: Introducción a los árboles B+ [F10.1-5]
(406-420).
- 27/03: Propiedades de los árboles B+ [F10.6-10]
(421-429).
- 30/03: Introducción a la dispersión [F11.1-4]
(430-447).
- 01/04: Técnicas de dispersión
[F11.5-8] (448-464).
- 03/04: Tercer examen
parcial (295-464). Fin del curso.
- 07/04: Ya tengo las calificaciones del 3er
examen.
- 08/04: Estas son las calificaciones finales,
por favor revísenlas.
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.