75.06. Organización de Datos

Capacitar al alumno en el diseño de soluciones de problemas que requieren grandes volúmenes de datos, utilizando medios de almacenamiento masivos (magnéticos y ópticos), brindándole un base sólida que le permita emplear técnicas y herramientas específicas de programación existentes y crear nuevas de ser necesario. Estar capacitado para operar en forma óptima sistemas de organización de información y de mejorar sus rendimientos

1. Organización de archivos.
2. Operaciones entre archivos.
3. Organización directa: Hashing.
4. Organización indexada: Arboles
5. Introducción a la teoría de la información y compresión de datos.
6. Indices e information retrieval.
7. Motores de bases de datos y data-mining.
8. Normalización.
9. Criptografía.
10. XML, DTD, XML Schema, XPath, XSLT
11. RDF, Topics Maps
12. File Systems.

1. Organización de archivos
2. Sistemas de recuperación total de textos
3. File Systems
4. Compresión
5. Criptografía y Archivos Multimediales

1. Organización de archivos
   • Introducción: Principios conceptuales y procedimentales. Organización de archivos: registros físicos y lógicos. Definición lógica y física de registros. Acceso secuencial y relativo a registros. Caso de estudio. Metadatos e independencia lógica de datos.
     
   • Organización secuencial de archivos: Índices de identificación y de clasificación de registros. Organización secuencial indexada de archivos. Árboles B+
     
   • Organización indexada de archivos: Árboles B,B* y de recuperación (tries)
     
   • Resolución de consultas con múltiples índices: Organización directa de archivos. Índices directos.
     
2. Sistemas de recuperación total de textos
   • Introducción: Estado del arte. Concepto de término y documento
     
   • Índices Invertidos: Compresión de números de documentos. Modelos Globales: códigos unarios, códigos gamma, códigos delta, modelo global tipo Bernoulli, códigos de golomb, forma vectorial de los códigos y modelo global de frecuencia observada. Modelos Locales: modelo local tipo Bernoulli, modelo local de frecuencia observada y batching. Almacenamiento de los términos: términos de longitud fija, concatenación de términos, front coding y hashing perfecto y mínimo. Construcción de Índices invertidos: inversión por transposición de matrices e inversión por sort.
     
   • Signature-Files: Construcción de signature files. Bit Slices
     
   • Optimizaciones: Case folding. Stop words. Stemming
     
   • Resolución de consultas: Consultas Booleanas. Wildcards: N-gramas y léxico rotado. Consultas ranqueadas: coordinate matching, producto interno, producto interno mejorado y modelos de espacios vectoriales (método del coseno). Phrase queries: Los índices nextword. Consultas por proximidad.
     
3. File Systems
   • Organización del espacio en disco: Identificación y localización de archivos. Seguridad y auditoria de accesos. Casos de estudio
     
   • Buffering:
4. Compresión
   • Introducción: Estado del arte. Datos e Información. Codificación. Desigualdad de Kraft Códigos Prefijos. Entropía
     
   • Compresores Estadísticos: Huffuman: Representación de bits en bytes. Huffman dinámico. Códigos de Shannon Fano. Manejo eficiente del árbol. Half coding. Compresión aritmética: Aritmética de enteros. Descompresión en aritmético. Implementación con números binarios. Utilización de contextos. PPMC: Inicio de la compresión. Descompresión
     
   • Compresión no estadística: LZ77. Lz78 – LZW: Caso particular. Clearing. Implementación eficiente de la tabla. LZHUFF. LZP
     
   • Localidad en archivos: Localidad. Move to Front. Block Sorting. Descompresión. Implementación. Modelos que aprovecha la transformación BS + MTF: Modelo de Shannon. Modelo aritmético. Modelo Estructurado. Half coding
     
