Rodrigo Alexander Castro Campos

Trimestres anteriores‎ > ‎2018-I‎ > ‎

1151041 - Almacenamiento y Estructuras de Archivos

Instructor: Dr. Rodrigo Alexander Castro Campos.

Trimestre: 2018-I.

Grupo: CSI01.

Horario: Lunes, miércoles y viernes de 11:30 a 13:00.

Salón: E-309.

Contenido oficial del curso:

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.

Calificación:

Habrán ocho tareas con un valor de 12.5 puntos cada una. Las tareas consistirán en programas escritos para la plataforma OmegaUp que resuelvan el problema de programación indicado para la evaluación. Su matrícula y nombre de usuario en OmegaUp deberán ser enviados a mi correo electrónico en la primera semana de clases. No se calificarán programas de ninguna otra forma. Cada tarea estará disponible con al menos una semana de anticipación con respecto a la fecha de entrega. No habrá evaluación terminal.

La calificación final se obtiene de la suma de los puntajes de las tareas resueltas al 100% según OmegaUp. La escala de calificación en acta es:

Al menos 60 puntos para acreditar con S.
Al menos 73 puntos para acreditar con B.
Al menos 87 puntos para acreditar con MB.

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 y se impondrá desde amonestación escrita hasta suspensión por dos trimestres.

Calendario: El siguiente calendario es tentativo y podrá cambiar a lo largo del curso.

15/01: Búsqueda de caracteres en cadenas.
17/01: Búsqueda de caracteres en subcadenas. Ejemplo de índice invertido.
19/01: Búsqueda de subcadenas.
22/01: Ordenamiento de cadenas. Ejemplo de radix sort.
24/01: Ordenamiento y procesamiento de cadenas. Tarea 1 para entrega el 02/02. Envíos aceptados.
26/01: Árboles de prefijos y E/S rápida. Funciones de dispersión. Ejemplos de funciones de dispersión.
29/01: Aplicaciones de dispersión en algoritmos.
31/01: Tablas de dispersión y resolución de colisiones. Tarea 2 para entrega el 12/02. Envíos aceptados.
02/02: Tablas de dispersión y redimensionamiento.
05/02: Día de descanso obligatorio.
07/02: Cachés y rendimiento. Ejemplo de benchmark de memoria. Tiempos de acceso experimentales.
09/02: Impacto del sistema operativo en el rendimiento. Ejemplo de benchmark de disco y generador de archivo.
12/02: Archivos físicos y lógicos. Ejemplo de benchmark del búfer de E/S de la biblioteca de C.
14/02: Operaciones fundamentales de archivos. Tarea 3 para entrega el 21/02. Ejemplos de instancias. Envíos aceptados.
16/02: Bloques, páginas y sistemas de archivos.
19/02: Fragmentación interna, externa y de datos.
21/02: Efectos de la fragmentación, discos magnéticos y de estado sólido. Artículo sobre la geometría física de un disco duro magnético. Tarea 4 para entrega el 28/02. Envíos aceptados.
23/02: Posicionamiento sobre el disco. Ejemplo de benchmark de posicionamiento en archivos.
26/02: Ordenamiento externo sin archivos temporales. Tarea 5 para entrega el 09/03. Envíos aceptados.
28/02: Montículos como estructura auxiliar para ordenamiento en disco.
02/03: Ordenamiento externo con archivos temporales.
05/03: Cintas magnéticas y discos ópticos.
07/03: Compresión con pérdida.
09/03: Compresión sin pérdida. Algoritmo de Huffman. Tarea 6 para el 19/03. Envíos aceptados.
12/03: Serialización de registros.
14/03: Registros de longitud constante y variable.
16/03: Clase cancelada por paro.
19/03: Mantenimiento de registros. Ejemplo de colección de enteros. Tarea 7 para el 30/03. Envíos aceptados.
21/03: Día de descanso obligatorio.
23/03: Encabezados de archivos. Segundo ejemplo de colección de enteros.
26/03: Índices primarios.
28/03: Índices secundarios. Tarea 8 para el 11/04. Envíos aceptados.
30/03: Día de descanso obligatorio.
02/04: Árboles B y B+. Ejemplo de visualización de árbol B+ (esta implementación deja la mediana del lado derecho).
04/04: Dispersión extendida.
Calificaciones finales.

Bibliografía:

Folk, Zoellick y Riccardi. File Structures: An Object-oriented Approach with C++. Addison Wesley.
Knuth. The Art of Computer Programming: Vol. 3 Sorting and Searching. Addison Wesley.
Pate. UNIX File Systems: Evolution, Design, and Implementation. Wiley.
Salomon. A Concise Introduction to Data Compression. Springer.
Sedgewick. Algoritmos en C++. Pearson.
Tharp. File Organization and Processing. Wiley.

archivo_disco.cpp

(1k)

benchmark_disco.cpp

(1k)

benchmark_memoria.cpp

(1k)

benchmark_seek.cpp

(1k)

benchmark_stdio.cpp

(1k)

calificaciones.txt

(1k)

coleccion.cpp

(1k)

coleccion2.cpp

(3k)

huffman.cpp

(1k)

invertido.cpp

(1k)

radix.cpp

(1k)

tarea1.txt

(0k)

tarea2.txt

(0k)

tarea3.txt

(0k)

tarea3.zip

(548k)

tarea4.txt

(0k)

tarea5.txt

(0k)

tarea6.txt

(0k)

tarea7.txt

(0k)

tarea8.txt

(0k)