Fornire un’introduzione ad argomenti all’intersezione tra probabilità, matematica discreta e informatica teorica. Il focus del corso sarà sia sui metodi matematici necessari all’analisi degli algoritmi, che su modelli ed esempi ispirati da problemi di natura informatica e combinatoria.
scheda docente materiale didattico
- Metodo probabilistico (metodo del momento primo e del momento secondo, lemma locale di Lovasz)
- Stime di concentrazione (es. disuguaglianze di Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid)
- Pairwise independence
- Martingale (introduzione, cf. CP410)
- Catene di Markov (introduzione, cf. CP420)
Modelli ed esempi:
- Algoritmi aleatori e analisi del caso medio (es. quicksort, routing su reti sparse, Johnson-Linderstrauss, balls-into-bins, funzioni di Hashing, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Grafi aleatori (es. Erdos-Reyni e preferential attachment)
- Passeggiate aleatorie su grafi (es. PageRank, cover times, algoritmo di Wilson)
- Sistemi stocastici multi-agente (es. contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
Alla fine di ogni lezione saranno condivisi con gli studenti gli appunti relativi
Programma
Metodi:- Metodo probabilistico (metodo del momento primo e del momento secondo, lemma locale di Lovasz)
- Stime di concentrazione (es. disuguaglianze di Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid)
- Pairwise independence
- Martingale (introduzione, cf. CP410)
- Catene di Markov (introduzione, cf. CP420)
Modelli ed esempi:
- Algoritmi aleatori e analisi del caso medio (es. quicksort, routing su reti sparse, Johnson-Linderstrauss, balls-into-bins, funzioni di Hashing, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Grafi aleatori (es. Erdos-Reyni e preferential attachment)
- Passeggiate aleatorie su grafi (es. PageRank, cover times, algoritmo di Wilson)
- Sistemi stocastici multi-agente (es. contact process, voter model)
Testi Adottati
Le lezioni saranno tratte principalmente da questi testi:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
Alla fine di ogni lezione saranno condivisi con gli studenti gli appunti relativi
Bibliografia Di Riferimento
Altri libri di riferimento: - David Levin e Yuval Peres, Markov chains and mixing times - Rajev Motwani e Prabhakar Raghavan, Randomized algorithms - Devdatt Dubhashi e Alessandro Panconesi, Concetration of measure for the analysis of randomized algorithmsModalità Frequenza
Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.Modalità Valutazione
L'esame orale verterà sugli argomenti presentati a lezione.