Processi stocastici


Insegnamento per il corso di laurea magistrale di Informatica
Dipartimento di Informatica
Università degli Studi di Milano
Anno accademico 2013/2014

Docente: M. Goldwurm




1. Presentazione del corso
2. Programma
3. Testi di riferimento
4. Dispense introduttive
5. Modalità d'esame
6. Appelli per l'a.a. 2015/2016
7. Orari di lezione e ricevimento


PRESENTAZIONE DEL CORSO

Questo corso è principalmente dedicato alle catene di Markov e alle loro applicazioni algoritmiche. Ricordiamo che le catene di Markov sono utilizzate nella progettazione e nell'analisi di numerosi algoritmi di ottimizzazione e conteggio per svariati problemi. Esempi classici sono quelli dell'annealing simulato e dei metodi di apprendimento con rinforzo, ma numerose sono le applicazioni recenti che riguardano algoritmi di approssimazione per problemi difficili. Inoltre, i modelli stocastici di tipo Markoviano, ottenuti come varianti o estensioni delle catene di Markov, sono utilizzati in numerose aree di ricerca, per esempio in biologia computazionale e in particolare nelle analisi statistiche di sequenze di DNA, nello sviluppo di strumenti per il riconoscimento di segnali vocali (Hidden Markov Models) e nella progettazione di algoritmi di esplorazione della rete web (Pagerank).
L'obiettivo del corso è quello di introdurre i risultati principali riguardanti le catene di Markov e di presentare alcune applicazioni algoritmiche. Il corso è di sei crediti e si divide in due parti principali. La prima è dedicata alle catene di Markov finite e alle loro proprietà ergodiche. La seconda parte riguarda invece applicazioni specifiche, principalmente dedicate agli algoritmi Monte Carlo basati su passeggiate a caso in catene di Markov ergodiche.


PROGRAMMA

Richiami di calcolo delle probabilità. Variabili aleatorie, distribuzione, momenti e loro funzione generatrice. Variabili discrete e continue: bernoulliane, binomiali, geometriche, normali, esponenziali, Poissoniane. Generalità sui processi stocastici discreti e continui. Processi di Poisson: ipotesi di stazionarietà, assenza di memoria, ordinarietà; derivazione della distribuzione delle variabili; tempi di attesa; distribuzione dei tempi di occorrenza degli eventi condizionati al loro numero.
Matrici non negative. Matrici irriducibili e primitive. La nozione di periodo nelle matrici irriducibili. Il teorema di Perron-Frobenius. La decomposizione triangolare a blocchi. Matrici e vettori stocastici. Catene di Markov finite e omogenee. Classificazione degli stati. Classi ricorrenti e transienti. Catene di Markov irriducibili e aperiodiche. Tempi di prima entrata in uno stato. Distribuzione stazionaria. Proprietà di convergenza alla distribuzione stazionaria (ergodicità). Catene di Markov reversibili. Esempi di passeggiate a caso su grafi.
Generazione casuale non uniforme. Procedure di simulazione di catene di Markov. Metodi Monte Carlo basati su catene di Markov. Campionatori di Gibbs: generazione casuale di insiemi indipendenti o di colorazioni di un grafo. L'algoritmo di Metropolis. Analisi della velocità di convergenza alla distribuzione stazionaria: il caso generale e l'esempio della generazione casuale di colorazioni di grafi. Algoritmi di conteggio approssimato mediante catene di Markov: calcolo del numero di colorazioni di un grafo. Metodi di ottimizzazione e annealing simulato.

TESTI DI RIFERIMENTO


DISPENSE

Sono disponibili due dispense a cura del docente, la prima dedicata alle catene di Markov finite, corredata da richiami di Calcolo delle Probabilità e di Algebra Lineare, mentre la seconda riguarda alcune applicazioni algoritmiche.

MODALITÀ D'ESAME

L'esame consiste in una prova orale sugli argomenti presentati a lezione.
Si ricorda che per sostenere l'esame è indispensabile iscriversi a terminale all'appello prescelto, dopo aver compilato il modulo on-line di valutazione della didattica relativa al presente corso.

APPELLI D'ESAME PER L'A.A. 2015/2016

Gli appelli per l'anno accademico 2015/2016 si svolgeranno secondo il calendario riportato nel sito del Collegio didattico di Informatica (pagina degli avvisi). In ogni appello l'esame consiste in una prova orale, la data e l'ora effettive vanno concordate con il docente per posta elettronica e saranno successive alla data che compare sul SIFA. Attualmente le date ufficiali (2016) sono: 21 aprile, 24 giugno, 28 luglio, 23 settembre. La chiusura delle iscrizioni avviene circa una settimana prima della data SIFA, mentre l'apertura avviene almeno un mese prima della stessa.

LEZIONI

Il corso attualmente non si tiene. È stato sostituito dal corso di "Metodi probabilistici per l'Informatica".


ORARIO DI RICEVIMENTO

Prof. Massimiliano Goldwurm, presso il Dip. di Matematica, via Saldini 50 (ufficio del docente al secondo piano), martedì ore 14:30-17:30, oppure su appuntamento (accordi per e-mail).


Ultimo aggiornamento: 27 Febbraio 2016