15 April - 21 April

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

• Πιθανοτικοί αλγόριθμοι, ο αλγόριθμος του Karger για το πρόβλημα της Ελάχιστης Τομής, balls and bins, coupons collector, πιθανοτικός αλγόριθμος για το πρόβλημα 2-SAT (δείτε ακόμη και αυτές τις διαφάνειες για το 2-SAT). 

• R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (κεφάλαιο 1 και ενότητες 10.2, 3.1 και 3.6). 
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (κεφάλαια 1 και 2, και ενότητα 7.1). 
• Δείτε ακόμη τον αλγόριθμο Miller-Rabin για τον έλεγχο πρώτων αριθμών. 

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

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