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 è

[F] Teoria dell’informazione, codici, cifrari di F. Fabris (Bollati Boringhieri 2001). Una copia è reperibile anche in biblioteca.

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.

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.