- Oggetto:
- Oggetto:
Probabilità applicata e processi stocastici
- Oggetto:
Algorithms for optimization and statistical inference
- Oggetto:
Anno accademico 2017/2018
- Codice dell'attività didattica
- INT0744
- Docente
- Prof. Alfredo Braunstein
- Corso di studi
- Laurea Magistrale Interateneo in Fisica dei sistemi complessi
- Anno
- 2° anno
- Tipologia
- C=Affine o integrativo
- Crediti/Valenza
- 6
- SSD dell'attività didattica
- MAT/07 - fisica matematica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Orale
- Prerequisiti
-
- Propedeutico a
-
- Mutuato da
- https://didattica.polito.it/pls/portal30/sviluppo.guide.visualizza?p_cod_ins=01NWJNG&p_a_acc=2018
- 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 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.
Mandatory teaching for the Master Degree in Physics of Complex Systems, planned for the II Educational Period of the I year. During this course some aspects of the information theory culturally related to Statistical Mechanics are introduced, whose study is elaborated in parallel in the course Statistical Physics and Biophysics. The course leads to the development of approximate algorithm for NP-complete problems, which present phase transitions in computational complexity, issue which is similar to the development of approximate methods for studying models of Statistical Mechanics which present phase transitions.
- 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 45 ore più esercitazioni svolte in aula per un totale di 15 ore.
The course consists of theoretical lessons (up to 45 hours) plus practice exercises discussed at class (up to 15 hours).
- Oggetto:
Modalità di verifica dell'apprendimento
L'esame consiste in una prova orale riguardante il contenuto del programma o, in alternativa, in un progetto su un tema legato ad alcuni degli argomenti trattati nel corso, concordato con il docente e svolto individualmente dallo studente.
The final exam can be chosen as either an oral exam on the contents of the course or, alternatively, an individual written project on a topic, closely related to the ones of the course, that has to be agreed upon with the lecturer.
- Oggetto:
Attività di supporto
- 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 Assessment and grading criteria
- "Biological Sequence Analysis", Durbin, Eddy, Krogh, Mitchison, Cambridge University Press, 1998
- Oggetto:
Note
- Oggetto: