Algoritmo determinista - Deterministic algorithm

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

Definicion formal

Los algoritmos deterministas se pueden definir 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 forma 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 punto, 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 aún así no detenerse ni terminar nunca y, por lo tanto, no puede producir un resultado.

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

¿Qué hace que los algoritmos no sean 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 la entrada del usuario, una variable global , un valor de temporizador de hardware, un valor aleatorio o datos de disco almacenados.
• Si funciona de una manera que depende del tiempo, por ejemplo, si tiene varios procesadores que escriben en 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 hace que su estado cambie de forma inesperada.

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

La prevalencia de procesadores de múltiples núcleos ha dado lugar a 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 lidiar con los desafíos para lidiar con los puntos muertos 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 de barajado de cartas utilizado en un juego de blackjack , por ejemplo, no debería ser predecible por 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 todo el contenido de la baraja con anticipación, lo que le permitirá hacer trampa; por ejemplo, el Grupo de Seguridad de Software en Reliable Software Technologies pudo hacer esto para una implementación de Texas Hold 'em Poker que es distribuida por ASF Software, Inc, lo que les permite predecir consistentemente el resultado de las manos con anticipación. Estos problemas pueden evitarse, 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 ello, se requiere una fuente de no determinismo, como la proporcionada por un generador de números aleatorios de hardware .

Tenga en cuenta que una respuesta negativa al problema P = NP no implicaría que los programas con salida no determinista sean teóricamente más poderosos 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 verificador .

Categorías de determinismo en idiomas

Mercurio

Este lenguaje de programación lógico-funcional establece diferentes categorías de determinismo para los modos de predicado como se explica en la referencia.

Haskell

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 de falla de la clase Monad, se puede utilizar para señalar una falla como excepción.
• el transformador de mónada Maybe y MaybeT proporcionan cálculos fallidos (detenga la secuencia de cálculo y devuelva Nada)

determinismo / no det 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).

Familia de AA y lenguajes derivados

Como se ve en Standard ML , OCaml y Scala

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

Java

• El valor de referencia nulo puede representar un resultado fallido (fuera del dominio).

Ver también

• Algoritmo aleatorizado

Referencias