Deterministični algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Determinističen algoritem je algoritem, ki se obnaša predvidljivo. Ko sprejme vhodni podatek, vedno poišče isto rešitev in stroj ali program, s katerim je algoritem implementiran, vedno opravi enako zaporedje operacij. Deterministični algoritmi so najbolj raziskovani in najbolj praktični algoritmi, ker jih lahko učinkovito implementiramo.

Deterministične algoritme lahko natančno definiramo v jeziku avtomatov: stanje opisuje, kaj avtomat dela v določenem trenutku. Takoj po tem, ko vnesemo vhodni podatek, je avtomat v začetnem stanju. Če je avtomat determinstičen, to pomeni, da od te točke naprej njegovo trenutno stanje natančno določa njegovo naslednje stanje; njegov potek prehodov med stanji je vnaprej določen. Avtomat je lahko determinističen, a se vseeno nikoli ne ustavi.

Primera determinističnih avtomatov sta deterministični Turingov stroj in deterministični končni avtomat.

Osebna orodja