76304 - TEORIA DELL'INFORMAZIONE E COMPLESSITA'

Scheda insegnamento

Anno Accademico 2017/2018

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.

Programma/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.

Alcuni argomenti verranno sviluppati con implementazione di specifiche applicazioni utili allo studio del linguaggio naturale e al trattamento di materiale testuale.


Testi/Bibliografia

Il testo di riferimento è:

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

 

Alcuni argomenti del corso vengono trattati in:

Zanette, D. H. "Statistical Patterns in Written Language.”

 

Metodi didattici

Lezioni in aula. 

 

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

Modalità di verifica 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.

Strumenti a supporto della didattica

In alcune lezioni verrà usato il calcolatore per mostrare simulazioni o elaborazione di dati sperimentali. 

Orario di ricevimento

Consulta il sito web di Giampaolo Cristadoro