====== 75.06. Organización de Datos ======

<note important>
Este es sólo un esqueleto sobre esta materia; te invitamos a que colabores completando la información relativa a la misma; al editar tendrás todas las instrucciones para hacerlo.
</note>

<!--
# Para editar esta página:
# Simplemente completá la información sugerida en estos comentarios; una vez que completes un comentario, borrá al mismo.
# Si necesitás ver los parámetros con los que nos manejamos; consultá la página de alguna otra materia que ya esté pasada, así todo se hace según las mismas convenciones.
-->

<!-- # Info del coordinador de la materia:
**Coordinador:** [[mail|nombre]]\\
-->

<!-- # Info de la página oficial de la materia:
**Página web oficial:** [[http://www.fi.uba.ar/materias/enlace]]\\
-->
**Cátedra Argerich:** [[http://ar.groups.yahoo.com/group/datos/]]\\
**Cátedra Servetto:** [[http://espanol.groups.yahoo.com/group/7506alumnos/]]\\

++++Carreras:|
^  Carrera  ^  Créditos  ^  Correlativas  ^  Condición  ^
|[[carreras:informática|Ingeniería en Informática]]  |  6  |  [[materias:66:70|66.70]] -  [[41|75.41]]  |  Obligatoria  |
|[[carreras:sistemas|Lic. en Análisis de Sistemas]]  |  6  |  [[03|75.03]] -  [[41|75.41]]  |  Obligatoria  |
<!-- # Para cada carrera en la que esté:
|[[carreras:nombrecarrrera|Nombre Carrera]]  |  #creditos  |  [[..:XX:XX|XX.XX]]...  |  (Obligatoria|Optativa|Según orientación)  |
-->
++++


===== Programa =====
++++Objetivos|
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
++++

<!-- # Objetivos de la materia:
++++Objetivos|
  - listaconlosobjetivos...
++++
-->
++++Programa sintético Saubidet|
  - Organización de archivos.
  - Operaciones entre archivos.
  - Organización directa: Hashing.
  - Organización indexada: Arboles
  - Introducción a la teoría de la información y compresión de datos.
  - Indices e information retrieval.
  - Motores de bases de datos y data-mining.
  - Normalización.
  - Criptografía.
  - XML, DTD, XML Schema, XPath, XSLT
  - RDF, Topics Maps
  - File Systems.
++++


++++Programa sintético Servetto|
  - Organización de archivos
  - Sistemas de recuperación total de textos
  - File Systems
  - Compresión
  - Criptografía y Archivos Multimediales
++++
<!-- # Programa sintético de la materia:
++++Programa sintético|
  - listaconelprogramasintetico...
++++
-->

++++Programa analítico Servetto|
  - 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. \\
  - 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. \\
  - File Systems
      * **Organización del espacio en disco:** Identificación y localización de archivos. Seguridad y auditoria de accesos. Casos de estudio \\
      * **Buffering:** 
  - 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 \\
  - 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 \\
++++
<!-- # Programa analítico de la materia:
++++Programa analítico|
  - listaconelprogramaanalitico...
-->

===== Cursos =====

<!-- # Cursos de la materia:
++++Mostrar cursos|
^  Curso  ^  Modalidad  ^  Docentes  ^  Días  ^  Horario  ^
# Para cada curso o modalidad u horario:
|  #curso  |  (TP|TPO|PO|P|...)  |Nombre Docentes  |  diasdelasemana  |  desde - hasta (HH:MM)  |
++++
-->
++++Mostrar cursos|
^  Curso  ^  Modalidad  ^  Docentes  ^  Días  ^  Horario  ^
|    1    |    TPO   |  Saubidet - Argerich - Golmar  |  Lunes y Jueves  |  19:00 - 22:00  |
|    2    |    TPO   |  Servetto- Cruz - Perez Rodal  |  Lunes y Miercoles  |  19:00 - 22:00  |
++++

===== Material =====





==== Cátedra Saubidet ====
++++Ejercicios de Parciales y finales separados por tema|
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.
<!-- # Guías sin subir:
    * [[.06:ejercicios_saubidet_ej2|Ejercicios de Diseño de una Organización de Archivos]]
    * [[.06:ejercicios_saubidet_indices|Ejercicios de Índices]]
    * [[.06:ejercicios_saubidet_|Ejercicios de ]]

-->
    * [[.06:ejercicios_saubidet_compresion|Ejercicios de Compresión]]
    * [[.06:ejercicios_saubidet_ej1|Ejercicios de Programación con las primitivas (ej 1 de los parciales)]]
    * [[.06:ejercicios_saubidet_codigos|Ejercicios de Codificación de Números]]
    * [[.06:ejercicios_saubidet_arboles|Ejercicios de Árboles B, B+ y B*]]
    * [[.06:ejercicios_saubidet_otros_arboles|Ejercicios de Árboles Patricia, Trie y Trie-Compacto]]
    * [[.06:ejercicios_saubidet_hashing|Ejercicios de Funciones de Hashing y Archivos Directos [Con RESUELTOS] ]]
    * [[.06:ejercicios_saubidet_sort|Ejercicios de Operaciones entre archivos (sort externo)]]
    * [[.06:ejercicios_saubidet_page_rank|Ejercicios de Page Rank [RESUELTOS] ]]
++++
++++Parciales Argerich|
    * {{:materias:75:06:parcial_datos_2014_1_1.pdf|Una resolución al primer parcial, primer cuatrimestre 2014, primera oportunidad}}
++++
++++Examenes por promoción|
    * [[.06:promocion_saubidet_20080630_xx|Examen por promoción del 30-06-2008]]
++++

++++Finales|
    * [[.06:final_saubidet_20090226_xx|Final del 26-02-2009]]
    * [[.06:final_saubidet_20090220_xx|Final del 20-02-2009]]
    * [[.06:final_saubidet_20090212_xx|Final del 12-02-2009]]
    * [[.06:final_saubidet_20080731_xx|Final del 31-07-2008]]
    * [[.06:final_saubidet_20080724_xx|Final del 24-07-2008]]
    * [[.06:final_saubidet_20080717_xx|Final del 17-07-2008]]
    * [[.06:final_saubidet_2006xxxx_1|Final del 2006]]
    * [[.06:final_saubidet_2005xxxx_1|Final del 2005]]
++++

==== Cátedra Servetto ====

<!-- # Enlaces a las guías de ejercicios:
++++Guías|
# Para cada capítulo:
    - [[.numeromateria:guia_[#catedra_]_(#guía)|Nombre unidad]]
# Por ejemplo: [[.63:guia_1|Sistemas Materiales]]
++++
-->
++++Guías de ejercicios|
  * [[materias:75:06:servetto_ejs_ssa|Ejercicios de Sistemas de Archivos]]
  * [[materias:75:06:servetto_ejs_oaa|Ejercicios de Organización de Archivos]]
  * [[materias:75:06:servetto_ejs_rtt|Ejercicios de Recuperación de Textos]]
  * [[materias:75:06:servetto_ejs_compresion|Ejercicios de Compresión]]
  * [[materias:75:06:servetto_ejs_criptografia|Ejercicios de Criptografía]]
++++

++++Parciales Organización de Archivos|
    * [[.06:parcial_2_20061018_1|Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2006]]
    * [[.06:parcial_2_20080430_1|Evaluación de Organización de archivos, cátedra Servetto 1er cuatrimestre 2008: 30/04]]
    * [[.06:parcial_2_20080723_1|Evaluación de Organización de archivos, cátedra Servetto 1er cuatrimestre 2008: 23/07]]
    * [[.06:parcial_2_20080924_1|Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2008: 24/09/2008]]
    * [[.06:parcial_2_20090211_1|Evaluación de Organización de archivos, cátedra Servetto 2do cuatrimestre 2008: 11/02/2009]]
++++

++++Parciales File Systems|
    * [[.06:parcial_2_20061018_2|Evaluación de Sistema de archivos (File System), cátedra Servetto 2do cuatrimestre 2006]]
    * [[.06:parcial_2_20080430_2|Evaluación de Sistema de archivos (File System), cátedra Servetto 1er cuatrimestre 2008]]
    * [[.06:parcial_2_20090304_2|Evaluación de Sistema de archivos (File System), cátedra Servetto 2do cuatrimestre 2008:04/03/2009]]

++++
++++Parciales Compresión|
    * [[.06:parcial_2_20061120_1|Evaluación de Compresión , cátedra Servetto 2do cuatrimestre 2006]]
    * [[.06:parcial_2_20090304_1|Evaluación de Compresión, cátedra Servetto 2do cuatrimestre 2008:04/03/2009]]
    * [[.06:parcial_2_20091102_1|Evaluación de Multimedia , cátedra Servetto 2do cuatrimestre 2008:11/02/2009]]
++++

++++Parciales Recuperación de Textos|
    * [[.06:parcial_2_2006116_1|Evaluación de FTRS , cátedra Servetto 2do cuatrimestre 2006]]
    * [[.06:parcial_2_2008116_1|Evaluación de FTRS , cátedra Servetto 2do cuatrimestre 2008: 11/06/2008]]
++++

++++Parciales Criptografía|
    * [[.06:parcial_2_20081203_1|Evaluación de Criptografía , cátedra Servetto 2do cuatrimestre 2008:03/12/2008]]
++++

==== General ====

++++Apuntes|
    * {{:materias:75:06:resumen_primer_parcial.pdf|Resumen para el 1er parcial, cátedra Saubidet}} 
++++

++++Libros|
  * [[http://amzn.com/0201874016|"File Structures - An Object-Oriented Aproach with C++"]]. Está en biblioteca.
  * [[http://amzn.com/1558605703|"Managing Gigabytes: Compressing and Indexing Documents and Images", por Ian H. Witten, Alistair Moffat and Timothy C. Bell]]
  * [[http://amzn.com/0139119914|"Text Compression", por Timothy C. Bell]]
  * [[http://amzn.com/1846286026|"Data Compression: The Complete Reference", por David Salomon]]
  * [[http://amzn.com/0471117099|"Applied Cryptography: Protocols, Algorithms, and Source Code in C"]]
  * [[http://amzn.com/0136006639|"Modern Operating Systems"]] (para cátedra Servetto)
  * [[http://amzn.com/0132017997|"The Design of the UNIX Operating System", por Maurice J. Bach]] (para cátedra Servetto). Está en biblioteca.
  * [[http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf|"An Introduction to Information Retrieval", por Christopher D. Manning]]
++++

<!-- # Enlaces a los artículos sobre parciales:
++++Parciales |
# Para cada parcial
    * [[.numeromateria:parcial_(#catedra)_yyyymmdd_(#articulo)|Descripción del parcial]]
# Rellenando con x los datos desconocidos.
# Por ejemplo: [[.63:parcial_13_200605xx_1|Primer parcial, primer cuatrimestre, cátedra X]]
++++
-->

<!-- # Enlaces a los artículos sobre finales:
++++Finales|
# Para cada final
    - [[.numeromateria:final_(#catedra)_yyyymmdd_(#articulo)|Descripción del final]]
# Rellenando con x los datos desconocidos.
# Por ejemplo: [[.63:final_13_200601xx_1|Primer final, verano de 2006, cátedra X]]
++++
-->

<!-- # Enlaces a páginas con material:
++++Enlaces|
# Para cada enlace:
    * [[http://paginawebenlace|Nombre Enlace]]: Descripción del material.
++++
-->
++++Enlaces|
  * [[http://ece.uprm.edu/~noack/icom5007/textslides/tanenbaumslides/MOS-Ch04-e3.ppt|File Systems]]: Diapositivas de File Systems (para cátedra Servetto).
  * [[http://web.cs.wpi.edu/~cs4513/d08/LectureNotes--d08/Week%202,%20File%20System%20Implementations.ppt|File Systems]]: Diapositivas de File Systems (para cátedra Servetto).
  * [[http://www.eecs.harvard.edu/~mdw/course/cs161/syllabus.html|File Systems]]: Diapositivas de File Systems (para cátedra Servetto).
  * [[http://web.itu.edu.tr/~bkurt/Courses/blg341/|Organización de Archivos]]: Resumen del libro "File Structures - An Object-Oriented Aproach with C++".
++++