Fornire un introduzione ad argomenti nell’intersezione tra probabilià, matematica discreta e informatica teorica, con particolare enfasi sui seguenti tre temi:
• Algoritmi aleatori e analisi del caso medio
• Grafi aleatori e processi stocastici su grafi: passeggiate aleatorie e modelli per la propagazione di infezioni/gossip/opinioni su reti sociali
• Tempi di arresto ottimali e prophet inequalities, con applicazioni alle aste combinatorie
• Algoritmi aleatori e analisi del caso medio
• Grafi aleatori e processi stocastici su grafi: passeggiate aleatorie e modelli per la propagazione di infezioni/gossip/opinioni su reti sociali
• Tempi di arresto ottimali e prophet inequalities, con applicazioni alle aste combinatorie
Curriculum
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
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
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
Modalità 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. 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
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
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
Modalità 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. 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
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
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
Modalità 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. 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
Fruizione: 20430033 METODI PROBABILISTICI E ALGORITMI ALEATORI in DATA SCIENCE LM-Data QUATTROPANI MATTEO
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
Modalità 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.