Nondeterministic algorithm
From Psychology Wiki
Community portal · Tasks to do · News · Help
Clinical · Educational · Ind&Org · Other fields · Professional · Transpersonal · World
Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language
Personality |
Philosophy |
Research Methods |
Social |
Statistics
Statistics: Scientific method · Research methods · Experimental design · Undergraduate statistics courses · Statistical tests · Game theory · Decision theory
In the theory of computation, a nondeterministic algorithm is an algorithm with one or more choice points where multiple different continuations are possible, without any specification of which one will be taken. A particular execution of such an algorithm picks a choice whenever such a point is reached. Thus, different execution paths of the algorithm arise when it is applied to the same input / initial state, and these paths, when they terminate, generally produce different output / end in different final states.
Contents |
[edit] Use
In the standard theory of computation, the term algorithm stands for a deterministic algorithm. However, it employs models of computation, such as the nondeterministic finite state machine, that use nondeterminism.
In algorithm design, nondeterministic algorithms are often used as specifications.
[edit] Turning nondeterministic algorithms into deterministic ones
One way to simulate a nondeterministic algorithm N using a deterministic algorithm D is to treat sets of states of N as states of D. This means that D simultaneously traces all the possible execution paths of N (see Powerset construction for this technique in use for finite automata).
Another is randomization, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.
[edit] Examples
[edit] Example 1: Spanning tree computation
The input is an undirected connected graph. An undirected graph is a set of nodes that may or may not be pairwise connected with edges. A subgraph of a graph consists of a subset of its nodes and/or edges. A graph connects two nodes if we can walk over its edges from one to the other. A path in a graph is a minimal subgraph connecting two of its nodes. A graph is connected if it connects all of its nodes.
The algorithm: while an edge can be removed such that the graph is still connected, remove such an edge.
The output: a spanning tree, that is, a minimal tree connecting all the nodes.
The result is never uniquely defined (unless the input was a tree already), but always has the same number of edges.
[edit] Example 2: Primality testing
Here is an example of a non-deterministic algorithm for testing if an integer n is prime.
- Guess an integer k such that 2 ≤ k ≤ n-1.
- If k is a divisor of n, stop with answer no; otherwise stop with answer don't know.
It is seen that the algorithm doesn't always give a useful answer, but never gives a wrong answer. Also, it is capable (at least sometimes) of giving a correct useful answer much faster than any deterministic primality algorithm.
| This page uses content from the English-language version of Wikipedia. The original article was at Nondeterministic algorithm. The list of authors can be seen in the page history. As with Psychology Wiki, the text of Wikipedia is available under the GNU Free Documentation License. |