5. Criptografía y Archivos Multimediales
   • Conceptos básicos sobre Criptografía: Objetivos de la criptografía. Criptosistema. Definición y tipos de criptoanálisis. Relación entre criptosistema y criptoanálisis
     
   • Criptografía clásica: Cifrado por bloque. Modos de cifrado por bloque. Cifrados por sustitución. Sustitución simple o monoalfabéticos. Cifrado Homofónico. Cifrado Polialfabético (Vigenere). Cifrado Poligráfico (Hill y PlayFair). Cifrado por transposición. Cifrado por producto. Cifrado por Flujo. One Time Pad
     
   • Criptografia de clave privada: undamentos. Data Encrytion Standard (DES). Triple DES. Advanced Encryption Standard (AES). Criptoanálisis diferencial y lineal
     
   • Criptografía de clave pública: Fundamentos matemáticos. Criptosistema RSA. Criptoanálisis de RSA (Factorización de n, Seguridad del algoritmo). Vulnerabilidades de RSA. Algoritmo de Merkle-Hellman (knapsack)
     
   • Firmas Digitales: Firma de clave privada. Firma de clave pública. Función resumen. Diferencias y similitudes entre la firma manuscrita y la firma digital
     
   • Administración de claves públicas: Certificados digitales
     
   • Pretty Good Privacy (PGP): Introduction. Esquema de encriptación y desencriptación. Esquema de firma digital. Certificados digitales
     
   • Protocolos criptográficos: ejemplos de aplicación
     
   • Archivos Multimediales: Aplicaciones de los temas anteriores de la materia a archivos multimediales y sistemas multimedios. Compactación de datos
     

En esta sección pongo ejercicios de exámenes separados por tema con la/las fecha/s en que aparecieron y el criterio en caso de tenerlo. La idea es que sea como una guía de ejercicios.

• Ejercicios de Compresión
• Ejercicios de Programación con las primitivas (ej 1 de los parciales)
• Ejercicios de Codificación de Números
• Ejercicios de Árboles B, B+ y B*
• Ejercicios de Árboles Patricia, Trie y Trie-Compacto
• Ejercicios de Funciones de Hashing y Archivos Directos [Con RESUELTOS]
• Ejercicios de Operaciones entre archivos (sort externo)
• Ejercicios de Page Rank [RESUELTOS]

• Una resolución al primer parcial, primer cuatrimestre 2014, primera oportunidad

• Examen por promoción del 30-06-2008

• Final del 26-02-2009
• Final del 20-02-2009
• Final del 12-02-2009
• Final del 31-07-2008
• Final del 24-07-2008
• Final del 17-07-2008
• Final del 2006
• Final del 2005

• Ejercicios de Sistemas de Archivos
• Ejercicios de Organización de Archivos
• Ejercicios de Recuperación de Textos
• Ejercicios de Compresión
• Ejercicios de Criptografía

• Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2006
• Evaluación de Organización de archivos, cátedra Servetto 1er cuatrimestre 2008: 30/04
• Evaluación de Organización de archivos, cátedra Servetto 1er cuatrimestre 2008: 23/07
• Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2008: 24/09/2008
• Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2008: 11/02/2009

• Evaluación de Sistema de archivos (File System), cátedra Servetto 2do cuatrimestre 2006
• Evaluación de Sistema de archivos (File System), cátedra Servetto 1er cuatrimestre 2008
• Evaluación de Sistema de archivos (File System), cátedra Servetto 2do cuatrimestre 2008:04/03/2009

• Evaluación de Compresión , cátedra Servetto 2do cuatrimestre 2006
• Evaluación de Compresión, cátedra Servetto 2do cuatrimestre 2008:04/03/2009
• Evaluación de Multimedia , cátedra Servetto 2do cuatrimestre 2008:11/02/2009

• Evaluación de FTRS , cátedra Servetto 2do cuatrimestre 2006
• Evaluación de FTRS , cátedra Servetto 2do cuatrimestre 2008: 11/06/2008

• Evaluación de Criptografía , cátedra Servetto 2do cuatrimestre 2008:03/12/2008

• Resumen para el 1er parcial, cátedra Saubidet

• "File Structures - An Object-Oriented Aproach with C++". Está en biblioteca.
• "Managing Gigabytes: Compressing and Indexing Documents and Images", por Ian H. Witten, Alistair Moffat and Timothy C. Bell
• "Text Compression", por Timothy C. Bell
• "Data Compression: The Complete Reference", por David Salomon
• "Applied Cryptography: Protocols, Algorithms, and Source Code in C"
• "Modern Operating Systems" (para cátedra Servetto)
• "The Design of the UNIX Operating System", por Maurice J. Bach (para cátedra Servetto). Está en biblioteca.
• "An Introduction to Information Retrieval", por Christopher D. Manning

• File Systems: Diapositivas de File Systems (para cátedra Servetto).
• File Systems: Diapositivas de File Systems (para cátedra Servetto).
• File Systems: Diapositivas de File Systems (para cátedra Servetto).
• Organización de Archivos: Resumen del libro “File Structures - An Object-Oriented Aproach with C++”.