Algoritmo determinístico - Deterministic algorithm

Em ciência da computação , um algoritmo determinístico é um algoritmo que, dada uma determinada entrada, sempre produzirá a mesma saída, com a máquina subjacente sempre passando pela mesma sequência de estados. Os algoritmos determinísticos são de longe o tipo de algoritmo mais estudado e familiar, bem como um dos mais práticos, uma vez que podem ser executados em máquinas reais de forma eficiente.

Formalmente, um algoritmo determinístico calcula uma função matemática ; uma função tem um valor único para qualquer entrada em seu domínio , e o algoritmo é um processo que produz esse valor específico como saída.

Definição formal

Os algoritmos determinísticos podem ser definidos em termos de uma máquina de estado : um estado descreve o que uma máquina está fazendo em um determinado instante no tempo. As máquinas de estado passam de maneira discreta de um estado para outro. Logo depois entramos na entrada, a máquina está em seu estado inicial ou estado inicial . Se a máquina é determinística, isso significa que, desse ponto em diante, seu estado atual determina qual será seu próximo estado; seu curso através do conjunto de estados é predeterminado. Observe que uma máquina pode ser determinística e ainda assim nunca parar ou terminar e, portanto, falhar em entregar um resultado.

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

O que torna os algoritmos não determinísticos?

Uma variedade de fatores pode fazer com que um algoritmo se comporte de forma não determinística ou não determinística:

• Se ele usa um estado externo diferente da entrada, como uma entrada do usuário, uma variável global , um valor de temporizador de hardware, um valor aleatório ou dados de disco armazenados.
• Se operar de uma forma que seja sensível ao tempo, por exemplo, se tiver vários processadores gravando nos mesmos dados ao mesmo tempo. Nesse caso, a ordem precisa em que cada processador grava seus dados afetará o resultado.
• Se um erro de hardware fizer com que seu estado mude de maneira inesperada.

Embora os programas reais raramente sejam puramente determinísticos, é mais fácil para os humanos, assim como para outros programas, raciocinar sobre os programas que o são. Por esse motivo, a maioria das linguagens de programação e especialmente as linguagens de programação funcionais fazem um esforço para evitar que os eventos acima aconteçam, exceto sob condições controladas.

A prevalência de processadores multi-core resultou em um surto de interesse no determinismo na programação paralela e os desafios do não determinismo foram bem documentados. Uma série de ferramentas para ajudar a lidar com os desafios foram propostas para lidar com impasses e condições de corrida .

Desvantagens do Determinismo

É vantajoso, em alguns casos, para um programa exibir comportamento não determinístico. O comportamento de um programa de embaralhamento de cartas usado em um jogo de blackjack , por exemplo, não deve ser previsível pelos jogadores - mesmo que o código-fonte do programa seja visível. O uso de um gerador de números pseudo - aleatórios muitas vezes não é suficiente para garantir que os jogadores sejam incapazes de prever o resultado de um embaralhamento. Um jogador inteligente pode adivinhar precisamente os números que o gerador escolherá e assim determinar todo o conteúdo do baralho com antecedência, permitindo que ele trapaceie; por exemplo, o Grupo de Segurança de Software da Reliable Software Technologies foi capaz de fazer isso para uma implementação do Texas Hold 'em Poker que é distribuído pela ASF Software, Inc, permitindo-lhes prever de forma consistente o resultado das mãos com antecedência. Esses problemas podem ser evitados, em parte, por meio do uso de um gerador de números pseudo-aleatórios criptograficamente seguro , mas ainda é necessário que uma semente aleatória imprevisível seja usada para inicializar o gerador. Para este propósito, uma fonte de não determinismo é necessária, como aquela fornecida por um gerador de números aleatórios de hardware .

Observe que uma resposta negativa ao problema P = NP não implicaria que programas com saída não determinística são teoricamente mais poderosos do que aqueles com saída determinística. A classe de complexidade NP (complexidade) pode ser definida sem qualquer referência ao não-determinismo usando a definição baseada no verificador .

Categorias de determinismo em línguas

Mercúrio

Essa linguagem de programação lógico-funcional estabelece diferentes categorias de determinismo para modos de predicado, conforme explicado na referência.

Haskell

Haskell fornece vários mecanismos:

não determinismo ou noção de falha

• os tipos Maybe e Either incluem a noção de sucesso no resultado.
• o método de falha da classe Monad, pode ser usado para sinalizar falha como exceção.
• o transformador Maybe monad e MaybeT monad fornecem cálculos falhados (pare a sequência de computação e retorne Nada)

determinismo / não det com várias soluções

você pode recuperar todos os resultados possíveis de um cálculo de resultados múltiplos, envolvendo seu tipo de resultado em uma mônada MonadPlus . (seu método mzero faz um resultado falhar e mplus coleta os resultados bem-sucedidos).

Família ML e linguagens derivadas

Conforme visto em Standard ML , OCaml e Scala

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

Java

• O valor de referência nulo pode representar um resultado malsucedido (fora do domínio).

Veja também

• Algoritmo Randomizado

Referências