Algoritmo determinista

En informática, un algoritmo determinista es un algoritmo que, dada una entrada particular, siempre producirá la misma salida, con la máquina subyacente siempre pasando por la misma secuencia de estados. Los algoritmos deterministas son, con diferencia, el tipo de algoritmo más estudiado y familiar, así como uno de los más prácticos, ya que pueden ejecutarse eficientemente en máquinas reales.

Formalmente, un algoritmo determinista calcula una función matemática; una función tiene un valor único para cualquier entrada en su dominio y el algoritmo es un proceso que produce este valor particular como salida.

Definición formal

Los algoritmos deterministas se pueden definir en términos de una máquina de estados: un estado describe lo que una máquina está haciendo en un instante particular en el tiempo. Las máquinas de estados pasan de manera discreta de un estado a otro. Justo después de ingresar la entrada, la máquina está en su estado inicial o estado de inicio. Si la máquina es determinista, esto significa que a partir de este momento su estado actual determina cuál será su próximo estado; su curso a través del conjunto de estados está predeterminado. Tenga en cuenta que una máquina puede ser determinista y aun así nunca detenerse ni terminar y, por lo tanto, no ofrecer un resultado.

Ejemplos de máquinas abstractas particulares que son deterministas incluyen la máquina determinista de Turing y el autómata finito determinista.

Algoritmos no deterministas

Una variedad de factores pueden hacer que un algoritmo se comporte de una manera que no sea determinista o no determinista:

• Si utiliza un estado externo que no sea la entrada, como entrada de usuario, una variable global, un valor de temporizador de hardware, un valor aleatorio o datos de disco almacenados.
• Si opera de una manera que es sensible al tiempo, por ejemplo, si tiene varios procesadores escribiendo a los mismos datos al mismo tiempo. En este caso, el orden preciso en el que cada procesador escribe sus datos afectará el resultado.
• Si un error de hardware provoca que su estado cambie de manera inesperada.

Aunque los programas reales rara vez son puramente deterministas, es más fácil para los humanos y otros programas razonar sobre los programas que lo son. Por esta razón, la mayoría de los lenguajes de programación y especialmente los lenguajes de programación funcionales se esfuerzan por evitar que ocurran los eventos anteriores, excepto bajo condiciones controladas.

La prevalencia de procesadores multinúcleo ha resultado en un aumento del interés en el determinismo en la programación paralela y los desafíos del no determinismo han sido bien documentados. Se han propuesto una serie de herramientas para ayudar a afrontar los desafíos para hacer frente a los estancamientos y las condiciones de carrera.

Desventajas del determinismo

En algunos casos, es ventajoso que un programa muestre un comportamiento no determinista. El comportamiento de un programa para barajar cartas utilizado en un juego de blackjack, por ejemplo, no debería ser predecible para los jugadores, incluso si el código fuente del programa es visible. El uso de un generador de números pseudoaleatorios a menudo no es suficiente para garantizar que los jugadores no puedan predecir el resultado de una mezcla. Un jugador inteligente podría adivinar con precisión los números que elegirá el generador y así determinar de antemano todo el contenido de la baraja, lo que le permitirá hacer trampa; por ejemplo, el grupo de seguridad de software de Reliable Software Technologies pudo hacer esto para una implementación de Texas Hold'em Poker distribuida por ASF Software, Inc, lo que les permitió predecir consistentemente el resultado de las manos con anticipación. Estos problemas se pueden evitar, en parte, mediante el uso de un generador de números pseudoaleatorios criptográficamente seguro, pero aún es necesario utilizar una semilla aleatoria impredecible para inicializar el generador. Para este propósito, se requiere una fuente de no determinismo, como la proporcionada por un generador de números aleatorios por hardware.

Tenga en cuenta que una respuesta negativa al problema P=NP no implicaría que los programas con resultados no deterministas sean teóricamente más poderosos que aquellos con resultados deterministas. La clase de complejidad NP (complejidad) se puede definir sin ninguna referencia al no determinismo utilizando la definición basada en verificadores.

Categorías de determinismo en idiomas

Mercurio

El lenguaje de programación funcional lógico de mercurio establece diferentes categorías de determinismo para modos de predicados como se explica en la referencia.

Haskell

Haskell proporciona varios mecanismos:

• No determinación o noción del fracaso
  • el Tal vez y Cualquiera los tipos incluyen la noción de éxito en el resultado.
  • el falla método de la clase Monad, se puede utilizar para indicar falla como excepción.
  • el transformador tal vez monad y tal vezT monad proporcionan computaciones fallidas (parar la secuencia de computación y no devolver nada)
• Neterminism/non-det con múltiples soluciones
  • puede recuperar todos los resultados posibles de una computación de resultados múltiples, envolviendo su tipo de resultado en una monada MonadPlus. (su método mzero hace fracasar el resultado y mplus recopila los resultados exitosos).

Familia ML y lenguajes derivados

Como se ve en Standard ML, OCaml y Scala

• El Opción tipo incluye la noción de éxito.

Java

En Java, el valor de referencia nulo puede representar un resultado fallido (fuera del dominio).