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

Στην θεωρητική πληροφορική, ένας **πιθανοτικός αλγόριθμος** (ή **τυχαιοποιημένος** ή **τυχαίος αλγόριθμος**) είναι ένας αλγόριθμος που χρησιμοποιεί τυχαιότητα ως μέρος της λογικής του ή της διαδικασίας του. Ο αλγόριθμος παίρνει ομοιόμορφα τυχαία bits ως βοηθητική είσοδο τα οποία χρησιμοποιεί για να καθοδηγήσει την εκτέλεσή του, με στόχο να επιτύχει καλή απόδοση στη "μέση περίπτωση" (όπως αυτή ορίζεται σε σχέση με τα τυχαία bits). Επομένως είτε ο χρόνος εκτέλεσης είτε η έξοδος (ή και τα δύο) είναι τυχαίες μεταβλητές.

Οι πιθανοτικοί αλγόριθμοι διακρίνονται σε αυτούς που πάντοτε τερματίζουν με τη σωστή απάντηση, αλλά όπου ο αναμενόμενος χρόνος εκτέλεσης είναι πεπερασμένος (αλγόριθμοι Λας Βέγκας, για παράδειγμα ο αλγόριθμος ταξινόμησης Quicksort) και αλγόριθμους που με κάποια πιθανότητα μπορεί να δώσουν ένα λανθασμένο αποτέλεσμα (αλγόριθμοι Monte Carlo, για παράδειγμα ο αλγόριθμος Monte Carlo για το πρόβλημα του ελάχιστου συνόλου ανάδρασης κορυφών) ή να αποτύχουν να παράγουν αποτέλεσμα είτε σηματοδοτώντας μια αποτυχία είτε αποτυγχάνοντας να τερματίσουν. Σε ορισμένες περιπτώσεις, οι πιθανοτικοί αλγόριθμοι είναι το μόνο πρακτικό μέσο επίλυσης ενός προβλήματος.

Είναι κοινή πρακτική, οι πιθανοτικοί αλγόριθμοι προσεγγίζονται χρησιμοποιώντας μια γεννήτρια ψευδοτυχαίων αριθμών στη θέση μιας πραγματικής πηγής τυχαίων bits. Μια τέτοια υλοποίηση μπορεί να αποκλίνει από την αναμενόμενη θεωρητική συμπεριφορά και τις μαθηματικές εγγυήσεις που μπορεί να εξαρτώνται από την ύπαρξη μιας ιδανικής πραγματικής γεννήτριας τυχαίων αριθμών.

## Παράδειγμα
Ως παράδειγμα, θα δούμε το πρόβλημα της εύρεσης ενός στοιχείου **a''<nowiki/>' σε έναν [[Πίνακας (δομή δεδομένων)|πίνακα]] ''n'' στοιχείων.

**Είσοδος** : Ένας πίνακας <math>n \geq 2</math> στοιχείων, στον οποίο τα μισά είναι ''a'' και τα άλλα μισά είναι ''b''.

**Έξοδος**: Βρείτε ένα ''a'' στον πίνακα.

Δίνουμε δύο εκδοχές του αλγορίθμου, έναν [[Αλγόριθμος Λας Βέγκας|αλγόριθμο Λας Βέγκας]] και έναν [[Αλγόριθμος Μόντε Κάρλο|αλγόριθμο Μόντε Κάρλο]] .

Ξεκινάμε με τον αλγόριθμο Λας Βέγκας:<syntaxhighlight lang="pascal">
findingA_LV(array A, n)
begin
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
  until A[j] = 'a'
end
</syntaxhighlight>Αυτός ο αλγόριθμος πετυχαίνει με πιθανότητα 1. Ο αριθμός των επαναλήψεων δεν είναι σταθερός και μπορεί να είναι αυθαίρετα μεγάλος, αλλά η [[αναμενόμενη τιμή]] των επαναλήψεων είναι 

: <math> \lim_{n \to \infty} \sum_{i = 1}^{n} \frac{i}{2^i} = 2</math>

Επειδή είναι σταθερά, ο αναμενόμενος χρόνος εκτέλεσης για πολλές κλήσεις είναι <math>\Theta(1)</math>.

Συνεχίζουμε με τον αλγόριθμο Μόντε Κάρλο:<syntaxhighlight lang="pascal">
findingA_MC(array A, n, k)
begin
  i := 0
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
    i := i + 1
  until i = k or A[j] = 'a'
