1151041 Almacenamiento y Estructuras de Archivos
Trimestre 2017 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 11 de septiembre a lunes 11 de
diciembre de 2017.
Grupo: CSI81 (lunes,
miércoles y viernes de 16:00 a 17:30).
Asesorías: lunes, miércoles
y viernes de 10:00 a 11:30 en la oficina H-264.
Salón: G208.
Cupo: 50.
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.
- Algoritmos de procesamiento de cadenas.
- Operaciones fundamentales de archivos.
- Sistemas de archivos.
- Organización de datos.
- Almacenamiento secundario y terciario.
- Compresión y compactación de archivos.
- Ordenamiento externo.
- Índices.
- Árboles B y B+.
- Dispersión y dispersión extendida.
Evaluación
Habrá tres exámenes y al menos ocho
tareas. Cada examen valdrá 20 puntos y
cada tarea valdrá 5 puntos. No habrá examen global. Se requiere
obtener
- al menos 30 puntos en los exámenes, 20 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 25 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 40 puntos en los exámenes, 30 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 aea en callix.azc.uam.mx y deberán estar escritas en 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 Kernighan y Ritchie [KR] a la derecha de cada tema. Aquí hay unas transparencias
que corresponden a un curso anterior.
11/09:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Cadenas.
13/09:
Búsqueda de caracteres en cadenas y subcadenas.
15/09:
Día
feriado.
18/09: Búsqueda de subcadenas: fuerza
bruta y Knuth-Morris-Pratt
[SW5.3, ESMA]. Tarea
1 (para el 16/10).
19/09-02/10: No
hubo clases por causas de fuerza mayor.
04/10: Ordenamiento de cadenas [SW5.1].
06/10: Búsqueda de subcadenas: Rabin-Karp
[SW5.3, ESMA].
09/10:
Dispersión [F11.1-8].
11/10:
Dispersión extendida [F12.1-3].
13/10:
Estructuras de archivos [F1.1].
16/10: Operaciones fundamentales de
archivos [F2.1-10] y [KR7]. Tarea
2 (para el 23/10).
18/10: Discos magnéticos [F3.1,7] y
cintas magnéticas [F3.2,3]. Lectura.
20/10: Discos
ópticos [F3.4-6] y de estado sólido.
Tarea 3 (para el 25/10).
23/10:
Archivos y el sistema operativo [F3.8-9] y [KR8]. Sistemas de
archivos [F3.10].
24/10:
Estaré en una conferencia.
25/10:
Primer examen parcial.
27/10:
Campos y registros en archivos [F4.1]. Tarea 4
(para el 04/12).
30/10: Manipulación de buffers
[F4.2-4].
01/11: Día feriado.
03/11: Manipulación de archivos de
registros [F5.1-2]. Tarea
5 (para el 24/11).
03/11: Comienza el XIV Concurso de
Programación de la UAM.
06/11:
Compresión
de archivos sin pérdida [F6.1].
08/11:
Compresión de archivos con pérdida [F6.1]. Compactación de
archivos [F6.2].
10/11:
Ordenamiento y búsqueda interna de claves [F6.3-4]. Tarea
6 (para el 01/12).
13/11: Índices sencillos y grandes
[F7.1-5].
15/11: Índices secundarios [F7.6-10].
17/11: Segundo examen parcial.
20/11:
Día feriado.
22/11:
Operaciones cosecuenciales [F8.1-4].
24/11:
Ordenamiento externo en discos [F8.5]. Tarea
7 (para el 08/12).
27/11: Ordenamiento externo en cintas
[F8.6].
29/11: Introducción a los árboles B
[F9.1-4].
01/12: Propiedades de los árboles B
[F9.5-11].
04/12:
Borrado y otros detalles en árboles B [F9.12-16]. Tarea
8 (para el 10/12).
04/12:
Termina el XIV
Concurso de Programación de la UAM.
06/12:
Introducción a los árboles B+ [F10.1-5].
08/12:
Propiedades de los árboles B+ [F10.6-10].
11/12: Tercer examen parcial.
Bibliografía
- Byers. Care
and Handling of CDs and DVDs: A Guide for Librarians and
Archivists. NIST.
- Charras y Lecroq. Exact
String Matching Algorithms. Université de Rouen.
- Folk, Zoellick y Riccardi.
File
Structures: An Object-oriented Approach with C++. Addison
Wesley.
- Hutchinson. Solid-State
Revolution. Ars technica.
- Kernighan y Ritchie. El lenguaje de programación C. Pearson.
- Knuth.
The
Art of Computer Programming: Vol. 3 Sorting and Searching.
Addison Wesley.
- Loomis. Data Management and File Structures. Prentice Hall.
- Pate. UNIX File Systems: Evolution, Design, and
Implementation. Wiley.
- O'Kelly. Reference
Guide for Optical Media. Memorex.
- Salomon. A Concise Introduction to Data Compression. Springer.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Wayne. Algorithms.
Pearson.
- Tharp. File
Organization and Processing. Wiley.