Teoria da Informação

Conhecimentos de Base Recomendados

Análise Matemática I, Estatística, Introdução à Programação e Resolução de Problemas, Princípios de Programação Procedimental.

Métodos de Ensino

Aulas teóricas com exposição detalhada dos conceitos, princípios e teorias fundamentais e com a resolução de exercícios práticos elementares que concretizem o interesse prático da matéria e exemplifiquem a sua aplicação a situações reais. 

Aulas teórico-práticas em que se pretende que os alunos, com a orientação do docente, resolvam alguns exercícios de papel e lápis, que exijam a conjugação de conceitos teóricos distintos e promovam o raciocínio crítico face a problemas mais complexos.

Aulas práticas dedicadas à realização de exercícios de programação envolvendo os diversos conceitos lecionados na disciplina. São propostos, durante as aulas teóricas, a realização de TPCs, existindo ainda mini-testes surpresa o que promove a aprendizagem continuada. A avaliação consiste ainda em exame final.

Resultados de Aprendizagem

Fornecer de uma forma sistemática as noções fundamentais da teoria da informação e a sua aplicação em contextos de aprendizagem computacional, análise de dados e, sobretudo, aos princípios da codificação nos contextos da codificação de fontes e de canal e na criptografia. É objetivo exporem-se os fundamentos algébricos por forma a permitir uma aprendizagem dos princípios abstratos da teoria da informação e a matemática sofisticada da codificação.

A disciplina contribui para a aquisição das seguintes competências:

Instrumentais:

- Capacidade de análise e de síntese em problemas complexos;
- Aprofundamento do raciocínio matemático;
- Capacidade de abstração e de generalização;
- Competência de resolução de problemas concretos no âmbito da aprendizagem computacional e da análise da informação, na compressão de dados, na codificação de canal e na encriptação e segurança.

Pessoais:

- Trabalho em grupo;
- Raciocínio critico.

Sistémicas:

- Auto aprendizagem;
- Investigação.

Estágio(s)

Não

Programa

1. Fundamentos:
Informação:intuição, conceito e propriedades;Entropia, incerteza e dispersão;Entropia conjunta, condicionada e propriedades;Divergência Kullback-Leibler;Informação Mútua; Regras da Cadeia;Princípio da entropia máxima
2. Entropia e compressão:
O teorema da codificação da fonte; Códigos e propriedades; Teorema de Kraft e de McMillan; Códigos Ótimos; Códigos de Shannon-Fano-Elias; Códigos de Huffman; Códigos Aritméticos; Códigos de dicionário.
3. Criptografia
Domínios e tipos de alg.; Alg. clássicos; Seq. pseudoaleatórias; Encriptação perfeita e imperfeita; Distribuição de chaves;Alg. de chave assimétrica – o RSA, o teorema de Euler, limites de segurança do RSA, alg.s de Euclides, peq. Teor. de Fermat, resto Chinês); Alg. de chave simétricas; Funções de Hashing
4. Códigos de Recuperação de Erros
Teorema da codificação de Canal;Tipos de Canais e de Códigos; Códigos lineares, códigos de Hamming; Códigos cíclicos, polinómio gerador, Propriedades na deteção e correção.

Docente(s) responsável(eis)

Paulo Fernando Pereira de Carvalho

Métodos de Avaliação

Avaliação final
Exame: 100.0%

Avaliação contínua
São propostos, durante as aulas teóricas, a realização de TPCs, existindo ainda mini-testes surpresa o que promove a aprendizagem continuada: 100.0%

Bibliografia

K. Sayood, Introduction to data compression: second edition, Morgan Kaufman, 2000. (selected chapters)
J. C. MacKay (2003) Information Theory, Inference and Learning Algorithms, University of Cambridge, (http://www.inference.phy.cam.ac.uk/mackay/itila/book.html)(selected chapters)
W. Trappe, L. Washington, Introduction to Cryptography with Coding Theory, Prentice Hall, 2nd Edition (selected chapters)
Shu Lin, Daniel J. Costello (2004) Error Control Coding, Second Edition, Prentice Hall; 2nd Edition (selected chapters)
Carvalho, P. (2011) – Slides de Teoria de Informação, DEI-FCTUC.

Complementar/Complementary:
T. Cover, J. Thomas (1991) Elements of Information Theory, John Wiley&Sons