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. |
[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] |
|
24 Maggio |
Esercizi. Proprietà dei codici lineari. |