1. Presentazione del corso
2. Programma
3. Testi di riferimento
4. Dispense introduttive
5. Orari di lezione e ricevimento
6. Indice delle lezioni svolte
6. Modalità d'esame
7. Proposte di tesi (Statistiche di pattern )

PRESENTAZIONE DEL CORSO

Le catene di Markov e le loro proprietà ergodiche 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 in maniera semplice i concetti e i risultati principali riguardanti le catene di Markov e di presentare alcune applicazioni algoritmiche. Il corso è di 6 crediti e si divide in due parti. La prima comprende gli argomenti generali di base ed è 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. I contenuti di questa seconda parte potranno variare nei vari anni accademici e saranno presentati anche attraverso lezioni tenute da esperti del settore.

PROGRAMMA

• 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 omogenee. Classificazione degli stati. Classi ricorrenti e transienti. Metodi di simulazione.
• Catene di Markov irriducibili e aperiodiche. Tempi di prima entrata in uno stato. Distribuzione stazionaria. Proprietà di convergenza alla distribuzione stazionaria. Catene di Markov reversibili.
• Metodi Monte Carlo basati su catene di Markov. Campionatori di Gibbs e valutazione dei tempi di convergenza. Algoritmi di conteggio approssimato. Metodi di ottimizzazione e annealing simulato.
• Altre applicazioni: gli Hidden Markov Models, l’algoritmo di Pagerank, statistiche di pattern.

TESTI DI RIFERIMENTO

• Testo di base
  Olle Häggström, Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003.
  Di questo libro è disponibile in rete una versione preliminare in formato pdf o in formato ps.
• Altri libri classici utilizzati
  J. Kemeny, J. Snell, Finite Markov Chains, Van Nostrand, 1960.
  Marius Iosifescu, Finite Markov Processes and their Applications, John Wiley & Sons, 1980.
  Eugene Seneta, Non-negative Matrices and Markov Chains, Springer-Verlag, 1981.
• Testo in italiano
  Wolfgang Woess, Catene di Markov e teoria del potenziale nel discreto, Quaderni dell'U.M.I., Pitagora Editrice, 1996.
• Per gli argomenti riguardanti l'algoritmo di Pagerank, i principali riferimenti sono:
  Monica Bianchini, Marco Gori, Franco Scarselli, Inside PageRank, disponibile alla pagina web Inside PageRank,
  Amy N. Langville, Carl D. Meyer, Deeper Inside PageRank, disponibile alla pagina web Deeper Inside PageRank.

DISPENSE INTRODUTTIVE