Algorytm deterministyczny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm deterministycznyalgorytm, 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żna 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 są znane efektywnych algorytmów deterministycznych, probabilistycznych ani kwantowych (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 pseudolosowych.