12 April - 18 April
Section outline
-
Διάλεξη 14/4: Πιθανοτικοί Αλγόριθμοι Ι
- Πιθανοτικοί αλγόριθμοι, ο αλγόριθμος του Karger για το πρόβλημα της Ελάχιστης Τομής, balls and bins, coupons collector, η πιθανοτική μέθοδος (απλά παραδείγματα εφαρμογής σε max-cut και maximum independent set).
Προτεινόμενη μελέτη:- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (κεφάλαιο 1 και ενότητες 10.2, 3.1, 3.2, 3.6, 5.1 και 5.2).
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (κεφάλαια 1 και 2, και ενότητες 3.1-3.3, 6.1, 6.2 και 6.4).
Προτάσεις για περαιτέρω μελέτη:- Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK (6th edition). Springer, 2018.
- Noga Alon Joel and H. Spencer. The Probabilistic Method. Wiley, 2008. Παλαιότερη έκδοση.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).