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, cammini, connettività, cicli ed alberi.
- Algoritmi ricorsivi e strutture su grafo, componenti connesse, grafi
bipartiti.
- Cammini ottimali e medi, prodotto max-sum di matrici. Algoritmo di
Dijkstra e cammini casuali.
- Alberi ottimali e medi, algoritmi di Prim e Kruskal, teorema di Kirchoff.
- Automi finiti, espressioni regolari, macchine di Turing e classi di
complessità, riduzioni polinomiali.
- Euristiche e algoritmi approssimati per problemi NP-Hard.
- Algoritmi randomizzati.
- Ottimizzazione su strutture casuali.
- Introduzione alle catene di Markov e Markov Chain Monte Carlo.
- Inferenza statistica, massima verosimiglianza, entropia massima e
apprendimento di Boltzmann.
- Introduzione al machine learning.

"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 consiste in una prova scritta relativa alla prima meta' del programma e in una prova orale (della durata di 30 minuti) riguardante la seconda parte. Il punteggio finale e' dato dalla media ponderata dei due risultati.