Algoritmo determinista

En ciencias de la computació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 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 determinista es la función matemática, pues esta extrae siempre la misma salida para una entrada dada. 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

Formalmente 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 abstractas deterministas son las máquinas de Turing deterministas y los autómatas finitos deterministas.

Other Languages