Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to że implementacja takiego algorytmu wykorzystuje przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie stale 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 da się go pominąć w analizie.
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 są złośliwe przypadki, dla których 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 stale 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 stale kończą się w ustalonym czasie, ale potrafią 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 dla przykładu w kryptografii oraz bezpieczeństwie komputerowym
Złożoność
Teoria złożoności obliczeniowej Kołmogorowa 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. Dla przykładu do klasy złożoności RP należą problemy, dla których istnieje algorytm probabilistyczny działający w czasie wielomianowym, który negatywne przypadki stale odrzuca, a pozytywne akceptuje z prawdopodobieństwem przynajmniej 50%. Dualną do tej klasy jest klasa Co-RP, a przecięcie tych dwóch klas nazywane jest klasą BPP. Problemy dla których są algorytmy probabilistyczne działające średnio w czasie wielomianowym (ale potencjalnie o dowolnie długim czasie działania) składają się na klasę ZPP.
Derandomizacja
Algorytmy probabilistyczne są zwykle prostsze oraz efektywniejsze od algorytmów deterministycznych dla tych samych problemów. Usuwanie wymagania losowości z algorytmów oraz wykonywanie w ten sposób równie silnych algorytmów deterministycznych jest aktualnie bardzo aktywnym obszarem badań.
Sprawdź też