Algorytmy probabilistyczne (intro)

Nowa wiadomość. W NASA powiedzieli, że w łaziku, do którego mamy dostęp, będzie generator liczb losowych. Dodano coś jeszcze: przypomnienie, że nasz algorytm musi działać w praktyce. Żeby coś działało w praktyce, to znaczy, że choć zawsze jest ryzyko błędu, to może tak małe, że je ignorujemy. Wydaje się to dziwne? Pomyślcie, że w świecie fizycznym nic nie jest pewne, zawsze jest ryzyko błędu. Np. opakowania czipów zawierają małe ilości promieniotwórczych zanieczyszczeń, a te, w czasie rozpadu, uwalniają cząstki alfa, które mogą odwrócić bity w pamięci i np. niespodziewanie zmienić liczbę. Co ciekawsze, promieniowanie kosmiczne też może spowodować błędy w oprogramowaniu. Nigdy całkowicie nie wyeliminujemy ryzyka błędu. Spytałem w NASA, jaki jest dopuszczalny margines błędu. Usłyszałem: „Prawdopodobieństwo błędu dla danej próby musi być niższe niż prawdopodobieństwo wygranej na loterii 2 razy z rzędu”. Prawdopodobieństwo trafienia 6 z 49, 2 razy z rzędu, to 6 razy 10 do potęgi minus 14, dla pewności zaokrąglimy w dół: prawdopodobieństwo błędu ma wynosić 10 do potęgi minus 15. Bezpiecznie: nie spodziewamy się błędu. A program może działać setki, tysiące razy. Pytam: czy dostęp do losowości pomoże nam przyspieszyć algorytm decyzyjny, jak w teście pierwszości? To głębokie pytanie. Spójrzmy z perspektywy. Mamy zbiór liczb całkowitych od 1 do jakiejś granicy n. Niech to będzie nasz wszechświat liczb całkowitych. Zawsze możemy podzielić zbiór na dwa podzbiory. Problem decyzyjny można uznać właśnie za taki podział na dwa podzbiory. Np., przy pytaniu, czy dana liczba jest mniejsza od 100, odpowiedź będzie brzmieć „tak” dla wszystkich liczb całkowitych mniejszych od 100. To jeden zbiór. W pozostałych przypadkach odpowiedzią będzie „nie”. Drugi zbiór. Teraz skupmy się na rozpoznawaniu liczb pierwszych. Idealnie byłoby mieć proste do obliczenia kryteria, spełniane przez wszystkie liczby pierwsze i przez żadne liczby złożone. Gdybyśmy znali jakiś prosty wzór opisujący położenie wszystkich i tylko liczb pierwszych, wystarczyłoby sprawdzić, czy dana liczba n pasuje do wzoru. Tylko że na razie nie znaleziono wyczerpującego, prosto obliczalnego wzoru, dla wszystkich liczb pierwszych i żadnych złożonych, albo dla wszystkich liczb złożonych i żadnych pierwszych. Znamy jednak szybkie testy dla większości liczb złożonych. Np., prostym kryterium byłby test na parzystość. Wszystkie liczby parzyste dzielą się przez 2. Szybko określimy parzystość na podstawie ostatniej cyfry. Nawet przy rosnącym n nie jest trudniej: patrzymy na ostatnią cyfrę, znaną też jako bit mniej znaczący. Możemy wykorzystać ten test parzystości jako niskiej jakości test na złożoność. Możemy więc mieć algorytm akceptujący liczbę całkowitą n i będzie on tylko sprawdzał, czy to liczba parzysta. Jeśli tak, i większa od dwóch, to mamy stuprocentową pewność, że jest liczbą złożoną. Mamy dowód. 2 to nasz świadek złożoności. A jeśli nie, to pewności nie mamy. Liczba nieparzysta może być pierwszą, bo wszystkie pierwsze są nieparzyste, albo jest jedną z wielu nieparzystych liczb złożonych, jak 9 lub 15. Z powodu wielkiej grupy nieparzystych liczb złożonych test jest nieakceptowalny. Dla jasności, narysujmy. Dane n może być albo liczbą pierwszą, albo złożoną. Jeśli n jest liczbą pierwszą różną od 2, algorytm powie to w 100% przypadków, bo nie ma parzystej liczby pierwszej większej od 2. Nie powie „n - złożona”, gdy dostanie liczbę pierwszą. Ale jeśli liczba n jest złożona, nasz algorytm powie „złożona” w 50% przypadków i „pierwsza” w 50% przypadków. Zatem jeśli nasz algorytm daje wynik „złożona”, to znaczy, że n jest liczbą złożoną. Jednak jeśli da wynik „pierwsza”, wiemy, że jest niedopuszczalnie wysokie ryzyko błędu. Do tej pory radziliśmy sobie z tym niedopuszczalnie dużym błędem przez iteracje. Narysujmy działanie naszej maszyny. Przy danym n, nasza maszyna przeprowadza serię testów podzielności, zaczynając od a równego 2. Pyta, czy a jest dzielnikiem n. Jeśli nie, to możemy wyeliminować cały ten obszar. Potem drugie pytanie: czy n dzieli się przez 3? Jeśli nie, wyeliminujemy całą tę sekcję. Dalej – czy n dzieli się przez 5, 7 itd. Zauważcie, że to zbiory rozłączne, które stopniowo wyczerpują wszystkie możliwe liczby złożone. Jeśli po drodze choć raz odpowiemy „tak”, to mamy dowód, że n jest liczbą złożoną. Liczba a, niezależnie od wartości, jest naszym świadkiem. Algorytm daje więc wynik „n złożone”. Jeśli nie, kontynuujemy do wyczerpania wszystkich możliwych liczb złożonych. Aż dojdziemy do pierwiastka z n. Bo przecież każda liczba złożona n musi mieć czynnik pierwszy mniejszy lub równy pierwiastkowi z n. Prowadzi to do ostatniego pytania w naszym algorytmie. Jeśli nie znajdziemy świadków, zaś a jest większe od pierwiastka kwadratowego z n, to nagle mamy dowód, że n jest liczbą pierwszą. Zauważcie, że algorytm daje nam dwa wyjścia. Oba stanowią dowód pewności, że n jest albo pierwsze, albo złożone. Gdy n jest liczbą pierwszą, próbujemy wszystkich możliwych podzielników, i wykluczamy je, co dowodzi, że n to liczba pierwsza. Problem z tą metodą polega na tym, że wartość testowa a wymaga przejścia przez każdą liczbę pierwszą od 2 do pierwiastka kwadratowego z n. A gdy n rośnie, to rośnie też ilość liczb pierwszych. Skutkiem jest zbyt wiele powtórzeń w najgorszym przypadku, gdy wprowadzamy do algorytmu liczbę pierwszą. Patrząc całościowo, zauważcie, że algorytm daje dowód, gdy n jest liczbą pierwszą. A teraz wiemy, że właściwie nam go nie trzeba. Nikt nie kazał udowadniać. Mieliśmy tylko mieć 99,9999… 15 dziewiątek procent pewności. Musimy się zastanowić nad testem na złożoność w naszym algorytmie. Najszybsze testy pierwszości metodą próbnych dzieleń do tej pory próbowały używać wzoru pierwszości, jak 6k, gdy wszystkie liczby pierwsze można przedstawić w postaci 6k +/- 1, by badać tylko liczby pierwsze, eliminując wiele liczb złożonych. To szybsze. Taki test można zmienić w test złożoności. Mając daną liczbę całkowitą n w postaci 6k plus lub minus 1, powiemy, że prawdopodobnie to liczba pierwsza, ale jeszcze wiele liczb złożonych, pasuje do tego wzoru. Kryterium nie obejmuje samych liczb pierwszych. Wszystkie liczby pierwsze i niektóre złożone. Myślmy o tych złożonych jak o przecieku. Ten przeciek to źródło błędu. A jeśli spytamy, czy n nie da się przedstawić w postaci 6k plus lub minus 1, to możemy powiedzieć z całkowitą pewnością, że to liczba złożona, więc przeciek jest źródłem błędu po stronie liczb pierwszych, ale tutaj to niedopuszczalne. To nie jest błąd zaniedbywalny. Prawdopodobieństwo jest znacznie większe. Trzeba zrobić nową procedurę sprawdzania złożoności, mogącą zmniejszyć tę przestrzeń i sprawić, że ryzyko błędu będzie zaniedbywalne. To znaczy, że musimy zobaczyć, jak możemy zmniejszyć liczbę błędów za pomocą iteracji. Myślę, że powinniście tu zamieścić pomysły na to, jaki rodzaj testów chcielibyście wykonać, i, co ważniejsze, jak naprawdę mógłby nam pomóc generator liczb losowych.