Algorytm deterministyczny - Deterministic algorithm

W informatyce , wykorzystując algorytm deterministyczny jest algorytm , który, biorąc pod uwagę przede wszystkim wejście, zawsze wytwarzają taką samą moc, ze maszyna bazowego zawsze przejazdem tej samej sekwencji stanów. Algorytmy deterministyczne są zdecydowanie najbardziej zbadanym i znanym rodzajem algorytmów, a także jednym z najbardziej praktycznych, ponieważ można je wydajnie uruchamiać na rzeczywistych maszynach.

Formalnie algorytm deterministyczny oblicza funkcję matematyczną ; funkcja ma unikalną wartość dla każdego wejścia w swojej dziedzinie , a algorytm to proces, który generuje tę konkretną wartość jako wyjście.

Formalna definicja

Algorytmy deterministyczne można zdefiniować w kategoriach maszyny stanów : stan opisuje, co maszyna robi w danym momencie. Maszyny stanowe przechodzą w sposób dyskretny z jednego stanu do drugiego. Zaraz po wprowadzeniu danych wejściowych maszyna znajduje się w stanie początkowym lub w stanie startowym . Jeśli maszyna jest deterministyczna, oznacza to, że od tego momentu jej aktualny stan określa, jaki będzie jej następny stan; jego przebieg przez zbiór stanów jest z góry określony. Należy pamiętać, że maszyna może być deterministyczna i nadal nigdy się nie zatrzymuje ani nie kończy, a zatem nie zapewnia wyniku.

Przykładami poszczególnych maszyn abstrakcyjnych, które są deterministyczne, są deterministyczna maszyna Turinga i deterministyczny automat skończony .

Co sprawia, że ​​algorytmy są niedeterministyczne?

Różne czynniki mogą powodować, że algorytm zachowuje się w sposób, który nie jest deterministyczny ani niedeterministyczny:

  • Jeśli używa stanu zewnętrznego innego niż dane wejściowe, takiego jak dane wejściowe użytkownika, zmienna globalna , wartość zegara sprzętowego, wartość losowa lub zapisane dane na dysku.
  • Jeśli działa w sposób wrażliwy na czas, na przykład, jeśli ma wiele procesorów zapisujących te same dane w tym samym czasie. W takim przypadku dokładna kolejność, w jakiej każdy procesor zapisuje swoje dane, wpłynie na wynik.
  • Jeśli błąd sprzętowy powoduje nieoczekiwaną zmianę jego stanu.

Chociaż prawdziwe programy rzadko są czysto deterministyczne, ludziom i innym programom łatwiej jest wnioskować o programach, które są. Z tego powodu większość języków programowania, a zwłaszcza funkcjonalnych języków programowania , podejmuje wysiłki, aby zapobiec występowaniu powyższych zdarzeń, z wyjątkiem kontrolowanych warunków.

Rozpowszechnienie procesorów wielordzeniowych spowodowało gwałtowny wzrost zainteresowania determinizmem w programowaniu równoległym, a wyzwania związane z niedeterminizmem zostały dobrze udokumentowane. Zaproponowano szereg narzędzi pomagających radzić sobie z wyzwaniami, aby radzić sobie z impasami i warunkami wyścigu .

Wady determinizmu

W niektórych przypadkach korzystne jest, aby program wykazywał niedeterministyczne zachowanie. Zachowanie programu do tasowania kart używanego na przykład w grze w blackjacka nie powinno być przewidywalne przez graczy — nawet jeśli widoczny jest kod źródłowy programu. Użycie generatora liczb pseudolosowych często nie wystarcza, aby gracze nie byli w stanie przewidzieć wyniku losowego. Sprytny hazardzista może dokładnie odgadnąć liczby, które wybierze generator i w ten sposób z wyprzedzeniem określić całą zawartość talii, pozwalając mu oszukiwać; na przykład Software Security Group w Reliable Software Technologies udało się to zrobić w celu wdrożenia Texas Hold 'em Poker, który jest dystrybuowany przez ASF Software, Inc, co pozwala im konsekwentnie przewidywać wynik rozdań z wyprzedzeniem. Problemów tych można częściowo uniknąć, stosując kryptograficznie bezpieczny generator liczb pseudolosowych , ale nadal konieczne jest użycie nieprzewidywalnego losowego ziarna do inicjalizacji generatora. W tym celu wymagane jest źródło niedeterminizmu, takie jak dostarczany przez sprzętowy generator liczb losowych .

