- Oggetto:
- Oggetto:
Probabilità statistica e processi stocastici
- Oggetto:
Algorithms for optimization, inference and learning
- Oggetto:
Anno accademico 2020/2021
- Codice dell'attività didattica
- FIS0116
- Docente
- Prof. Alfredo Braunstein
- Corso di studi
- Laurea Magistrale Interateneo in Fisica dei sistemi complessi
- Anno
- 2° anno
- Periodo didattico
- Da definire
- Tipologia
- C=Affine o integrativo
- Crediti/Valenza
- 8
- SSD dell'attività didattica
- MAT/07 - fisica matematica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Inglese
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Orale
- Prerequisiti
-
Elementi basici di teoria della probabilità e programmazione (qualunque linguaggio)
Basics of probability theory and programming (any language) - Propedeutico a
-
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
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 fondamentali dalla computazione, comprese tecniche ricorsive quali la programmazione dinamica e le loro applicazioni all'inferenza ed ottimizzazione in grafi e network, e la classificazione di problemi rilevanti alla fisica in classi di complessità computazionale. Sono introdotti inoltre alcuni importanti aspetti di teoria dell'informazione ed inferenza statistica, con applicazioni al machine learning.
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.
- Oggetto:
Risultati dell'apprendimento attesi
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.
The student must learn the fundamental concepts of the complexity theory, the techniques for analyse computational complexity of an algorithm and the main approximate algorithms for NP-complete problems. He has also to learn how to apply these algorithms to problems of statistical interference and combinatoric optimization.
- Oggetto:
Modalità di insegnamento
L'insegnamento consiste di lezioni teoriche per un totale di 60 ore più esercitazioni svolte in aula per un totale di 20 ore.
The course consists of theoretical lessons (up to 60 hours) plus practice exercises discussed at class (up to 20 hours).
- Oggetto:
Modalità di verifica dell'apprendimento
Esame: prova scrita; optional oral exam; individual project;
Le abilità degli studenti nel risolvere problemi saranno prima valutate attraverso una prova scritta (libri e note del corso sono ammesse durante la prova). L'esame finale è orale e consiste in 1-3 domande generali sui temi principali del corso, e saranno svolte come segue: il docente scegliera un argomento e sarà dato tempo allo studente un breve tempo (all'incirca 15 minuti) per rivederlo da libri o note. Successivamente, spiegherà l'argomento al docente oppure risponderà a domande più specifiche. Il voto finale terrà conto sia dalla prova scritta che dell'esame orale. Gli studenti che hanno ricevuto una buona valutazione nella prova scritta potranno scegliere di sostituire l'esame orale con un progetto individuale con tema vicino a quelli del corso e concordato con il docente. Il progetto deve essere consegnato nella forma di una breve relazione (5-10 pagine). La relazione sarà commentata inizialmente dal docente alla prima sottomissione (senza valutazione), e sarà valutata alla seconda sottomissione.
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.- Oggetto:
Attività di supporto
Si terranno esercitazioni in laboratorio informatico per la programmazione concreta dei concetti spiegati a lezione (approssimatamente 20 ore).
The course includes tutorial lessons in the lab for the concrete programming implementation of the concepts explained in class (about 20h).
- Oggetto:
Programma
- Ricorsione e programmazione dinamica.- Introduzione alla teoria dei grafi.
- Strutture dati ed alberi.
- Algoritmi su grafi.
- Teoria della complessità ed NP-completezza.
- Teoria dell'informazione e inferenza statistica: massima entropia, massima verosimiglianza e ricostruzione di reti.
- Belief Propagation.
- Inferenza ed ottimizzazione su alberi: teorema di Chow-Liu
- Hidden Markov Models.
- Recursion and dynamic programming.- Introduction to graph theory.
- Trees and data structures.
- Algorithms on trees.
- Algorithmic complexity, polynomial reductions and NP-completeness.
- Information theory and statistical inference: maximum entropy, maximum likelihood and Boltzmann learning.
- Belief Propagation and inference on trees.
- Inference of Trees: Chow-Liu theorem.
- Hidden Markov models.
Testi consigliati e bibliografia
- Oggetto:
Texts, readings, handouts and other learning resources:
- "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.
- "Information, Physics and Computation", M. Mezard, A. Montanari, Oxford University Press, 2009.
- "Biological Sequence Analysis", Durbin, Eddy, Krogh, Mitchison, Cambridge University Press, 1998
- Oggetto:
Orario lezioni
Nota: II semestre
- Oggetto:
Note
Il corso è mutuato da
Algorithms for optimization, inference and learning
Corso di Laurea Magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi) - Torino/Trieste/Parigi
Corso di Laurea Magistrale in Ingegneria Matematica - Torino- Oggetto:
