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 è

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.

Diapositive
Lavagna

[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.

Lavagna

[F 2.1, 2.2]

2 Marzo

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

Lavagna

3 Marzo

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

Lavagna

[F 2.2]

4 Marzo

Mutua informazione condizionata, entropia condizionata su più variabili, entropia e mutua informazione di v.a. vettoriali, disuguaglianza di Fano.

Lavagna

[F 2.3]

9 Marzo

Esercizi. Minimi dell’entropia. Calcolo della mutua informazione condizionata. Analisi del sistema SIGSALY.

Lavagna

10 Marzo

Dimostrazione della disuguaglianza di Fano. Teoremi di elaborazione dati.

Lavagna

[F 2.3, 2.5]

11 Marzo

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

Lavagna

[F 3.1, 3.2]

16 Marzo

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

Lavagna

17 Marzo

Sequenze tipiche in probabilità. Principio di equipartizionamento asintotico.

Lavagna

[F 3.3, 3.3.1]

18 Marzo

Funzioni di codifica, tipi di codici.

Lavagna

[F 3.4, 3.4.1, 3.4.2]

23 Marzo

Esercizi. Statistiche sufficienti, massima verosimiglianza. Esempi di codifica di sorgente.

Lavagna

24 Marzo

Alberi di codice. Disuguaglianza di McMillan-Kraft.

Lavagna

[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.

Lavagna

[F 3.4.6, 3.4.7]

30 Marzo

Esercizi. Codifica di sorgente. Algoritmo di Sardinas-Patterson.

Lavagna

31 Marzo

Teorema della codifica di sorgente per codici blocco-blocco.

Lavagna

[F 3.5]

1 Aprile

Codice di Fano. Proprietà dei codici ottimi. Codice di Huffman.

Lavagna

[F 5.1, 5.2]

7 Aprile

Codici universali. Codice multinomiale.

Lavagna

[F 5.6, 5.6.1]

8 Aprile

Codice di Ziv-Lempel (LZ77)

Lavagna

[F 5.6.2]

13 Aprile

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

Lavagna

14 Aprile

Introduzione alla codifica di canale. Canali e capacità.

Lavagna

[F 4.1, 4.2, 4.2.1]

15 Aprile

Canali senza perdite, deterministici, inutili, simmetrici, con cancellazione.

Lavagna

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

27 Aprile

Esercizi. Calcolo della capacità di canale.

Lavagna

28 Aprile

Criteri di decodifica. Teorema inverso di codifica di canale.

Lavagna

[F 4.3, 4.3.1, 4.3.2, 4.4]

29 Aprile

Dimostrazione del teorema inverso di codifica di canale.

Lavagna

[F 4.4.1]

4 Maggio

Esercizi. Canale Z. Sfere di Hamming.

Lavagna

5 Maggio

Teorema diretto della codifica di canale.

Lavagna

[F 4.4.2]

6 Maggio

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

Lavagna

[F 6.1, 6.2, 6.2.1, 6.2.2]

11 Maggio

Esercizi. Classificazione bayesiana. Decodifica Ziv-Lempel. Concatenazione di canali.

Lavagna

12 Maggio

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

Lavagna

[F 6.2.2]

13 Maggio

Codici lineari. Codifica e matrice generatrice.

Lavagna

[F 6.3.1]

18 Maggio

Esercizi. Proprietà dei codici lineari.

Lavagna

19 Maggio

Matrice di controllo. Codici di Hamming.

Lavagna

[F 6.3.2, 6.3.3]

20 Maggio

Decodifica con sindrome. Codici perfetti.

Lavagna

[F 6.3.2]

25 Maggio

Esercizi. Tabella di Slepian. Decodifica dei codici di Hamming.

Lavagna

26 Maggio

Codici ciclici.

Lavagna

[F 6.4]

27 Maggio

Funzioni hash

Lavagna

Materiale su funzioni hash