El Algoritmo determinista

Introducción

Un algoritmo determinista 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 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 determinista es la función matemática, pues esta extrae siempre la misma salida para una entrada. No obstante un algoritmo describe explícitamente cómo la salida se obtiene de la entrada, mientras que las funciones definen implícitamente su salida.

Definición formal

Los algoritmos deterministas se pueden definir en términos de una máquina de estado; un estado describe qué 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 determinista, comenzará la ejecución de la secuencia de estados predeterminados. Una máquina puede ser determinista y no tener límite temporal para la ejecución o quedarse en un bucle de estados cíclicos eternamente.

Ejemplos de máquinas deterministas son las máquinas de Turing deterministas y los autómatas finitos deterministas.

Condiciones para que un algoritmo pueda volverse no determinista

Por diversos motivos un algoritmo determinista puede comportarse de una forma no determinista:

• Si emplea en la ejecución de la secuencia de estados otro estado «externo» como entrada del proceso; 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.
• 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 deterministas, es conveniente considerar que sí lo son ya que es más fácil razonar sobre estos.

Problemas con algoritmos deterministas

Para algunos problemas es difícil implementar un algoritmo determinista. Por ejemplo, existen eficientes y simples algoritmos probabilistas 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 los1970 (por ejemplo, el test de primalidad de Fermat); sin embargo tuvieron que pasar 30 años para que se desarrollara un algoritmo determinista similar que fuera asintóticamente igual de rápido.

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 determinista.

Otro problema sobre el planteamiento de algoritmos deterministas es que a veces no es deseable que los resultados sean completamente predecibles. Por ejemplo, en un juego on-line de blackjack que utiliza un generador pseudoaleatorio de números para barajar las cartas, un jugador astuto podría determinar con exactitud los números que el generador fuera a elegir y por consiguiente averiguar el contenido del mazo antes de tiempo.