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 orale obbligatoria; Prova scritta su carta con videosorveglianza dei docenti; Elaborato progettuale individuale;

- The problem-solving ability of the student will be first evaluated through a written exam (online -- with webcam surveillance). 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 (printed or hand-taken) and physical books - 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.

Modalità di esame: Prova scritta (in aula); Prova orale obbligatoria; Prova scritta su carta con videosorveglianza dei docenti; Elaborato progettuale in gruppo;

- The problem-solving ability of the student will be first evaluated through a written exam (online -- with webcam surveillance). 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 (printed or hand-taken) and physical books are 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.