Zauważ, że negatywna odpowiedź na problem P=NP nie sugerowałaby, że programy z niedeterministycznym wyjściem są teoretycznie silniejsze niż te z deterministycznym wyjściem. Klasę złożoności NP (złożoność) można zdefiniować bez odniesienia do niedeterminizmu przy użyciu definicji opartej na weryfikatorze .

Kategorie determinizmu w językach

Rtęć

Ten język programowania logiczno-funkcjonalnego ustanawia różne kategorie determinizmu dla trybów predykatów, jak wyjaśniono w odnośniku.

Haskell

Haskell udostępnia kilka mechanizmów:

niedeterminizm lub pojęcie niepowodzenia
  • gdy Może i Albo typy to pojęcie sukcesu w wyniku.
  • nie metodą klasy Monad może być stosowany do sygnalizowania nie jako wyjątek.
  • transformatory Maybe monad i MaybeT monad zapewniają niepowodzenie obliczeń (zatrzymaj sekwencję obliczeń i zwróć Nothing)
determinizm/niezidentyfikowany z wieloma rozwiązaniami
można pobrać wszystkie możliwe skutki wielokrotnego obliczania wyników, owijając jej typ skutkować MonadPlus monady . (jego metoda mzero powoduje niepowodzenie wyniku, a mplus zbiera pomyślne wyniki).

Rodzina ML i języki pochodne

Jak widać w Standard ML , OCaml i Scala

  • Typ opcji zawiera pojęcie sukcesu.

Jawa

  • Zerowa wartość odniesienia może stanowić nieskuteczne (out-of-Domain) wynik.

Zobacz też

Bibliografia

  1. ^ Edward A. Lee. „Problem z wątkami” (PDF) . Źródło 2009-05-29 .
  2. ^ Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). Programowanie równoległe musi być domyślnie deterministyczne . Warsztaty USENIX na temat gorących tematów w paralelizmie.
  3. ^ "Intel Parallel Inspector Thread Checker" . Źródło 2009-05-29 .
  4. ^ Yuan Lin. „Wykrywanie wyścigu danych i zakleszczeń za pomocą narzędzia Sun Studio Thread Analyzer” (PDF) . Źródło 2009-05-29 .
  5. ^ Wywiad. „Inspektor równoległy firmy Intel” . Źródło 2009-05-29 .
  6. ^ David Worthington. „Intel zajmuje się cyklem rozwoju oprogramowania za pomocą Parallel Studio” . Zarchiwizowane z oryginału dnia 2009-05-28 . Źródło 2009-05-26 .
  7. ^ McGraw, Gary ; Viega, John . „Spraw, aby Twoje oprogramowanie się zachowywało: Gra w liczby: Jak oszukiwać w grach hazardowych online” . Zarchiwizowane z oryginału dnia 2008-03-13 . Źródło 2007-07-02 .
  8. ^ „Kategorie determinizmu w języku programowania Mercury” . Zarchiwizowane od oryginału w dniu 2012-07-03 . Pobrano 23.02.2013 .
  9. ^ „Tryby predykatu rtęci” . Zarchiwizowane od oryginału w dniu 2012-07-03 . Pobrano 25.02.2013 .
  10. ^ „Reprezentowanie porażki za pomocą monady Maybe” .
  11. ^ "Klasa MonadPlus" .