Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2017/18
01NWJPF, 01NWJNG
Algorithms for optimization and statistical inference
Corso di Laurea Magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi) - Torino/Trieste/Parigi
Corso di Laurea Magistrale in Ingegneria Matematica - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Braunstein Alfredo   A2 FIS/02 45 0 15 0 5
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/05 6 B - Caratterizzanti Discipline ingegneristiche
Presentazione
Corso obbligatorio nel Master "Physics of Complex Systems", nel secondo semestre del primo anno. Il corso introduce aspetti fondamentali della computazione, includendo tecniche ricorsive quali la programmazione dinamica per l’ottimizzazione discreta in grafi e reti e la definizione delle classi di complessità computazionale. Sono introdotti alcuni aspetti di teoria dell’informazione e dell’inferenza statistica con applicazioni al machine learning.
Risultati di apprendimento attesi
Acquisire familiarità con soluzioni esatte classiche a problemi computazionali, compresa la ricorsione e programmazione lineare, con enfasi in problemi combinatori classici di soluzione ricorsiva quali problemi di convoluzione, così come cammini, alberi e assegnazioni di peso minimo e generalizzazioni.
Imparare i concetti fondamentali della teoria della complessità, le tecniche per analizzare il tempo di calcolo di un algoritmo, ed alcune tecniche di approssimazione.
Essere in grado di classificare problemi combinatori nelle classi di complessità.
Essere in grado di applicare le tecniche algoritmiche a problemi complessi di inferenza statistica e machine learning.
Prerequisiti / Conoscenze pregresse
Conoscenze basiche di probabilità e programmazione (qualunque linguaggio)
Programma
- Ricorsione e programmazione dinamica
- Introduzione alla teoria dei grafi
- Alberi e strutture di dati
- Algoritmi su grafi
- Complessità computazionale, riduzioni polinomiali e NP-completezza
- Teoria dell’informazione e inferenza statistica, massima entropia, massima verosimiglianza e apprendimento di Boltzmann
- Belief Propagation e inferenza su alberi
- Inferenza di alberi: teorema di Chow-Liu
- Hidden Markov models
Organizzazione dell'insegnamento
Il corso è diviso in 45 ore di lezioni alla lavagna, più 15 ore di esercitazioni di laboratorio informatico in cui gli studenti devono implementare gli algoritmi descritti a lezione ed alcune delle sue varianti. Per la soluzione numerica sarà utilizzato python (di cui una breve descrizione sarà data all’inizio del corso). Saranno proposti problemi ed esercizi sia durante le lezioni che nelle note. Saranno dedicate circa sei ore alla risoluzione di problemi in aula.
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
- Note del corso
- 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.
- The nature of computation. C. Moore, S. Mertens. Oxford University Press, 2011
- Information, Physics and Computation, M. Mezard, A. Montanari, Oxford University Press, 2009. - Biological Sequence Analysis, Durbin, Eddy, Krogh, Mitchison, Cambridge University Press, 1998
Criteri, regole e procedure per l'esame
L’abilità degli studenti nella risoluzione di problemi ed esercizi sarà valutata con un esame scritto (le note del corso saranno consultabili durante l’esame). L’esame finale è orale e consiste in una o due domande sui principali argomenti del corso, e si svolgerà come segue. Il docente individuerà un argomento e darà allo studente un breve intervallo di tempo per per rivederlo dalle note o libri. Successivamente, lo studente dovrà spiegarlo alla lavagna o su un foglio. I studenti che ricevono una buona valutazione nel esame scritto possono sostituire l’esame orale con un progetto da svolgere individualmente su un argomento vicino a quelli del corso concordato con il docente. Il progetto deve essere presentato nella forma di una breve relazione (5-10 pagine).
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2017/18
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti