Enciencias de la computación, unalgoritmo determinista es unalgoritmo que, en términos informales, es completamente predictivo si se conocen susentradas. Dicho de otra forma, si se conocen las entradas del algoritmo siempre producirá la mismasalida, 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 lafunció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.
Formalmente los algoritmos deterministas se pueden definir en términos de unamá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 demáquinas abstractas deterministas son lasmáquinas de Turing deterministas y losautómatas finitos deterministas.
Por diversos motivos un algoritmo determinista puede comportarse de una forma no determinista:
Aunque los programas reales rara vez son puramente deterministas, es conveniente considerar que sí lo son ya que es más fácil razonar sobre estos. Por este motivo, la mayoría de loslenguajes de programación y especialmente aquellos que entran dentro de la categoría de laprogramación funcional son lenguajes que hacen un esfuerzo en prevenir eventos que se ejecuten sin control. Este tipo de restricciones fuerzan el carácter determinista y por ello a los algoritmos deterministas se les suele denominar puramente funcionales.
La prevalencia de los procesadores de varios núcleos ha levantado el interés por el determinismo en la programación en paralelo y se han documentado bien los problemas del no determinismo.[1][2]Numerosas herramientas útiles en estos problemas se han propuesto para tratar con losbloqueos mutuos y lascondiciones de carrera.[3][4][5][6][7]
Para algunos problemas es muy difícil implementar un algoritmo determinista. Por ejemplo, existen eficientes y simplesalgoritmos probabilistas que pueden determinar si unnúmero entero esprimo o no, pero tienen una pequeña posibilidad de equivocarse. Algunos de ellos son muy conocidos desde los 1970 (véase, por ejemplo, eltest de primalidad de Fermat); sin embargo tuvieron que pasar 30 años para que se desarrollara un algoritmo determinista similar que fueraasintóticamente igual de rápido (véaseAKS).[8]
Otro ejemplo puede encontrarse en los problemasNP-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 unamáquina de Turing no determinista, pero no se ha encontrado aún un algoritmo eficiente para esta tarea, tan solo soluciones aproximadas para casos especiales.
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 juegoon-line deblackjack que utiliza ungenerador 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. Problemas similares pueden encontrarse encriptografía, donde lasclaves privadas a menudo se crean mediante uno de estos generadores. Este tipo de problemas se evita mediante el empleo de ungenerador de números pseudo-aleatorios criptográficamente seguro.
| Control de autoridades |
|
|---|
Datos:Q1064349