Modelli stocastici Markoviani


Insegnamento complementare per i corsi di laurea magistrale di Informatica
e di Tecnologie dell'Informazione e della Comunicazione
Università degli Studi di Milano -- Anno accademico 2008/2009

Docente: M. Goldwurm




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


TESTI DI RIFERIMENTO


DISPENSE INTRODUTTIVE

  • È disponibile una dispensa introduttiva a cura del docente dedicata alle catene di Markov finite, corredata da richiami di Calcolo delle Probabilità e di Algebra Lineare.
    M. Goldwurm,
    Introduzione alle catene di Markov finite,
    Rapporto interno n. 321-08, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Maggio 2008.

    Il rapporto reperibile al sito file pdf

    MODALITÀ D'ESAME

    L'esame consiste in una prova orale sugli argomenti fondamentali presentati a lezione.
    Per sostenere l'esame è indispensabile iscriversi a terminale, e occorre concordare direttamente con il docente la data della prova (per e-mail).

    LEZIONI

    Il corso si svolge nel secondo semestre.

    Inizio delle lezioni il 2 Marzo 2009.

    Le lezioni si terranno in auletta 4, presso il D.S.I., via Comelico 39.


    ORARIO DI RICEVIMENTO

    Prof. Massimiliano Goldwurm, stanza P106 (primo piano), martedì ore 11-13, oppure su appuntamento (accordi per e-mail). Si avvisa che martedì 26 marzo 2013 il ricevimento studenti è spostato alle ore 15:30.


    Ultimo aggiornamento: 9 Aprile 2013