Diferencia entre algoritmos deterministas y no deterministas

En el algoritmo determinista , para una entrada particular dada, la computadora siempre producirá la misma salida pasando por los mismos estados, pero en el caso del algoritmo no determinista , para la misma entrada, el compilador puede producir una salida diferente en diferentes ejecuciones. De hecho, los algoritmos no deterministas no pueden resolver el problema en tiempo polinomial y no pueden determinar cuál es el siguiente paso. Los algoritmos no deterministas pueden mostrar diferentes comportamientos para la misma entrada en diferentes ejecuciones y existe cierto grado de aleatoriedad.

Para implementar un algoritmo no determinista, tenemos un par de lenguajes como Prolog, pero estos no tienen operadores de lenguaje de programación estándar y estos operadores no forman parte de ningún lenguaje de programación estándar.

Algunos de los términos relacionados con el algoritmo no determinista se definen a continuación :

• choice(X) : elige aleatoriamente cualquier valor del conjunto X.
• fail() : denota la solución fallida.
• éxito(): la solución es exitosa y el hilo actual termina.

Ejemplo :

Declaración del problema: busque un elemento x en A [1: n] donde n> = 1, en una búsqueda exitosa, devuelva j si a [j] es igual a x; de lo contrario, devuelva 0.

Algoritmo no determinista para este problema:

1.j= choice(a, n)
2.if(A[j]==x) then
    {
       write(j);
       success();
    }
3.write(0); failure();

Algoritmo determinista	Algoritmo no determinista
Para una entrada en particular, la computadora siempre dará la misma salida.	Para una entrada en particular, la computadora dará una salida diferente en una ejecución diferente.
Puede resolver el problema en tiempo polinomial.	No se puede resolver el problema en tiempo polinomial.
Puede determinar el siguiente paso de ejecución.	No se puede determinar el siguiente paso de ejecución debido a más de una ruta que puede tomar el algoritmo.