Algoritmo no determinista
- Algoritmo no determinista
-
En Ciencias de la computación, un algoritmo no determinístico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinístico.
Uso
En la teoría estándar de la computación la definición de algoritmo deja en claro que de por sí un algoritmo es determinístico.
Sin embargo, los algoritmos no determinísticos emplean modelos de computación tales como la Máquina de Turing probabilística, que no son determinísticos. Se considera entonces que los algoritmos no determinísticos son un caso especial.
Convirtiendo algoritmos no determinísticos en determinísticos
Una forma de simular algoritmos no determinísticos N mediante el empleo de otros deterministícos D puede realizarse tratando los estados de N como estados de D. Esto significa que D puede tracear todas las posibilidades y trayectorias de ejecución del algoritmo N.
Otra posibilidad es emplear algoritmos de generación de números aleatorios que consisten en perturbar los estados mediante el establecimiento de todas las posibilidades mediante un generador de números aleatorios. El resultado es un algoritmo determinístico probabilístico.
Véase también
- Algoritmo pro determinístico
Wikimedia foundation.
2010.
Mira otros diccionarios:
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 … Wikipedia Español
Algoritmo cuántico — Transformada de Fourier cuántica sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase. Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación… … Wikipedia Español
Algoritmo probabilista — Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos… … Wikipedia Español
Algoritmo de Floyd-Warshall — En informática, el algoritmo de Floyd Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de… … Wikipedia Español
Algoritmo de Boruvka — Contenido 1 Historia 2 Algoritmo 3 Complejidad 4 Otros algoritmos 5 Referencias … Wikipedia Español
Libreta de un solo uso — Extracto de una libreta de un solo uso. En criptografía, la libreta de un solo uso (del inglés one time pad) es un algoritmo de cifrado por el que el texto en claro se combina con una clave aleatoria o «libreta» igual de larga que el texto en… … Wikipedia Español
ESPACIOP — Saltar a navegación, búsqueda En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial (S(n) … Wikipedia Español
PSPACE — En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial ( ) y tiempo ilimitado. La definición no depende del… … Wikipedia Español
Criptosistema Rabin — Saltar a navegación, búsqueda El criptosistema de Rabin es una técnica criptográfica asimétrica cuya seguridad, al igual que RSA, se basa en la complejidad de la factorización. Sin embargo, la ventaja del criptosistema de Rabin es que se ha… … Wikipedia Español
Número pseudoaleatorio — Se ha sugerido que este artículo o sección sea fusionado con Secuencia pseudoaleatoria (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. Un número pseudo aleatorio es un número generado en un… … Wikipedia Español
