26
What is a deterministic and nondeterministic algorithm?
- What are the characteristics of both?
- It is possible to implement both in any language?
NOTE: if possible exemplify with some implementation
2 answers
20
Deterministic algorithm is what always produces the same result given certain data entries.
Most algorithms are deterministic. Thank goodness :)
Therefore, algorithms do not always reproduce the problems of the world well, real problems are usually indeterministic, any attempt to reproduce the real world borders on insanity. It is possible to make a simplified representation of the real problem. Hence the definition of OOP as a tool to reproduce the real world is fundamentally wrong.
Nondeterministic algorithm is the one that can produce different results even with the same input data.
This is common because any algorithm that relies on external data, such as time, competition or hardware failure, for example, will possibly or certainly produce a different result.
The most obvious examples are the ones that take the time of the computer at the time of execution, the ones that use random number generators, which have inherently probabilistic characteristics.
But there are less obvious cases, such as those that depend on data that cannot be well classified. As its name says, when it is not possible to determine what to do the result may be different. A sorting algorithm that runs on a roll of data that have exact duplicities should classify them as? Is there a way to determine this? There are algorithms that cannot.
An algorithm that reads files, networks or other forms (at a low level) are indeterministic, it is not known what will come of this reading, since what will be done with the data read (at a higher level) will possibly be deterministic, since they pass to be an input of new algorithms. These algorithms don’t know what they’ll find there, they’re external data, they may have been modified by other sources. Then looking at a higher level the read algorithm will be deterministic.
The tracing Garbage Collector is one of the most famous indeterminisms of computing. Although the rules are well established, it is not known when it will be fired, it is not known when the algorithm will produce a result that fires it. It depends on many factors, some of them that are not under application control.
Note that determinism is not the same as random. It does not mean that necessarily anything will happen, only that it cannot be determined in advance.
Yes, it is possible to implement them in any language. A few avoid, or at least try to isolate, the use of indeterministics. But there’s no running away from them in most problems.
15
A deterministic algorithm is one that behaves the same way in different runs, given the same inputs and the same internal state of the machine (if relevant). A non-deterministic would be one that can behave differently in the same situation.
The computers are deterministic. Except for some hardware flaw (that would introduce a bug in the program), any implementation of any algorithm on a classic (non-quantum) computer will be deterministic, even if its output or its behavior seems "chaotic" to our eyes. It is even possible to prove that a nondeterministic Turing machine is equivalent to a deterministic (that is, any nondeterministic algorithm could be expressed - and therefore implemented - as a deterministic algorithm).
For this reason, it is difficult to draw a line separating the deterministic from the non-deterministic. A common criterion for differentiating them is whether they depend on any factor random in its execution - even if in practice this factor is given by means of a pseudo-random number generator (therefore deterministic) and/or some external input. For even if the algorithm uses a different approach (e.g., simulating all possible execution paths) at the time of choose one he will need some criterion for such.
What are the characteristics of both ?
The main characteristic of the non-deterministic is that one cannot predict its execution time, memory consumption, etc., even knowing the inputs [other than the random factor]. It’s often hard to do that analytically also for deterministic ones, but at least two executions with the same entries will always result in the same behavior.
It is possible to implement both in any language ?
Yes, because as already mentioned, it is possible to simulate a non-deterministic Turing machine in a deterministic one. If a language is Turing complete, then it can implement any nondeterministic algorithm.
if possible exemplify with some implementation
A classic example is the quicksort with random pivot: choose any element from the list, pass all the elements smaller than it backwards, and all the largest forward. Then the algorithm is called recursively in the first and second part, until one of them contains only zero or an element.
(Note that in the absence of duplicate elements, exit of the algorithm is always the same, random factor or not; only the demeanor of which changes - how many steps it took to reach the same exit)
Contrast quicksort with arbitrary pivot, which is commonly the central element of the list, or the first, or a 1/3 or 2/3 of the path.
There are still cases that one does not know an efficient deterministic algorithm to execute a given function, but a nondeterministic one does. As I commented on question about quantum computing, a famous case is the "primality test", which receives a number and states with X% of certainty whether or not it is prime (i.e. there is 1-X% of chance it classify a composite number as "prime"). Today we already know a deterministic polynomial algorithm to determine whether a number is prime, but there are still other unsolved problems.
The class of problems that can be solved by a probabilistic algorithm is the BPP ("polynomial time probabilistic committed to errors"), and it is conjectured that BPP = P. And of course, as to implement any probabilistic algorithm on a deterministic computer requires an external random factor, these implementations could be called nondeterministic.
Browser other questions tagged algorithm terminology computer-science
You are not signed in. Login or sign up in order to post.
I didn’t quite understand the reading part of file or network. If the same algorithm reads the same byte string more than once (the same file, or the same data trafficked in the network), why would it be nondeterministic?
– bfavaretto
Improved now?
– Maniero
Haskell treats it in an excellent way.
– ptkato
IS, Monads.
– Maniero
Not much improved... The example of reading external data continues to bring some confusion. If the algorithm processes the contents of the file and the file is the same, the outputs will be the same - the algorithm is deterministic. If the file changes, then the algorithm entries have changed - but the algorithm remains deterministic.
– Caffé
@Caffé agrees that the highest-level algorithm is deterministic but the low-level algorithm is not. He tells you to read a position on the disk or he tells you to read what’s on buffer data entry is the request to read something, not the data. Asked to be something, came a thing, then asked again, that something is the same (same position of the disc or buffer, for example), something else comes, because what is there is not control of that algorithm. This is indeterministic. It is external data that cannot be guaranteed. I think the problem there is the interpretation of what data entry is.
– Maniero
@bigown I also found this definition a little too broad. And a generator of pseudo-random numbers, is it deterministic or not? Each time you call, gives a different output, and no input at all... But I would rather call a PRNG deterministic, because its output is determined by its state internal. Similarly, the function it reads from a file depends rather on its state (or, if it receives a stream, on the state of the stream, to which byte of the file it "points"), but this does not make it indeterministic. This is all just my opinion, however, drawing a line between the two is complicated...
– mgibsonbr
@mgibsonbr I tried to improve. The generator may be deterministic, but its use may not be. The stream is already something intermediate, is already something that has as input the data that were present somewhere, there is deterministic even. It all depends on what the data entry is. The confusion is there. That’s my understanding. I agree that drawing the line is not so simple.
– Maniero
With your penultimate comment, I understood what you meant. What is in the comment (what is the input) is clearer than in the reply.
– bfavaretto