115112 Almacenamiento y Recuperación de la Información
Trimestre 2013 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 22 de abril a martes 9 de julio de 2013.
Grupo: CSI01 (lunes,
miércoles y viernes de 11:30 a 13:00).
Asesorías: lunes, miércoles
y viernes de 10:00 a 11:30 en la oficina H-264.
Salón: E309.
Cupo: 50 alumnos.
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 al menos 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 callix.azc.uam.mx y podrán estar escritas en C o C++.
Su cuenta está en la misma máquina, a la que se pueden conectar
con ssh.
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).
22/04:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Estructuras
de
archivos [F1.1] (1-10).
24/04:
Operaciones fundamentales de archivos [F2.1-8] (11-30).
25/04:
Por favor regístrense en esta plataforma
al curso "Almacenamiento y Recuperación de Información Zaragoza"
con la clave ARI13P a más tardar el 26/04. Si tienen problemas,
por favor escriban inmediatamente a cbienlinea@correo.azc.uam.mx
para que los registren. También descarguen este manual.
26/04:
Hardware de discos [F3.1]
(31-42). Tarea 1 (ya está en la plataforma, son dos partes, para
el (a) 29/04 y (b) 01/05).
29/04: Hardware de cintas [F3.2,3,7] (43-55).
01/05: Día
feriado.
03/05: Archivos y el sistema
operativo [F3.8-9] (56-67).
06/05:
Campos y registros en archivos [F4.1] (68-81). Hoy y mañana será
la visita de CACEI
para Ingeniería en Computación.
08/05:
Manipulación de archivos de registros [F5.1-2] (82-95). Tarea 2 (para el 17/05).
10/05:
Día feriado.
13/05: Compresión de archivos [F6.1]
(96-106).
15/05: Día
feriado.
17/05: Reutilizando espacio en
archivos [F6.2] (107-117) y Ordenamiento y búsqueda interna de
claves [F6.3-4] (118-128).
20/05:
Primer examen parcial
(1-128) será en el Aula educativa H299 (los pares de 11:30 a
12:10, los impares de 12:20 a 13:00).
22/05:
Representación de grafos no dirigidos y aplicaciones [S29]
(129-149).
24/05:
Representación de grafos dirigidos y aplicaciones [S32] (150-164).
Tarea 3 (para el 03/06).
27/05: Búsqueda en profundidad y
búsqueda en amplitud [S29 y S32] (165-196).
29/05: Conexidad, unión-pertenencia y
ordenamiento topológico [S30 y S32] (197-218).
31/05: Árboles abarcadores de costo
mínimo (Kruskal y Prim) [S31] (219-239). Tarea
4 (para el 10/06).
03/06:
Caminos más cortos (Dijkstra y Floyd) [S31 y S32] (240-256).
05/06:
Árboles AVL y árboles 2-3-4 [S15] (257-276).
07/06:
Árboles AVL y árboles rojinegros [S15] (277-294). Tarea 5 (para el 14/06).
10/06: Segundo examen parcial (129-294) será en el
Aula educativa H299 (los impares de
11:30 a 12:10, los pares de 12:20 a
13:00).
11/06: Asistan a esta plática.
Inviten a sus compañeros y profesores.
12/06: Índices sencillos y grandes
[F7.1-5] (295-309).
14/06: Índices secundarios [F7.6-10]
(310-324).
17/06:
Operaciones cosecuenciales [F8.1-4] (325-337).
19/06:
Ordenamiento externo en discos [F8.5] (338-348).
21/06:
Ordenamiento externo en cintas [F8.6] (349-360).
24/06: Introducción a los árboles B
[F9.1-4] (361-384).
26/06: Propiedades de los árboles B
[F9.5-11] (385-405). Tarea 6 (para el
02/07).
28/06: Introducción a los árboles B+
[F10.1-5] (406-420).
01/07:
Propiedades de los árboles B+ [F10.6-10] (421-429).
03/07:
Décimo
concurso de programación de la UAM: Examen
eliminatorio.
03/07:
Introducción a la dispersión [F11.1-4] (430-447). Tarea 7 (para el 08/07).
05/07:
Técnicas de dispersión [F11.5-8] (448-464).
08/07: Tercer examen parcial (295-464) será en el Aula
educativa H299 (los primeros 20 que
lleguen de 11:30 a 12:10, los demás
de 12:20 a 13:00).
12/07: Estas son las 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.
- 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.