Algoritmo no determinista

En informática y programación informática , un algoritmo no determinista es un algoritmo que, incluso para la misma entrada, puede exhibir comportamientos diferentes en diferentes ejecuciones, a diferencia de un algoritmo determinista .

Diferentes modelos de cálculo dan lugar a diferentes razones por las que un algoritmo puede ser no determinista y a diferentes formas de evaluar su rendimiento o corrección:

• Un algoritmo concurrente puede funcionar de manera diferente en distintas ejecuciones debido a una condición de carrera . Esto puede suceder incluso con un algoritmo de un solo subproceso cuando interactúa con recursos externos. En general, se considera que un algoritmo de este tipo funciona correctamente solo cuando todas las ejecuciones posibles producen los resultados deseados.
• El comportamiento de un algoritmo probabilístico depende de un generador de números aleatorios llamado por el algoritmo. Estos se subdividen en algoritmos de Las Vegas , para los cuales (al igual que los algoritmos concurrentes) todas las ejecuciones deben producir un resultado correcto, y algoritmos de Monte Carlo, a los que se les permite fallar o producir resultados incorrectos con baja probabilidad. El rendimiento de un algoritmo de este tipo a menudo se mide de forma probabilística, por ejemplo, utilizando un análisis de su tiempo esperado .
• En la teoría de la complejidad computacional , el no determinismo se modela a menudo utilizando un mecanismo explícito para hacer una elección no determinista, como en una máquina de Turing no determinista . Para estos modelos, se considera que un algoritmo no determinista funciona correctamente cuando, para cada entrada, existe una ejecución que produce el resultado deseado, incluso cuando otras ejecuciones producen resultados incorrectos. Este poder existencial hace que los algoritmos no deterministas de este tipo sean más eficientes que los algoritmos deterministas conocidos para muchos problemas. El problema P versus NP encapsula esta mayor eficiencia conjeturada disponible para los algoritmos no deterministas. Los algoritmos de este tipo se utilizan para definir clases de complejidad basadas en la complejidad temporal y espacial no determinista . Pueden simularse utilizando programación no determinista , un método para especificar algoritmos no deterministas y buscar las opciones que conducen a una ejecución correcta, a menudo utilizando una búsqueda de retroceso .

La noción de no determinismo fue introducida por Robert W. Floyd en 1967. ^[1]

• Cormen, Thomas H. (2009). Introducción a los algoritmos (3.ª ed.). MIT Press. ISBN 978-0-262-03384-8.
• "Algoritmo no determinista". Instituto Nacional de Estándares y Tecnología . Consultado el 7 de julio de 2013 .
• "Algoritmos no deterministas". New York University Computer Science . Consultado el 7 de julio de 2013 .