IN420 Teoria dell’Informazione – A.A. 2024/25

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

Avvisi

Martedì 13/5 e Giovedì 15/5 le lezioni si svolgeranno in Aula C di Via Vasca Navale 84 in quanto l’Aula L sarà utilizzata come seggio elettorale
Mercoledì 14/5 l’esercitazione non si terrà (sarà recuperata successivamente)

Orari ed aule

Mar 11-13 aula L
Mer 14-16 aula L (esercitazione)
Gio 11-13 aula L

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.

Legenda: = scaricabile, = disponibile in biblioteca.

Diario delle lezioni

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

Data	Argomenti	Riferimenti al testo	Allegati
25 Febbraio	Presentazione del corso. Simboli, alfabeti, parole. Divergenza informazionale tra due distribuzioni. Disuguaglianza di Gibbs.	[F 1.1, 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5, 2.1]	Diapositive
27 Febbraio	Dimostrazione delle disuguaglianza di Gibbs. Definizione di mutua informazione ed entropia.	[F 2.1, 2.2]
4 Marzo	Entropia congiunta ed entropia condizionata. Regola della catena. Diagrammi informazionali.	[F 2.2]
5 Marzo	Esercizi. Esempi di calcolo dell’entropia. Entropia di funzioni di v.a. Dall’entropia alla divergenza informazionale.		Lavagne esercizi (2021)
6 Marzo	Mutua informazione condizionata, entropia condizionata in più variabili, entropia di sequenze di v.a. Mutua informazione di v.a. vettoriali, disuguaglianza di Fano.	[F 2.3]
11 Marzo	Teoremi di elaborazione dati. Sorgenti. Stazionarietà, assenza di memoria.	[F 2.5, 3.1]
12 Marzo	Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del one-time pad binario.
13 Marzo	Legge dei grandi numeri. Disuguaglianza e teorema di Chebyshev. Principio di equipartizionamento asintotico.	[F 3.2, 3.3]
18 Marzo	Sequenze tipiche in probabilità. Introduzione ai codici di sorgente.	[F 3.3, 3.3.1, 3.4]
19 Marzo	Esercizi. Mutua informazione di 3 v.a. ed applicazioni. Teorema della segretezza perfetta di Shannon.
20 Marzo	Codici di sorgente. Funzioni di codifica, tipi di codici. Alberi di codice.	[F 3.4, 3.4.1, 3.4.2, 3.4.3]
25 Marzo	Disuguaglianza di McMillan-Kraft. Tasso di un codice.	[F 3.4.3, 3.4.4]
26 Marzo	Esercizi. Statistiche sufficienti. Principio di massima verosimiglianza.
27 Marzo	Teoremi di Shannon per codifiche blocco-lunghezza variabile. Codice di Shannon-Fano. Codici blocco-blocco.	[F 3.4.6, 3.4.7]
1 Aprile	Teorema della codifica di sorgente per codici blocco-blocco. Codice di Fano.	[F 3.5, 5.1]
2 Aprile	Esercizi. Esempi di codifica di sorgente. Algoritmo di Sardinas-Patterson.
3 Aprile	Proprietà dei codici ottimi. Codice di Huffman.	[F 5.2]
8 Aprile	Codici universali. Codice multinomiale. Codice di Ziv-Lempel (LZ77).	[F 5.2, 5.6, 5.6.1, 5.6.2]
9 Aprile	Esercizi. Esempi di codifiche Fano, Huffman, Ziv-Lempel. Cenni al codice LZ78.
10 Aprile	Esempi di codifica LZ77. Introduzione alla codifica di canale.	[F 5.6.2, 4.1]
29 Aprile	Canali e capacità. Canali senza perdite, deterministici, inutili, simmetrici, con cancellazione.	[F 4.2, 4.2.2, 4.2.3, 4.2.4, 4.2.5, 4.2.6]
30 Aprile	Esercizi. Calcolo della capacità di canale.
6 Maggio	Criteri di decodifica.	[F 4.3, 4.3.1, 4.3.2]
7 Maggio	Esercizi. Sfere di Hamming.
8 Maggio	Dimostrazione del teorema inverso di codifica di canale.	[F 4.4, 4.4.1]
13 Maggio	Teorema diretto della codifica di canale.	[F 4.4.2]
15 Maggio	Codici correttori d’errore. Richiami sulle strutture algebriche. Decodifica a distanza minima.	[F 6.1, 6.2, 6.2.1, 6.2.2], [GRS 1.1-1.3, 2.1-2.2]
20 Maggio	Distanza di un codice. Capacità di correzione. Limitazione di Singleton. Codici a ripetizione. Introduzione ai codici lineari.	[F 6.2.2, 6.6.1], [GRS 1.4-1.5, 4.3]
21 Maggio	Esercizi. Classificazione bayesiana e codifica di canale.
22 Maggio	Codici lineari. Matrice generatrice e codifica. Equazioni di controllo.	[F 6.3.1], [GRS 2.3]
27 Maggio	Matrice di controllo. Codici di Hamming e loro decodifica efficiente.	[F 6.3.2, 6.3.3], [GRS 2.4-2.5]
28 Maggio	Esercizi. Proprietà dei codici lineari. Codici di Hadamard.	[GRS 2.6]
29 Maggio	Decodifica con sindrome di codici lineari.	[F 6.3.2]
3 Giugno	Codici ciclici.	[F 6.4]
4 Giugno	Funzioni hash e codici di canale. Esercizi.	[GRS 20.1-20.3]
5 Giugno	Codici Reed-Solomon.	[GRS 5.1-5.2]

