115112 Almacenamiento y Recuperación de la Información
Trimestre 2011 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes 9
de mayo a viernes a viernes 22 de julio de 2011.
Grupo: CSI81 (lunes,
miércoles y viernes de 15:00 a 16:30).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: E-309.
Cupo: 55 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á 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 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).
09/05:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Estructuras
de archivos [F1.1] (1-10).
11/05:
No habrá clase.
13/05:
Operaciones
fundamentales
de
archivos
[F2.1-8]
(11-30).
16/05: Hardware
de
discos [F3.1] (31-42).
18/05: Hardware
de
cintas [F3.2,3,7] (43-55).
20/05: Archivos y el sistema operativo
[F3.8-9] (56-67). Tarea 1 (para el 23/05).
23/05:
Campos
y
registros
en
archivos
[F4.1]
(68-81).
25/05:
Manipulación
de
archivos
de
registros
[F5.1-2]
(82-95).
27/05:
Compresión
de
archivos
[F6.1]
(96-106).
30/05: Reutilizando
espacio en archivos [F6.2] (107-117) y Ordenamiento y búsqueda
interna de claves [F6.3-4]
(118-128).
01/06: No habrá clase debido a la
presentación de la propuesta de plan de estudios de
Ingeniería en computación.
03/06: Primer examen
parcial (1-128). El password es ARIZ. Tarea 2
(para el 10/06).
06/06:
Representación
de
grafos
no
dirigidos
y
aplicaciones
[S29]
(129-149)
y
representación
de
grafos
dirigidos
y
aplicaciones
[S32] (150-164).
08/06:
No habrá clase.
10/06:
Búsqueda
en
profundidad
y
búsqueda
en
amplitud
[S29
y
S32]
(165-196).
13/06: Conexidad,
unión-pertenencia y ordenamiento
topológico [S30 y S32] (197-218).
15/06: Árboles abarcadores de
costo mínimo (Kruskal
y
Prim) [S31] (219-239).
17/06: Caminos más cortos
(Dijkstra y Floyd) [S31 y S32]
(240-256).
20/06:
Árboles
AVL
y
árboles
2-3-4
[S15]
(257-276).
22/06:
Árboles
AVL
y
árboles
rojinegros
[S15]
(277-294).
24/06:
Segundo examen
parcial (129-294).
27/06: Índices sencillos y
grandes [F7.1-5] (295-309).
29/06: Índices secundarios
[F7.6-10] (310-324).
01/07: Operaciones cosecuenciales
[F8.1-4] (325-337). Tarea 3 (para el 08/07).
04/07:
Ordenamiento
externo
en
discos
[F8.5]
(338-348).
Tarea 4 (para el 13/07).
06/07:
Ordenamiento
externo
en
cintas
[F8.6]
(349-360).
08/07:
Introducción
a
los
árboles
B
[F9.1-4]
(361-384).
11/07: Propiedades de los árboles
B
[F9.5-11] (385-405).
13/07: Introducción a los
árboles B+ [F10.1-5]
(406-420).
15/07: Propiedades de los árboles
B+ [F10.6-10]
(421-429). Tarea 5 (para el 22/07).
18/07:
Introducción
a
la
dispersión
[F11.1-4]
(430-447).
Tarea 6 (para el 25/07)
20/07:
Técnicas
de
dispersión
[F11.5-8]
(448-464).
22/07: Tercer examen
parcial (295-464). Fin del curso.
02/08:
Entrega del acta. Cualquier aclaración
regresando de
vacaciones.
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.
