SITE TITLE

LOGO DIETI

Teoria dell'informazione

Titolo insegnamento in inglese:

Information Theory 

 Lingua: Italiano

Insegnamento: Teoria dell'informazione

Anno di corso: II

CFU: 6

SSD: INF/01

Ore di lezione: 48

Semestre: 2

Modulo: Nessuno

Codice: 11497

Obiettivi formativi:

L'obiettivo principale del corso è di fornire le basi matematiche, sia di natura algebrica che combinatoria e probabilistica, necessarie per lo studio della problematica della trasmissione dell'informazione così come sviluppata da C. Shannon. Un ulteriore obiettivo consiste nell'inquadrare la teoria dei codici a lunghezza variabile nell'ambito della teoria dei linguaggi formali, illustrando metodi matematici che utilizzano la combinatoria delle parole e che sono essenziali per studiare problemi di interesse applicativo quali la compressione dei testi o l'analisi di sequenze biologiche.

Contenuti:

Il corso affronta alcuni classici problemi della comunicazione delle informazioni, secondo l'impronta data da Claude Shannon. Un concetto di base in questo approccio è quello di entropia di una sorgente d'informazione, o più in generale di una variabile aleatoria. Una prima, consistente parte del corso è dedicata alla codifica efficiente dell'informazione proveniente da una sorgente (compressione dei dati). In tale ambito si inserisce la teoria dei codici a lunghezza variabile, preceduta nel corso da un riepilogo delle nozioni algebriche necessarie (semigruppi e monoidi liberi). Alcuni contenuti in dettaglio: caratterizzazioni dei codici (univocamente decifrabili): teoremi di Sardinas-Patterson e Levenshtein; misura: disuguaglianza di Kraft-McMillan e teorema di Kraft; codici massimali e completi; costo di una codifica, primo teorema di Shannon e codici ottimali; ritardo di decifrazione. Nella seconda parte si estendono le nozioni precedenti al caso di sorgenti con memoria, ripassando i concetti probabilistici richiesti (processi stocastici, catene di Markov) e in seguito spostando l'attenzione al canale di comunicazione e alla capacità di trasmissione senza errori anche in presenza di rumore (secondo teorema di Shannon). Si conclude con accenni ad altre questioni di recente interesse nella teoria dell'informazione.

Prerequisiti: Nessuno

Modalità didattiche:

Lezioni frontali.

Materiale didattico:

Aldo de Luca, F. D'Alessandro. Teoria degli Automi Finiti. Springer Italia, 2013

J. Berstel, D. Perrin, C. Reutenauer. Codes and Automata. Cambridge University Press, 2009

T.M. Cover, J.A. Thomas. Elements of Information Theory. 2a edizione, Wiley, 2006.

Modalità di esame: 

L'esame si articola in prova

 

 

 

 

 

 

Solo orale

 

 

 

 

 

 

 

 

 

 

In caso di prova scritta i quesiti sono

 

     

 

   

 

Altro 

 

Docente: De Luca Alessandro