Deterministic algorithm

Deterministic algorithm

In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.

Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any given input, and the algorithm is a process that produces this particular value as output.

Contents

Formal definition

Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.

Examples of particular abstract machines which are deterministic include the deterministic Turing machine and deterministic finite automaton.

What makes algorithms non-deterministic?

A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:

  • If it uses external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data.
  • If it operates in a way that is timing-sensitive, for example if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.
  • If a hardware error causes its state to change in an unexpected way.

Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most programming languages and especially functional programming languages make an effort to prevent the above events from happening except under controlled conditions.

The prevalence of multi-core processors has resulted in a surge of interest in determinism in parallel programming and challenges of non-determinism have been well documented.[1][2] A number of tools to help deal with the challenges have been proposed[3][4][5][6][7] to deal with deadlocks and race conditions.

Problems with deterministic algorithms

Unfortunately, for some problems deterministic algorithms are also hard to find. For example, there are simple and efficient probabilistic algorithms that determine whether a given number is prime and have a very small chance of being wrong. These have been known since the 1970s (see for example Fermat primality test); the known deterministic algorithms remain considerably slower in practice.

As another example, NP-complete problems, which include many of the most important practical problems, can be solved quickly using a machine called a nondeterministic Turing machine, but efficient practical algorithms have never been found for any of them. At best, we can currently only find approximate solutions or solutions in special cases.

Another major problem with deterministic algorithms is that sometimes, we don't want the results to be predictable. For example, if you are playing an on-line game of blackjack that shuffles its deck using a pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold 'em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.[8] Similar problems arise in cryptography, where private keys are often generated using such a generator. This sort of problem is generally avoided using a cryptographically secure pseudo-random number generator.

References

  1. ^ Edward A. Lee. "The Problem with Threads". http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf. Retrieved 2009-05-29. 
  2. ^ James Reinders. "Parallel terminology definitions". http://intel.zdnet.co.uk/parallelism/?id=260632239. Retrieved 2009-05-29. 
  3. ^ "Intel Parallel Inspector Thread Checker". http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/. Retrieved 2009-05-29. 
  4. ^ Yuan Lin. "Data Race and Deadlock Detection with Sun Studio Thread Analyzer". http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf. Retrieved 2009-05-29. 
  5. ^ Intel. "Intel Parallel Inspector". http://software.intel.com/en-us/intel-parallel-inspector. Retrieved 2009-05-29. 
  6. ^ David Worthington. "Intel addresses development life cycle with Parallel Studio". http://sdtimes.com/link/33497. Retrieved 2009-05-26. 
  7. ^ Parallel Studio
  8. ^ Gary McGraw and John Viega. Make your software behave: Playing the numbers: How to cheat in online gambling. http://www.ibm.com/developerworks/library/s-playing/#h4

Wikimedia Foundation. 2010.

См. также в других словарях:

  • Deterministic system — In mathematics, a deterministic system is a system in which no randomness is involved in the development of future states of the system.[1] A deterministic model will thus always produce the same output from a given starting condition or initial… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… …   Wikipedia

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

  • Deterministic encryption — A deterministic encryption scheme (as opposed to a probabilistic encryption scheme) is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

  • Nondeterministic algorithm — In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A… …   Wikipedia

  • Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list …   Wikipedia

  • Deutsch–Jozsa algorithm — The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992[1] with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998.[2] Although it is of little practical use …   Wikipedia

  • Deutsch-Jozsa algorithm — The Deutsch Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca in 1998.cite journal author = David Deutsch and Richard Jozsa title =… …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»