115112 Almacenamiento y Recuperación de la Información
Trimestre 2008 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso:
miércoles 18 de junio a miércoles 27 de agosto de 2008.
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: Sala Charles
Babbage (Edificio T).
Cupo: 30 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.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 (corregidas) a la derecha
de cada
tema (A-B).
- 18/06: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Estructuras de archivos [F1.1] (1-10).
- 20/06: Operaciones fundamentales
de archivos [F2.1-8] (11-30).
- 23/06: Hardware de
discos [F3.1] (31-42).
- 25/06: Hardware de
cintas [F3.2,3,7] (43-55). Primera tarea (para
el 07/07).
- 27/06: Archivos y el sistema operativo [F3.8-9] (56-67).
- 30/06: Campos y registros en archivos [F4.1] (68-81).
- 02/07: Manipulación de archivos de registros [F5.1-2]
(82-95).
- 04/07: Compresión de archivos [F6.1] (96-106).
- 07/07: Reutilizando
espacio en archivos [F6.2] (107-117).
- 09/07: Ordenamiento y búsqueda interna de claves [F6.3-4]
(118-128). Segunda
tarea (para el 21/07).
Calificada (promedio 4.0).
- 11/07: Primer examen
parcial (1-128). Promedio
55 de 75.
- 14/07: Representación de
grafos no dirigidos y aplicaciones [S29] (129-149).
- 16/07: Representación de
grafos dirigidos y aplicaciones [S32] (150-164).
- 18/07: Búsqueda en profundidad y búsqueda en
amplitud [S29 y S32] (165-196).
- 21/07: Conexidad, unión-pertenencia y ordenamiento
topológico [S30 y S32] (197-218). Tercera
tarea (para el 28/07). Calificada
(promedio 0.9).
- 23/07: Árboles abarcadores de costo mínimo (Kruskal
y
Prim) [S31] (219-239).
- 25/07: Caminos más cortos (Dijkstra y Floyd) [S31 y S32]
(240-256).
- 28/07: Árboles AVL y árboles 2-3-4
[S15] (257-276).
- 30/07: Árboles
AVL y árboles rojinegros [S15] (277-294). Cuarta
tarea (para el 15/08).
Calificada (promedio 3.7).
- 01/08: Segundo examen
parcial (129-294). Promedio
44 de 75.
- 04/08: Índices sencillos y grandes [F7.1-5] (295-309).
- 06/08: Índices secundarios
[F7.6-10] (310-324).
- 08/08: Operaciones cosecuenciales [F8.1-4] (325-337).
- 11/08: Ordenamiento externo en discos [F8.5] (338-348). Quinta
tarea (para el 20/08).
Calificada (promedio 3.4).
- Ya está
funcionando la conexión a mi maquina.
- Usen el IP 148.206.75.15 (también funciona el servidor
de nombres).
- Tendrán
hasta el 15/08 para entregarme la cuarta tarea y hasta el 20/08 para
entregarme la quinta tarea.
- 13/08: Ordenamiento externo en cintas [F8.6] (349-360).
- 15/08: Introducción a los árboles B [F9.1-4]
(361-384).
- 18/08: Propiedades de los árboles B
[F9.5-11] (385-405).
- 20/08 a 27/08: Etapa eliminatoria del Quinto Concurso de
Programación de la UAM.
- 20/08: Introducción a los árboles B+ [F10.1-5]
(406-420). Sexta tarea (para el 28/08). Calificada (promedio 4.1).
- Ya puedes descargar el examen
eliminatorio del Quinto Concurso de Programación de la UAM.
Aclaraciones: Problema 2.
- Asiste hoy a las 14:30 en la sala D001 a la visita de la
compañía alemana Continental
Corporation líder en el desarrollo de sistemas
electrónicos para el automóvil.
- 22/08: Propiedades de los árboles B+ [F10.6-10]
(421-429).
- 25/08: Introducción a la dispersión [F11.1-4]
(430-447).
- 27/08: Técnicas de dispersión
[F11.5-8] (448-464). Fin del curso.
- 01/09:
Tercer examen
parcial (295-464) de
10:00 a 11:30 en el salón F212. Promedio 42 de 75.
- 02/09: Entrega de calificaciones finales y entrega del acta.
- 02/09 a 04/09: Nueva fecha límite para entrega de
solicitudes de Becas Erasmus.
- 30/09: Exámen de recuperación (Titular: Francisco
Zaragoza, Suplente: Josué Figueroa, 13:00).
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.