end
</syntaxhighlight>Αν βρεθεί ένα  '<nowiki/>''a''<nowiki/>', ο αλγόριθμος πετυχαίνει, διαφορετικά ο αλγόριθμος αποτυγχάνει. Αφού σε κάθε επανάληψη ο αλγόριθμος πετυχαίνει με πιθανότητα <math>1/2</math>, και οι επαναλήψεις είναι ανεξάρτητες, μετά από ''k'' επαναλήψεις, η πιθανότητα να βρεθεί ένα ' ''a'' ' είναι:<div style="text-align:center;">
<math>\Pr[\text{βρέθηκε}\ a] = 1 - (1/2)^k</math>
</div>Δεν είναι εγγυημένο ότι ο αλγόριθμος θα πετύχει κάθε φορά, αλλά είναι εγγυημένο ότι ο χρόνος εκτέλεσης είναι πεπερασμένος, καθώς ο αριθμός των επαναλήψεων είναι πάντα μικρότερος ή ίσος του ''k''. Θεωρώντας το ''k'' ως σταθερά, ο χρόνος εκτέλεσης (αναμενόμενος και απόλυτος) είναι <math>\Theta(1)</math> .

Οι πιθανοτικοί αλγόριθμοι είναι ιδιαίτερα χρήσιμοι όταν υπάρχει ένας κακόβουλος "αντίπαλος" που προσπαθεί σκόπιμα να δώσει μία είσοδο στον αλγόριθμο ώστε να καθυστερήσει τον αλγόριθμο (βλ . χειρότερη περίπτωση πολυπλοκότητα και ανταγωνιστική ανάλυση (αλγόριθμοι)) όπως στο [[δίλημμα του φυλακισμένου]]. Αυτός είναι και ο λόγος που η τυχαιότητα είναι πανταχού παρούσα στην [[κρυπτογραφία]]. Σε κρυπτογραφικές εφαρμογές, δεν μπορούν να χρησιμοποιηθούν ψευδοτυχαίοι αριθμοί, αφού ο αντίπαλος μπορεί να τους προβλέψει, καθιστώντας τον αλγόριθμο ντετερμινιστικό. Επομένως, απαιτείται είτε μια πηγή "πραγματικά" τυχαίων αριθμών είτε μια κρυπτογραφικά ασφαλής γεννήτρια ψευδοτυχαίων αριθμών . Ένας άλλος τομέας στον οποίο η τυχαιότητα είναι εγγενής είναι ο [[Κβαντική πληροφορική|κβαντικός υπολογισμός]] .

