IN420 Teoria dell’Informazione – A.A. 2021/22

La pagina web inerente la precedente erogazione dell’insegnamento da parte del docente è reperibile qui.


Avvisi

Nei giorni 18/4, 19/4, 21/4 e 25/4 non si terrà lezione.

Orari ed aule

Quando: Lunedì 14.15-16.00 (M4), Martedì 14.15-16.00 (M4) e Giovedì 14.15-16.00 (M4)
Dove: aula M4

Libro di testo

Il libro di testo adottato è

Alcune precisazioni al testo.

Altri riferimenti bibliografici utili sono:

  • [CT] T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991. Reperibile in formato elettronico attraverso Roma Tre Discovery.

  • [GRS] V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Bozza disponibile online, 2019.

Per ulteriori riferimenti bibliografici si rimanda alla scheda GOMP dell’insegnamento.

Diario delle lezioni

I riferimenti [F] indicano le sezioni del libro di testo.

Data Argomenti Allegati Riferimenti al testo

21 Febbraio

Presentazione del corso. Simboli, alfabeti, parole. Divergenza informazionale tra due distribuzioni. Disuguaglianza di Gibbs.

Diapositive
Lavagna

[F 1.1, 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5, 2.1]

22 Febbraio

Dimostrazione delle disuguaglianze di Jensen e di Gibbs. Disuguaglianza della somma logaritmica. Definizione di mutua informazione ed entropia.

[F 2.1, 2.2]

24 Febbraio

Esercizi. Esempi di calcolo dell’entropia. Entropia di funzioni di v.a. Dall’entropia alla divergenza informazionale.

28 Febbraio

Entropia congiunta ed entropia condizionata. Regola della catena. Diagrammi informazionali.

[F 2.2]

1 Marzo

Mutua informazione condizionata, entropia condizionata su più variabili, entropia di v.a. vettoriali.

[F 2.3]

3 Marzo

Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del sistema SIGSALY.

7 Marzo

Mutua informazione di v.a. vettoriali, disuguaglianza di Fano. Teoremi di elaborazione dati.

[F 2.3, 2.5]

8 Marzo

Sorgenti. Stazionarietà, assenza di memoria. Legge dei grandi numeri. Disuguaglianza e teorema di Chebyshev.

[F 3.1, 3.2]

10 Marzo

Esercizi. Mutua informazione di 3 v.a. ed applicazioni. Teorema della segretezza perfetta di Shannon.

14 Marzo

Sequenze tipiche in probabilità. Principio di equipartizionamento asintotico.

[F 3.3, 3.3.1]

15 Marzo

Funzioni di codifica, tipi di codici.

[F 3.4, 3.4.1, 3.4.2]

17 Marzo

Esercizi. Statistiche sufficienti, massima verosimiglianza. Esempi di codifica di sorgente.

21 Marzo

Alberi di codice. Disuguaglianza di McMillan-Kraft.

[F 3.4.3, 3.4.4]

22 Marzo

Tasso di un codice. Teoremi di Shannon per codifiche blocco-lunghezza variabile. Codice di Shannon-Fano.

[F 3.4.6, 3.4.7]

24 Marzo

Esercizi. Codifica di sorgente. Algoritmo di Sardinas-Patterson.

28 Marzo

Teorema della codifica di sorgente per codici blocco-blocco.

[F 3.5]

29 Marzo

Codice a 2 lunghezze. Codice di Fano. Proprietà dei codici ottimi.

[F 3.5, 5.1]

31 Marzo

Esercizi. Esempi di codifica di sorgente (Fano, Huffman).

4 Aprile

Codice di Huffman. Codici universali. Codice multinomiale.

[F 5.2, 5.6, 5.6.1]

5 Aprile

Codice di Ziv-Lempel (LZ77).

[F 5.6.2]

7 Aprile

Esercizi. Esempi su Huffman, Ziv-Lempel.

11 Aprile

Introduzione alla codifica di canale. Canali e capacità.

[F 4.1, 4.2, 4.2.1]

12 Aprile

Canali senza perdite, deterministici, inutili, simmetrici, con cancellazione.

[F 4.2.2, 4.2.3, 4.2.4, 4.2.5, 4.2.6]

14 Aprile

Esercizi. Calcolo della capacità di canale.

26 Aprile

Criteri di decodifica.

[F 4.3, 4.3.1, 4.3.2]

28 Aprile

Esercizi. Canale Z. Sfere di Hamming.

2 Maggio

Dimostrazione del teorema inverso di codifica di canale.

[F 4.4, 4.4.1]

3 Maggio

Teorema diretto della codifica di canale.

[F 4.4.2]

5 Maggio

Esercizi. Classificazione bayesiana e codifica di canale.

9 Maggio

Codici correttori d’errore. Richiami sulle strutture algebriche. Spazio di Hamming.

[F 6.1, 6.2, 6.2.1, 6.2.2]

12 Maggio

Decodifica a distanza minima. Capacità di correzione. Codici a ripetizione.

[F 6.2.2]

16 Maggio

Codici lineari. Matrice generatrice e codifica. Equazioni di controllo.

[F 6.3.1]

17 Maggio

Matrice di controllo. Codici di Hamming.

[F 6.3.2, 6.3.3]

19 Maggio

Decodifica con sindrome.

[F 6.3.2]

23 Maggio

Codici ciclici. Funzioni hash e codici di canale.

[F 6.4]
Materiale su funzioni hash

24 Maggio

Esercizi. Proprietà dei codici lineari.