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. |
I - Oferta Académica | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
II - Equipo Docente | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
|
III - Características del Curso | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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 ingenieria netamente aplicativa para la ciencia de la computacion. Por tal motivo, tiene en la formación profesional un soporte teórico, fundamentalmente matemático y luego se basa en la aplicación de la ciencia de la computación en desarrollos ingenieriles, ya sea en canales de comunicación como en almacenamiento y su posterior recuperación de la información. Debido a esta causa, la materia tiene una primer fase de estudio teórico con sus correspondientes prácticas de aula y posteriormente un fuerte estudio de investigación y desarrollo para la aplicación en casos concretos de los conceptos estudiados. La idea central de la investigación y el desarrollo se orienta a volcar el trabajo realizado en una monografía con el respaldo de una implementación hecha en computadora. Cabe destacar que para finalizar, se envían los trabajos de I+D en formato de publicacion 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 publicacion (como preliminar a su tesis de grado), provocar la evaluacion del trabajo por un jurado externo a la cátedra y a la universidad, tener la posibilidad de exponer los resultados de su I+D en un congreso. |
V - Objetivos |
---|
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 ingenieria netamente aplicativa para la ciencia de la computacion. Debido a que la materia incide en la formación profesional como respaldo ingenieril para la aplicación matemática y computacional en problemas de codificación y manipulación de códigos para transmisión y almacenamiento eficientes de la información, es que se plantea como objetivo que al final del curso el alumno sea capaz de resolver un eventual problema de transmitir o almacenar información digital eficientemente. |
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 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. |
VIII - Regimen de Aprobación |
---|
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 los prácticos de máquina. Para promocionar la asignatura el alumno debe aprobar un examen final ó la realización de una monografía que surge de un trabajo de investigación. |
IX - Bibliografía Básica |
---|
[1] \\\"Coding and Information Theory\\\",
[2] Richard W. Hamming, [3] Prentice-Hall, 1980. [4] \\\"Códigos de Corrección de Errores para Grabación Magnética [5] y Arreglos de Discos\\\" [6] M. Blaum, [7] IBM Almaden Research Center, USA. ECI\\\'95 [8] \\\"An Introduction to Information Theory\\\", [9] Fazlollah M. Reza, [10] McGraw Hill, 1961. |
X - Bibliografia Complementaria |
---|
[1] \\\"Error-Correcting Codes\\\",
[2] W. Wesley Peterson and E. J. Weldon, [3] The MIT Press, 1994. [4] \\\"Introduction to The Theory of Error Correcting Codes\\\", [5] Vera Pless, [6] John Wiley and Sons, 1989. [7] \\\"Elementary Information Theory\\\", [8] D. S. Jones, [9] Clarendon Press, 1979. [10] \\\"Key Papers in Development of Information Theory\\\", [11] Ed. David Slepian, [12] IEEE Computer Society Press, 1974. [13] \\\"A mathematical theory of communication\\\", [14] C. E. Shannon, [15] Bell Syst., July 1948. [16] \\\"A mathematical theory of communication\\\", [17] C. E. Shannon, [18] Bell Syst., Oct. 1948. [19] \\\"A method for the construction of minimum redundancy codes\\\", [20] D. A. Huffman, [21] Proc. IRE, Sept. 1952. [22] \\\"The basic theorems of information theory\\\", [23] B. McMillan, [24] Ann. Math. Stat., June 1953. |
XI - Resumen de Objetivos |
---|
Debido a que la materia incide en la formación profesional como respaldo ingenieril para la aplicación matemática y computacional en problemas de codificación y manipulación de códigos para transmisión y almacenamiento eficientes de la información, es que se plantea como objetivo que al final del curso el alumno sea capaz de resolver un eventual problema de transmitir o almacenar información digital eficientemente. Debido a esta causa, la materia tiene una primer fase de estudio teórico con sus correspondientes prácticas de aula y posteriormente un fuerte estudio de investigación y desarrollo (I+D) para la aplicación en casos concretos de los conceptos estudiados. La idea central de la I+D se orientan a volcar el trabajo realizado en una monografía con el respaldo de una implementación hecha en computadora. Para finalizar, se envían los trabajos de I+D en formato de publicacion 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 publicacion (como preliminar a su tesis de grado), provocar la evaluacion del trabajo por un jurado externo a la cátedra y a la universidad, tener la posibilidad de exponer los resultados de su I+D en un congreso. |
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 |
---|
|