115112 Almacenamiento y Recuperación de la Información
Trimestre 2013 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 14 de enero a martes 2 de abril de 2013.
Grupo: CSI81 (lunes,
miércoles y viernes de 15:00 a 16:30).
Asesorías: lunes, miércoles
y viernes de 16:30 a 18:00 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).
14/01:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Estructuras
de
archivos [F1.1] (1-10).
16/01:
Operaciones fundamentales de archivos [F2.1-8] (11-30).
18/01:
Hardware de discos [F3.1]
(31-42). Tarea 1 (para el 23/01).
21/01: Hardware de cintas [F3.2,3,7] (43-55).
23/01: Archivos y el sistema
operativo [F3.8-9] (56-67).
24/01: Por
favor regístrense en esta plataforma
al curso "Almacenamiento y Recuperación de Información Zaragoza"
con la clave ARIZ a más tardar el 31/01. Si tienen problemas,
por favor escriban inmediatamente a cbienlinea@correo.azc.uam.mx
para que los registren.
25/01: Campos y registros en archivos
[F4.1] (68-81).
28/01:
Manipulación de archivos de registros [F5.1-2] (82-95). Tarea 2 (para el 04/02). Almacenamiento
en ADN.
30/01:
Compresión de archivos [F6.1] (96-106).
01/02:
Reutilizando espacio en archivos [F6.2] (107-117) y Ordenamiento y
búsqueda interna de claves [F6.3-4] (118-128).
04/02: Primer examen parcial (1-128).
06/02: Representación de grafos no
dirigidos y aplicaciones [S29] (129-149).
08/02: Representación de grafos
dirigidos y aplicaciones [S32] (150-164).
11/02:
Búsqueda en profundidad y búsqueda en amplitud [S29 y S32]
(165-196). Tarea 3 (para el 18/02).
13/02:
Conexidad, unión-pertenencia y ordenamiento topológico [S30 y S32]
(197-218).
15/02:
Árboles abarcadores de costo mínimo (Kruskal y Prim) [S31]
(219-239).
18/02: Caminos más cortos (Dijkstra y
Floyd) [S31 y S32] (240-256).
20/02: Árboles AVL y árboles 2-3-4
[S15] (257-276). Tarea 4 (para el 27/02).
22/02: Árboles AVL y árboles
rojinegros [S15] (277-294).
25/02:
Índices sencillos y grandes [F7.1-5] (295-309).
27/02:
Índices secundarios [F7.6-10] (310-324).
01/03:
Operaciones cosecuenciales [F8.1-4] (325-337).
04/03: Día feriado.
06/03: Segundo examen parcial (129-337).
08/03: Ordenamiento externo en discos
[F8.5] (338-348).
11/03:
Ordenamiento externo en cintas [F8.6] (349-360). Tarea 5 (para el 18/03).
13/03:
Introducción a los árboles B [F9.1-4] (361-384).
15/03:
Propiedades de los árboles B [F9.5-11] (385-405).
18/03: Introducción a los árboles B+
[F10.1-5] (406-420).
20/03: Propiedades de los árboles B+
[F10.6-10] (421-429).
22/03: No
habrá clase por causas de fuerza mayor.
25/03:
Introducción a la dispersión [F11.1-4] (430-464). Tarea 6 (para el 01/04).
27/03:
Curso terminado.
29/03:
Día feriado.
01/04:
Tercer examen parcial
(338-464).
08/04:
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.
