115112 Almacenamiento y Recuperación de la Información
Trimestre 2007 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
17 de septiembre a viernes 7 de diciembre.
Grupo: CCT01 (lunes,
miércoles y viernes de 10:00
a
11:30).
Asesorías: lunes,
miércoles y viernes de 11:30 a 13:00 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á tres exámenes y ocho tareas. Cada examen
valdrá 20 puntos y cada tarea valdrá 5 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
(¡completas!) a la derecha
de cada
tema (N).
- 17/09: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Estructuras de archivos [F1.1] (N1-9).
- 19/09: Operaciones fundamentales
de archivos [F2.1-8] (N10-24).
- 21/09: Hardware de
discos [F3.1] (N25-36).
- 24/09: Hardware de
cintas [F3.2,3,7] (N37-47). Primera tarea (para
el
01/10).
- 26/09: Archivos y el sistema operativo [F3.8-9] (N48-57).
- 28/09: Campos y registros en archivos [F4.1] (N58-71).
- 01/10: Manipulación de archivos de registros [F5.1-2]
(N72-84). Segunda tarea (para el 08/10).
- 03/10: Compresión de archivos [F6.1] (N85-95).
- 05/10: Reutilizando espacio en archivos [F6.2] (N96-105).
- 08/10: Ordenamiento y búsqueda interna de claves [F6.3-4]
(N106-114).
- 10/10: Representación de
grafos no dirigidos y aplicaciones [S29] (N115-134). Tercera
tarea
(para el 05/11).
- 11/10: El disco duro de la máquina donde estaban sus
cuentas amaneció muerto. Me tomará cierta cantidad de
tiempo darles cuentas nuevas. La fecha de entrega de cualquier tarea
que haya dejado se correrá a al menos una semana después
de que les dé sus nuevas cuentas.
- 11/10 a 15/10: Cuarto concurso de
programación de la UAM Azcapotzalco. Examen eliminatorio.
- 12/10: Día feriado.
- 15/10: Sesión de preguntas sobre el examen.
- 17/10: Primer examen
parcial (F1 a F6).
- 19/10: No habrá
clase, estaré en un congreso. Entrega de
calificaciones del primer examen parcial.
- 22/10: Representación de
grafos dirigidos y aplicaciones [S32] (N135-149).
- 23/10: Cuarto concurso de
programación de la UAM Azcapotzalco. Examen final.
- 24/10: Búsqueda en profundidad y búsqueda en
amplitud [S29 y S32] (N150-163). Ya
tienen cuentas y claves nuevas. Envíen sus
dos primeras tareas a más tardar el 02/11.
- 26/10: Conexidad, unión-pertenencia y ordenamiento
topológico [S30 y S32] (N164-177).
- 29/10: Árboles abarcadores de costo mínimo (Kruskal
y
Prim) [S31] (N178-188).
- 31/10: Caminos más cortos (Dijkstra y Floyd) [S31 y S32]
(N189-198). Cuarta
tarea (para el 12/11).
- 02/11: Día feriado.
- 03/11 y 04/11: Competencia regional de México y
Centroamérica del ACM ICPC en Querétaro.
- 05/11: Árboles AVL y árboles 2-3-4
[S15] (N199-214).
- 07/11: Árboles
AVL y árboles rojinegros [S15] (N215-230).
- 09/11: Segundo examen
parcial (S15 y S29 a S32).
- 12/11: Índices sencillos y grandes [F7.1-5] (N231-243). Quinta tarea
(para el
19/11).
- 14/11: Índices secundarios
[F7.6-10] (N244-258).
- 16/11: Operaciones cosecuenciales [F8.1-4] (N259-270).
- 19/11: Ordenamiento externo en discos [F8.5] (N271-281). Sexta tarea
(para el 26/11).
- 21/11: Ordenamiento externo en cintas [F8.6] (N282-293).
- 23/11: Introducción a los árboles B [F9.1-4]
(N294-303).
- 26/11: Operaciones y propiedades de los árboles B
[F9.5-11] (N304-313). Séptima tarea (para
el 03/12).
- 28/11: Borrado y otros detalles en árboles B [F9.12-16]
(N314-329).
- 30/11: Introducción a los árboles B+ [F10.1-5]
(N330-342).
- 03/12: Propiedades de los árboles B+ [F10.6-10]
(N343-351). Octava
tarea (para el 10/12).
- 05/12: Introducción a la dispersión [F11.1-4]
(N352-365).
- 07/12: Fin del curso. Técnicas de dispersión
[F11.5-8] (N366-378).
- 10/12: Tercer
examen parcial (F7 a F11). No habrá global, pero
está programado para esta fecha a las 10:00 en el E309. Recordatorio:
Entréguenme al inicio del examen las correcciones que consideren
convenientes de las notas. Cada corrección buena será un
punto adicional (hasta un máximo de 5).
- 13/12: Calificaciones finales.
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.
- Parberry. Problems
on Algorithms.
Prentice Hall.
- Sedgewick.
Algoritmos en C++.
Pearson. [Libro de texto]
- Tharp. File
Organization and Processing. Wiley.