Materia	Carrera	Plan	Año	Periodo
(OPTATIVAS) TEORIA DE LA INFORMACION	LIC.CS.COMP.	18/11	2013	1° cuatrimestre

Docente	Función	Cargo	Dedicación
MONTEJANO, GERMAN ANTONIO	Prof. Responsable	P.Adj Exc	40 Hs
SILVESTRI, MARIO ALFREDO	Responsable de Práctico	JTP Simp	10 Hs

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.

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.

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.

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 MÁQUINA

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.

Para regularizar la asignatura el alumno debe aprobar un examen teórico - práctico o su correspondiente recuperación, y presentar en forma y tiempo y aprobar los prácticos de laboratorio, o sus respectivas recuperaciones.

Para promocionar la asignatura el alumno debe cumplir con las condiciones de regularización, haber asistido al menos al 80% de las clases 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 que trabajan tienen una recuperación adicional tal como lo regula la normativa vigente (Ordenanzas C.S. N° 26/97, 15/00 y 13/03).

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 máquina desarrollados y la monografía que surge de un trabajo de investigación.

[1] "Coding and Information Theory", Richard W. Hamming, Prentice-Hall, 1980.
[2] "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
[3] "An Introduction to Information Theory", Fazlollah M. Reza, McGraw Hill, 1961.

[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.

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.

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.