Vai al contenuto principale
Oggetto:
Oggetto:

Probabilità statistica e processi stocastici

Oggetto:

Algorithms for optimization, inference and learning

Oggetto:

Anno accademico 2019/2020

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
Secondo periodo didattico Terzo periodo didattico
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:
Ultimo aggiornamento: 18/06/2019 15:22
Location: https://fisica-sc.campusnet.unito.it/robots.html
Non cliccare qui!