1151041 - Almacenamiento y Estructuras de Archivos - Rodrigo Alexander Castro Campos

Rodrigo A. Castro Campos‎ > ‎

1151041 - Almacenamiento y Estructuras de Archivos

Instructor: Rodrigo Alexander Castro Campos.

Trimestre: 2022-O.

Grupo: CSI01.

Horario: Lunes, miércoles y viernes de 7:00 a 8:30.

Salón: E306.

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 once tareas con un valor de 9.1 puntos cada una. El curso se impartirá en el lenguaje C++. Las tareas consistirán en escribir programas para la plataforma omegaUp que resuelvan el problema de programación indicado para la evaluación. Sus datos deberán enviarse mediante este formulario antes de la entrega de la primera tarea. 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.

Una tarea sólo cuenta si aparece resuelta al 100% según omegaUp. La calificación final se obtiene de sumar los puntos provenientes de las tareas. 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. Los alumnos que incurran en esta falta no tendrán derecho a aprobar el curso.

¡¡¡ Participa en el XVII Concurso de Programación de la UAM "Luis Erick González Moreno" !!!

Pueden consultar esta lista de problemas de "Programación Estructurada" para que practiquen.

Pueden consultar esta lista de problemas de "Algoritmos y Estructuras de Datos" para que practiquen.

Pueden consultar esta lista de problemas de "Almacenamiento y Estructuras de Archivos" para que practiquen.

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

17/10: Presentación del curso. Introducción a omegaUp 1, 2. Prueba diagnóstica.
19/10: La brecha entre el procesador y la memoria. Benchmark de memoria.
21/10: Almacenamiento primario, niveles de caché y líneas de coherencia. Tarea 1 para el 31/10. Envíos aceptados.
24/10: Conjuntos no ordenados. Funciones de dispersión y tablas de dispersión.
26/10: Tablas de dispersión, funciones de dispersión y colisiones.
28/10: Tablas de dispersión con encadenamiento separado y direccionamiento abierto. Tarea 2 para el 07/11. Envíos aceptados.
31/10: Archivos lógicos y físicos. Flujos estándar.
02/11: Día de descanso obligatorio.
04/11: Entrada y salida con formato.
07/11: Entrada y salida sin formato. Tarea 3 para el 16/11. Envíos aceptados.
09/11: Apertura de archivos persistentes.
11/11: Búferes de la biblioteca estándar y del sistema de archivos. Benchmark de escritura en archivos.
14/11: Búferes del sistema de archivos. Benchmark de lectura en archivos.
16/11: Posicionamiento en archivos. Código de problema. Tarea 4 para el 28/11. Envíos aceptados.
18/11: Bloques del sistema de archivos y fragmentación. Tarea 5 para el 30/11. Envíos aceptados.
21/11: Almacenamiento secundario: discos magnéticos y de estado sólido. Benchmark de acceso secuencial y arbitrario.
23/11: Almacenamiento terciario: discos ópticos y cintas magnéticas.
25/11: Ordenamiento externo sin archivos temporales. Tarea 6 para el 05/12. Envíos aceptados.
28/11: Ordenamiento externo con archivos temporales.
30/11: Búsqueda lineal y búsqueda binaria en archivos. Comparación entre estrategias de búsqueda a nivel de elemento.
02/12: Multibúsqueda. Alfabetos y representación de cadenas. Comparación entre estrategias de búsqueda a nivel de bloque. Código de ejemplo. Tarea 7 para el 19/12. Envíos aceptados.
05/12: Compresión de cadenas sin pérdida.
07/12: Operadores de manipulación de bits. Tarea 8 para el 23/12. Envíos aceptados.
09/12: Compresión de cadenas sin pérdida mediante tablas de decodificación. Compresión con pérdida.
12/12: Ordenamiento de cadenas.
14/12: Árboles de prefijos. Código de problema. Tarea 9 para el 23/12. Envíos aceptados.
16/12: Búsqueda de subcadenas. Serialización de registros.
19/12: Representación de secuencias de longitud fija y variable.
21/12: Encabezados de archivos.
23/12: Mantenimiento de registros y compactación. Tarea 10 para el 19/01. Envíos aceptados.
09/01: Indices primarios. Código de ejemplo.
11/01: Índices secundarios y árboles B. Tarea 11 para el 19/01. Envíos aceptados.
13/01: Árboles B+. Dispersión extendida.
Calificaciones finales.

Entornos de programación que pueden usar localmente:

CodeBlocks (Windows, Linux): http://www.codeblocks.org/downloads/26.
- Si tienen algún problema usando la versión más reciente, pueden probar la versión 17.12.
- En Windows se sugiere descargar el instalador que incluye el compilador MinGW (enlace directo a la version 20.3), (enlace directo a la version 17.12).
Xcode (macOS): https://developer.apple.com/xcode/ide/.

Entornos de programación que pueden usar en línea:

Entorno de programación para la clase en vivo: https://racc.mx/ide
OnlineGDB: https://www.onlinegdb.com
Repl.it: https://repl.it/languages/cpp

Bibliografía:

Castro Campos. Notas de curso (se irán actualizando conforme avance el trimestre).
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

Enlaces de interés:

RAMMap de Windows Sysinternals: https://docs.microsoft.com/es-mx/sysinternals/downloads/rammap
7-Zip LZMA Benchmark: https://www.7-cpu.com
Ejemplos de funciones de dispersión: https://gist.github.com/qxj/1520414
Ejemplos de funciones de dispersión: https://github.com/brandondahler/retter
Especificación de HDD Seagate Barracuda (2018): https://www.seagate.com/www-content/product-content/barracuda-fam/barracuda-new/en-us/docs/100804187g.pdf
Especificación de SSD Intel Optane (2018): https://www.intel.la/content/dam/www/public/us/en/documents/product-briefs/optane-ssd-905p-product-brief.pdf
Características de discos Blu-Ray: https://en.wikipedia.org/wiki/Blu-ray
Especificación de lector Blu-Ray: https://www8.hp.com/h20195/v2/GetPDF.aspx/c04532032.pdf
Especificación de Cinta IBM TS1160 (2018): https://www.ibm.com/downloads/cas/ZV2V7D8Q
Características de cintas magnéticas: https://en.wikipedia.org/wiki/IBM_3592
Evolución de cintas magnéticas: https://indico.cern.ch/event/810635/contributions/3596108/attachments/1922647/3181001/IBMs_3592_Storage_Solution_-_a_taste_of_the_future_2019.pdf