Στο παραπάνω παράδειγμα, ο αλγόριθμος Λας Βέγκας δίνει πάντα τη σωστή απάντηση, αλλά ο χρόνος εκτέλεσης του είναι μια τυχαία μεταβλητή. Ο αλγόριθμος Monte Carlo (που σχετίζεται με τη [[Μέθοδος Μόντε Κάρλο|μέθοδο προσομοίωσης Monte Carlo]]) εγγυάται ότι θα τερματίσει σε ένα πεπερασμένο χρονικό διάστημα, το μήκος του οποίου φράζεται από μία συνάρτηση του μεγέθους της εισόδου και της παραμέτρου ''k'', αλλά επιτρέπει μια ''μικρή πιθανότητα σφάλματος''. Παρατηρήστε ότι οποιοσδήποτε αλγόριθμος Λας Βέγκας μπορεί να μετατραπεί σε αλγόριθμο Μόντε Κάρλο (μέσω της [[Ανισότητα Μάρκοφ|ανισότητας Μάρκοφ]]), βάζοντάς του να επιστρέψει μία αυθαίρετη (πιθανώς λανθασμένη απάντηση) εάν αποτύχει να ολοκληρωθεί εντός του καθορισμένου χρόνου. Αντίθετα, εάν έχουμε έναν αποδοτικό αλγόριθμο για να ελέγξουμε εάν μια απάντηση είναι σωστή (στο παραπάνω παράδειγμα αυτό ήταν απλά `''A[j] = a''<nowiki/>'), τότε ένας αλγόριθμος Monte Carlo μπορεί να μετατραπεί σε αλγόριθμο Λας Βέγκας εκτελώντας τον αλγόριθμο Monte Carlo επανειλημμένα μέχρι να λάβουμε μια σωστή απάντηση.

== Υπολογιστική πολυπλοκότητα ==
Η [[Θεωρία πολυπλοκότητας|θεωρία της υπολογιστικής πολυπλοκότητας]] μοντελοποιεί πιθανοτικούς αλγόριθμους με τις ''πιθανοτικές μηχανές Turing''. Στον τομέα έχουν μελετηθεί και οι αλγόριθμοι Λας Βέγκας και Μόντε Κάρλο, και επίσης έχουν διατυπωθεί αρκετές άλλες κλάσεις πολυπλοκότητας σχετικές με την τυχαιότητα. Η πιο βασική πιθανοτική κλάση πολυπλοκότητας είναι η RP, η οποία περιλαμβάνει [[Πρόβλημα απόφασης|προβλήματα απόφασης]] για τα οποία υπάρχει ένας αποδοτικός (που τρέχει σε πολυωνυμικό χρόνο) πιθανοτικός αλγόριθμος (ή ισοδύναμα μία πιθανοτική μηχανή Turing) που αναγνωρίζει τις περιπτώσεις ΟΧΙ με απόλυτη βεβαιότητα και αναγνωρίζει τις περιπτώσεις ΝΑΙ με πιθανότητα τουλάχιστον 1/2. Το συμπλήρωμα της κλάσης RP είναι η κλάση co-RP. Τα προβλήματα που έχουν (πιθανώς μη τερματιζόμενους) αλγόριθμους με πολυωνυμικό αναμενόμενο χρόνο εκτέλεσης και των οποίων η έξοδος είναι πάντα σωστή ανήκουν στην κλάση ZPP .

Η κλάση των προβλημάτων για τα οποία οι αλγόριθμοι έχουν πιθανότητα σφάλματος και στις ΝΑΙ και στις ΟΧΙ  περιπτώσεις ονομάζεται BPP. Αυτή η κλάση είναι η αντίστοιχη πιθανοτική κλάση του P, δηλ το BPP αντιπροσωπεύει την κατηγορία των αποδοτικών πιθανοτικών αλγορίθμων.

== Ιστορία ==

=== Ταξινόμηση ===
Ο αλγόριθμος [[Γρήγορη ταξινόμηση|Quicksort]] για την [[Αλγόριθμος ταξινόμησης|ταξινόμηση]] ανακαλύφθηκε από τον [[Τόνι Χορ]] το 1959, και στη συνέχεια δημοσιεύτηκε το 1961. Την ίδια χρονιά, ο Χορ δημοσίευσε τον αλγόριθμο [[Γρήγορη επιλογή|Quickselect]] που βρίσκει το [[Διάμεσος|διάμεσο]] στοιχείο μιας λίστας σε γραμμικό αναμενόμενο χρόνο. Το πρόβλημα του αν υπήρχε ντετερμινιστικός αλγόριθμος γραμμικού χρόνου παρέμεινε ανοιχτό μέχρι το 1973.

=== Θεωρία αριθμών ===
Το 1917, ο [[Henry Cabourn Pocklington]] εισήγαγε έναν πιθανοτικό αλγόριθμο γνωστό ως [[Ο αλγόριθμος του Pocklington|αλγόριθμος Pocklington]] για την αποτελεσματική εύρεση [[Τετραγωνική ρίζα|τετραγωνικών ριζών]] modulo πρώτων αριθμών. Το 1970, ο[[Έλγουιν Μπέρλεκαμπ|Elwyn Berlekamp]] εισήγαγε έναν τυχαιοποιημένο αλγόριθμο για τον αποτελεσματικό υπολογισμό των ριζών ενός πολυωνύμου σε ένα πεπερασμένο πεδίο. Το 1977, ο [[Robert M. Solovay]] και ο [[Φόλκερ Στράσσεν|Volker Strassen]] ανακάλυψαν έναν αλγόριθμο για να ελέγχει αν ένας αριθμός είναι [[Πρώτος αριθμός|πρώτος]] σε πολυωνυμικό χρόνο. Λίγο αργότερα, ο [[Michael O. Rabin]] έδειξε ότι ο αλγόριθμος ελέγχου πρώτων του Miller (του 1976) μπορεί επίσης να μετατραπεί σε έναν πολυωνυμικό πιθανοτικό αλγόριθμο. Εκείνη την εποχή, δεν ήταν γνωστός κάποιος ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου για τον έλεγχο πρώτων αριθμών.

=== Δομές δεδομένων ===
Μία από τις πρώτες πιθανοτικές δομές δεδομένων είναι ο [[πίνακας κατακερματισμού]], ο οποίος εισήχθη το 1953 από τον [[Χανς Πίτερ Λουν|Hans Peter Luhn]] στην [[IBM]]. Ο πίνακας κατακερματισμού του Luhn χρησιμοποιούσε μία αλυσίδα για την επίλυση συγκρούσεων και ήταν επίσης μια από τις πρώτες εφαρμογές [[Συνδεδεμένη λίστα|συνδεδεμένων λιστών]]. Στη συνέχεια, το 1954, [[Τζιν Άμνταλ|οι Gene Amdahl]], [[Elaine M. McGraw]], [[Nathaniel Rochester (επιστήμονας υπολογιστών)|Nathaniel Rochester]] και [[Άρθουρ Σάμουελ|Arthur Samuel]] της IBM Research εισήγαγαν τη [[Γραμμική ανίχνευση|γραμμική εξέταση]], αν και [[Αντρέι Ερσόφ|ο Andrey Ershov]] ανεξάρτητα είχε την ίδια ιδέα το 1957. Το 1962, [[Ντόναλντ Κνουθ|ο Donald Knuth]] πραγματοποίησε την πρώτη σωστή ανάλυση γραμμικής εξέτασης, αν και το σημείωμα που είχε την ανάλυσή του δεν δημοσιεύτηκε μέχρι αργότερα. Η πρώτη δημοσιευμένη ανάλυση ήταν από τον Konheim και τον Weiss το 1966.

Οι πρώτες αναλύσεις των πινάκων κατακερματισμού υπέθεταν ότι είτε υπάρχει πρόσβαση σε μια πλήρως τυχαία συνάρτηση κατακερματισμού είτε ότι τα κλειδιά ήταν τυχαία. Το 1979, οι Carter και Wegman εισήγαγαν τις καθολικές συναρτήσεις κατακερματισμού και έδειξαν ότι μπορούν να χρησιμοποιηθούν για την υλοποίηση αλυσιδωτών πινάκων κατακερματισμού με σταθερό αναμενόμενο χρόνο ανά πράξη.

Το 1970, ο [[Burton Howard Bloom]] εισήγαγε τα [[Φίλτρο Μπλουμ|φίλτρα Bloom]], μία δομή δεδομένων που δίνει προσεγγιστικές απαντήσεις για το αν ένα στοιχείο ''x'' ανήκει σε ένα σύνολο ''S''.  Το 1989, ο [[Ραϊμούντ Σάιντελ|Raimund Seidel]] και η [[Cecilia R. Aragon]] εισήγαγαν ένα πιθανοτικό και ισορροπημένο δυαδικό δέντρο αναζήτησης γνωστό ως treap. Την ίδια χρονιά, ο [[William Pugh (επιστήμονας υπολογιστών)|William Pugh]] παρουσίασε ένα άλλο τυχαιοποιημένο δέντρο αναζήτησης γνωστό ως [[Παράλειψη λίστας|λίστα παράλειψης]].

=== Χρήσεις στη Συνδυαστική ===
Πριν γίνουν διαδεδομένοι οι πιθανοτικοί αλγόριθμοι στην επιστήμη των υπολογιστών, ο [[Πολ Έρντος]] έκανε δημοφιλή τη χρήση πιθανοτικών μεθόδων ως μια μαθηματική τεχνική για την απόδειξη ύπαρξης μαθηματικών αντικειμένων. Αυτή η τεχνική έχει γίνει γνωστή ως [[πιθανοτική μέθοδος]]. Ο [[Πολ Έρντος|Erdős]] έκανε την πρώτη του εφαρμογή της πιθανοτικής μεθόδου το 1947, όταν χρησιμοποίησε μια απλή πιθανοτική κατασκευή για να αποδείξει την ύπαρξη [[Θεώρημα Ράμσεϋ|γράφων Ramsey]].  Επίσης χρησιμοποίησε έναν πολύ πιο περίπλοκο πιθανοτικό αλγόριθμο το 1959 για να διαπιστώσει την ύπαρξη γράφων με υψηλή [[Περιφέρεια (θεωρία γράφων)|περιφέρεια]] και [[Χρωματικός αριθμός|χρωματικό αριθμό]].

== Παραδείγματα ==

=== Quicksort ===
Η [[γρήγορη ταξινόμηση]] είναι ένας γνωστός, ευρέως χρησιμοποιούμενος αλγόριθμος ο οποίος κάνει χρήση της τυχαιότητας. Πολλές ντετερμινιστικές εκδοχές αυτού του αλγορίθμου (π.χ. που διαλέγουμε πάντα το πρώτο στοιχείο ως άξονα) χρειάζονται Θ(''n''<sup>2</sup>) χρόνο για να ταξινομήσουν ''n'' αριθμούς για μία κατηγορία καλά διατυπωμένων εισόδων (π.χ. τους ήδη ταξινομημένους πίνακες). Ωστόσο, εάν ο αλγόριθμος επιλέγει τον άξονα ομοιόμορφα στην τύχη (από τα υπολειπόμενα στοιχεία), τότε με μεγάλη πιθανότητα τελειώνει σε ''O''(''n''&nbsp;log n) χρόνο ανεξάρτητα από τα χαρακτηριστικά της εισόδου.

=== Πιθανοτικές σταδιακές κατασκευές στη γεωμετρία ===
Στην [[υπολογιστική γεωμετρία]], μια κλασσική τεχνική για την κατασκευή μιας γεωμετρικής δομής όπως το [[κυρτό περίβλημα]] ή η [[Τριγωνισμός Delaunay|τριγωνοποίηση Delaunay]] είναι πρώτα να πάρουμε μία τυχαία [[μετάθεση]] των σημείων εισόδου και στη συνέχεια να τα εισάγουμε στην υπάρχουσα δομή το ένα μετά το άλλο. Η τυχαιότητα της σειράς που τα εισάγουμε διασφαλίζει ότι ο αναμενόμενος συνολικός αριθμός αλλαγών στη δομή είναι μικρός και έτσι ο αναμενόμενος χρόνος εκτέλεσης του αλγορίθμου είναι μικρός. Αυτή η τεχνική είναι γνωστή ως [[Randomized incremental construction|τυχαιοποιημένη σταδιακή κατασκευή]].

=== Ελάχιστη τομή ===
**Είσοδος**: Ένας [[γράφος]] ''G''(''V'', ''E'').

**Έξοδος*': Μία [[Τομή (θεωρία γράφων)|τομή]] που χωρίζει τις κορυφές στα [[Σύνολο|σύνολα]] *L* και *R*, και έχει τον ελάχιστο αριθμό ακμών μεταξύ των *L* και *R.*

Η [[Συστολή ακμής|συστολή]] δύο κορυφών *u* και *v* σε έναν ([[Πολυγράφος (θεωρία γράφων)|πολυ]]-)γράφο δίνει μία νέα κορυφή *u*<nowiki/>' με ακμές που είναι η ένωση των ακμών που προσπίπτουν είτε στον *u* είτε στον *v*, εξαιρουμένων των ακμών μεταξύ των *u* και *v*. Το Σχήμα 1 δίνει ένα παράδειγμα συστολής των *Α* και *Β*. Μετά τη συστολή, ο γράφος που προκύπτει μπορεί να έχει παράλληλες ακμές, αλλά δεν περιέχει [[Βρόχος (θεωρία γράφων)|βρόχους]].
[[Αρχείο:Single_run_of_Karger’s_Mincut_algorithm.svg|μικρογραφία|340x340εσ| Σχήμα 2: Επιτυχής εκτέλεση του αλγορίθμου του Karger σε έναν γράφο 10 κορυφών. Η ελάχιστη τομή έχει μέγεθος 3 και υποδεικνύεται από τα χρώματα κορυφής.]]
[[Αρχείο:Contraction_vertices.jpg|κέντρο|μικρογραφία|300x300εσ| Σχήμα 1: Συστολή των κορυφών Α και Β.]]
Ο απλός αλγόριθμος του Karger:<syntaxhighlight lang="pascal">
begin 
   i := 1 
   repeat 
      repeat 
         Διαλέγουμε μία τυχαία ακμή (u,v) ∈ E στον G
         Διαγράφουμε τις κορυφές u και v
         Προσθέτουμε τη συστολή τους u΄
      until να μείνουν ακριβώς δύο κουρφές
      Λαμβάνουμε την αντίστοιχη τομή Cᵢ
      i := i + 1
   until i = m 
   Τυπώνουμε την ελάχιστη τομή από τις C₁, C₂, ..., Cₘ.
end

</syntaxhighlight>Ο αλγόριθμος επαναλαμβάνει τον εσωτερικό βρόχο <math>m </math> φορές, που βρίσκει μία τομή <math>C_i</math>. Ο χρόνος εκτέλεσης του εσωτερικού βρόχου είναι <math>O(n)</math>, όπου *n* το πλήθος των κορυφών του γράφου. Μετά από *m* εκτελέσεις του εξωτερικού βρόχου, κρατάμε την ελάχιστη τομή μεταξύ όλων των αποτελεσμάτων. Το Σχήμα 2 δίνει ένα παράδειγμα μιας εκτέλεσης του αλγορίθμου, στο τέλος της οποίας λαμβάνουμε μια τομή ή μεγέθους 3.


==== Ανάλυση του αλγορίθμου ====
Η πιθανότητα να πετύχει ο αλγόριθμος είναι 1 μείον την πιθανότητα να αποτύχουν όλες οι προσπάθειες. Επειδή κάθε επανάληψη είναι [[Ανεξαρτησία (Θεωρία πιθανοτήτων)|ανεξάρτητη]], η πιθανότητα να αποτύχουν όλες οι προσπάθειες είναι<math display="block">
\prod_{i=1}^m \Pr(C_i\neq C)=\prod_{i=1}^m(1-\Pr(C_i=C)).
</math>Από το Λήμμα 1, η πιθανότητα να έχουμε  είναι η πιθανότητα να μην επιλέξαμε καμία ακμή του *C* κατά την επανάληψη *i* . Θεωρήστε τον εσωτερικό βρόχο και έστω  ο γράφος μετά από *j* συστολές ακμών για  . Τότε ο  έχει  κορυφές. Χρησιμοποιούμε τον κανόνα της αλυσίδας για την κατά συνθήκη πιθανότητα. Η πιθανότητα η ακμή που επιλέχθηκε στην επανάληψη *j* να μην είναι στο *C*, δεδομένου ότι δεν έχουμε επιλέξει καμία ακμή του *C* προηγουμένως, είναι <math>1-\tfrac{k}</math> . Παρατηρήστε ότι ο  εξακολουθεί να έχει ελάχιστη τομή μεγέθους *k*, επομένως από το Λήμμα 2, εξακολουθεί να έχει τουλάχιστον <math>\tfrac{(n-j)k}{2}</math> ακμές.

Επομένως, <math>1-\tfrac{k}\geq 1-\tfrac{2}{n-j}=\tfrac{n-j-2}{n-j}</math> .

Συνεπώς, χρησιμοποιώντας τον κανόνα της αλυσίδας, η πιθανότητα να βρεθεί η ελάχιστη τομή *C* είναι<math display="block">
 \Pr[C_i=C] \geq \left(\frac{n-2}{n}\right)\left(\frac{n-3}{n-1}\right)\left(\frac{n-4}{n-2}\right)\ldots\left(\frac{3}{5}\right)\left(\frac{2}{4}\right)\left(\frac{1}{3}\right).
</math>Μετά την απλοποίηση λαμβάνουμε ότι <math>\Pr[C_i=C] \geq \tfrac{2}{n(n-1)}</math> . Έτσι η πιθανότητα να πετύχει ο αλγόριθμος είναι τουλάχιστον <math>1- \left(1-\tfrac{2}{n(n-1)}\right)^m</math> . Θέτοντας <math>m = \tfrac{n(n-1)}{2}\ln  n</math>, η πιθανότητα είναι τουλάχιστον <math>1-\tfrac{1}{n}</math> . Καταλήγουμε ότι ο αλγόριθμος βρίσκει την ελάχιστη τομή με πιθανότητα τουλάχιστον <math>1 - \tfrac{1}{n}</math>, σε χρόνο <math>O(mn) = O(n^3 \log n)</math> .

== Αποτυχαιοποίηση ==
Η τυχαιότητα μπορεί να θεωρηθεί ως ένας πόρος, όπως είναι ο χώρος και ο χρόνος. Η αποτυχαιοποίηση είναι η διαδικασία *αφαίρεσης* της τυχαιότητας (ή χρήσης όσο το δυνατόν λιγότερης από αυτήν) από έναν πιθανοτικό αλγόριθμο. Δεν είναι προς το παρόν γνωστό εάν όλοι οι αλγόριθμοι μπορούν να αποτυχαιοποιηθούν χωρίς να αυξηθεί σημαντικά ο χρόνος εκτέλεσης τους. Για παράδειγμα, στην [[θεωρία πολυπλοκότητας]], είναι άγνωστο εάν P = BPP, δηλαδή, δεν γνωρίζουμε εάν μπορούμε να πάρουμε έναν αυθαίρετο τυχαιοποιημένο αλγόριθμο που εκτελείται σε πολυωνυμικό χρόνο με μικρή πιθανότητα σφάλματος και να τον αποτυχαιοποιήσουμε ώστε να εκτελείται σε πολυωνυμικό χρόνο χωρίς τη χρήση τυχαιότητας.

Υπάρχουν κάποιες γενικές μέθοδοι που μπορούν να χρησιμοποιηθούν για την αποτυχαιοποίηση συγκεκριμένων τυχαιοποιημένων αλγορίθμων:

* η [[μέθοδος της κατά συνθήκη πιθανότητας]] και η γενίκευσή της, με τους απαισιόδοξους εκτιμητές
* η [[θεωρία ασυμφωνίας]] (η οποία χρησιμοποιείται κυρίως για την αποτυχαιοποίηση γεωμετρικών αλγορίθμων)
* η εκμετάλλευση περιορισμένης ανεξαρτησίας μεταξύ των τυχαίων μεταβλητών που χρησιμοποιούνται από τον αλγόριθμο, όπως η [[Ανεξαρτησία κατά ζεύγη|ανεξαρτησία ανά δύο]] που χρησιμοποιείται στον [[Καθολικός κατακερματισμός|καθολικό κατακερματισμό]]
* η χρήση [[Γράφος επεκτατής|γράφων επεκτατών]] για *την ενίσχυση* μιας μικρής ποσότητας αρχικής τυχαιότητας (αυτή η τελευταία προσέγγιση αναφέρεται επίσης ως δημιουργία ψευδοτυχαίων bits από μια τυχαία πηγή και οδηγεί στο σχετικό θέμα της ψευδοτυχαιότητας)
* αλλαγή του τυχαιοποιημένου αλγόριθμου για χρήση μιας [[Συνάρτηση κατακερματισμού|συνάρτησης κατακερματισμού]] ως πηγή τυχαιότητας για τις εργασίες του αλγορίθμου και, στη συνέχεια, αποτυχαιοποίηση του αλγορίθμου με ωμή βία όλων των πιθανών παραμέτρων (seeds) της συνάρτησης κατακερματισμού. Αυτή η τεχνική χρησιμοποιείται συνήθως για την εξαντλητική αναζήτηση ενός δειγματοληπτικού χώρου και κάνει τον αλγόριθμο ντετερμινιστικό (π.χ. πιθανοτικοί αλγόριθμοι γράφων)

== Εκεί που η τυχαιότητα βοηθάει ==
Για τις [[Μηχανή Τούρινγκ|μηχανές Turing]], είναι ανοιχτό πρόβλημα εάν η δυνατότητα να κάνουμε τυχαίες επιλογές επιτρέπει την επίλυση ορισμένων προβλημάτων σε πολυωνυμικό χρόνο που δεν μπορούν να λυθούν σε πολυωνυμικό χρόνο χωρίς αυτήν τη δυνατότητα. Το πρόβλημα συνοψίζεται στο αν P = BPP. Ωστόσο, σε άλλα πλαίσια, υπάρχουν συγκεκριμένα παραδείγματα προβλημάτων όπου η τυχαιοποίηση προσφέρει αυστηρά καλύτερα αποτελέσματα.

* Με βάση το αρχικό παράδειγμα: δοσμένης μιας εκθετικά μεγάλης συμβολοσειράς 2<sup>*k*</sup> χαρακτήρων, όπου οι μισοί χαρακτήρες είναι *a* και οι άλλοι μισοί είναι *b*, μια μηχανή τυχαίας πρόσβασης χρειάζεται 2<sup>*k*−1</sup> προσβάσεις στον πίνακα στη χειρότερη περίπτωση για να βρει την θέση ενός *a''. Εάν επιπλέον έχει τη δυνατότητα να κάνει τυχαίες επιλογές, τότε μπορεί να λύσει αυτό το πρόβλημα σε έναν αναμενόμενο πολυωνυμικό αριθμό προσβάσεων.
* Στην πολυπλοκότητα της επικοινωνίας, η ισότητα δύο συμβολοσειρών μπορεί να επαληθευτεί σε κάποια αξιοπιστία χρησιμοποιώντας \log n bits επικοινωνίας με ένα πρωτόκολλο που κάνει χρήση τυχαιότητας. Από την άλλη οποιοδήποτε ντετερμινιστικό πρωτόκολλο απαιτεί \Theta(n) bits αν υπάρχει ένας δυνατός αντίπαλος.
* Ο όγκος ενός κυρτού σώματος μπορεί να εκτιμηθεί με έναν τυχαιοποιημένο αλγόριθμο με αυθαίρετη ακρίβεια σε πολυωνυμικό χρόνο.  Οι Bárány και Füredi έδειξαν ότι κανένας ντετερμινιστικός αλγόριθμος δεν μπορεί να κάνει το ίδιο.  Αυτό ισχύει άνευ όρων, δηλαδή χωρίς να βασιζόμαστε σε οποιεσδήποτε θεωρητικές υποθέσεις πολυπλοκότητας, υποθέτοντας ότι το κυρτό σώμα μπορεί να διερευνηθεί μόνο ως μαύρο κουτί.
* Στην θεωρία πολυπλοκότητας, η κλάση IP αποτελείται από όλες τις γλώσσες που μπορούν να γίνουν αποδεκτές (με μεγάλη πιθανότητα) από μια αλληλεπίδραση πολυωνυμικού μήκους μεταξύ ενός πανίσχυρου αποδείκτη και ενός επαληθευτή που εφαρμόζει έναν αλγόριθμο BPP. Ισχύει ότι IP = PSPACE. Ωστόσο, εάν απαιτείται ο επαληθευτής να είναι ντετερμινιστικός, τότε ισχύει ότι IP = NP .
* Σε ένα δίκτυο χημικών αντιδράσεων (ένα πεπερασμένο σύνολο αντιδράσεων όπως A+B → 2C + D που λειτουργούν σε έναν πεπερασμένο αριθμό μορίων), η ικανότητα να φθάσουμε ποτέ σε μια κατάσταση από μια αρχική κατάσταση είναι αποφασίσιμη, ενώ προσεγγίζεται ακόμη και η πιθανότητα. Η επίτευξη μιας δεδομένης κατάστασης στόχου (χρησιμοποιώντας την τυπική πιθανότητα που βασίζεται στη συγκέντρωση για την οποία θα συμβεί η επόμενη αντίδραση) δεν μπορεί να αποφασιστεί. Πιο συγκεκριμένα, μια περιορισμένη μηχανή Turing μπορεί να προσομοιωθεί ώστε με μεγάλη πιθανότητα να λειτουργεί σωστά πάντοτε, μόνο εάν χρησιμοποιηθεί ένα τυχαίο δίκτυο χημικής αντίδρασης. Με ένα απλό μη ντετερμινιστικό δίκτυο χημικών αντιδράσεων (οποιαδήποτε πιθανή αντίδραση μπορεί να συμβεί στη συνέχεια), η υπολογιστική ισχύς περιορίζεται σε πρωταρχικές αναδρομικές συναρτήσεις . 

## Περαιτέρω ανάγνωση

### Ελληνικά βιβλία
* 
* 
* 
* 

### Ξενόγλωσσα βιβλία
* 
* 
* 
* 
* 
* 
* 

### Επισκοπήσεις
* 
* 
* 

## Δείτε επίσης

* Πιθανοτική ανάλυση αλγορίθμων
* Αλγόριθμος Atlantic City
* Αλγόριθμος Μόντε Κάρλο
* Αλγόριθμος Λας Βέγκας
* Bogosort
* Αρχή της αναβαλλόμενης απόφασης
* HyperLogLog
* Count-min sketch
* Αλγόριθμος του Karger

## Παραπομπές

Κατηγορία:Αλγόριθμοι