Matematica
Cod 198373
- Laurea magistrale
- 2 anni
- 120 CFU
- LM-40 R
MAT/06
CP450 - Metodi Probabilistici e Algoritmi Aleatori
Codice: 20410556
Scheda insegnamento
- Anno Accademico di erogazione
- 2026/2027
- Corso di studi
- Scienze Computazionali
- Periodo di erogazione
- Secondo semestre
- CFU
- 6 CFU
- Lingua
- Italiano
- SSD
- MAT/06
Scopri il programma didattico
Programma, testi adottati e modalità d’esame sono quelli pubblicati dai docenti per l’anno accademico 2026/2027. L’insegnamento è diviso in canali: ogni canale ha il suo programma.
- Docente
- Matteo Quattropani
- Curriculum
- Crittografia e sicurezza informatica
- Anno di corso
- 1
- Periodo
- Secondo semestre
- Ore
- 60
- CUIN
- 260008582
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)
Prerequisiti
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
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 algorithms
Modalità di erogazione
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.
Modalità di frequenza
Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.
Modalità di valutazione
L'esame orale verterà sugli argomenti presentati a lezione.
Prove previste
- Prova orale
- Docente
- Matteo Quattropani
- Curriculum
- Modellistica fisica e simulazioni numeriche
- Anno di corso
- 1
- Periodo
- Secondo semestre
- Ore
- 60
- CUIN
- 260008637
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)
Prerequisiti
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
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 algorithms
Modalità di erogazione
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.
Modalità di frequenza
Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.
Modalità di valutazione
L'esame orale verterà sugli argomenti presentati a lezione.
Prove previste
- Prova orale
- Docente
- Matteo Quattropani
- Curriculum
- Analisi dei dati e statistica
- Anno di corso
- 1
- Periodo
- Secondo semestre
- Ore
- 60
- CUIN
- 260008692
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)
Prerequisiti
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
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 algorithms
Modalità di erogazione
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.
Modalità di frequenza
Le lezioni si terranno 3 volte a settimana, per due ore ciascuna (per un totale di 30 lezioni). La frequenza non è obbligatoria.
Modalità di valutazione
L'esame orale verterà sugli argomenti presentati a lezione.
Prove previste
- Prova orale
Esplora gli obiettivi dell’insegnamento
Ambito disciplinare: Formazione matematica modellistico-computazionale avanzata
Per questo insegnamento non sono pubblicati obiettivi formativi.
Informazioni utili
Per questo insegnamento non sono pubblicate informazioni aggiuntive. Materiale didattico e documenti si trovano sulla piattaforma del corso.