Data

Argomenti

Riferimenti al testo

Allegati

25 Febbraio

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

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

Diapositive

27 Febbraio

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

[F 2.1, 2.2]

4 Marzo

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

[F 2.2]

5 Marzo

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

Lavagne esercizi (2021)

6 Marzo

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

[F 2.3]

11 Marzo

Teoremi di elaborazione dati. Sorgenti. Stazionarietà, assenza di memoria.

[F 2.5, 3.1]

12 Marzo

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

13 Marzo

Legge dei grandi numeri. Disuguaglianza e teorema di Chebyshev. Principio di equipartizionamento asintotico.

[F 3.2, 3.3]

18 Marzo

Sequenze tipiche in probabilità. Introduzione ai codici di sorgente.

[F 3.3, 3.3.1, 3.4]

19 Marzo

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

20 Marzo

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

[F 3.4, 3.4.1, 3.4.2, 3.4.3]

25 Marzo

Disuguaglianza di McMillan-Kraft. Tasso di un codice.

[F 3.4.3, 3.4.4]

26 Marzo

Esercizi. Statistiche sufficienti. Principio di massima verosimiglianza.

27 Marzo

Teoremi di Shannon per codifiche blocco-lunghezza variabile. Codice di Shannon-Fano. Codici blocco-blocco.

[F 3.4.6, 3.4.7]

1 Aprile

Teorema della codifica di sorgente per codici blocco-blocco. Codice di Fano.

[F 3.5, 5.1]

2 Aprile

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

3 Aprile

Proprietà dei codici ottimi. Codice di Huffman.

[F 5.2]

8 Aprile

Codici universali. Codice multinomiale. Codice di Ziv-Lempel (LZ77).

[F 5.2, 5.6, 5.6.1, 5.6.2]

9 Aprile

Esercizi. Esempi di codifiche Fano, Huffman, Ziv-Lempel. Cenni al codice LZ78.

10 Aprile

Esempi di codifica LZ77. Introduzione alla codifica di canale.

[F 5.6.2, 4.1]

29 Aprile

Canali e capacità. Canali senza perdite, deterministici, inutili, simmetrici, con cancellazione.

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

30 Aprile

Esercizi. Calcolo della capacità di canale.

6 Maggio

Criteri di decodifica.

[F 4.3, 4.3.1, 4.3.2]

7 Maggio

Esercizi. Sfere di Hamming.

8 Maggio

Dimostrazione del teorema inverso di codifica di canale.

[F 4.4, 4.4.1]

13 Maggio

Teorema diretto della codifica di canale.

[F 4.4.2]

15 Maggio

Codici correttori d’errore. Richiami sulle strutture algebriche. Decodifica a distanza minima.

[F 6.1, 6.2, 6.2.1, 6.2.2], [GRS 1.1-1.3, 2.1-2.2]

20 Maggio

Distanza di un codice. Capacità di correzione. Limitazione di Singleton. Codici a ripetizione. Introduzione ai codici lineari.

[F 6.2.2, 6.6.1], [GRS 1.4-1.5, 4.3]

21 Maggio

Esercizi. Classificazione bayesiana e codifica di canale.

22 Maggio

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

[F 6.3.1], [GRS 2.3]

27 Maggio

Matrice di controllo. Codici di Hamming e loro decodifica efficiente.

[F 6.3.2, 6.3.3], [GRS 2.4-2.5]

28 Maggio

Esercizi. Proprietà dei codici lineari. Codici di Hadamard.

[GRS 2.6]

29 Maggio

Decodifica con sindrome di codici lineari.

[F 6.3.2]

3 Giugno

Codici ciclici.

[F 6.4]

4 Giugno

Funzioni hash e codici di canale. Esercizi.

[GRS 20.1-20.3]

5 Giugno

Codici Reed-Solomon.

[GRS 5.1-5.2]