Τυχαιοποιημένοι Αλγόριθμοι

Report
Ειδικά Θέματα Υπολογισμού και Πολυπλοκότητας
Σπυριδούλα Γραβάνη
31/05/2012
Input
Algorithm
Output
Random
numbers
2
 Χρησιμοποιεί το αποτέλεσμα μιας τυχαίας διεργασίας
σε κάποια υπολογιστικά βήματα.
 Η έξοδος αποτελεί μια τυχαία μεταβλητή, δηλαδή
μπορεί να διαφέρει σε διαφορετικές εκτελέσεις του
αλγορίθμου πάνω στην ίδια είσοδο.
3
 Ντετερμινιστικοί αλγόριθμοι για την επίλυση ενός
προβλήματος βρίσκουν τη βέλτιστη λύση σε
απαγορευτικά μεγάλο χρόνο.
 Προσεγγιστικοί αλγόριθμοι τερματίζουν σε μικρότερο
χρόνο αλλά βρίσκουν υποβέλτιστη λύση.
4
 Οι πιθανοκρατικοί αλγόριθμοι είναι αλγόριθμοι που
τερματίζουν σε μικρό χρόνο με μεγάλη πιθανότητα.
 Βρίσκουν τη βέλτιστη λύση με μεγάλη πιθανότητα.
 Συνήθως είναι απλοί και εύκολοι στην υλοποίηση τους.
5
 Δεν πρέπει να συγχέονται με την πιθανοτική ανάλυση
του μέσου χρόνου εκτέλεσης ενός ντετερμινιστικού
αλγόριθμου.
 Στην περίπτωση αυτή η είσοδος προέρχεται από
πιθανοτική κατανομή.
 Στόχος είναι ο υπολογισμός του αναμενόμενου χρόνου
εκτέλεσης.
6
 Monte Carlo: Τερματίζει σε ντετερμινιστικό
(πολυωνυμικό) χρόνο, πιθανώς με λανθασμένη έξοδο.
 Las Vegas: Παράγει πάντοτε τη σωστή έξοδο. Ο
χρόνος τερματισμού του ωστόσο αποτελεί μια τυχαία
μεταβλητή με φραγμένη αναμενόμενη τιμή.
7
 Θεωρούμε τον εξής πιθανοκρατικό αλγόριθμο για το
πρόβλημα SAT:
“Ξεκίνα με οποιαδήποτε τιμοδοσία Τ και επανέλαβε τα
επόμενα r φορές:
 Αν επαληθεύονται όλες οι προτάσεις, τότε απάντησε: “ ο
τύπος είναι αληθεύσιμος” και σταμάτα.
 Αλλιώς, σε μια πρόταση που δεν επαληθεύεται, διάλεξε
τυχαία μια από τις μεταβλητές τις και δώσε την
αντίθετη τιμοδοσία σε αυτή.
Μετά από r φορές τερμάτισε , απαντώντας: “ ο τύπος δεν
ικανοποιείται με μεγάλη πιθανότητα”. ”
8
 Θεωρούμε το πρόβλημα: 2-SAT =
{ <φ> | ο φ είναι ένας αληθεύσιμος τύπος σε 2CNF }
 Θεώρημα:
Αν εφαρμόσουμε τον Τυχαίο Περίπατο για  = 
βήματα σε οποιοδήποτε αληθές στιγμιότυπο του 2-SAT
με n μεταβλητές, τότε με πιθανότητα τουλάχιστον ίση με
½ θα προκύψει αληθής τιμοδοσία.
9
 Υπάρχει πεπερασμένη πιθανότητα λάθους. Αυτή η
πιθανότητα ωστόσο , μπορεί να γίνει αυθαίρετα μικρή
με επαναληπτική εκτέλεση της τυχαιότητας.
 Δεν υπάρχει πραγματική τυχαιότητα αριθμών. Οι
αλγόριθμοι χρησιμοποιούν ψευδοτυχαίους αριθμούς ,
γι’αυτό και η έξοδός τους εξαρτάται από την ποιότητα
της γεννήτριας.
 Η ανάλυση του χρόνου εκτέλεσης, καθώς και της
