Deterministický algoritmus

Deterministický algoritmus je v informatice označení pro algoritmus, který vždy ze stejných výchozích (vstupních) podmínek svým během vytvoří stejné výsledky (je tedy předvídatelný). Každý aktuální i následující krok vykonávání algoritmu je vždy jednoznačně definován, což je rozdíl oproti nedeterministickým algoritmům, kde následující krok nemusí být vždy jednoznačně určen.

Využití determinističnosti je aktuálně předmětem studií v mnoha oborech, především pro možnost praktického a efektivního způsobu použití na dnešních běžných počítačích. Formálně je deterministický algoritmus definován jako algoritmus pro výpočet matematických funkcí, které mají konkrétní hodnotu výstupu pro daný vstup.

Formální definice

Deterministický algoritmus může být definován konečným automatem (stavovým strojem), kde jsou jednoznačně určeny podmínky přechodu mezi vnitřními stavy automatu. Každý stav popisuje stav automatu v konkrétním časovém okamžiku. Stavové automaty procházejí podle předem daných pravidel diskrétním způsobem z jednoho stavu do druhého. Na začátku je vždy automat v počátečním stavu a má dány vstupní hodnoty. Pokud je automat deterministický, jeho aktuální stav určuje skupinu stavů následujících, přičemž je dle přechodové podmínky vybrán vždy právě jeden nový stav. Je důležité mít na paměti, že stroj může být deterministický a zároveň nekonečný, to znamená, že nikdy nebude znám výsledek algoritmu. Příkladem konkrétních abstraktních deterministických strojů je Turingův stroj a deterministické konečné automaty.

Příčiny nedeterminismu

Následující faktory mohou zapříčinit vznik nedeterminismu v deterministickém algoritmu:

• pokud je vstup algoritmu neošetřený na nepřípustné hodnoty – uživatelský vstup, globální proměnná, hodnota hardwarového časovače nebo náhodná hodnota
• pokud je zpracování algoritmu závislé na časování a následné synchronizaci (při paralelním zpracování^[1]) – například vice procesů postupně zapisuje do proměnné, konečný výstup je závislý na pořadí zapsání hodnot
• pokud chyba hardwaru může způsobit přechod mezi stavy nedefinovanou cestou, nebo naopak nekonečné zacyklení algoritmu

I když jsou dnešní programy zřídka kdy čistě deterministické, jsou pro člověka mnohem více pochopitelné. Proto většina programovacích jazyků nabízí možnosti, jak předejít všem výše uvedeným faktorům pro vznik nedeterminismu, kromě kontrolovaných výjimek, které ovšem programátor musí ošetřit.

Problém deterministických algoritmů

Stále jsou aktuálně známé problémy pro které je obtížné najít deterministický algoritmus, který by daný problém vyřešil. Klasickým příkladem je určení, zda je dané číslo prvočíslo. Jako algoritmy pro určení jsou dnes využívány tzv. pravděpodobnostní algoritmy. Jsou známé již od roku 1970 (Fermatův test prvočíselnosti), jsou ovšem v praxi velmi pomalé a neefektivní.

Jako další příklad lze uvést NP-úplné problémy, které zahrnují mnohé z nejdůležitějších praktických problémů. Ty lze teoreticky efektivně řešit pomocí nedeterministických Turingových strojů, ovšem konkrétní praktické (deterministické) algoritmy zatím nalezeny nebyly. V dnešní době lze najít pouze přibližné řešení.

Dalším problém deterministických algoritmů je, že v některých případech požadujeme pravý opak – výsledek zcela nepředvídatelný. Například při karetních hrách (Black Jack), kdy je míchání balíčku realizováno pomocí pseudonáhodného generátoru čísel, je možné po určité době sledování odhadnout přesně se generující řadu čísel a tím pádem i obsah celého balíčku.^[2] Podobné problémy vznikají v kryptografii, kde jsou soukromé klíče často generovány pomocí tohoto generátoru. Těmto druhům problémů se lze obecně vyhnout pomocí kryptograficky bezpečného pseudo-generátoru náhodných čísel.

Reference

V tomto článku byl použit překlad textu z článku Deterministic_algorithm na anglické Wikipedii.