- Oggetto:
- Oggetto:
Probabilità applicata e processi stocastici
- Oggetto:
Algorithms for optimization and statistical inference
- Oggetto:
Anno accademico 2016/2017
- Codice dell'attività didattica
- INT0744
- Docenti
- Prof. Riccardo Zecchina (Titolare del corso)
Prof. Alfredo Braunstein (Titolare del corso) - 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=01NWJPF&p_a_acc=2016
- 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.
- 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.- 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.
- 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 modelsTesti 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:
