19 April - 25 April

Διάλεξη 21/4: Πιθανοτικοί Αλγόριθμοι ΙI

• Πιθανοτικοί αλγόριθμοι: πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problem, (δείτε ακόμη εδώ για secretary problems), Lovasz Local Lemma και εφαρμογή στην ικανοποιησιμότητα k-SAT, Chernoff-Hoeffding bounds, set balancing. 

• R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (ενότητες 4.1, 5.5, 6.1, 6.2 και 6.3). 
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (Ενότητες 3.1-3.3, 4.1-4.5, 6.7 και 7.1). 

• Thomas S. Ferguson. Who Solved the Secretary Problem? Statist. Sci. 4(3): 282-289, 1989.

Βίντεο της διάλεξης 

(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).