IN420 Teoria dell’Informazione – A.A. 2022/23

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

Avvisi

Il giorno 18/4/2023 non si terrà lezione. Il giorno 28/4/2023 non si terrà esercitazione.

Orari ed aule

Quando: Martedì 15.30-17.30 (aula A), Giovedì 10.30-12.30 (A) e Venerdì 15.30-17.30 (A)
Dove: aula A (via Vasca Navale)

Libro di testo

Il libro di testo adottato è

[F] F. Fabris. Teoria dell’informazione, codici, cifrari. Bollati Boringhieri, 2001. Una copia del testo è reperibile nella biblioteca di area scientifica, sede Torri.

Alcune precisazioni al testo.

Altri riferimenti bibliografici utili sono:

[CT] T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991. Una copia del testo è reperibile nella biblioteca di area scientifica, sede Torri. Una riedizione del 2006 è reperibile anche in formato elettronico attraverso Roma Tre Discovery.
[GRS] V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Bozza disponibile online, 2022.

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	[F 1.1, 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5, 2.1]
23 Febbraio	Dimostrazione delle disuguaglianza di Gibbs. Definizione di mutua informazione ed entropia.		[F 2.1, 2.2]
28 Febbraio	Entropia congiunta ed entropia condizionata. Regola della catena. Diagrammi informazionali.		[F 2.2]
2 Marzo	Mutua informazione condizionata, entropia condizionata in più variabili, entropia di sequenze di v.a.		[F 2.3]
3 Marzo	Esercizi. Esempi di calcolo dell’entropia. Entropia di funzioni di v.a. Dall’entropia alla divergenza informazionale.
7 Marzo	Mutua informazione di v.a. vettoriali, disuguaglianza di Fano. Teoremi di elaborazione dati.		[F 2.3, 2.5]
9 Marzo	Sorgenti. Stazionarietà, assenza di memoria. Legge dei grandi numeri. Disuguaglianza e teorema di Chebyshev.		[F 3.1, 3.2]
10 Marzo	Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del one-time pad.
14 Marzo	Sequenze tipiche in probabilità. Principio di equipartizionamento asintotico.		[F 3.3, 3.3.1]
16 Marzo	Codici di sorgente. Funzioni di codifica, tipi di codici.		[F 3.4, 3.4.1, 3.4.2]
17 Marzo	Esercizi. Mutua informazione di 3 v.a. ed applicazioni. Teorema della segretezza perfetta di Shannon.
21 Marzo	Alberi di codice. Disuguaglianza di McMillan-Kraft.		[F 3.4.3, 3.4.4]
23 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. Statistiche sufficienti, massima verosimiglianza. Equipartizione asintotica.
28 Marzo	Teorema della codifica di sorgente per codici blocco-blocco.		[F 3.5]
30 Marzo	Codice di Fano. Proprietà dei codici ottimi.		[F 5.1]
31 Marzo	Esercizi. Esempi di codifica di sorgente. Algoritmo di Sardinas-Patterson.
4 Aprile	Codice di Huffman. Codici universali. Codice multinomiale.		[F 5.2, 5.6, 5.6.1]
6 Aprile	Codice di Ziv-Lempel (LZ77).		[F 5.6.2]
13 Aprile	Introduzione alla codifica di canale. Canali e capacità.		[F 4.1, 4.2, 4.2.1]
14 Aprile	Esercizi. Esempi su codifiche Fano, Huffman, Ziv-Lempel.
20 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]
21 Aprile	Esercizi. Calcolo della capacità di canale.
27 Aprile	Criteri di decodifica.		[F 4.3, 4.3.1, 4.3.2]
2 Maggio	Dimostrazione del teorema inverso di codifica di canale.		[F 4.4, 4.4.1]
4 Maggio	Teorema diretto della codifica di canale.		[F 4.4.2]
5 Maggio	Esercizi. Sfere di Hamming.
9 Maggio	Codici correttori d’errore. Richiami sulle strutture algebriche. Spazio di Hamming.		[F 6.1, 6.2, 6.2.1, 6.2.2]
11 Maggio	Decodifica a distanza minima. Capacità di correzione. Codici a ripetizione.		[F 6.2.2]
12 Maggio	Esercizi. Classificazione bayesiana e codifica di canale.
16 Maggio	Codici lineari. Matrice generatrice e codifica. Equazioni di controllo.		[F 6.3.1]
18 Maggio	Matrice di controllo. Codici di Hamming.		[F 6.3.2, 6.3.3]
19 Maggio	Esercizi. Proprietà dei codici lineari.
23 Maggio	Decodifica con sindrome.		[F 6.3.2]
25 Maggio	Codici ciclici.		[F 6.4]
26 Maggio	Funzioni hash e codici di canale. Esercizi.	Materiale su funzioni hash	[GRS 20.1—20.3]

