Teoria dell'Informazione, A.A. 2004/2005

Orari del corso:

• martedí I fascia (48),
• giovedí I fascia (42),
• venerdí 14-16 (42).

Argomenti trattati a lezione

1. 28 Settembre 2004. Presentazione del corso. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità.
2. 30 Settembre 2004. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice.
3. 5 Ottobre 2004. Entropia. Divergenza. Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi.
4. 8 Ottobre 2004. Descrizione con variabili aleatorie di una sorgente di Informazione. Tasso del codice. Sorgenti stazionarie e senza memoria. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio.
5. 12 Ottobre 2004. Il codice di Huffman. Entropia condizionata, mutua informazione. Tipi e loro dimensioni. Codice multinomiale.
6. 14 Ottobre 2004. Asintotica ottimalità del codice di Huffman. Codici LV-B. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft.
7. 15 Ottobre 2004. Generazione di famiglie complete. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità degli stessi.
8. 19 Ottobre 2004. Rapporti asintotici del tasso dei codici di Tunstall con l'entropia della sorgente. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel.
9. 21 Ottobre 2004. Codice universale di Ziv Lempel e Welch. Codice universale di Burrows-Wheeler.
10. 22 Ottobre 2004. Codici B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima. Determinazione delle dimensioni di un tipo T con il metodo probabilistico.
11. 26 Ottobre 2004. Codici δ-tipici e Secondo Teorema di Shannon.
12. 28 Ottobre 2004. Codici LV-LV. Limiti e codici asintoticamente ottimi. Codici segreti. Breve storia della crittografia e principali risultati della crittografia a chiave pubblica.
13. Codifica di CANALE.