Índice:
- Definição - O que significa Algoritmo Não-Determinístico?
- Techopedia explica algoritmo não determinístico
Definição - O que significa Algoritmo Não-Determinístico?
Um algoritmo não determinístico pode fornecer saídas diferentes para a mesma entrada em diferentes execuções. Ao contrário de um algoritmo determinístico que produz apenas uma única saída para a mesma entrada, mesmo em execuções diferentes, um algoritmo não determinístico viaja em várias rotas para chegar a diferentes resultados.
Algoritmos não determinísticos são úteis para encontrar soluções aproximadas, quando uma solução exata é difícil ou dispendiosa de derivar usando um algoritmo determinístico.
Techopedia explica algoritmo não determinístico
Um exemplo de algoritmo não determinístico é a execução de algoritmos simultâneos com condições de corrida, que podem exibir diferentes saídas em diferentes execuções. Ao contrário de um algoritmo determinístico que viaja um único caminho da entrada à saída, um algoritmo não determinístico pode seguir muitos caminhos, alguns chegando às mesmas saídas e outros chegando a saídas diferentes. Esse recurso é usado matematicamente em modelos de computação não determinísticos, como autômato finito não determinístico.
Um algoritmo não determinístico é capaz de executar em um computador determinístico que possui um número ilimitado de processadores paralelos. Um algoritmo não determinístico geralmente possui duas fases e etapas de saída. A primeira fase é a fase de adivinhação, que faz uso de caracteres arbitrários para executar o problema.
A segunda fase é a fase de verificação, que retorna verdadeiro ou falso para a sequência escolhida. Existem muitos problemas que podem ser conceituados com a ajuda de algoritmos não determinísticos, incluindo o problema não resolvido de P vs NP na teoria da computação.
Algoritmos não determinísticos são usados na resolução de problemas que permitem múltiplos resultados. Todo resultado produzido pelo algoritmo não determinístico é válido, independentemente das escolhas feitas pelo algoritmo durante a execução.
