Teoria dell'informazione (2006/2007)

Corso a esaurimento

Codice insegnamento
4S00039
Docente
Andrea Acquaviva
crediti
5
Altri corsi di studio in cui è offerto
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
2° Q dal 8-gen-2007 al 9-mar-2007.

Orario lezioni

2° Q
Giorno Ora Tipo Luogo Note
martedì 11.30 - 13.30 lezione Aula B  
mercoledì 9.30 - 10.30 lezione Aula C  
giovedì 9.30 - 11.30 lezione Aula C  

Obiettivi formativi

Il corso intende presentare i concetti fondamentali della teoria dell'Informazione e le sue applicazioni alla teoria della comunicazione e all'informatica quali compressione, sicurezza e complessità. Verranno trattati inoltre argomenti relativi alle tecniche di codifica a correzione di errore e tecniche di codifica avanzate quali trellis e graph codes.

Programma

1. Introduction
---------------
1.1. Entropy, relative entropy, mutual information
1.2. Asymptotic equipartition property
1.3. Entropy rates of a stochastic process

2. Data compression
-------------------
2.1 Block, symbol, stream codes, codes for integers
2.2 Huffman, LZ, arithmetic coding, Shannon-Fano codes

3. Shannon coding theory
---------------------
3.1. Kraft inequality, Shannon's source coding theorem
3.2. Channel capacity (jointly typical sequences, Fano's inequality, Shannon's channel coding theorem and its converse)

4. Differential entropy
-----------------------
4.1. Defintion of differential entropy
4.2. Relationship with discrete entropy and properties

5. Gaussian channels
---------------------
5.1. Coding theorem for gaussian channels
5.2. Parallel, colored and feedback gaussian channels
5.3. Error correcting codes

6. Rate-distortion theory
-------------------------
6.1. Quantization
6.2. Rate distortion theorem and rate distortion function


7. Advanced Coding
------------------
7.1. Advanced coding (Hash, binary codes)
7.2. Exact marginalization in trellises and graphs
7.3. Sparse graph codes

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
T. M. Cover, J. A. Thomas Elements of Information Theory (Edizione 1) John Wiley & Sons, Inc. 1991 0471062596 Testo principale
David J.C. MacKay Information theory, inference and learning algorithms (Edizione 1) Cambridge University Press 2003 Testo secondario - disponibile online

Modalità d'esame

1. Prova scritta
2. Discussione tesina orale

Materiale didattico

Documenti