What is a deterministic and non-deterministic algorithm?

Deterministic algorithm is what always produces the same result given certain data inputs.

Most algorithms are deterministic. Still good:)

That's why algorithms do not always reproduce the problems of the world well. The 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 being a tool to reproduce the real world is fundamentally wrong.

Nondeterministic algorithm is one that can produce different results even with the same data entered.

This is common because any algorithm that depends on external data, such as time, competition or hardware failure, for example, possibly or certainly will produce a different result.

The most obvious examples are those that take the computer time at the time of execution, those that use random number generators, those with inherently probabilistic characteristics.

But there are less obvious cases, such as those that depend on data that can not be well graded. As the name itself says, when it is not possible to determine what to do, the result may be different. A sort algorithm that runs on a roll of data that has exact duplicates should classify them as? Is there a way to determine this? There are algorithms that can not.

An algorithm that reads files, networks, or other forms (at a low level) is indeterministic. It is not known what will come of this reading. What will be done with the data read (higher level), possibly will be deterministic, since they happen to be an entry of new algorithms. These algorithms do not know what they will find there, they are external data, they may have been modified by other sources. Then looking at a higher level the reading algorithm will be deterministic.

The garbage collector is one of the most famous indeterminism of computing. As much as 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 triggers it. It depends on many factors, some of which are not under application control.

Note that indeterminism is not the same as random. It does not mean that anything will necessarily happen, only that it can not be determined.

Yes, you can deploy them in any language. A few avoid, or at least attempt to isolate, the use of indeterministic ones. But there's no getting away from them in most problems.

A deterministic algorithm is one that behaves in the same way in different runs, given the same inputs and the same internal state of the machine (if relevant). A non-deterministic one would be one that can behave differently in the same situation.

Computers are deterministic. Except for some hardware failure (introducing a bug in the program), any implementation of any algorithm on a classical (non-quantum) computer will be deterministic, even if its output or behavior seems "chaotic" to our eyes. It is even possible to prove that a nondeterministic Turing Machine is equivalent to a deterministic (ie, 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 nondeterministic. A common criterion for differentiating them is whether they depend on some random power in their execution - although in practice this factor is given by a pseudo-random (hence deterministic) number generator and / or some external input. For even if the algorithm uses a different approach (eg, to simulate all possible execution paths) at the time of choose one it will need some criteria to do so.

  

What are the characteristics of both?

  

Is it possible to implement both in any language?

Yes, 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 non-deterministic algorithm.

  

If possible, exemplify with some implementation

A classic example is quicksort with random pivot: you choose any element from the list, you move all the smaller elements behind it, and all the bigger elements forward. Then the algorithm is called recursively in the first and second parts, until one of them contains only zero or one element.

(Note that in the absence of duplicate elements, the output of the algorithm is always the same, random or not; only the behavior of it changes - how many steps were needed to get to the same exit)

Contrast quicksort with arbitrary pivot, which is usually the center element of the list, or the first, or a 1/3 or 2/3 of the way.

There are still cases that do not know an efficient deterministic algorithm to perform a certain function, but a non-deterministic yes. As I commented in the question about quantum computing , a famous case is the "primality test", which receives a number and affirms with X% certainty whether or not he is prime (ie there is 1-X % chance of classifying a compound number as "prime"). A deterministic polynomial algorithm is now known to determine whether a number is prime, but there are still other problems with no solution.

The class of problems that can be solved by a probabilistic algorithm is the BPP ("probabilistic of polynomial time committed to errors "), and it is conjectured that BPP = P . And, of course, how to implement any probabilistic algorithm in a deterministic computer requires an external random factor, these implementations could be called non-deterministic.