Nedeterministický algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Nedeterministický algoritmus (= stochastický) je takový algoritmus, který v některých krocích může volit z několika možností dalších kroků. Nedeterministický algoritmus při stejném vstupu může dávat rozdílné výsledky.

Jeho opakem je deterministický algoritmus.

Lze zkoumat množinu všech výsledků nedeterministického algoritmu a určovat

  • zda existuje alespoň jeden výsledek vyhovující zadání. Příkladem tohoto využití je nedeterministický konečný automat.
  • Pravděpodobnost provedení některých kroků algoritmu, pokud jsou známy pravděpodobnosti výběru dalších kroků algoritmu. Problémy tohoto typu zkoumá například teorie hromadné obsluhy.