πιθανότητας σωστής εξόδου μπορεί να είναι δύσκολη.
10
11
 Μη ντετερμινιστική μηχανή Turing στην οποία κάθε
βήμα λέγεται κερματοριπτικό και έχει δύο αποδεκτές
επόμενες κινήσεις.
 Σε κάθε κλάδο b του υπολογισμού της για είσοδο w
αποδίδουμε πιθανότητα:
  = −
όπου k: το πλήθος των κερματοριπτικών βημάτων κατά
μήκος του b.
 Πιθανότητα αποδοχής της w από τη μηχανή:
  =
⁡
[]
 ά 
ί ό
12
 Πιθανότητα απόρριψης της w από τη μηχανή:
  =  −  
 Για  ≤  <


, η μηχανή διαγιγνώσκει τη γλώσσα L με
πιθανότητα σφάλματος ε όταν ισχύουν οι εξής
συνθήκες:    ∈  → Pr  ≥ 1 − 
   ∉  → Pr  ≥ 1 − .
 Δηλαδή η πιθανότητα λάθους κατά την προσομοίωση
της μηχανής δεν πρέπει να υπερβαίνει την ποσότητα ε.
13
 Μια γλώσσα L ανήκει στην RP αν και μόνο αν υπάρχει
πολυωνυμικού χρόνου πιθανοκρατική μηχανή Turing Μ
τέτοια ώστε για κάθε  ∈ 
να ισχύουν τα εξής:   ∈  → Pr    ≥ 12
∗
  ∉  → Pr    = 0.
 Ένας RP αλγόριθμος είναι Monte Carlo.
 Λάθος έξοδος μπορεί να προκύψει μόνο αν  ∈  .
 Η πιθανότητα λάθους μπορεί να γίνει εκθετικά μικρή
εκτελώντας ανεξάρτητες επαναλήψεις του αλγορίθμου.
14
 Συμπληρωματική κλάση της RP
 Μια γλώσσα L ανήκει στην coRP αν και μόνο αν υπάρχει
πολυωνυμικού χρόνου πιθανοκρατική μηχανή Turing
Μ τέτοια ώστε για κάθε  ∈ 
να ισχύουν τα εξής:   ∈  → Pr    = 1
∗
  ∈  → Pr    ≠ 0.
 Ένας coRP αλγόριθμος είναι Monte Carlo.
 Λάθος έξοδος μπορεί να προκύψει μόνο αν  ∈ 
15
 Μια γλώσσα L ανήκει στην κλάση ZPP αν και μόνο αν:
 ∈  ∩ 
 Ένα πρόβλημα που ανήκει στην κλάση ZPP έχει
αλγόριθμο που δεν κάνει ποτέ λάθος, δηλαδή έναν
αλγόριθμο Las Vegas.
16
 Μια γλώσσα L ανήκει στην PP αν και μόνο αν υπάρχει
πολυωνυμικού χρόνου πιθανοκρατική μηχανή Turing
Μ τέτοια ώστε για κάθε  ∈ 
να ισχύει το εξής:  ∈  →     > 
∗
 Μια τέτοια μηχανή Μ αποφασίζει την L “βάσει
πλειοψηφίας” .
17
 Μια γλώσσα L ανήκει στην BPP αν και μόνο αν υπάρχει
πολυωνυμικού χρόνου πιθανοκρατική μηχανή Turing
Μ τέτοια ώστε για κάθε  ∈ 
3


∈

→
Pr



≥
να ίσχουν τα εξής:
4
1
∗
  ∈  → Pr    ≤ .
4
 Μια τέτοια μηχανή Μ αποδέχεται “βάσει καθαρής
πλειοψηφίας” ή απορρίπτει “βάσει καθαρής
μειοψηφίας”.
18
 Οι βασικοί εγκλεισμοί είναι:
 ⊆  ⊆ 
 Ο δεύτερος ισχύει καθώς μια μηχανή που αποφασίζει
