Definição – O que significa Algoritmo Não Determinístico?
Um algoritmo não determinístico pode fornecer diferentes saídas 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 resultados diferentes.
Algoritmos não determinísticos são úteis para encontrar soluções aproximadas, quando uma solução exata é difícil ou cara de derivar usando um algoritmo determinístico.
Definirtec explica Algoritmo Não Determinístico
Um exemplo de algoritmo não determinístico é a execução de algoritmos concorrentes com condições de corrida, que podem exibir saídas diferentes em execuções diferentes. Ao contrário de um algoritmo determinístico que viaja em um único caminho da entrada à saída, um algoritmo não determinístico pode seguir muitos caminhos, com alguns chegando às mesmas saídas e outros chegando a saídas diferentes. Este recurso é matematicamente usado em modelos de computação não determinísticos, como autômatos finitos não determinísticos.
Um algoritmo não determinístico é capaz de ser executado em um computador determinístico que possui um número ilimitado de processadores paralelos. Um algoritmo não determinístico geralmente tem 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 string 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 vários resultados. Cada resultado que o algoritmo não determinístico produz é válido, independentemente das escolhas feitas pelo algoritmo durante a execução.