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

Lezione 18

Classificazione dei codici. Disuguaglianza di Kraft. Codici istantanei ottimali.

Lezione 17

Spiegazione del secondo principio della termodinamica nel modellino della catena di Markov (crescita della funzione H, ecc.): interpretazioni puntuale (entropia di Boltzmann) vs. interpretazione statistica (entropia di Shannon). Esercizi di ripasso. Compressione dati.

Lezione 16

Tasso di entropia di un processo stocastico stazionario. Interpretazione nel teorema generale di Shannon-McMillan-Breiman. Tasso di entropia di una catena di Markov stazionaria. Esercizi.

Lezione 15

Le probabilità condizionali determinano un processo stocastico. Condizione di stazionerietà per una catena di Markov. Teorema ergodico per catene di Markov.

Lezione 14

Seminario della dott.ssa Chiara Basile: "Metodi entropici per l'estrazione di informazione da testi scritti".
Notebook di Mathematica per replicare alcuni grafici del seminario.

Lezione 13

Compressione dati tramite il Teorema di Shannon-McMillan-Breiman. Catene di Markov (temporalmente) omogenee. Stazionarietà di un processo stocastico.

Lezione 12

Lemma dell'equipartizione asintiotica. Teorema di Shannon-McMillan-Breiman (versione di Shannon per variabili i.i.d.).

Lezione 11

Stima dall'alto della probabilità di errore per variabili indipendenti. Varianza. Convergenza in probabilità. Disuguaglianza di Chebychev. Spazi per (finiti o infiniti) esperimenti ripetuti. Legge debole dei grandi numeri.

Lezione 10

Disuguaglianza di Fano. Esercizi.

Lezione 9

Data-processing Inequality.

Lezione 8

Altri esempi e proprietà dell'informazione reciproca. Composizione di una v.a. = "ingrezzimento" della sua partizione. Applicazioni delle proprietà di I. Informazione reciproca condizionata. Regole di composizione multipla per H e I.
Letture extra interessanti: falsificabilità di una teoria scientifica, compendio dell'epistemologia di Popper.
Chi pensa che queste cose non abbiano rilevenza pratica legga questo paragrafo.

Lezione 7

Seconda parte della disuguaglianza di Jensen (per funzioni strettamente convesse). Dimostrazione che l'entropia relativa è nondegenere. Informazione reciproca e sue proprietà, esempi.

Lezione 6

Si inizia ad usare più direttamente il testo:
Entropia di una variabile aleatoria, entropia condizionale di una v.a. rispetto ad un'altra, entropia congiunta. Entropia relativa.

Lezione 5

Dimostrazione del Teoremone.

Lezione 4

Enunciato del "Teoremone" sull'entropia condizionale e sua interpretazione. Disuguaglianza di Jensen.

Lezione 3

Cenni sugli spazi di probabilità e la probabilità condizionale. Entropia di una partizione. Ordinamento parziale e operazioni sulle partizioni. Entropia condizionale.

Lezione 2

Lezione Zero del corso: Dall'entropia di Boltzmann all'entropia di Shannon.
Letture extra interessanti: La freccia del tempo e l'entropia di Boltzmann, di J. Lebowitz.
Gioco in rete: Twenty Questions.

Lezione 1

Presentazione del corso e accordi vari.