Algorytm deterministyczny

Algorytm deterministyczny – algorytm, którego działanie jest całkowicie zdeterminowane przez warunki początkowe (wejście). Oznacza to, że kilkukrotne uruchomienie takiego algorytmu doprowadzi za każdym razem do takiego samego wyniku. Algorytmy deterministyczne stanowią główny obszar badań informatycznych i są najczęściej stosowane, ponieważ mogą być łatwo realizowane na współczesnych komputerach.

Formalna definicja

Formalnie algorytm deterministyczny może być zdefiniowany w terminach zmiany stanów maszyny wykonującej ten algorytm. Algorytm jest deterministyczny, jeśli dla dowolnego stanu i dowolnych danych wejściowych istnieje dokładnie jedna dopuszczalna zmiana stanu. Oznacza to, że rozpoczynając od stanu początkowego można dokładnie określić, jakie będą wszystkie kolejne stany tej maszyny.

Obecnie algorytmy deterministyczne są wykorzystywane również przy projektowaniu niehazardowych automatów do gier, które nie zawierają elementu losowości, w tym generatora liczb pseudolosowych. W tej chwili na świecie istnieją zaledwie dwa rozwiązania o takiej charakterystyce.

Algorytmy, które nie są deterministyczne

W informatyce bada się również algorytmy nienależące do tej klasy. Przykładami takich algorytmów są:

• niektóre algorytmy równoległe i rozproszone – w których interakcja pomiędzy niezależnie wykonywanymi obliczeniami może prowadzić do różnych rezultatów,
• algorytmy probabilistyczne – w których używane są ciągi losowych (lub pseudolosowych) bitów,
• algorytmy kwantowe – w których do obliczeń wykorzystywane są zjawiska kwantowe.

Wady algorytmów deterministycznych

Istnieje wiele problemów, dla których nie znamy efektywnych deterministycznych algorytmów. Przykładowo sprawdzenie, czy dana liczba jest pierwsza, można przeprowadzić bardzo efektywnie za pomocą prostych probabilistycznych algorytmów, znanych od lat siedemdziesiątych (np. test Millera-Rabina). Algorytm deterministyczny dla tego problemu został znaleziony dopiero w 2002 r. (patrz test pierwszości AKS) i jest bardziej skomplikowany i mniej efektywny.

Kolejnym przykładem jest problem rozkładu podanej liczby na czynniki pierwsze. Istnieje dla tego problemu rozwiązanie kwantowe: probabilistyczny (algorytm Shora), jego praktyczna implementacja wymaga zbudowania komputera kwantowego. Brak możliwości efektywnego (obecne komputery kwantowe są zbyt słabe) rozkładu dużych liczb na czynniki pierwsze stanowi podstawę bezpieczeństwa większości algorytmów kryptografii asymetrycznej.

Istnieją wreszcie problemy NP-zupełne, dla których nie są znane efektywne algorytmy deterministyczne, probabilistyczne ani kwantowe (choć nie udowodniono, że nie istnieją). Problemy te są o tyle ważne, że obejmują większość istotnych praktycznych zagadnień występujących w przemyśle. Obecnie znane są jedynie sposoby efektywnego znajdowania przybliżonych rozwiązań i to tylko dla niektórych problemów tego typu.

W niektórych przypadkach problemem jest sama przewidywalność zachowania algorytmów deterministycznych. Przykładowo przy algorytmach kryptograficznych niezbędne jest, aby nikt z zewnątrz nie był w stanie zgadnąć zachowania algorytmu, który generuje klucze. Najczęściej realizowane jest to przy użyciu kryptograficznie bezpiecznych generatorów liczb pseudolosowych.