Il corso si propone di fornire gli elementi di base sulla connessione tra i metodi di fisica statistica e i problemi piu' importanti di teoria dell'informazione. Tale connessione verra' resa esplicita con la discussione di esempi presi da tipici problemi di ottimizzazione combinatoria quali il number partitioning problem o il minimum spanning tree, cosi' che gli studenti possano vedere gli algoritmi usati per affrontarli e la corrispettiva trattazione basata sui metodi di fisica statistica.

- Conoscenza e capacità di comprensione: Acquisire la conoscenza dei
concetti fondamentali della fisica statistica e delle tecniche con cui possono essere applicati a problemi di teoria dell'informazione e di ottimizzazione combinatoria.

- Conoscenza e capacità di comprensione applicate: Acquisire la capacità
di comprendere in modo critico le applicazioni della fisica statistica alla teoria dell'informazione e le loro interconnessioni.

- Autonomia di giudizio:
Rendere lo studente capace di applicare i concetti e gli strumenti appresi in modo critico, controllando la coerenza logica delle argomentazioni proposte.

- Abilità comunicativa: Rendere lo studente capace di spiegare le conoscenze apprese e capace di trasmetterle ad altri; di saper inquadrare un problema specifico in un contesto più ampio.

- Capacità di apprendere: Rendere lo studente capace di apprendere in modo critico concetti e strumenti di risoluzione.

Elementi di base di analisi e algebra lineare.

1) Variabili random ed entropia 2) Variabili correlate 3) Trasmissione e compressione di dati 4) Nozioni di base di ottimizazione combinatoriale e reminder su complessita' computazionale 5) La distribizione di Boltzmann 6) Cenni sui modelli di meccanica statistica rilevanti per i problemi di ottimizzazione combinatoria e di coding 7) Cenni di large deviations per variabili indipendenti 8) Il random energy model e il random code ensemble 9) Number partitioning e sua trattazione con metodi di fisica statistica 10) Cenni di belief propagation

M. Mezard and A. Montanari: Information, Physics and Computation

Variabili random, entropia e sequenze di variabili random

Variabili correlate e loro studio attraverso l'entropia

Nozioni di teoria della probabilita': somma di variabili i.i.d. e connessione con il teorema del limite centrale

Nozioni fondamentali di teoria dell'informazione: codici, canali e teoremi di Shannon

Nozioni di fisica statistica dei sistemi
di spin e loro connessione con i problemi trattati nella prima parte del corso

Discussione di esempi specifici (variabili di Ising, uno/due spin, catene, campo medio)

Problemi di ottimizzazione combinatoriale: esempi e loro complessita' computazionale

Large deviations e teorema di fluttuazione-dissipazione

Definizione e termodinamica del random energy model - sua applicazione ai problemi di coding

Number partitioning problem - studio del modello di fisica statistica associato

Metodo del belief propagation - belief propagation su trees

Lezioni alla lavagna/tablet - esercizi - semplici simulazioni numeriche.

Esame scritto ed orale. Il voto finale tiene conto della capacità di risolvere correttamente e discutere chiaramente gli esercizi e gli argomenti proposti. La prova scritta consiste nello svolgimento di esercizi sulla parte di Teoria della Probabilita', Fisica Statistica, Teoria dell'Informazione e Ottimizzazione Combinatoria. La prova scritta è composta di 4 esercizi suddivisi in 3 o 4 punti da svolgere commentando i risultati ottenuti. A ciascun esercizio è assegnato un punteggio da 8 a 10. Il punteggio massimo per un esercizio è assegnato allo svolgimento corretto e chiaramente esposto dell'esercizio. Il voto dello scritto è pari alla somma dei voti conseguiti nei singoli esercizi. Lo studente è ammesso all'esame orale se ha ottenuto allo scritto almeno il punteggio minimo di 18. L'esame orale è focalizzato sulla parte di fisica statistica e le sue applicazioni alla teoria dell'informazione. Le domande vertono sulla definizione dei concetti di base e sulla comprensione ragionata dei concetti studiati. All'esame orale viene assegnato un punteggio in trentesimi (indipendente dal punteggio conseguito nell'esame scritto). Il voto finale media il voto conseguito alla scritto con la valutazione riportata nell'esame orale (che deve essere almeno di 18/30).

9 - Industria, innovazione e infrastrutture