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

E' possibile sostenere l’esame in anticipo rispetto all’acquisizione della frequenza

Modalità di esame: Prova scritta (in aula); Prova orale obbligatoria;

Exam: Written test; Compulsory oral exam;

... The problem-solving ability of the student will be first evaluated through a written exam. The written exam consists in 3-4 problems on the topics of the course. The duration of the written exam is 3-4 hours. Lecture notes will be allowed during the written exam. The final exam is oral and consists in 2-4 broad questions on the main topics of the lecture and will be developed as follows. The lecturer will select the topics from the ones covered on the course and the student will be given a short time (about 15-20 minutes) to review them from the notes or books. Afterwards, the student will either explain the topics on the blackboard or on a blank page or answer to a more specific question by the lecturer. The scope of the exam is to ascertain the understanding of the theoretical topics, and the capacity of the student to generalize and apply them to a different settings. Topics that were satisfactorily solved on the written exam will be assumed to be known by the student and will be excluded from oral examination. The typical total duration of the oral exam varies between 1.5 and 2 hours. Students that receive a very good overall evaluation on 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. The final submission should happen at least one week before the intended exam date to accommodate time for review and grading.

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.