Content deleted Content added
Line 63:
There are many algorithms that may make an arbitrary choice at some point that are not considered nondeterministic by any source I'm aware of. In nearly any search, there is a choice of which node to visit next, but that does not make the search nondeterministic. In quicksort, any element may be chosen as the partition, but that does not make quicksort nondeterministic. According to [[CLRS]], a multithreaded algorithm is nondeterministic if its behavior might vary from run to run. That is, the algorithm makes a choice, and '''on different runs that choice may differ'''. In other words, the exact behavior of the algorithm cannot be ''determined'' ahead of time. I will rework this article entirely unless someone can come up with a source that contains a different definition. -- [[User:Schapel|Schapel]] ([[User talk:Schapel|talk]]) 17:08, 16 August 2011 (UTC)
* I am not sure if you reworked it but this presentation seems completely wrong. Two of the references get it right with one reference claiming: (A nondeterministic algorithm is) " A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It is not random, as in randomized algorithm, or indeterminate. Rather it has the supercomputational characteristic of choosing the optimal behavior."
* Can we please copy that definition. Nondeterministic algorithms don't really have physical counterparts as in algorithms with choice points which choose a progression. Rather, they are used in studies of conceptual algorithms and formal verification. I.e., they are convenient in providing specifications. A (deterministic) sorting algorithm is equivalent to its nondeterministically specified algorithm which simply chooses the right ordered sequence. Typically, a nondeterministic algorithm doesn't have a direct computational interpretation which seems to be the source of all the confusion here. Providing a definition as if it has a computational interpretation completely misses the point.
* The introduction is not 80% correct, it is completely wrong. This article needs a rewrite. [[Special:Contributions/86.82.44.193|86.82.44.193]] ([[User talk:86.82.44.193|talk]]) 14:01, 5 July 2015 (UTC)
| |||