Wikia

Psychology Wiki

Nondeterministic algorithm

Talk0
34,140pages on
this wiki
Revision as of 20:54, December 2, 2008 by Drawde83 (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

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.

Use Edit

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.

Turning nondeterministic algorithms into deterministic ones Edit

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.

Examples Edit

Example 1: Spanning tree computation Edit

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.

Example 2: Primality testing Edit

Here is an example of a non-deterministic algorithm for testing if an integer n is prime.

  1. Guess an integer k such that 2 ≤ kn-1.
  2. 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 Creative Commons Licensed content from Wikipedia (view authors).

Around Wikia's network

Random Wiki