Usuário(a):Igorlrgomes/Testes

Em ciência da computação, um algoritmo não determinístico é um algoritmo que pode apresentar comportamentos diferentes em diferentes execuções, ao contrário de um algoritmo determinístico. Um algoritmo concorrente pode executar de forma diferente em diferentes execuções devido a uma condição de concorrência. O comportamento de um algoritmo probabalistico depende de um gerador de números aleatórios. Um algoritmo que resolve um problema de tempo polinomial não determinístico pode ser executado em tempo polinomial ou tempo exponencial em função das escolhas que faz durante a execução.

Uso

Muitas vezes, na teoria computacional, o termo "algoritmo" refere-se a um algoritmo determinístico. Um algoritmo não determinístico é diferente de sua contraparte determinista em sua capacidade de chegar a resultados usando diversas rotas. Se um algoritmo determinístico representa um único caminho de uma entrada para um resultado, um algoritmo não determinístico representa um caminho resultante em muitos caminhos, alguns dos quais podem chegar ao mesmo resultado e alguns dos quais podem chegar a resultados únicos. Esta propriedade é chamada matematicamente de modelo de computação "não determinístico", como o autômato finito não determinístico. Em alguns cenários, todos os caminhos possíveis estão autorizados a funcionar simultaneamente.

Na concepção do algoritmo, algoritmos não determinísticos são frequentemente utilizados quando o problema resolvido pelo algoritmo inerentemente permite múltiplos resultados (ou quando existe um resultado único com vários caminhos através dos quais o resultado pode ser descoberto, cada um igualmente preferível). Fundamentalmente, todos os resultados que o algoritmo não determinístico produz são válidos, independentemente das escolhas que o algoritmo faz durante a execução.

Em teoria da complexidade computacional, algoritmos não determinísticos são aqueles que, a cada passo possível, podem permitir múltiplas continuações (imagine um homem andando por um caminho em uma floresta e, a cada vez que ele pisa mais, ele deve escolher qual bifurcação da estrada que ele deseja tomar). Esses algoritmos não chegam a uma solução para cada caminho computacional possível, no entanto, eles garantem chegar a uma solução correta por algum caminho (ou seja, o homem caminhava pela floresta só pode encontrar sua cabana se ele pega alguma combinação de caminhos "corretos"). As escolhas podem ser interpretados como palpites num processo de busca.

Um grande número de problemas pode ser conceituado através de algoritmos não determinísticos, incluindo a questão não resolvida mais famosa em teoria da computação, P versus NP.

Implementação de algoritmos não determinístico com os determinísticos

Uma forma de simular um algoritmo não determinístico N usando um algoritmo determinístico D é tratar conjuntos de estados de N como estados de D. Isso significa que, D simultaneamente rastreia todos os caminhos de execução possíveis de N (veja Construção do conjunto das partes para esta técnica utilizada em automatos finitos).

Outra é aleatorização, que consiste em deixar que todas as escolhas serem determinadas por um gerador de números aleatórios. O resultado é chamado de algoritmo deterministico probabilístico.

Exemplos

Exemplo 1: merge sort

Suponha que temos um conjunto finito de coisas (digamos, 300 provas de estudantes) que precisamos para classificar (por exemplo, por número de aluno).

Um algoritmo para fazer isso (chamado merge sort):

• Dividir a coleção em duas partes aproximadamente iguais
• Ordenar as duas metades com merge sort (ou seja, recursivamente)
• Juntar os resultados

Itens só podem ser exclusivamente classificados se o critério de classificação escolhido sempre define uma ordem total; por exemplo o número de estudantes é único, mas se nós classificarmos as provas por nome e acontecer de ter dois estudantes com o mesmo nome, a ordem em que as provas são classificadas é deixada indefinida. Em tais casos, merge sort sempre chega a uma das ordenações possíveis válida, mas qual é deixado indeterminado, portanto, é não determinísticas.

Exemplo 2: Spanning Tree

A entrada é um grafo conexo não direcionado. Um grafo não direcionado é um conjunto de nós que podem ou não podem ser ligados aos pares por arestas. O subgrafo de um grafo consiste de um subconjunto de seus nós e/ou arestas. Um grafo conecta dois nós se pode caminhar sobre as suas arestas de um para o outro. Um caminho em um grafo é um subgrafo mínimo conectando dois de seus nós. Um grafo é conexo se ele conecta todos os seus nós.

O algoritmo: enquanto uma aresta pode ser removido de forma que o gráfico continua conectado, retire essa aresta.

A saída: a spanning tree, isto é, um subgrafo que é uma árvore ligando todos os nós.

Cada grafo (que está conectado e não uma árvore) tem várias árvores geradoras, por isso, mais uma vez temos um exemplo em que o problema em si permite que vários resultados possíveis, e o algoritmo escolhido pode chegar a qualquer um deles, mas nunca vai chegar a um outro resultado .

Este é, novamente, um algoritmo que sempre chega a uma solução correta para o problema.

Exemplo 3: teste de primalidade

O problema: dado um número natural n maior do que dois, determinar se ele é primo.

Um algoritmo não determinístico para este problema é o seguinte com base no pequeno teorema de Fermat :

1. Repita 30 vezes:
2. # Escolha um inteiro aleatório a tal que 2 ≤ a ≤ n-1.
3. # Se $a^{n-1}\neq 1{\pmod {n}}$, retorne composto
4. Retorne provavelmente primo.

Se este algoritmo retorna a resposta composto, então o número não é certamente primo. Se o algoritmo retorna a resposta provavelmente primo, então há uma alta probabilidade de que o número é primo, mas uma pequena chance de que é composto. Este é um exemplo de um algoritmo não determinístico probabilístico, porque ele não retornará sempre o mesmo resultado para uma entrada específica.

Veja também

• Máquina de Turing não determinística
• Autômato finito não-determinístico

Referencias

Cormen; et al. Introduction to Algorithms, Third Edition. [S.l.: s.n.] ISBN 978-0-262-03384-8  !CS1 manut: Uso explícito de et al. (link)
«nondeterministic algorithm». NIST 
«Non-deterministic Algorithms»