Section outline

  • 11/5

    Πιθανοτικοί αλγόριθμοι:

    • Πρόβλημα ελάχιστης τομής (mincut - αλγόριθμος του Karger) [MU, 1.5].
    • Πρόβλημα μέγιστης τομής (maxcut - πιθανοτική μέθοδος και derandomization) [MU, 6.2 & 6.3].
    • Αλγόριθμοι Las Vegas και Monte Carlo (MU, σελ. 62).
    • Πιθανοτικό πρωτόκολλο για έλεγχο ισότητας συμβολοσειρών. [R. Karp: Introduction to Randomized Algorithms, Section 5]


    MU: Mitzenmacher-Upfal, 2nd edition

    Δείτε και: https://www.cs.ox.ac.uk/people/elias.koutsoupias/pc2016-17/lectures.pdf (2.2, 3.2)