Deterministický algoritmus - Deterministic algorithm

Ve vědě o počítačích , je deterministický algoritmus je algoritmus , který, vzhledem k tomu, konkrétní vstup, bude vždy produkovat stejný výstup s tím, že základní stroj vždy prochází stejným pořadím států. Deterministické algoritmy jsou zdaleka nejstudovanějším a nejznámějším druhem algoritmu a také jedním z nejpraktičtějších, protože je lze efektivně provozovat na skutečných strojích.

Formálně deterministický algoritmus vypočítává matematickou funkci ; funkce má jedinečnou hodnotu pro jakýkoli vstup ve své doméně a algoritmus je proces, který produkuje tuto konkrétní hodnotu jako výstup.

Formální definice

Deterministické algoritmy lze definovat pomocí stavového stroje : stav popisuje, co stroj dělá v určitém časovém okamžiku. Státní stroje procházejí diskrétním způsobem z jednoho stavu do druhého. Hned poté, co zadáme vstup, je stroj v počátečním stavu nebo v počátečním stavu . Pokud je stroj deterministický, znamená to, že od tohoto bodu jeho aktuální stav určuje, jaký bude jeho další stav; jeho průběh množinou stavů je předem určen. Všimněte si, že stroj může být deterministický a přesto se nikdy nezastaví nebo nedokončí, a proto nedokáže doručit výsledek.

Příklady konkrétních abstraktních strojů, které jsou deterministické, zahrnují deterministický Turingův stroj a deterministický konečný automat .

Proč jsou algoritmy nedeterministické?

Různé faktory mohou způsobit, že se algoritmus bude chovat způsobem, který není deterministický ani nedeterministický:

• Pokud používá jiný externí stav než vstup, například vstup uživatele, globální proměnnou , hodnotu hardwarového časovače, náhodnou hodnotu nebo uložená data na disku.
• Pokud funguje způsobem, který je citlivý na načasování, například pokud má více procesorů zapisujících do stejných dat současně. V tomto případě bude mít na výsledek vliv přesné pořadí, ve kterém každý procesor zapisuje svá data.
• Pokud chyba hardwaru způsobí, že se jeho stav změní neočekávaným způsobem.

Ačkoli skutečné programy jsou zřídka čistě deterministické, je pro lidi i pro jiné programy snazší uvažovat o programech, které existují. Z tohoto důvodu se většina programovacích jazyků a zejména funkčních programovacích jazyků snaží zabránit tomu, aby se výše uvedené události děly, s výjimkou kontrolovaných podmínek.

Prevalence vícejádrových procesorů vedla k nárůstu zájmu o determinismus v paralelním programování a výzvy nedeterminismu byly dobře zdokumentovány. Byla navržena řada nástrojů, které mají pomoci vypořádat se s výzvami, aby se vyrovnaly se zablokováním a závodními podmínkami .

Nevýhody determinismu

V některých případech je výhodné, aby program vykazoval nedeterministické chování. Chování programu míchání karet používaného například ve hře blackjack by nemělo být předvídatelné hráči - i když je viditelný zdrojový kód programu. Použití generátoru pseudonáhodných čísel často nestačí k zajištění toho, aby hráči nebyli schopni předvídat výsledek náhodného zamíchání. Chytrý hazardní hráč by mohl přesně uhodnout čísla, která si generátor vybere, a tak předem určit celý obsah balíčku, což mu umožní podvádět; například skupina Software Security Group ve společnosti Reliable Software Technologies to dokázala pro implementaci Texas Hold 'em Poker distribuovaného společností ASF Software, Inc, což jim umožnilo důsledně předvídat výsledek hand dopředu. Těmto problémům se lze částečně vyhnout použitím kryptograficky zabezpečeného generátoru pseudonáhodných čísel , ale pro inicializaci generátoru je stále nutné použít nepředvídatelné náhodné semeno . Za tímto účelem je vyžadován zdroj nedeterminismu, například zdroj poskytovaný hardwarovým generátorem náhodných čísel .

Negativní odpověď na problém P = NP by neznamenala, že programy s nedeterministickým výstupem jsou teoreticky silnější než programy s deterministickým výstupem. Třídu složitosti NP (složitost) lze definovat bez jakéhokoli odkazu na nedeterminismus pomocí definice založené na ověřovateli .

Kategorie determinismu v jazycích

Rtuť

Tento logicky funkční programovací jazyk stanoví různé kategorie determinismu pro predikátové režimy, jak je vysvětleno v odkazu.

Haskell

Haskell poskytuje několik mechanismů:

nedeterminismus nebo pojem selhání

• že Možná i Bud typy zahrnují ponětí o úspěchu ve výsledku.
• selhání metodou třídy monádě, mohou být použity pro signalizaci selhání jako výjimky.
• Monadový transformátor Možná monad a Možná monad zajišťují neúspěšné výpočty (zastavte výpočetní sekvenci a nevraťte nic)

determinismus/non-det s více řešeními

můžete získat všechny možné výsledky výpočtu více výsledků zabalením jeho typu výsledku do MonadPlus monad . (jeho metoda mzero způsobí selhání výsledku a mplus sbírá úspěšné výsledky).

Rodina ML a odvozené jazyky

Jak je vidět na Standard ML , OCaml a Scala

• Typ možnosti zahrnuje pojem úspěch.

Jáva

• Null Referenční hodnota může představovat výsledek neúspěšné (out-of-domény).

Viz také

• Randomizovaný algoritmus

Reference