Teoria dell'informazione (2008/2009)

Obiettivi formativi

Il corso intende presentare i concetti fondamentali della teoria dell'Informazione e della teoria della comunicazione, approfondendo in particolare: codifica, compressione, entropia, trasmissione, trasduzione, sicurezza e complessita' algoritmica.

1. Codifica
---------------
1.1. Introduzione.
1.2. Informazione, misure informative ed entropia.
1.3. Classi di codici e principali caratteristiche.
1.4. Sorgenti informative e Codici ottimali.

2. Compressione
-------------------
2.1. Norma di Kraft e teorema di McMillan.
2.2. Huffman, LZ, Arithmetic, Shannon-Fano, Burrow-Weeler.
2.3. Primo teorema di Shannon.

3. Entropia
-----------------------
3.1. Vari tipi di entropia e rapporti reciproci.
3.2. Distanza informativa e Mutua Informazione.
3.2. Sorgenti stocastiche e marcoviane.

4. Tipicita'
---------------------
4.1. Sequenze tipiche ed AEP (Asintotic Equipartition Propety).

5. Trasmissione
---------------------
5.1. Codici di trasmissione, capacita' di canale e tasso di trasmissione.
5.2. Secondo Teorema di Shannon
5.3. Cenno ai codici autocorrettori (Codici di Hamming).

6. Trasduzione
-------------------------
6.1. Estensione al continuo dei concetti entropici.
6.2. Teorema del campionamento
6.3. Teorema di Maxwell
6.4. Terzo teorema di Shannon

7. Sicurezza
------------------
7.1. Crittografia a chiave privata. Sviluppi storici e problema delle chiavi.
7.2. Protocollo di Diffie-Hellman
7.3. Crittografia a chiave pubblica.
7.4. Schemi di autenticazione, firme e certificati elettronici. Protocollo di Bennet-Brassard.

7. Complessita'
------------------
8.1. Complessita' algoritmica di Kolmogorov-Chaitin
8.2 Stringhe random e programmi eleganti.
8.3.Teorema di Chaitin sull'eleganza.

Esame Orale