Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Informatica
Área: Area IV: Pr. y Met. de Des. del Soft.
(Programa del año 2019)
I - Oferta Académica
Materia Carrera Plan Año Periodo
(OPTATIVA) TEORIA DE LA INFORMACION LIC.CS.COMP. 32/12 2019 1° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
MONTEJANO, GERMAN ANTONIO Prof. Responsable P.Asoc Exc 40 Hs
SILVESTRI, MARIO ALFREDO Responsable de Práctico JTP Simp 10 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total B - Teoria con prácticas de aula y laboratorio Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
1 Hs. 1 Hs. 1 Hs. 2 Hs. 5 Hs. 1º Cuatrimestre 13/03/2019 21/06/2019 15 75
IV - Fundamentación
Debido a que la ubicación del curso en el Plan de Estudios está sobre el final de la carrera, es evidentemente una materia de ingeniería netamente aplicativa para la ciencia de la computación.

Por tal motivo, el profesional debe tener en su formación básica el conocimiento teórico, fundamentalmente matemático, y luego las estrategias, métodos y técnicas para la aplicación de la ciencia de la computación en desarrollos ingenieriles en problemas de codificación y manipulación de códigos para transmisión y almacenamiento eficientes de la información.

El profesional debe ser capaz de enfrentar una amplia variedad de problemas, por lo cual es importante generar la actitud investigadora para desarrollar la mejor solución según un determinado criterio y finalmente volcar en un informe monográfico estas ideas centrales.
V - Objetivos / Resultados de Aprendizaje
El objetivo general de la materia consiste en la formación de los alumnos en dos grandes áreas del conocimiento:
- adquirir el conocimiento y emplear las estrategias, métodos y técnicas para abordar el modelo de sistemas de señalización, la codificación de alfabetos y el álgebra utilizados en la teoría de la codificación,
- introducir al alumno en las bases de la teoría de la información explotando los conceptos de entropía de un sistema de codificación; capacidad, codificación e información de un canal.

El objetivo final es desarrollar habilidades en los alumnos para construir sistemas de codificación usando los conceptos mencionados y enfatizando aspectos de calidad con restricciones de costo, tiempo y seguridad, con el menor costo en la pérdida de la información.

Como un objetivo particular se pretende desarrollar en el futuro profesional la actitud investigadora, promoviendo la búsqueda de la solución más adecuada y su posterior desarrollo en una implementación hecha en computadora con el respaldo de un informe monográfico final.

Es deseable que el alumno envíe su trabajo de I+D en formato de publicación a un capítulo estudiantil de un congreso. Esto trae aparejado las ventajas de: introducir al alumno en el campo de las habilidades necesarias para expresar ideas y trabajos con fines de publicación (como preliminar a su tesis de grado), provocar la evaluación del trabajo por un jurado externo a la cátedra y a la universidad, y tener la posibilidad de exponer los resultados de su I+D en un congreso.
VI - Contenidos
1. CONCEPTOS PRELIMINARES
Breve historia.
El modelo del sistema de señalización.
La codificación de un alfabeto fuente.
Código binario, Morse, van Duuren, radix r.
Caracteres de escape.
El álgebra en la teoría de la codificación.

2. CÓDIGOS DE DETECCIÓN DE ERROR
Concepto.
Control de paridad.
Detección de errores independientes.
Detección de errores en racha.
Código ponderado.

3. CÓDIGOS DE CORRECCIÓN DE ERROR
Motivación.
Códigos lineales: rectangular, n-dimensionales, de Hamming.
Detección de errores dobles y corrección de errores simples.
Enfoque geométrico y algebraico.
Códigos cíclicos: cíclico propiamente dicho, cuasi cíclico.

4. CÓDIGOS DE LONGITUD VARIABLE
Concepto de códigos de longitud variable.
Códigos instantáneos, Huffman, Huffman Radix r, Hamming- Huffman.

