115112 Almacenamiento y Recuperación de la Información
Trimestre 2009 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
18 de mayo a miércoles 29 de julio de 2009.
Grupo: CCT81 (martes y jueves
de 15:15
a
17:30).
Asesorías: lunes y
miércoles de 15:15 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á dos exámenes y seis tareas. Cada examen
valdrá 35 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 callix
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.79.29.
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/05: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Árboles AVL [S15] (1-16).
- 21/05: Árboles 2-3-4. Árboles rojinegros [S15]
(17-42).
- 26/05: Representación de
grafos no dirigidos y dirigidos. Aplicaciones [S29 y S32] (43-78).
- 28/05: Búsqueda en profundidad y búsqueda en
amplitud [S29, S30 y S32] (79-110). Primera tarea
(para
el 18/06).
- 02/06: Aplicaciones de búsqueda en profundidad y
búsqueda en
amplitud [S29, S30 y S32] (111-132).
- 04/06: Búsqueda por prioridad. Árboles abarcadores
de costo mínimo (Kruskal
y
Prim) [S31] (133-153).
- 09/06: Caminos más cortos (Dijkstra y Floyd) [S31 y S32]
(154-170).
- 11/06: Estructuras de archivos [F1.1]. Operaciones fundamentales
de archivos [F2.1-8] (171-196).
- 16/06: Primer examen
parcial: Árboles balanceados y grafos. Entrega de cuentas. Calificaciones del primer
parcial.
- 18/06: Hardware de
discos [F3.1]. Hardware de
cintas [F3.2,3,7] (197-221).
- 23/06: Archivos y el sistema operativo [F3.8-9]. Campos y
registros en archivos [F4.1] (222-247).
- 25/06: Manipulación de archivos de registros [F5.1-2]
(248-261). Segunda tarea (para el 07/07).
- 30/06: Compresión de archivos [F6.1]. Reutilizando
espacio en archivos [F6.2] (262-283). Tercera tarea
(para el 02/07).
- 02/07: Ordenamiento y búsqueda interna de claves [F6.3-4]
(284-294).
- 07/07: Índices sencillos y grandes [F7.1-5] (295-309).
- 09/07: Índices secundarios
[F7.6-10]. Operaciones cosecuenciales [F8.1-4] (310-332). Cuarta tarea (para el 17/07).
- 14/07: Ordenamiento externo en discos [F8.5] (333-348). Quinta tarea (para el 24/07).
- 16/07: Ordenamiento externo en cintas [F8.6] (349-360).
- 21/07: Árboles B [F9.1-11] (361-405). Sexta
tarea (para el
31/07).
- 23/07: Árboles B+ [F10.1-10] (406-429).
- 28/07: Técnicas de dispersión [F11.1-8] (430-464).
- 30/07: Segundo
examen
parcial: Estructura de archivos,
índices, árboles B y B+ y técnicas de
dispersión (13:00 a 15:00 en el E302).
- 03/08: Calificaciones finales.
- 09/09: Examen de recuperación
(7:00 a 10:00, salón por definirse).
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.