Algoritmo no determinístico
- Algoritmo no determinístico
-
Algoritmo no determinístico
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 determinístico — Saltar a navegación, búsqueda En Ciencias de la computación, un algoritmo determinístico 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… … Wikipedia Español
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… … Wikipedia Español
Algoritmo de Earley — El algoritmo de Earley[1] es un algoritmo no determinístico de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por Jay Earley. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la… … Wikipedia Español
Algoritmo de Thompson — El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no determinístico con transiciones vacías (AFND ε) a partir de expresiones regulares (ER). Algoritmo… … Wikipedia Español
Algoritmo Quine–McCluskey — El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más … Wikipedia Español
Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n … Wikipedia Español
Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número … Wikipedia Español
Compuerta NOT — Se ha sugerido que este artículo o sección sea fusionado con Puerta NOT#Puerta NO (NOT) (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. INPUT OUTPUT A … Wikipedia Español
ALOHAnet — (o simplemente ALOHA) fue un sistema de redes de ordenadores pionero desarrollado en la Universidad de Hawái. Fue desplegado por primera vez en 1970, y aunque la propia red ya no se usa, uno de los conceptos esenciales de esta red es la base para … Wikipedia Español
Unidad de estado sólido — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar … Wikipedia Español
