Teoria da Informação

Conhecimentos de Base Recomendados

Análise Matemática I e II, 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 que concretizem o interesse prático da matéria e exemplifiquem a sua aplicação a situações reais.

Aulas práticas dedicadas à realização de exercícios de programação envolvendo os diversos conceitos lecionados

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 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 e na encriptação e segurança.

Pessoais:

•          Trabalho em grupo;

•          Raciocínio critico.

Sistémicas:

•          Autoaprendizagem;

•          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 Óptimos; 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. pseudo-aleató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, Curvas elipticas, aplicações em protocolos de segurança (distribuição de chaves, Kerberos, PKI, X.509, PGP, SSL e TLS).

Docente(s) responsável(eis)

Rui Pedro Pinto de Carvalho e Paiva

Métodos de Avaliação

Avaliação
Resolução de problemas: 10.0%
Projecto: 40.0%
Exame: 50.0%

Bibliografia

 K. Sayood, Introduction to data compression: fourth edition, Morgan Kaufman, 2017. (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)

Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography, Taylor & Francis Inc, 2020

Carvalho, P. (2024) – Slides de Teoria de Informação, DEI-FCTUC.

Complementar/Complementary:

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