5. ESQUEMAS CON MEMORIA
Procesos ergódicos.
Codificadores predictivos.
Codificación Hashing.
Codificación Gray.

6. INFORMACIÓN
Concepto. Entropía.
Codificación Shannon-Fano.
Entropía de las extensiones de un código.
Entropía de un proceso de Markov.

7. CANAL
Concepto. Información del canal.
Entropías del sistema.
Información mutua.
Capacidad de canal.
Canal uniforme, entrada uniforme.
Canal simétrico binario: entropía, capacidad.

8. TEOREMA DE SHANNON
Concepto del Teorema Principal de Shannon.
Reglas de decisión.
El teorema en el canal simétrico binario.
Codificación aleatoria.
El límite dado por Fano.
La inversa del teorema de Shannon.

9. TEORÍA DE CODIFICACIÓN ALGEBRAICA
Revisión de códigos: de detección y corrección de un error, de detección de dos errores y cíclicos.
Polinomios primos. Raíces primitivas.
Códigos perfectos Hamming.

VII - Plan de Trabajos Prácticos
1. PRÁCTICOS DE AULA
Código binario, octal, hexadecimal, ASCII, Morse, van Duuren, radix r. Uso de caracteres de escape en algún lenguaje de programación.
Control de paridad. Detección de errores independientes. Detección de errores en racha. Código ponderado.
Códigos rectangulares, triangulares, cúbicos, n-dimensionales, de Hamming. Detección de errores dobles y corrección de errores simples. Códigos cíclico propiamente dicho y cuasi cíclico.
Códigos Huffman, Huffman Radix r, Hamming- Huffman.
Procesos ergódicos. Codificadores predictivos. Codificación Hashing. Codificación Gray.
Codificación Shannon-Fano. Entropía de las extensiones de un código. Entropía de un proceso de Markov.
Información del canal. Entropías del sistema. Información mutua. Canal simétrico binario: entropía y capacidad.
Teorema Principal de Shannon. Reglas de decisión.
Códigos perfectos Hamming.

2. PRÁCTICOS DE LABORATORIO
Implementación de programas para control de paridad y detección de errores independientes.
Implementación de programas para códigos rectangulares, triangulares, cúbicos, n-dimensionales, de Hamming, y detección de errores dobles y corrección de errores simples.
Implementación de programas para códigos cíclicos.
Implementación de programas para códigos Huffman.
Implementación de programas para estadísticas de información del canal simétrico binario y capacidad.

3. PRÁCTICOS DE CAMPO
Deben hacer una implementación y un informe a tal efecto de resolución de un problema real en un ámbito existente en la temática del curso.
VIII - Regimen de Aprobación
Para regularizar la asignatura el alumno debe haber asistido al menos al 80% de las clases, aprobar un examen teórico - práctico, o sus respectivas recuperaciones, y presentar en forma y tiempo y aprobar los prácticos de laboratorio, o sus respectivas recuperaciones, y aprobar el práctico de campo.

Para promocionar la asignatura el alumno debe cumplir con las condiciones de regularización y aprobar los trabajos prácticos de laboratorio y el examen integrador con nivel superior o igual a siete puntos sobre un total de diez.

Para promocionar la asignatura, alternativamente, en lugar de aprobar un examen final, se puede realizar una monografía que surge de un trabajo de investigación y defenderla con una presentación oral y pública.

El seguimiento continuo de los alumnos que cursan se realiza mediante la observación e interacción sistemática durante las clases prácticas, la evaluación de los prácticos y la evaluación final integradora.
La evaluación final integradora está basada en un examen tomando como línea base de construcción del mismo los trabajos prácticos y la teoría dada.

Los alumnos tienen una recuperación adicional en cada instancia tal como lo regula la normativa vigente.

La cátedra permite alumnos libres, para los cuales se les exigirán:
- la entrega y aprobación de los prácticos de laboratorio desarrollados durante el cursado de la materia,
- la realización y aprobación de una monografía que surge de un trabajo de investigación,
- la aprobación de un examen final teórico-práctico.

