Saltar a: navegación, buscar

Algoritmos no determinísticos

Algoritmos no determinísticos
Información sobre la plantilla
Tiles Scrambled.jpg
Concepto:Algoritmo que con la misma entrada ofrece muchos posibles resultados
Algoritmo no determinístico. En Ciencias de la computación, 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.

Fuente

Véase también