Lezione 51

Dimostrazione del tasso di compressione dell'algoritmo LZ78, seconda parte..

Lezione 50

Dimostrazione del tasso di compressione dell'algoritmo LZ78, prima parte.

Verifica scritta facoltativa

Materiale verificato: teoria dell'informazione e cenni di probabilità, fino alle catene di Markov.

Lezione 49

Compressori universali. Algoritmo LZ78.

Lezione 48

Efficienza del codice di Shannon-Elias-Fano in termini di generazione del codice per stringhe di cifre. Esercizi di ripasso.

Lezione 47

Fine della dimostrazione dell'ottimalità del codice di Huffman. Codice di Shannon-Elias-Fano.

Lezione 46

Ottimalità del codice di Huffman.

Lezione 45

Codice di Huffman. Esempi e definizione formale.

Lezione 44

Dimostrazione della disuguaglianza di Kraft. Codici ottimali. Superottimalità. Codice di Shannon. Esempi. Stima dell'efficienza di un codice. Codice di Shannon ed entropia. Raggruppamento in stringhe di cifre per migliorare la compressione. Codici errati. Disuguaglianza di Kraft per codici univocamente decifrabili.

Lezione 43

Esercizi di ripasso. Compressione dati. Classificazione dei codici. Disuguaglianza di Kraft.

Lezione 42

Tasso di entropia per catene di Markov. Modello supersemplificato di sistema fisico come catena di Markov: crescita dell'entropia di Shannon. Relazione fra la funzione H di uno spazio di fase fisico e l'entropia di Shannon di una sua discretizzazione.

Lezione 41

Dimostrazione del teorema ergodico per CM omogenee. Tasso di entropia di un processo stocastico. Suo significato in termini di compressione dei dati.

Lezione 40

Criterio di stazionerietà per CM. Rappresentazione grafica di matrici di transizione. Matrici stocastiche ergodiche. Teorema ergodico per CM omogenee.

Lezione 39

Processi stocastici. Catene di Markov. Stazionarietà ed omogeneità per CM. Probabilità dello stato iniziale, matrice di transizione e loro utilizzo.

Lezione 38

Lemma dell'equipartizione asintiotica. Teorema di Shannon-McMillan-Breiman (versione di Shannon per variabili i.i.d.). Compressione dati tramite il Teorema di SMB.

Lezione 37

Esercizi. Entropia di una partizione numerabile. Introduzione al teorema di Shannon-McMillan-Breiman.

Lezione 36

Dimostrazione della disuguaglianza di Fano; corollari ed applicazioni. Stime dall'alto della probabilità di errore.

Lezione 35

Data Processing Inequality. Corollari ed esempi. Disuguaglianza di Fano.

Lettura extra: Minibiografia di Robert(o) Fano (da Wikipedia).

Lezione 34

Esercizi sulla mutua informazione ed ulteriori proprietà. Regola di composizione dell'entropia (condizionale). Mutua informazione condizionale. Regola di composizione della mutua informazione (condizionale). Sequenze brevi di Markov.

Lezione 33

Versione forte della disuguaglianza di Jensen. Entropia relativa (divergenza di Kullback-Leibler). Spiegazione euristica dell'entropia relativa come spreco medio di bit per cifra usando un codice sbagliato. Mutua informazione (informazione comune) e sue proprietà.