Compresión de Datos sin Pérdida
Diagrama de temas
-
Compresión de Datos sin Pérdida
Este curso está orientado a estudiantes tanto de grado como de posgrado. Se presentan los principios básicos y temas avanzados de la teoría de la compresión de datos sin pérdida. Los aspectos teóricos se ilustran con ejemplos prácticos de actualidad. Este curso está ofrecido por el Núcleo de Teoría de la Información de la Facultad de Ingeniería.
Fecha de inicio: 1 de marzo de 2021.
Horarios: lunes y viernes de 14:00 a 16:00.
Docentes: Álvaro Martín y Gadiel Seroussi.
Fechas importantes:
Pruebas: 26/03/2021, 14/05/2021, 28/06/2021
Tarea 1: 16/04/2021 - 31/05/2021
Tarea 2: 04/06/2021 - 05/07/2021-
Completar el formulario de inscripción es obligatorio para los estudiantes de cursos de posgrado, actualización y educación permanente. Los datos obtenidos serán procesados y utilizados con fines estadísticos por la Unidad Central de Educación Permanente de la Universidad de la República.
-
Enviar retroalimentación
Completar el formulario de evaluación es obligatorio para los estudiantes de cursos de posgrado, actualización y educación permanente. Los datos obtenidos serán procesados y utilizados con fines estadísticos por la Unidad Central de Educación Permanente de la Universidad de la República.
La encuesta de evaluación es anónima, salvo que el estudiante desee renunciar explícitamente al anonimato incluyendo su nombre en el campo opcional ‘Nombre’.
-
Enlace zoom para las clases URL
-
Conceptos básicos de Teoría de la Información
Veremos definiciones de Entropía y Divergencia, y estudiaremos algunas de sus propiedades.
Estos conceptos forman los pilares sobre los que construiremos herramientas teóricas para estudiar el problema de compresión de datos. -
Códigos para distribuciones de probabilidad conocidas
Estudiaremos cómo codificar (comprimir) de forma óptima (en el sentido de minimizar la esperanza del largo de código), datos que son generados de acuerdo a una distribución de probabilidad conocida.
-
Procesos estocásticos
Repasaremos nociones básicas de procesos estocásticos y estudiaremos el concepto de tasa de entropía de un proceso. Estas herramientas nos permitirán modelar una fuente de información aleatoria que genera una cantidad infinita de símbolos a codificar y estudiarla asintóticamente. -
Algoritmos de Lempel-Ziv
Presentaremos y analizaremos la familia de algoritmos de compresión de Lempel y Ziv, que son utilizados en numerosas aplicaciones prácticas (gzip, WinZIP, 7z, RAR, GIF, TIFF, PNG, PDF ...).
-
Codificación aritmética
La codificación aritmética permite comprimir grandes secuencias de símbolos de forma práctica desde un punto de vista de complejidad computacional, alcanzando, al mismo tiempo, un largo de código cercano al óptimo. Esta técnica se utilizará como base en muchos de los algoritmos que estudiaremos posteriormente.
-
Codificación universal y doblemente universal
Veremos cómo codificar datos generados de acuerdo a una distribución de probabilidad desconocida a priori. Asumiendo que esta distribución pertenece a una familia paramétrica de distribuciones conocida (por ejemplo la familia de todos los procesos de Markov de orden k), estudiaremos una cota inferior para la mínima esperanza de largo de código que podemos aspirar a lograr. Mostraremos ejemplos donde podemos alcanzar esa cota, logrando, asintóticamente, un largo de código promedio por símbolo tan bueno como el que lograríamos si supiéramos la distribución que gobierna los datos de entrada.
Estos resultados se pueden generalizar a familias de modelos más amplias, obtenidas como unión de familias paramétricas, como por ejemplo la familia de todos los procesos de Markov de cualquier orden, dando lugar a códigos doblemente universales. -
Códigos de Golomb
Estudiaremos la familia de códigos de Golomb para la codificación de variables con distribución de probabilidad Geométrica. Este tipo de códigos admiten implementaciones muy eficientes tanto en software como en hardware, y son ampliamente usados en la práctica.