Lezione 25

Definizione di ergodicità per un processo stocastico stazionario: spiegazione euristica.Teorema sul tasso di compressione di LZ78 per sequenze generate da un processo stocastico stazionario ed ergodico (solo enunciato).

Lezione 24

Spiegazione euristica dell'efficienza dei codici di Shannon-Fano-Elias in fase di costruzione del codice. Compressori universali: algoritmo LZ78.
Applet: applet per LZ78.

Prima verifica scritta

Materiale verificato: fino ai codici di Huffman.

Lezione 23

Codici di Shannon-Fano-Elias.

Lezione 22

Fine dimostrazione dell'ottimalità del codice di Huffman.

Lezione 21

Esempi di codici di Huffman. Ottimalità del codice di Huffman. Twenty questions e il codice di Huffman. Inizio dimostrazione dell'ottimalità.

Lezione 20

Disuguaglianza di Kraft per codici univocamente decifrabili (problema della minimizzazione della lunghezza sulla famiglia dei codici univocamente decifrabil). Codici di Huffman.

Lezione 19

Stima dell'efficienza di un codice: caso di variabile singola (o processo i.i.d.) e caso di processo stocastico stazionario. Stima per un codice ottimizzato per una distribuzione errata. Spiegazione di alcune idee contenute in: D. Benedetto, E. Caglioti and V. Loreto, "Language Trees and Zipping", Phys. Rev. Lett. 88, 4 (2002) (preprint disponibile qui).