In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation 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.
One simple model for deterministic algorithms is the mathematical function; just as a function always produces the same output given a certain input, so do deterministic algorithms. The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function The difference is that algorithms describe precisely how the output is obtained from the input, whereas abstract functions may be defined implicitly.
Contents |
Formal definition
Formally, 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, as long as we can predict with certainty what states it will pass through.
Examples of particular abstract machines which are deterministic include the deterministic Turing machine and deterministic finite automaton. An abstract machine, also called an abstract computer, is a theoretical model of a Computer hardware or software system used in Automata theory. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm In the Theory of computation, a deterministic finite state machine (also known as deterministic finite state automaton (DFSA or deterministic finite
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. A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and Because of the way such restrictions enforce determinism, deterministic algorithms are sometimes called purely functional. Purely functional is a term in Computing used to describe Algorithms Data structures or Programming languages that exclude destructive modifications
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 but have a very small chance of being wrong. A randomized algorithm or probabilistic algorithm is an Algorithm which employs a degree of randomness as part of its logic These have been known since the 1970s (see for example Fermat primality test); the known deterministic algorithms remain considerably slower in practice. The Fermat primality test is a probabilistic test to determine if a number is probably prime.
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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In Theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers 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. Blackjack (also known as Twenty-one, Vingt-et-un (French for Twenty-one or Pontoon) is the most widely played casino banking A pseudorandom number generator ( PRNG) is an Algorithm for generating a sequence of numbers that approximates the properties of random numbers [1] Similar problems arise in cryptography, where private keys are often generated using such a generator. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" This sort of problem is generally avoided using a cryptographically secure pseudo-random number generator. A cryptographically secure pseudo-random number generator ( CSPRNG) is a Pseudo-random number generator (PRNG with properties that make it suitable for use in
References
- ^ 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
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic