Claude Shannon Andrey N. Kolmogorov
teoria dell'informazione e della trasmissione

6 crediti, laurea triennale, secondo semestre

DOCENTI: Nicolò Cesa-Bianchi

Materiale bibliografico:

Thomas Cover e Joy Thomas, "Elements of Information Theory (2nd edition)". Wiley, 2006.
Il testo verrà integrato da dispense fornite dal docente.

Obiettivi:

L'obiettivo del corso è fornire un'introduzione alla teoria dell'informazione secondo Shannon e i concetti principali relativi alla codifica di sorgente e di canale. Il corso includerà anche alcuni cenni alla teoria dell'informazione secondo Kolmogorov. La parte finale del corso riguarderà tematiche di complemento scelte dal docente.

Programma preliminare:

Introduzione al corso e nozioni matematiche di base. Entropia, entropia relativa e informazione mutua. La data processing inequality. La disuguaglianza di Fano. Codifica sorgente. Esempi di codice. Disuguaglianza di Kraft. Codici ottimi. La disuguaglianza di McMillan. Codici di Huffman e loro ottimalità. Codici di Shannon-Fano. Primo teorema di Shannon. Codifica di canale. La capacità di canale. Esempi di canale. Canali simmetrici. Secondo teorema di Shannon. Discussione. Cenni alla complessità di Kolmogorov. Applicazioni della teoria dell'informazione alla gestione di portafogli finanziari ed ai problemi di predizione sequenziale.

Modalità d'esame:

L'esame consiste in una prova scritta ed in una prova orale, entrambe obbligatorie. La prova scritta consiste nella soluzione di problemi relativi a: calcolo di quantità legate all'entropia, costruzione di codici sorgente, calcolo di capacità ed di altre quantità legate ai canali di trasmissione. La prova orale consiste nella presentazione di concetti, definizioni e dimostrazione di risultati relativi al programma svolto.

Testi, soluzioni e risultati esami

Consultare la pagina esami.

Note al corso:

  1. Introduzione al corso (versione del 1 marzo 2016)
  2. Codifica sorgente: definizioni (versione del 4 marzo 2016, corretta piccola svista)
  3. Codici istantanei e disuguaglianza di Kraft (versione dell'8 marzo 2016)
  4. Entropia (versione dell'8 marzo 2016)
  5. Primo Teorema di Shannon (versione del 15 marzo 2015)
  6. Codici di Huffman (versione del 15 marzo 2016)
  7. Disuguaglianza di Kraft-McMillan (versione del 31 marzo 2015)
  8. Derivati dell'entropia (versione del 23 marzo 2016)
  9. Simulazione di variabili casuali con lanci di monete
  10. Codifica di canale (versione del 6 aprile 2016)
  11. Proprietà di equipartizione asintotica (versione del 6 aprile 2016)
  12. Secondo Teorema di Shannon (versione del 12 aprile 2016)
  13. Conversa al Secondo Teorema di Shannon (versione del 16 aprile 2016)
  14. Teorema di Codifica Congiunta Sorgente-Canale (versione del 14 aprile 2014)
  15. Complessità di Kolmogorov (versione del 1 maggio 2016)
  16. Informazione e predizione (versione preliminare)
  17. Gestione di portafogli (versione del 6 maggio 2014)

Avvisi

Calendario lezioni:

Sfogliate le pagine del calendario e cliccate sulle date per trovare l'elenco degli argomenti svolti in ciascuna lezione.