Insegnamento obbligatorio per la Laurea Magistrale in Physics of Complex Systems, collocato al II pd del I anno. In questo insegnamento vengono introdotti alcuni aspetti della teoria dell'informazione culturalmente affini alla fisica statistica, il cui studio viene parallelamente approfondito nell'insegnamento Statistical Physics and Biophysics. L'insegnamento conduce allo sviluppo di algoritmi approssimati per problemi NP-completi che presentano transizioni di fase nella complessità computazionale, problema analogo allo sviluppo di metodi approssimati per lo studio di modelli della meccanica statistica che presentano transizioni di fase.

Lo studente deve apprendere i concetti fondamentali della teoria della complessità, le tecniche per l'analisi della complessità computazionale di un algoritmo e i principali algoritmi approssimati per problemi NP-completi. Deve inoltre imparare ad applicare tali algoritmi a problemi di inferenza statistica e di ottimizzazione combinatoria.

Nessuno.

- Ricorsione e programmazione dinamica.
- Introduzione alla teoria dei grafi.
- Strutture dati ed alberi.
- Algoritmi su grafi.
- Teoria della complessità ed NP-completezza.
- Teoria dell'informazione e inferenza statistica: massima entropia, massima verosimiglianza e ricostruzione di reti.
- Belief Propagation.
- Inferenza ed ottimizzazione su alberi: teorema di Chow-Liu
- Hidden Markov Models.

"Introduction to Algorithms", T.H. Cormen, C.E. Leiserson, R.L. Rivest, MIT Press, 2000.
"Elements of the theory of computation", R. Lewis and C. H. Papadimitriou. Prentice-Hall.
"Computer and Intractability. A Guide to NP-Completeness". M. R. Garey and D. S. Johnson. Publisher W. H. Freeman, 1979.
"Information Theory, Inference, and Learning Algorithms", D. J. C. MacKay, Cambridge University Press, 2003.
"Information, Physics and Computation", M. Mezard, A. Montanari, Oxford University Press, 2009.
“Biological Sequence Analysis”, Durbin, Eddy, Krogh, Mitchison, Cambridge University Press, 1998

L'esame consiste in una prova orale riguardante il contenuto del programma o, in alternativa, in un progetto su un tema legato ad alcuni degli argomenti trattati nel corso, concordato con il docente e svolto individualmente dallo studente.