CP450 - Metodi Probabilistici e Algoritmi Aleatori

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)

Un corso di probabilità elementare:
- Funzioni di distribuzione/densità di variabili aleatorie
- Variabili aleatorie notevoli: Bernoulliane, Binomiali, Poisson, Geoemetriche, Esponenziali, Gaussiane
- Valore atteso/varianza
- Legge debole dei grandi numeri

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

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 algorithms

Le lezioni saranno di tipo frontale, alla lavagna. Le lezioni verranno trasmesse in streaming e registrate per consentire agli/alle studenti lavoratori/lavoratrici di poterne usufruire in differita.

Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.

L'esame orale verterà sugli argomenti presentati a lezione.

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)

Un corso di probabilità elementare:
- Funzioni di distribuzione/densità di variabili aleatorie
- Variabili aleatorie notevoli: Bernoulliane, Binomiali, Poisson, Geoemetriche, Esponenziali, Gaussiane
- Valore atteso/varianza
- Legge debole dei grandi numeri

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

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 algorithms

Le lezioni saranno di tipo frontale, alla lavagna. Le lezioni verranno trasmesse in streaming e registrate per consentire agli/alle studenti lavoratori/lavoratrici di poterne usufruire in differita.

Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.

L'esame orale verterà sugli argomenti presentati a lezione.

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)

Un corso di probabilità elementare:
- Funzioni di distribuzione/densità di variabili aleatorie
- Variabili aleatorie notevoli: Bernoulliane, Binomiali, Poisson, Geoemetriche, Esponenziali, Gaussiane
- Valore atteso/varianza
- Legge debole dei grandi numeri

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

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 algorithms

Le lezioni saranno di tipo frontale, alla lavagna. Le lezioni verranno trasmesse in streaming e registrate per consentire agli/alle studenti lavoratori/lavoratrici di poterne usufruire in differita.

Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.

L'esame orale verterà sugli argomenti presentati a lezione.

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)

Un corso di probabilità elementare:
- Funzioni di distribuzione/densità di variabili aleatorie
- Variabili aleatorie notevoli: Bernoulliane, Binomiali, Poisson, Geoemetriche, Esponenziali, Gaussiane
- Valore atteso/varianza
- Legge debole dei grandi numeri

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

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 algorithms

Le lezioni saranno di tipo frontale, alla lavagna. Le lezioni verranno trasmesse in streaming e registrate per consentire agli/alle studenti lavoratori/lavoratrici di poterne usufruire in differita.

Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.

L'esame orale verterà sugli argomenti presentati a lezione.