Instructor: Dr. Rodrigo Alexander Castro Campos.
Trimestre: 2019-P.
Grupo: CSI01.
Horario: Lunes, miércoles y viernes de 10:00 a 11:30.
Salón: G-206.
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 nueve tareas, las cuales 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 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.
La calificación final se obtiene de las tareas resueltas al 100% según OmegaUp. La escala de calificación en acta es:
- Resolver siete tareas para acreditar con S.
- Resolver ocho tareas para acreditar con B.
- Resolver nueve tareas 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.
Pueden consultar esta lista de problemas de programación para que practiquen.
Calendario: El siguiente calendario es tentativo y podrá cambiar a lo largo del curso.
- 09/09: Presentación del curso e introducción a OmegaUp 1, 2, 3. La brecha entre el procesador y la memoria. Benchmark de acceso a memoria.
- 11/09: Almacenamiento primario y niveles de caché. Tiempos de acceso experimentales. Tarea 1 para el 20/09. Envíos aceptados.
- 13/09: Introducción a tablas de dispersión.
- 16/09: Día de descanso obligatorio.
- 18/09: Funciones de dispersión y encadenamiento separado. Ejemplos de funciones de dispersión 1, 2. Comparación entre un arreglo dinámico y una lista enlazada. Tarea 2 para el 27/09 y comentarios adicionales. Envíos aceptados.
- 20/09: Direccionamiento abierto y filtros de Bloom.
- 23/09: Acceso a archivos y E/S en formato de texto. Ejemplo de código.
- 25/09: Manipulación de texto y E/S en formato binario. Ejemplos de código 1, 2, 3, 4, 5, 6.
- 27/09: Codificación de enteros en binario. Ejemplo de salida sin formato. Tarea 3 para el 07/10 y casos de prueba. Envíos aceptados.
- 30/09: Posicionamiento en archivos y búferes de la biblioteca estándar. Generador de archivo y benchmark de la biblioteca estándar.
- 02/10: Búferes y bloques del sistema de archivos. Ejemplos de código 1, 2. Problema de práctica.
- 04/10: Fragmentación interna, externa y de datos. Tarea 4 para el 14/10. Envíos aceptados.
- 07/10: Almacenamiento secundario: discos magnéticos y de estado sólido. Benchmark de acceso a disco. Especificación de Toshiba X300 y páginas de benchmark 1, 2. Especificación de Intel SSD 660p y artículo sobre SSD.
- 09/10: Almacenamiento terciario: discos ópticos y cintas magnéticas. Especificación de Samsung SE-506BB/MIBD y de IBM 3592.
- 11/10: Ordenamiento externo sin archivos temporales y montículos. Tarea 5 para el 28/10. Ejemplo de montículos. Envíos aceptados.
- 14/10: Ordenamiento externo con archivos temporales.
- 16/10: Alfabetos y representación de cadenas. Tarea 6 para el 28/10. Envíos aceptados.
- 18/10: Ordenamiento de cadenas y búsqueda de prefijos. Ejemplo de código 1, 2.
- 21/10: Búsqueda de subcadenas y ordenamiento de sufijos.
- 23/10: Compresión de cadenas sin pérdida. Tarea 7 para el 27/11. Ejemplo del algoritmo de Huffman. Envíos aceptados.
- 25/10: Compresión de cadenas con pérdida.
- 28/10: Serialización de registros.
- 30/11: Registros de longitud constante y variable.
- 01/11: Día de descanso obligatorio.
- 04/11: Encabezados de archivos.
- 06/11: Mantenimiento de registros. Tarea 8 para el 27/11. Ejemplo de código. Envíos aceptados.
- 08/11: Acompañaré al equipo de la UAM-A a la final nacional del Concurso de Programación ICPC.
- 11/11: Índices primarios. Tarea 9 para el 27/11. Envíos aceptados.
- 13/11: Preprocesamiento de peticiones. Problema de ejemplo.
- 15/11: Árboles B e índices secundarios.
- 18/11: Árboles B+ y dispersión extendida. Ejemplos de visualización de árbol B y árbol B+.
- 20/11: Día de descanso obligatorio.
- 22/11: Sesión de preguntas y respuestas para las tareas.
- Calificaciones finales.
Enlaces de interés:
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.
|