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