RANDOMIZED METHODS IN COMPUTER SCIENCE

Anno accademico
2023/2024 Programmi anni precedenti
Titolo corso in inglese
RANDOMIZED METHODS IN COMPUTER SCIENCE
Codice insegnamento
PHD189-2 (AF:497968 AR:279260)
Modalità
In presenza
Crediti formativi universitari
4
Livello laurea
Corso di Dottorato (D.M.45)
Settore scientifico disciplinare
INF/01
Periodo
Annuale
Anno corso
1
Sede
VENEZIA
Spazio Moodle
Link allo spazio del corso
Il concetto di casualità è una parte essenziale del design degli algoritmi moderni. Informalmente, la casualità equivale a scegliere una tra un insieme predefinito di opzioni lanciando una moneta. In questo corso mostreremo come la casualità sia presente nella ricerca sugli algoritmi in due modi diversi: (1) nel design degli algoritmi stessi e (2) nelle loro analisi. Il primo consiste nel permettere all'algoritmo di scegliere probabilisticamente tra più opzioni durante la sua esecuzione. Qui mostriamo, attraverso esempi classici, come tale facoltà possa portare a prestazioni migliori rispetto a scelte esclusivamente deterministiche. Il secondo aspetto riguarda l'analisi degli algoritmi su input soggetti a casualità, ossia input che seguono una certa distribuzione. In questo caso, vedremo come fornire affermazioni rigorose riguardo al comportamento di un algoritmo su tali input, cioè daremo garanzie probabilistiche (ad esempio, garanzie che valgono in aspettativa o con alta probabilità). A sua volta, questo ci aiuterà a comprendere meglio la complessità dei problemi che questi algoritmi stanno risolvendo.
Alla fine del corso, lo studente sarà in grado di:
1) comprendere gli approcci classici per incorporare la casualità nel design degli algoritmi,
2) eseguire analisi probabilistiche di algoritmi in contesti non deterministici.
conoscenze base di:
- algoritmi e strutture dati
- teoria della probabilità
Revisione dei fondamenti della teoria della probabilità,
Coupon Collector e Contention Resolution,
Principio di Yao e il Secretary Problem,
Dimostrazione probabilistica,
Alcuni algoritmi classici randomizzati: Min-Cut, Test di identità polinomiale e Quicksort,
Chernoff bound e Load Balancing,
Rete casuale,
Smoothed Analysis
Mitzenmacher, Michael, and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Completare con successo le quattro schede di esercizi che verranno consegnate nel periodo delle lezioni.
Didattica frontale, lavagna.
Inglese
scritto
Il programma è ancora provvisorio e potrà subire modifiche.
Data ultima modifica programma: 25/08/2023