Algoritmo determinístico

Em Ciência da Computação, um algoritmo determinístico é um algoritmo em que, dada uma certa entrada, ela produzirá sempre a mesma saída, com a máquina responsável sempre passando pela mesma seqüência de estados. Algoritmos determinísticos são, de longe, o tipo mais estudado e conhecido de algoritmo, assim como um dos mais práticos, uma vez que podem ser executados em máquinas reais de forma eficiente. Formalmente, um algoritmo determinístico computa uma função matemática; uma função tem um valor único para cada entrada dada, e o algoritmo é um processo que produz este valor em particular como saída.

Definição Formal

Algoritmos determinísticos podem ser definidos em termos de uma máquina de estados: um estado descreve o que uma máquina está fazendo em um instante específico no tempo. Máquinas de estado passam de maneira discreta de um estado para outro. Imediatamente depois de colocarmos a entrada, a máquina está no que chamamos estado inicial. Se a máquina é determinística, isto significa que deste ponto em diante, seu estado atual determinará qual será o seu próximo estado; seu caminho através do conjunto de estados é predeterminado. Note que uma máquina pode ser determinística e ainda assim nunca parar ou terminar, e portanto, deixar de retornar um resultado.

Exemplos de máquinas abstratas em particular que são determinísticas incluem a máquina de Turing determinística e o autômato finito determinístico.

O que faz um algoritmo ser não-determinístico?

Diversos fatores podem levar um algoritmo a se comportar de uma maneira não-determinística:

• Se ele usa algum valor externo que não o de entrada, como uma entrada do usuário, uma variável global, uma leitura de temporizador de hardware, um valor aleatório, ou dados armazenados em disco.
• Se ele opera de uma maneira sensível ao tempo. Por exemplo, se ele tiver vários processadores escrevendo em um mesmo conjunto de dados ao mesmo tempo, a ordem específica na qual cada processador escreve seus dados vai afetar o resultado.
• Se um erro de hardware causa uma mudança de estado inesperada.

Embora programas reais raramente sejam puramente deterministicos, é mais simples para seres humanos, assim como para outros programas, trabalhar com programas que o sejam. Por esta razão, a maioria das linguagens de programação, especialmente as linguagens funcionais, fazem esforços para evitar que os eventos acima ocorram, exceto sob condições controladas.

A prevalência de processadores multinúcleo resultou em um aumento no interesse em determinismo em programação paralela e desafios do não-determinismo têm sido bem documentados. para lidar com deadlocks e condições de corrida. Várias ferramentas estão sendo propostas

Problemas com algoritmos determinísticos

Infelizmente, encontrar algoritmos determinísticos para alguns problemas é difícil. Por exemplo, existem algoritmos probabilísticos simples e eficientes que determinam se um dado número é primo e apresentam uma pequena margem de erro (por exemplo, o teste de primalidade de Fermat). Os algoritmos determinísticos conhecidos para resolver o mesmo problema ainda são consideravelmente mais lentos na prática.

Outro exemplo: os problemas NP-completos, que incluem muitos dos problemas práticos mais importantes, podem ser resolvidos rapidamente por máquinas de Turing não-deterministicas; porém, nunca foram encontrados algoritmos práticos e eficientes para qualquer um deles. No máximo, consegue-se apenas encontrar soluções aproximadas ou soluções para casos especiais.

Outro grande problema com algoritmos determinísticos é que, às vezes, não queremos que os resultados sejam previsíveis. Por exemplo, se alguém está jogando uma rodada de blackjack online que embaralha as cartas usando um gerador de números pseudoaleatórios, é possível para um jogador inteligente descobrir com precisão os números que o gerador irá escolher, determinando assim todo o conteúdo do baralho previamente e permitindo-lhe trapacear; por exemplo, o grupo de segurança de software (SSG) da Reliable Software Technologies foi capaz de fazer isso em uma implementação da variante de poquer Texas Hold 'em que é distribuída pela ASF Software, Inc, permitindo-lhes prever de maneira consistente o resultado das mãos de maneira prévia. Problemas similares são encontrados em criptografia, onde as chaves privadas são muitas vezes criadas usando esse tipo de gerador. Isso geralmente pode ser evitado através do uso de um gerador de números pseudo-aleatórios criptograficamente seguro.

Categorias determinísticas em linguagens

Mercury

Esta linguagem de programação lógica-funcional permite estabelecer diferentes categorias de determinismo para modos de predicados.

Haskell

Haskell fornece diversos mecanismos:

não-determinismo ou noção de falha

• Os tipos Maybe e Either adicionam a noção de sucesso ao resultado.
• O método fail da classe Monad, pde ser usado para sinalizar fail como exceção.
• A Monad Maybe e o transformador de Monads MaybeT determinam o comportamento em caso de falha computacional (pára a sequencia de computação e retorna Nothing).

Determinismo/não-determinismo com múltplas soluções

É possível obter todas as possíveis saídas de uma computação que gera resultados múltiplos, envolvendo o tipo do resultado em uma Monad MonadPlus (o método mzero gera falhas de saída e o mplus coleta resultados bem-sucedidos).

Família ML e linguagens derivadas

Como pode ser visto em Standard ML, OCaml e Scala

• O tipo option inclui a noção de sucesso.

Java

• O valor de referência null pode representar um resultado mal-sucedido (fora-do-domínio).