Tabla de contenido:
- Definición: ¿Qué significa el algoritmo no determinista?
- Techopedia explica el algoritmo no determinista
Definición: ¿Qué significa el algoritmo no determinista?
Un algoritmo no determinista puede proporcionar diferentes salidas para la misma entrada en diferentes ejecuciones. A diferencia de un algoritmo determinista que produce una sola salida para la misma entrada, incluso en diferentes ejecuciones, un algoritmo no determinista viaja en varias rutas para llegar a los diferentes resultados.
Los algoritmos no deterministas son útiles para encontrar soluciones aproximadas, cuando una solución exacta es difícil o costosa de obtener utilizando un algoritmo determinista.
Techopedia explica el algoritmo no determinista
Un ejemplo de algoritmo no determinista es la ejecución de algoritmos concurrentes con condiciones de carrera, que pueden exhibir diferentes salidas en diferentes carreras. A diferencia de un algoritmo determinista que recorre un solo camino desde la entrada hasta la salida, un algoritmo no determinista puede tomar muchos caminos, algunos llegando a las mismas salidas y otros llegando a diferentes salidas. Esta característica se usa matemáticamente en modelos de cálculo no deterministas como el autómata finito no determinista.
Un algoritmo no determinista es capaz de ejecutarse en una computadora determinista que tiene un número ilimitado de procesadores paralelos. Un algoritmo no determinista generalmente tiene dos fases y pasos de salida. La primera fase es la fase de adivinanzas, que utiliza caracteres arbitrarios para ejecutar el problema.
La segunda fase es la fase de verificación, que devuelve verdadero o falso para la cadena elegida. Hay muchos problemas que pueden conceptualizarse con la ayuda de algoritmos no deterministas, incluido el problema no resuelto de P vs NP en la teoría de la computación.
Los algoritmos no deterministas se utilizan para resolver problemas que permiten múltiples resultados. Cada resultado que produce el algoritmo no determinista es válido, independientemente de las elecciones realizadas por el algoritmo durante la ejecución.
