Algoritmo no determinista

En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la misma entrada ofrece muchos posibles resultados, y por tanto no ofrece una solución única. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinista.

Uso

En la teoría estándar de la computación la definición de algoritmo deja en claro que de por sí un algoritmo es determinista.

Sin embargo, los algoritmos no deterministas emplean modelos de computación tales como la Máquina de Turing probabilística, que no son deterministas. Se considera entonces que los algoritmos no deterministas son un caso especial.

Conversión de algoritmos no deterministas en deterministas

Una forma de simular algoritmos no deterministas N mediante el empleo de otros deterministas D puede realizarse tratando los estados de N como estados de D. Esto significa que D puede trazar todas las posibilidades y trayectorias de ejecución del algoritmo N.

Otra posibilidad es emplear algoritmos de generación de números aleatorios que consisten en perturbar los estados mediante el establecimiento de todas las posibilidades mediante un generador de números aleatorios. El resultado es un algoritmo determinista probabilístico.

Conversión de algoritmos deterministas en no deterministas

El algunas ocasiones, el hecho anterior puede producirse en el sentido inverso de manera que el comportamiento de un algoritmo varie pase a encontrarse en un lugar diferente

En este caso, deben existir una serie de factores que permitan que dicho algoritmo llegue a convertirse en uno no determinista. A continuación se expondrán las causas más importantes:

• El hecho de emplear un estado ajeno durante el proceso de secuenciación de datos (como puede ser la introducción de un dato por parte de un usuario, o la aparición de una nueva variable que no ha sido controlada) y por ello se considera aleatoria.

• Un fallo en el ámbito ya sea del software o hardware puede producir un resultado no previsto tras la ejecución de cada una de las fases.

• Una última causa puede ser que al intentar realizar ciertas operaciones, existan estados concurrentes (hecho que puede darse si se mantienen muchos procesos ejecutándose al mismo tiempo en un solo archivo).Si ocurre algo similar a lo descrito anteriormente podría originarse una salida no deseada por el usuario.

Véase también

• Algoritmo determinista

Esta página se editó por última vez el 23 mar 2021 a las 19:14.