Algorytm probabilistyczny
Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w "średnim przypadku", dzięki czemu złośliwe dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny że można go pominąć w analizie.
Spis treści |
[edytuj] Motywacja
Załóżmy że mamy znaleźć literę 'a' w tablicy o n elementach, z których połowa jest literami 'a' a połowa literami 'b'. Zwyczajne przeglądanie tablicy może spowodować że znajdziemy 'a' dopiero po sprawdzeniu połowy (n/2 elementów), jeśli cały początek tablicy jest wypełniony literami 'b'. Podobnie przeglądanie tablicy od końca będzie czasochłonne jeśli cały koniec tablicy jest wypełniony literami 'b' itp. Faktycznie dla dowolnej strategii przeglądania tablicy w ustalonym porządku istnieją złośliwe przypadki kiedy algorytm działa długo. Z drugiej strony, jeśli będziemy sprawdzać losowe elementy, dla dowolnej tablicy z dużym prawdopodobieństwem trafimy bardzo szybko na literę 'a'.
Powyższy przykład opisuje algorytm który zawsze zwraca prawidłową odpowiedź, ale jego czas działania nie jest z góry ustalony. Algorytmy tego typu nazywane są algorytmami Las Vegas. Drugim typem algorytmów są algorytmy Monte Carlo które zawsze kończą się w ustalonym czasie, ale mogą z pewnym prawdopodobieństwem zwrócić zły wynik bądź zwracają wynik tylko z pewną dokładnością.
Algorytmy randomizowane są szczególnie użyteczne jeśli rozważamy sytuację w której jakiś "przeciwnik" próbuje zmusić algorytm do dłuższego działania. Ma to miejsce na przykład w kryptografii i bezpieczeństwie komputerowym
[edytuj] Złożoność
Teoria złożoności obliczeniowej definiuje algorytmy probabilistyczne przy użyciu pojęcia probabilistycznej maszyny Turinga. Model ten definiuje odpowiednie klasy złożoności obliczeniowej, analogicznie do klasycznej maszyny Turinga. Przykładowo do klasy złożoności RP należą problemy dla których istnieje algorytm probabilistyczny działający w czasie wielomianowym, który dla negatywne przypadki zawsze odrzuca, a pozytywne akceptuje z prawdopodobieństwem co najmniej 50%. Dualną do tej klasy jest klasa Co-RP, a przecięcie tych dwóch klas nazywane jest klasą BPP. Problemy dla których istnieją algorytmy probabilistyczne działające średnio w czasie wielomianowym (ale potencjalnie o dowolnie długim czasie działania) tworzą klasę ZPP.
[edytuj] Derandomizacja
Algorytmy probabilistyczne są zwykle prostsze i efektywniejsze od algorytmów deterministycznych dla tych samych problemów. Usuwanie wymagania losowości z algorytmów i tworzenie w ten sposób równie silnych algorytmów deterministycznych jest obecnie bardzo aktywnym obszarem badań.