Mandatory course for the Master in Physics of Complex Systems, 1st year, 2nd term. The course introduces fundamental aspects of computation, including recursive computational tecniques such as dynamic programming and their application to optimization on graphs and networks, and the classification of problems into computational complexity classes. Important aspects of information theory and statistical inference are introduced, with applications to machine learning.

To become familiar with techniques for the exact solution of computational problems, including dynamic programming and recursion with emphasis on classical combinatorial optimization problems such as convolution ones, minimum weight paths, spanning trees and matchings and their generalizations. To learn the fundamental concepts of computational complexity theory, the techniques for analyzing the computation time of an algorithm, and some approximation techniques for NP-complete problems. To be able to apply practically such algorithms to complex statistical inference and machine learning problems. To be able to classify new problems into complexity classes.

Basics of probability theory and programming (any language)

Recursion and dynamic programming (20h) - Introduction to graph theory, Trees and data structures, Algorithms on graphs (20h) - Algorithmic complexity, polynomial reductions and NP-completeness (15h) - Information theory and statistical inference: maximum entropy, maximum likelihood and Boltzmann learning, Belief Propagation and inference on trees, Inference of Trees: Chow-Liu theorem, Expectation Propagation, Hidden Markov models (25h)

The course is divided into 60 hours of traditional lectures on the blackboard, plus 20 lab hours, on which the students are asked to implement (preferably individually or on groups of two at maximum) the algorithms described on the lecture and small variants. Problems will be proposed both during lectures and in the handouts. About 6 hours will be dedicated to problem solving in class.

- Course handouts - 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. - The nature of computation. C. Moore, S. Mertens. Oxford University Press, 2011 - Information, Physics and Computation, M. Mezard, A. Montanari, Oxford University Press, 2009. - Biological Sequence Analysis, Durbin, Eddy, Krogh, Mitchison, Cambridge University Press, 1998

Modalità di esame: Prova scritta (in aula); Prova orale facoltativa; Progetto individuale;

Exam: Written test; Optional oral exam; Individual project;

... The problem-solving ability of the student will be first evaluated through a written exam (lecture notes will be allowed during the exam). The final exam is oral and consists in 1-3 broad questions on the main topics of the lecture and will be developed as follows. The lecturer will select one topic from the ones covered on the course and the student will be given a short time (about 15 minutes) to review the topic from the notes or books. Afterwards, she/he will either explain the topic on the blackboard or on a blank page or answer to a more specific question by the lecturer. The final grade will be given by taking into account both the written and oral exams. Students that receive a good evaluation of the written exam can choose to replace the oral exam with an individual project on a topic that is closely related to the ones of the course, that has to be agreed upon with the lecturer. The project is to be presented as a short written report (5-10 pages). Feedback will be given after a first submission of the project (no evaluation will be done at this stage), and the project will be graded after a second final submission.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.