Data

Argomenti

Allegati

Riferimenti al testo

21 Febbraio

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

Diapositive

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

23 Febbraio

Dimostrazione delle disuguaglianza di Gibbs. Definizione di mutua informazione ed entropia.

[F 2.1, 2.2]

28 Febbraio

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

[F 2.2]

2 Marzo

Mutua informazione condizionata, entropia condizionata in più variabili, entropia di sequenze di v.a.

[F 2.3]

3 Marzo

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

7 Marzo

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

[F 2.3, 2.5]

9 Marzo

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

[F 3.1, 3.2]

10 Marzo

Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del one-time pad.

14 Marzo

Sequenze tipiche in probabilità. Principio di equipartizionamento asintotico.

[F 3.3, 3.3.1]

16 Marzo

Codici di sorgente. Funzioni di codifica, tipi di codici.

[F 3.4, 3.4.1, 3.4.2]

17 Marzo

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

21 Marzo

Alberi di codice. Disuguaglianza di McMillan-Kraft.

[F 3.4.3, 3.4.4]

23 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. Statistiche sufficienti, massima verosimiglianza. Equipartizione asintotica.

28 Marzo

Teorema della codifica di sorgente per codici blocco-blocco.

[F 3.5]

30 Marzo

Codice di Fano. Proprietà dei codici ottimi.

[F 5.1]

31 Marzo

Esercizi. Esempi di codifica di sorgente. Algoritmo di Sardinas-Patterson.

4 Aprile

Codice di Huffman. Codici universali. Codice multinomiale.

[F 5.2, 5.6, 5.6.1]

6 Aprile

Codice di Ziv-Lempel (LZ77).

[F 5.6.2]

13 Aprile

Introduzione alla codifica di canale. Canali e capacità.

[F 4.1, 4.2, 4.2.1]

14 Aprile

Esercizi. Esempi su codifiche Fano, Huffman, Ziv-Lempel.

20 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]

21 Aprile

Esercizi. Calcolo della capacità di canale.

27 Aprile

Criteri di decodifica.

[F 4.3, 4.3.1, 4.3.2]

2 Maggio

Dimostrazione del teorema inverso di codifica di canale.

[F 4.4, 4.4.1]

4 Maggio

Teorema diretto della codifica di canale.

[F 4.4.2]

5 Maggio

Esercizi. Sfere di Hamming.

9 Maggio

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

[F 6.1, 6.2, 6.2.1, 6.2.2]

11 Maggio

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

[F 6.2.2]

12 Maggio

Esercizi. Classificazione bayesiana e codifica di canale.

16 Maggio

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

[F 6.3.1]

18 Maggio

Matrice di controllo. Codici di Hamming.

[F 6.3.2, 6.3.3]

19 Maggio

Esercizi. Proprietà dei codici lineari.

23 Maggio

Decodifica con sindrome.

[F 6.3.2]

25 Maggio

Codici ciclici.

[F 6.4]

26 Maggio

Funzioni hash e codici di canale. Esercizi.

Materiale su funzioni hash

[GRS 20.1—20.3]