Teoria dell'Informazione

Periodo di svolgimento
‌‌
Info sul corso
Ore del corso
40
Ore dei docenti responsabili
40
Ore di didattica integrativa
0
CFU 6
‌‌

Modalità esame

Prova orale

Docente

Vedi dettagli del docente

Prerequisiti

Si richiede una conoscenza elementare della teoria della probabilità. 
Il corso e' adatto agli studenti del III anno di matematica e fisica, ma e' assolutamente accessibile (almeno in gran parte) a studenti interessati del II anno, e utile presumibilmente anche a studenti della laurea magistrale e perfezionandi interessati.

Programma

Entropia di Shannon. Entropia relativa. Informazione mutua. Proprietà di equipartizione asintotica.

Compressione dei dati, , diseguaglianza di Kraft, codifica di Huffman e di Shannon. Algoritmo di Lempel-Ziv. Tasso di entropia di un processo stocastico.
Catene di Markov. Camminata aleatoria
su un grafo. Predizione, entropia e scommesse: criterio di
Kelly, corse di cavalli. Entropia di una lingua. Stima dell'entropia della lingua inglese.
Teoria dell'informazione, codici, compressione dei dati e
predizione.

Capacità di un canale.

Complessità di Kolmogorov e entropia. Caso e pseudocaso. 


Entropia e sistemi dinamici:
Entropia topologica. Entropia di Kolmogorov-Sinai.
Schemi di Bernoulli. Catene di Markov. Grafi, cammini
aleatori su grafi. Teorema di Perron-Frobenius. Algoritmo
di page-rank di Google.

 

Obiettivi formativi

L'obiettivo del corso è di introdurre le nozioni
fondamentali della teoria dell'informazione.

Riferimenti bibliografici

Cover-Thomas: Elements of Information Theory 2nd edition Wiley (2006)

Mennucci-Mitter: Probabilità e informazione 2nd edition Edizioni della Normale (2008)

Mackay: Information Theory, Inference, and Learning Algorithms Cambridge University Press (2003)

Ulteriori riferimenti bibliografici saranno dati durante le lezioni.