Algoritmo determinístico
De Wikipedia, la enciclopedia libre
En Ciencias de la computación, un algoritmo determinístico es un algoritmo que en términos informales: es completamente predictivo si se conocen las entradas al mismo. 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.
Tabla de contenidos |
[editar] Definición formal
Formalmente los algoritmos deterministicos 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 determistica comenzará la ejecución de la secuencia de estados predeterminados. Es de notar que 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 se pueden incluir en máquinas de Turing determinsiticas y los autómatas finitos determinísticos.
[editar] ¿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 por esta razón a los algoritmos deterministicos se les denomina purely functional.
[editar] Problemas con los algoritmos determinísticos
Desafortunadamente 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 deterministica, pero no se ha encontrado aún un algoritmo eficientes para esta tarea, al menos ahora sólo encuentran soluciones aproximadas en casos especiales.
Otro problema sobre el planteamiento de algoritmos determinsiticos es que a veces no es "deseable" que los resultados sean completamente predecibles. Por ejemplo, si se es un jugador que juega al blackjack un algoritmo puede mezclar una serie de Generador de números pseudoaleatorios 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 pseudo-aleatorio.
