Algorytm deterministyczny

Z Wikipedii

Ten artykuł wymaga uzupełnienia źródeł podanych informacji. Aby uczynić go weryfikowalnym, należy podać przypisy do materiałów opublikowanych w wiarygodnych źródłach.

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: jak najbardziej mówi się zarówno o równoległych jak i rozproszonych algorytmach deterministycznych.. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

W informatyce: algorytm deterministyczny to algorytm, którego działanie jest całkowicie zdeterminowane przez warunki początkowe (wejście). Oznacza to, że uruchomienie kilkukrotne 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.

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

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

W informatyce bada się również algorytmy nienależące do tej klasy. Najczęściej badane są:

• 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.

[edytuj] 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. Obecnie nie są znane nawet probabilistyczne algorytmy efektywnie rozwiązujące ten problem. Istnieje dla tego problemu rozwiązanie kwantowe (algorytm Shora), jednak jego praktyczna implementacja wymaga zbudowania nieistniejącego w tym momencie komputera kwantowego. Brak możliwości efektywnego 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 wypadkach 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.