Algorytm deterministyczny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W informatyce, algorytm deterministyczny to 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[edytuj | edytuj kod]

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żemy dokładnie określić, jakie będą wszystkie kolejne stany tej maszyny.

Algorytmy, które nie są deterministyczne[edytuj | edytuj kod]

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

Wady algorytmów deterministycznych[edytuj | edytuj kod]

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 znamy efektywnych algorytmów deterministycznych, probabilistycznych ani kwantowych (choć nie potrafimy również pokazać że nie istnieją). Problemy te są o tyle istotne, że obejmują większość istotnych praktycznych zagadnień występujących w przemyśle. Obecnie potrafimy jedynie znajdować rozwiązania przybliżone, i to nie we wszystkich przypadkach.

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 klucz. Realizowane jest to najczęściej przy użyciu kryptograficznie bezpiecznych generatorów pseudolosowych.