Algoritmo determinista

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

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.

Los algoritmos deterministas pueden definirse en términos de una máquina de estados : un estado describe lo que está haciendo una máquina 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 que ingresamos 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 punto, su estado actual determina cuál será su próximo estado; su curso a través del conjunto de estados está predeterminado. Nótese que una máquina puede ser determinista y aún así nunca detenerse o terminar, y por lo tanto no entregar un resultado.

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

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

• Si utiliza un estado externo distinto de la entrada, como una entrada de usuario, una variable global , un valor de temporizador de hardware, un valor aleatorio o datos de disco almacenados.
• Si funciona de una manera sensible al tiempo, por ejemplo, si tiene varios procesadores escribiendo 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 forma inesperada.

Aunque los programas reales rara vez son puramente deterministas, es más fácil para los humanos y para otros programas razonar sobre programas que sí lo son. Por este motivo, la mayoría de los lenguajes de programación , y especialmente los lenguajes de programación funcional , hacen un esfuerzo por evitar que los eventos anteriores ocurran excepto en 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. ^{[1] [2]} Se han propuesto varias herramientas para ayudar a lidiar con los desafíos ^{[3] [4] [5] [6]} para lidiar con los bloqueos y las condiciones de carrera .

En algunos casos, resulta ventajoso que un programa presente un comportamiento no determinista. El comportamiento de un programa de barajado de 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 un barajado. Un jugador astuto podría adivinar con precisión los números que elegirá el generador y así determinar todo el contenido de la baraja con antelación, lo que le permitiría 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 que es distribuido por ASF Software, Inc, lo que les permite predecir de forma consistente el resultado de las manos con antelación. ^[7] Estos problemas se pueden evitar, en parte, mediante el uso de un generador de números pseudoaleatorios criptográficamente seguro , pero sigue siendo necesario que se utilice 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 de hardware .

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

El lenguaje de programación lógico-funcional Mercury establece diferentes categorías de determinismo para los modos de predicado como se explica en la referencia. ^{[8] [9]}

Haskell proporciona varios mecanismos:

• No determinismo o noción de fracaso
  • Los tipos Quizás y Cualquiera incluyen la noción de éxito en el resultado.
  • El método fail de la clase Monad, puede usarse para señalar el fail como excepción.
  • La mónada Maybe y el transformador de mónada MaybeT permiten cálculos fallidos (detienen la secuencia de cálculo y devuelven Nothing) ^[10]
• Neterminismo/no determinismo con múltiples soluciones
  • Puede recuperar todos los resultados posibles de un cálculo de resultados múltiples, envolviendo su tipo de resultado en una mónada MonadPlus . (su método mzero hace que un resultado falle y mplus recopila los resultados exitosos). ^[11]

Como se ve en Standard ML , OCaml y Scala

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

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

• Algoritmo aleatorio