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.

Introduzione alla teoria dei grafi.
Algoritmi su grafi.
Analisi, nel caso medio, di semplici algoritmi.
Strutture dati e alberi.
Ricerca combinatoria: backtracking e programmazione dinamica.
Algoritmi probabilistici e ricerca aleatoria.
Teoria della complessità ed NP-completezza.
Trattare la NP-completezza: euristiche (algoritmi approssimati, branch-and-bound e backtracking, ricerca locale e simulated annealing).
Teoria dell'informazione e inferenza statistica: massima verosimiglianza, clustering e ricostruzione di una rete.
Strutture aleatorie: famiglie di grafi o reti aleatorie e teoria della percolazione.
Ottimizzazione e inferenza statistica su strutture aleatorie: complessità del caso tipico e transizioni di fase.
Algoritmi di ottimizzazione e inferenza statistica in biologia computazionale.

"Introduction to Algorithms", T.H. Cormen, C.E. Leiserson, R.L. Rivest, MIT Press, (2000).
Concrete Mathematics, R.L. Graham, D. E. Knuth, and O. Patashnik, Addison-Wesley, 1994.
Computational Complexity, C.H. Papadimitriou, Addison Wesley (1994).
Combinatorial optimization: algorithms and complexity (Prentice-Hall 1982, C.H. Papadimitriou, K. Steiglitz; second edition by Dover, 1998).
M. R. Garey and D. S. Johnson. Computer and Intractability. A Guide to NP-Completeness. W. H. Freeman, 1979.
Randomized Algorithms, R. Motwani, P.Raghavan, Cambridge University Press (1995).
Information Theory, Inference, and Learning Algorithms, D.J.C. MacKay, Cambridge University Press, 2003.
M. Mezard, A. Montanari, Information, Physics and Computation, Oxford Un. Press, 2009.
Jones, Neil, and Pavel Pevzner. An Introduction to Bioinformatics Algorithms. Cambridge, MA: MIT Press, 2004.

L'esame consisterà in una prova orale sul programma del corso, o in alternativa nella discussione di un approfondimento svolto dallo studente su un argomento inerente il programma.