Vai al contenuto principale
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:
Ultimo aggiornamento: 15/02/2018 13:49
Non cliccare qui!