Para poder rendir el examen final teórico-práctico, previamente el alumno debe haber entregado y aprobado los prácticos de laboratorio desarrollados y la monografía que surge de un trabajo de investigación.
IX - Bibliografía Básica
[1] "Information Theory: A Tutorial Introduction", JV Stone, University of Sheffield, England, 2014.
[2] "Information Theory: Coding Theorems for Discrete Memoryless Systems", Imre Csiszár, János Körner, 2nd. Edition, Cambridge University Press, 2011.
[3] "Coding and Information Theory", Steven Roman, Springer Science & Business Media, 1992.
[4] "Coding and Information Theory", Richard W. Hamming, Prentice-Hall, 1980.
[5] "Códigos de Corrección de Errores para Grabación Magnética y Arreglos de Discos", M. Blaum, IBM Almaden Research Center, USA. ECI''95
[6] "An Introduction to Information Theory", Fazlollah M. Reza, McGraw Hill, 1961.
X - Bibliografia Complementaria
[1] "Error-Correcting Codes", W. Wesley Peterson and E. J. Weldon, The MIT Press, 1994.
[2] "Introduction to The Theory of Error Correcting Codes", Vera Pless, John Wiley and Sons, 1989.
[3] "Elementary Information Theory", D. S. Jones, Clarendon Press, 1979.
[4] "Key Papers in Development of Information Theory", Ed. David Slepian, IEEE Computer Society Press, 1974.
[5] "A mathematical theory of communication", C. E. Shannon, Bell Syst., July 1948.
[6] "A mathematical theory of communication", C. E. Shannon, Bell Syst., Oct. 1948.
[7] "A method for the construction of minimum redundancy codes", D. A. Huffman, Proc. IRE, Sept. 1952.
[8] "The basic theorems of information theory", B. McMillan, Ann. Math. Stat., June 1953.
XI - Resumen de Objetivos
El objetivo final es desarrollar habilidades en los alumnos para construir sistemas de codificación usando el conocimiento de estrategias, métodos y técnicas para abordar el modelo de sistemas de señalización, la codificación de alfabetos y el álgebra utilizados en la teoría de la codificación, las bases de la teoría de la información explotando los conceptos de entropía de un sistema de codificación; capacidad, codificación e información de un canal y enfatizando aspectos de calidad con restricciones de costo, tiempo y seguridad, con la menor pérdida de la información.
XII - Resumen del Programa
Conceptos preliminares de la Teoria de la Información y la Codificación. El modelo del sistema de señalización. La codificación de un alfabeto fuente. El álgebra en la teoría de la codificación.

Códigos de detección de error. Control de paridad. Detección de errores independientes. Detección de errores en racha. Código ponderado.

Códigos de corrección de error. Códigos lineales. Detección de errores dobles y corrección de errores simples. Enfoque geométrico y algebraico. Códigos cíclicos.

Códigos de longitud variable. Códigos instantáneos, Huffman, Huffman Radix r, Hamming-Huffman.

Esquemas con memoria. Procesos ergódicos. Codificadores predictivos. Codificación Hashing. Codificación Gray.

Información. Entropía. Codificación Shannon-Fano. Entropía de las extensiones de un código y de un proceso de Markov.

Canal. Información del canal. Entropías del sistema. Información mutua. Capacidad de canal.Canal uniforme, entrada uniforme. Canal simétrico binario: entropía, capacidad.

Teorema de Shannon. Reglas de decisión. El teorema en el canal simétrico binario. Codificación aleatoria. El límite dado por Fano. La inversa del teorema de Shannon.

Teoría de codificación algebraica. Revisión de códigos. Polinomios primos. Raíces primitivas. Códigos perfectos Hamming.
XIII - Imprevistos
 
XIV - Otros