76304 - TEORIA DELL'INFORMAZIONE E COMPLESSITA'

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - possiede nozioni approfondite di teoria dell'informazione e della complessità algoritmica nei loro principali aspetti applicativi; - è in grado di condurre autonomamente l'approfondimento anche computazionale, delle tematiche sopra citate.

Contenuti

Entropia di una partizione e di una variabile aleatoria. Entropia congiunta ed entropia condizionale. Entropia relativa. Mutua informazione. Lemma dell'equipartizione asintotica e teorema di Shannon-McMillan-Breiman per variabili i.i.d. Applicazione alla compressione dei dati. Tasso di entropia per processi stocastici stazionari. Cenni al teorema generale di Shannon-McMillan-Breiman. Applicazioni. Codici. Disuguaglianza di Kraft. Codici ottimali. Codice di Shannon. Stima dell'efficienza di un codice. Codici errati. Codice di Huffman. Codice di Shannon-Elias-Fano. Compressori universali. Algoritmo LZ78. Algoritmo LZW.

Macchine di Turing. Calcolatori universali. Complessità algoritmica di Kolmogorov. Complessità di Kolmogorov ed entropia. Complessità dei numeri naturali e delle stringe. Probabilità universale. Problema dell'arresto. Numero di Chaitin. Relazione fra complessità di Kolmogorov e probabilità universale.

Testi/Bibliografia

Il testo di riferimento è:

T. M. Cover & J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley-Interscience

Il corso sarà tenuto ad un livello matematico leggermente più alto rispetto al testo base. Questo è fatto per aiutare gli studenti (che hanno una formazione matematica). All'uopo, buoni testi di supporto sono:

Ya. G. Sinai, "Probability Theory", Springer

R. Durrett, "Probability: Theory and Examples", Cambridge

Metodi didattici

Lezioni in aula.

In caso di presenza di studenti internazionali le lezioni potranno essere svolte in inglese.

Modalità di verifica e valutazione dell'apprendimento

Il voto verrà assegnato tramite esame orale.

L'esame comprenderà domande teoriche, quesiti sulle applicazioni delle nozioni imparate nel corso ed almeno un esercizio alla lavagna. In questo modo lo studente verrà valutato sia sull'apprendimento delle nozioni da un punto di vista matematico che sulla loro utilità, nonché sulla capacità di maneggiarle in autonomia.

Orario di ricevimento

Consulta il sito web di Marco Lenci