IN420 Teoria dell’Informazione – A.A. 2020/21
La pagina web inerente l’anno precedente di erogazione è reperibile qui.
Avvisi
Nella settimana 19-23 Aprile (settimana degli esoneri) non saranno erogate lezioni o esercitazioni.
L’orario del mercoledì è stato spostato nella fascia 12.00 — 14.00.
Il ricevimento attualmente si svolge in remoto; si prega di richiedere gli appuntamenti via email al docente.
Orari ed aule
Quando: Martedì 14.00-16.00, Mercoledì 12.00-14.00 e Giovedì 12.00-14.00
Dove: Microsoft Stream
Libro di testo
Il libro di testo adottato è
-
Teoria dell’informazione, codici, cifrari di F. Fabris (Bollati Boringhieri 2001).
Alcune precisazioni al testo.
Per altri riferimenti bibliografici e per altre informazioni ufficiali sull’insegnamento si rimanda al GOMP.
Diario delle lezioni
I riferimenti [F] indicano le sezioni del libro di testo.
| Data | Argomenti | Appunti | Riferimenti al testo |
|---|---|---|---|
24 Febbraio |
Presentazione del corso. Simboli, alfabeti, parole. Divergenza informazionale tra due distribuzioni. Disuguaglianze di Gibbs e di Jensen. |
[F 1.1, 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5, 2.1] |
|
25 Febbraio |
Dimostrazione delle disuguaglianze di Jensen e di Gibbs. Disuguaglianza della somma logaritmica. Definizione di mutua informazione ed entropia. |
[F 2.1, 2.2] |
|
2 Marzo |
Esercizi. Esempi di calcolo dell’entropia. Dall’entropia alla divergenza informazionale. Entropia di funzioni di v.a. |
||
3 Marzo |
Entropia congiunta ed entropia condizionata. Regola della catena. Diagrammi informazionali. |
[F 2.2] |
|
4 Marzo |
Mutua informazione condizionata, entropia condizionata su più variabili, entropia e mutua informazione di v.a. vettoriali, disuguaglianza di Fano. |
[F 2.3] |
|
9 Marzo |
Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del sistema SIGSALY. |
||
10 Marzo |
Dimostrazione della disuguaglianza di Fano. Teoremi di elaborazione dati. |
[F 2.3, 2.5] |
|
11 Marzo |
Stazionarietà, assenza di memoria. Legge dei grandi numeri. Disuguaglianza e teorema di Chebyshev. |
[F 3.1, 3.2] |
|
16 Marzo |
Esercizi. Mutua informazione di 3 v.a. ed applicazioni. Teorema della segretezza perfetta di Shannon. |
||
17 Marzo |
Sequenze tipiche in probabilità. Principio di equipartizionamento asintotico. |
[F 3.3, 3.3.1] |
|
18 Marzo |
Funzioni di codifica, tipi di codici. |
[F 3.4, 3.4.1, 3.4.2] |
|
23 Marzo |
Esercizi. Statistiche sufficienti, massima verosimiglianza. Esempi di codifica di sorgente. |
||
24 Marzo |
Alberi di codice. Disuguaglianza di McMillan-Kraft. |
[F 3.4.3, 3.4.4] |
|
25 Marzo |
Tasso di un codice. Teoremi di Shannon per codifiche blocco-lunghezza variabile. Codice di Shannon-Fano. |
[F 3.4.6, 3.4.7] |
|
30 Marzo |
Esercizi. Codifica di sorgente. Algoritmo di Sardinas-Patterson. |
||
31 Marzo |
Teorema della codifica di sorgente per codici blocco-blocco. |
[F 3.5] |
|
1 Aprile |
Codice di Fano. Proprietà dei codici ottimi. Codice di Huffman. |
[F 5.1, 5.2] |
|
7 Aprile |
Codici universali. Codice multinomiale. |
[F 5.6, 5.6.1] |
|
8 Aprile |
Codice di Ziv-Lempel (LZ77) |
[F 5.6.2] |
|
13 Aprile |
Esercizi. Esempi su Fano, Huffman, Ziv-Lempel. |
||
14 Aprile |
Introduzione alla codifica di canale. Canali e capacità. |
[F 4.1, 4.2, 4.2.1] |
|
15 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] |
|
27 Aprile |
Esercizi. Calcolo della capacità di canale. |
||
28 Aprile |
Criteri di decodifica. Teorema inverso di codifica di canale. |
[F 4.3, 4.3.1, 4.3.2, 4.4] |
|
29 Aprile |
Dimostrazione del teorema inverso di codifica di canale. |
[F 4.4.1] |
|
4 Maggio |
Esercizi. Canale Z. Sfere di Hamming. |
||
5 Maggio |
Teorema diretto della codifica di canale. |
[F 4.4.2] |
|
6 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 |
Esercizi. Classificazione bayesiana. Decodifica Ziv-Lempel. Concatenazione di canali. |
||
12 Maggio |
Decodifica a distanza minima. Capacità di correzione. Codici a ripetizione. |
[F 6.2.2] |
|
13 Maggio |
Codici lineari. Codifica e matrice generatrice. |
[F 6.3.1] |
|
18 Maggio |
Esercizi. Proprietà dei codici lineari. |
||
19 Maggio |
Matrice di controllo. Codici di Hamming. |
[F 6.3.2, 6.3.3] |
|
20 Maggio |
Decodifica con sindrome. Codici perfetti. |
[F 6.3.2] |
|
25 Maggio |
Esercizi. Tabella di Slepian. Decodifica dei codici di Hamming. |
||
26 Maggio |
Codici ciclici. |
[F 6.4] |
|
27 Maggio |
Funzioni hash |