με “καθαρή” πλειοψηφία, σίγουρα αποφασίζει και με
“απλή”.
Πιο αυστηρά , από τους ορισμούς, η BPP έχει
πιθανότητα λάθους μικρότερη από 0.25 ενώ η PP
επιτρέπει πιθανότητα λάθους αυθαίρετα κοντά στο 0.5.
19
 Για τον πρώτο εγκλεισμό, σκεφτόμαστε ως εξής: Έστω
 ∈  ⇒ ∃ ή ή   ύ ό
∶ ∀  ∈ ∗  ύ  ή:
  ∈  →     ≥


  ∉  →     = 
 Ορίζουμε μια πιθανοκρατική μηχανή M’ ως εξής:
“ Για είσοδο x εξομοίωσε την M(x) δύο φορές. Αποδέξου
αν και μόνο αν μια από τις δύο εξομοιώσεις κατέληξε σε
κατάσταση αποδοχής, διαφορετικά απόρριψε.”
20
 Αν  ∉  τότε η Μ(x) δε θα αποδεχθεί, συνεπώς δε θα
αποδεχθεί ούτε η M’(x)

⇒  ′   = 0 ≤

 Αν  ∈ 
τότε εξ’ ορισμού:
συνεπώς:
 ′ () <
 Συνεπώς:

    <

 
∗
⇔  ′  
 
≥


 ∈ 
21
 Ένας τελευταίος εγκλεισμός είναι ο εξής:
 ⊆ 
 Έστω μια γλώσσα L στo NP η οποία διαγιγνώσκεται από μια μη
ντετερμινιστική μηχανή Ν.
 Ορίζουμε μια νέα μηχανή N’ , πανομοιότυπη με την Ν εκτός από
μια νέα αρχική κατάσταση και μια μη ντετερμινιστική επιλογή
από αυτή.
 Η μια πιθανή κίνηση οδηγεί στον αρχικό υπολογισμό της N πάνω
στην ίδια είσοδο.
 Η δεύτερη επιλογή πάντα σε κατάσταση αποδοχής.
22
 Έστω μια λέξη x. Αν η Ν με είσοδο x χρειάζεται p(|x|) βήματα και
παράγει (  ) μονοπάτια υπολογισμού, τότε η N’ παράγει 
μονοπάτια.
 +
 Από αυτά τουλάχιστον τα μισά θα τερματίσουν σε κατάσταση
αποδοχής (αυτά που ανταποκρίνονται στα μισά μονοπάτια
αποδοχής της N’).
 Έτσι, η πλειοψηφία των υπολογισμών της N’ αποδέχεται αν και
μόνο αν υπάρχει τουλάχιστον ένα μονοπάτι υπολογισμού της N(x)
που καταλήγει σε αποδοχή, δηλαδή αν και μόνο αν  ∈  .
 Συνεπώς η Ν’ αποδέχεται την L με πλειοψηφία και
 ∈ 
.
23
 Η εισαγωγή τυχαιότητας οδηγεί σε απλότητα και
αποτελεσματικότητα κατά τη λύση ενός προβλήματος.
 Προϋποθέτει την ύπαρξη μιας αμερόληπτης γεννήτριας
ανεξάρτητων τυχαίων αριθμών.
 Η πρόσβαση σε τέτοιες ακολουθίες αριθμών είναι ακριβή,
γι’αυτό πρέπει να χρησιμοποιείται με φειδώ όπως ο χώρος
και ο χρόνος.
 Υπάρχουν τρόποι να μειωθεί η τυχαιότητα από τους
αλγόριθμους, διατηρώντας την αποδοτικότητα σχεδόν
σταθερή.
24
 Η σχέση μεταξύ των κλάσεων BPP και NP παραμένει
άγνωστη. Αν  ⊆  , τότε:  =  .
 Ένας τέτοιος εγκλεισμός μοιάζει απίθανος , καθώς θα
σήμαινε πως υπάρχουν πρακτικές λύσεις για NP-Πλήρη
προβλήματα.
 Γνωρίζουμε πως το RP είναι υποσύνολο του BPP και το
BPP είναι υποσύνολο του PP , αλλά δεν γνωρίζουμε αν
είναι γνήσια υποσύνολα.
25
26
Ευχαριστώ!

similar documents