Teoria da Informação (2020)

  • 4ª-feira 12:00 – 13:30 via Zoom: link.
  • 6ª-feira 8:30 (!) – 10:00 na Sala 029 do FC6
  • Segunda Fase (exame/melhoria): Algures em Março. (registo obrigatório! link)
  • Entrega do segundo trabalho: Quarta, 27 de Janeiro.
  • Entrega dos trabalho em 2a fase: Algures em Março.
  • Enunciado do primeiro trabalho:
  • Instruções para submissão e esclarecimentos sobre o primeiro trabalho:
  • Enunciado do segundo trabalho: Dúvidas: 1 Alguns Testes: link
  • Sumeter o segundo trabalho por email, num ficheiro <numero-de-aluno>-<nome-do-aluno>.zip , com dois ficheiros readme.txt e ldpc.py.
  • Notas do 1º Trabalho (entrega 1ª fase):
  • Notas do 2º Trabalho (entrega 1ª fase)
  • Todos os alunos que têm “All OK” estão passados com 4 valores. Os alunos que têm “Some fail” poderão ainda recuperar na entrega dos trabalhos em 2ª fase.
  • Notas finais provisórias 1ª fase:

Sumários

  • Aula 01, 7/Out — Introdução à Teoria da Informação. Modelos e códigos para compressão e correcção de erros. O código de repetição. Aproximação de Stirling simplificada.
  • Aula 02, 14/Out — Aproximação de Stirling simplificada (2). O código H_{7,4} e suas propriedades.
  • Plano de estudos da semana 01: .
  • Aula 03, 16/Out — Fim da aula anterior. Repescagem de teoria das probabilidades (1). O vídeo da aula perdeu-se devido a um problema técnico 😩 😠 🤦‍♂️ De modo que, excepcionalmente, preparei umas notas para colocar aqui:
  • Aula 04, 21/Out — Mais teoria das probabilidades.
  • Aula 05, 23/Out — Ainda mais teoria das probabilidades. Desigualdades de Markov, Chebyshev, Jensen.
  • Plano de estudos sobre probabilidades Tinha ERROS! Foi corrigido!
  • Exercício de programação
  • Aula 06, 26/Out — Entropia.
  • Aula 07, 28/Out — Mais entropia. Introdução ao primeiro teorema de Shannon (1). O vídeo da aula perdeu-se outra vez, por um erro diferente (fiquei sem espaço no disco 😩 😠 🤦‍♂️). De modo que, outra vez excepcionalmente (sorry 😅), preparei umas notas para colocar aqui:
  • Aula 08, 28/Out — Introdução ao primeiro teorema de Shannon (2)
  • TPC desta semana: compreender as notas da aula 08:
  • Aula 09, 04/Nov — Demonstração do primeiro teorema de Shannon. O PDF tinha erros (sinais +- trocados)! Foi corrigido!
  • Plano de estudo sobre o primeiro teorema de Shannon:
  • Aula 10, 06/Nov — Códigos de Símbolos (1).
  • Aula 11, 11/Nov — Códigos de Símbolos (2).
  • Plano de estudo sobre códigos de símbolos:
  • Correspondência entre matéria dada nas aulas e capítulos do livro:
  • Aula 12, 13/Nov — Compressão Lempel-Ziv (versão bébé).
  • Aulas 13 e 14 — Dúvidas e Exercícios.
  • Aula 15, 25 Nov — Entropia condicional e informação mútua (§8). Finalmente online:
  • Aula 16 — Canais e sua capacidade.
  • Aula 17 — Como computar a capacidade de um canal simétrico.
  • Aula 18 — Introdução ao 2º Teorema de Shannon, lema da típicalidade.
  • Aula 19 — 1ª parte do 2º Teorema de Shannon.
  • Aula 20 (de facto) — 1ª parte do 2ºTS, Lema da tipicalidade.
  • Aula 20 21 — 1ª parte do 2º Teorema de Shannon.
  • Plano de estudo sobre o 2º teorema de Shannon. Tinha uma IMPRECISÃO! Foi corrigido! Solução do exercício sobre capacidades pelo Ruben Dhanaraju
  • Correspondência entre matéria dada nas aulas e capítulos do livro:
  • Aula 21 22 — Códigos LDPC (versão bébé para o canal de rasura). writeup do que está no quadro
  • Aula 23 —
  • Aula 24 — Duvidas sobre 2º Trabalho

O livro da cadeira

  • David MacKay, Information theory, inference, and learning algorithms
    Sacar o livro (disponível de graça) na página dele.
    Utilizaremos para quase tudo e seguiremos o livro de perto.

O programa da cadeira

  1. Introduçao à teoria da informação (2 aulas).
    MacKay Capítulo 1.
  2. Repescagem de teoria das probabilidades, entropia e informação mútua (3-4 aulas).
    MacKay Capítulo 2.
  3. O primeiro teorema de Shannon, e vários códigos de fonte (6 aulas).
    MacKay Capítulos 4, 5 e 6.
  4. O segundo teorema de Shannon e códigos LDPC (8 aulas).
    MacKay Capítulos 8, 9, 10 e 47.

Como o total planeado da cadeira são 26 aulas, sobram 6 aulas para haver espaço de manobra, para dar apoio aos projectos, tirar dúvidas, tratar outros temas, etc.

Avaliação

A avaliação consiste em 2 testes e 2 trabalhos práticos de programação.

O primeiro teste será sobre as partes 2 e 3 do programa (ver acima). O segundo teste será sobre a parte 4. O teste consistirá de exercícios do livro, e será pedido para fazer demonstrações dadas na aula.

O primeiro trabalho prático será uma implementação de um compressor e descompressor Lempel-Ziv, e o segundo será uma implementação de um codificador e descodificador para um código LDPC. Os programas serão avaliados, primeiro automáticamente (para comprimir/descomprimir, e codificar/descodificar), e depois da entrega do código, serão feitas a cada aluno perguntas simples para confirmar que foi o próprio aluno a escrever o código.

A linguagem de programação será o Python, que é irrealista como linguagem de programação para compressão e codificação, mas permitirá tornar o código mais simples de escrever e corrigir.

Ambos os testes e trabalhos práticos podem ser recuperados na 2ª época de exames.

Advertisement