Algoritmo não determinístico - Nondeterministic algorithm

Este artigo é sobre não determinismo na programação de computadores . Para não determinismo na teoria da complexidade computacional , consulte Modelo não determinístico de computação .

Em programação de computador , um algoritmo não determinístico é um algoritmo que, mesmo para a mesma entrada, pode exibir comportamentos diferentes em execuções diferentes, ao contrário de um algoritmo determinístico . Existem várias maneiras pelas quais um algoritmo pode se comportar de maneira diferente de uma execução para outra. Um algoritmo simultâneo pode ter um desempenho diferente em diferentes execuções devido a uma condição de corrida . O comportamento de um algoritmo probabilístico depende de um gerador de números aleatórios . Um algoritmo que resolve um problema em tempo polinomial não determinístico pode ser executado em tempo polinomial ou em tempo exponencial, dependendo das escolhas feitas durante a execução. Os algoritmos não determinísticos são freqüentemente usados ​​para encontrar uma aproximação para uma solução, quando a solução exata seria muito cara de se obter usando uma determinística.

A noção foi introduzida por Robert W. Floyd em 1967.

Usar

Freqüentemente, na teoria computacional , o termo "algoritmo" se refere a um algoritmo determinístico . Um algoritmo não determinístico é diferente de sua contraparte determinística mais familiar em sua capacidade de chegar a resultados usando várias rotas. Se um algoritmo determinístico representa um único caminho de uma entrada para um resultado, um algoritmo não determinístico representa um único caminho originado em muitos caminhos, alguns dos quais podem chegar à mesma saída e alguns dos quais podem chegar a saídas exclusivas. Esta propriedade é capturada matematicamente em modelos "não determinísticos" de computação , como o autômato finito não determinístico . Em alguns cenários, todos os caminhos possíveis podem ser executados simultaneamente.

No projeto de algoritmos, os algoritmos não determinísticos são frequentemente usados ​​quando o problema resolvido pelo algoritmo permite inerentemente vários resultados (ou quando há um único resultado com vários caminhos pelos quais o resultado pode ser descoberto, cada um igualmente preferível). Crucialmente, todo resultado que o algoritmo não determinístico produz é válido, independentemente de quais escolhas o algoritmo faz durante a execução.

Na teoria da complexidade computacional , os algoritmos não determinísticos são aqueles que, a cada passo possível, podem permitir várias continuações (imagine uma pessoa caminhando por um caminho em uma floresta e, cada vez que ela dá um passo adiante, ela deve escolher qual bifurcação na estrada que deseja pegar). Esses algoritmos não chegam a uma solução para todos os caminhos computacionais possíveis; entretanto, eles têm a garantia de chegar a uma solução correta para algum caminho (ou seja, a pessoa que caminha pela floresta só pode encontrar sua cabana se escolher alguma combinação de caminhos "corretos"). As escolhas podem ser interpretadas como suposições em um processo de pesquisa .

Um grande número de problemas pode ser conceituado por meio de algoritmos não determinísticos, incluindo a questão não resolvida mais famosa na teoria da computação, P vs NP .

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

Uma forma de simular um algoritmo não-determinístico N utilizando um algoritmo determinista D é para tratar conjuntos de estados de N como estados de D . Isso significa que D traça simultaneamente todos os caminhos de execução possíveis de N (consulte a construção do conjunto de potência para esta técnica em uso para autômatos finitos ).

Outra é a randomização , que consiste em permitir que todas as escolhas sejam determinadas por um gerador de números aleatórios . O resultado é chamado de algoritmo determinístico probabilístico .

Veja também

Referências

Leitura adicional