Deterministický a nedeterministický algoritmus

Zpráva

Velous · #1 Příspěvek od **Velous** » 07 led 2013, 13:03

Zdravím,

chci se vás zeptat. Jaký je rozdíl mezi deterministickým a nedeterministickým algoritmem?
Mám pravdu, když řeknu, že deterministický algoritmus dává pro stejné vstupy stejné výstupy, kdežto nedeterministický algoritmus dává pro různé vstupy různé výstupy? Díky.

p32 · #2 Příspěvek od **p32** » 07 led 2013, 13:36

Deterministický algoritmus je algoritmus, který na stejný vstup (resp. na stejné výchozí podmínky) reaguje vždy stejně (tedy předvídatelně) a v každém jeho kroku je vždy jednoznačně definován i krok následující.

Jeho opakem je nedeterministický algoritmus.

#3 Příspěvek od **Zaky** » 07 led 2013, 14:59

Typický systém založený na nedeterministických algoritmech je žena :-)

p32 · #4 Příspěvek od **p32** » 07 led 2013, 16:41

Nedeterministický algoritmus proti ženě se počítá jako deterministický algoritmus ! :lol:

#5 Příspěvek od **mtajovsky** » 07 led 2013, 19:19

Velous píše:Zdravím,

chci se vás zeptat. Jaký je rozdíl mezi deterministickým a nedeterministickým algoritmem?

Nechtěl jste spíš vědět rozdíl mezi deterministickým a heuristickým algoritmem?

Ten první se snaží přesným postupem dostat exaktní výsledky. Jenže pro velkou množinu složitých problémů to není dobrý postup vzhledem ke složitosti, která často roste kvadraticky nebo exponenciálně s lineárně narůstajícím počtem vstupů a má tak potenciální nerealizovatelnost. A zde přichází na řadu heuristický postup, který dává výsledky přesné jen s určitou pravděpodobností. Davá dostatečně přesné výsledky, které však nelze obecně dokázat. Výhodou je malá časová náročnost. Naopak výhodou deterministického algoritmu je to, že lze dokázat, že dal přesný výsledek, respektive se prokáže, že obecně dává přesné výsledky. Jeho konkrétní výsledky se pak automaticky považují za přesné bez dalšího dokazování.

#6 Příspěvek od **Cust** » 08 led 2013, 08:02

http://cs.wikipedia.org/wiki/Nedeterministický_algoritmus

Heuristika s tím nebude mít mnoho společného, ta je podle mne deterministická...

p32 · #7 Příspěvek od **p32** » 08 led 2013, 09:22

To už je snad v druhém příspěvku. :lol:

#8 Příspěvek od **Cust** » 08 led 2013, 09:37

Ve druhém příspěvku je kopie tohoto:
http://cs.wikipedia.org/wiki/Deterministický_algoritmus

p32 · #9 Příspěvek od **p32** » 08 led 2013, 10:03

Aha, měl jsem dojem že to ukazuje na stejné, špatně čtu. :wink:

Habesan · #10 Příspěvek od **Habesan** » 08 led 2013, 11:27

Já měl dojem, že oba články na sebe navzájem odkazují, a oba jsou k ničemu.

Není příkladem Deterministického algoritmu PC Translator, a příkladem Nedeterministického algoritmu Google Translator ???