En Ciencias de la computación, un algoritmo determinístico es un algoritmo que, en términos informales, es completamente predictivo si se conocen sus entradas. Dicho de otra forma, si se conocen las entradas del algoritmo siempre producirá la misma salida, y la máquina interna pasará por la misma secuencia de estados. Este tipo de algoritmos ha sido el más estudiado durante la historia y por lo tanto resulta ser el tipo más familiar de los algoritmos, así como el más práctico ya que puede ejecutarse en las máquinas eficientemente.

Un modelo simple de algoritmo determinístico es la función matemática, de esta forma se puede establecer el siguiente paralelismo: la función extrae la misma salida para una entrada dada, al igual que los algoritmos determinísticos. La diferencia es que un algoritmo describe explícitamente como la salida se obtiene de la entrada, mientras que las funciones definen implícitamente su salida.

Definición formal

Formalmente los algoritmos determinísticos se pueden definir en términos de una máquina de estado: un estado describe que está haciendo la máquina en un instante particular de tiempo. Justo cuando se produce la entrada, la máquina comienza en su estado inicial y, posteriormente, si la máquina es determinística, comenzará la ejecución de la secuencia de estados predeterminados. Una máquina puede ser determinística y no tener límite temporal para la ejecución o quedarse en un bucle de estados cíclicos eternamente.

Ejemplos de máquinas abstractas determinísticas son las máquinas de Turing determinísticas y los autómatas finitos determinísticos.

Qué hace a un algoritmo no determinístico

Una variedad de factores puede ser la causa de que un algoritmo determinístico se comporte como de una forma no determinística:

• Si emplea en la ejecución de la secuencia de estados otro estado "externo" como entrada del proceso, como por ejemplo: una entrada de un usuario, una variable objetivo, un valor de un temporizador de hardware, un valor aleatorio, etc.
• Si al operar se encuentra con concurrencia de estados, por ejemplo si tiene múltiples procesadores escribiendo al mismo tiempo en un fichero. En este caso el orden preciso en el que cada procesador escribe el dato puede afectar a la salida y no está pre-planificado su valor inicial.
• Si un error (cuyo origen puede deberse al hardware o al software) causa un inesperado cambio en la secuencia de ejecución de estados.

Aunque los programas reales rara vez son puramente determinísticos, es más fácil que los seres humanos así como otros programas determinar sobre la esencia de lo que realmente son. Por esta razón, la mayoría de los lenguajes de programación y especialmente aquellos que entran dentro de la categoría de programación funcional son lenguajes que hacen un esfuerzo en prevenir eventos que se ejecutan sin control. Por esta razón este tipo de restricciones fuerzan el carácter determinístico, a los algoritmos deterministicos se les denomina purely functional.

Problemas con los algoritmos determinísticos

Para algunos problemas es muy difícil implementar un algoritmo determinístico. Por ejemplo, existen eficientes y simples algoritmos probabilísticos que pueden determinar si un número entero es primo o no, pero tienen una pequeña posibilidad de equivocarse. Algunos de ellos son muy conocidos desde 1970 (véase, por ejemplo, el Test de primalidad de Fermat); solamente tras otros 30 años de investigación focalizada en investigar se ha encontrado un algoritmo determinístico similar, pero mucho más lento.

Otro ejemplo puede encontrarse en los problemas NP-completos. Dentro de esta categoría puede encontrarse la mayoría de los problemas prácticos; este tipo de problemas puede resolverse rápidamente empleando de forma masiva y paralela una máquina de Turing no determinística, pero no se ha encontrado aún un algoritmo eficiente para esta tarea, al menos ahora sólo encuentran soluciones aproximadas en casos especiales.

Otro problema sobre el planteamiento de algoritmos determinísticos es que a veces no es "deseable" que los resultados sean completamente predecibles. Por ejemplo, si se es un jugador de blackjack, un algoritmo puede mezclar una serie de Generador de números seudoaleatorios y, de esta forma, un apostador espabilado podría averiguar los números del generador y determinar las cartas sobre la mesa de juego permitiendo engañar durante todo el tiempo al croupier (esto ocurre actualmente). Problemas similares pueden encontrarse en criptografía, donde las claves privadas a menudo se crean mediante uno de estos generadores. Este tipo de problemas se evita mediante el empleo de un generador criptográfico seguro de números seudoaleatorios.

Véase también

• Algoritmo no determinístico