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
Referências
- ^ Edward A. Lee. "O problema com threads" (PDF) . Página visitada em 29/05/2009 .
- ^ Bocchino Jr., Robert L .; Adve, Vikram S .; Adve, Sarita V .; Snir, Marc (2009). A programação paralela deve ser determinística por padrão . Workshop USENIX sobre tópicos importantes em paralelismo.
- ^ "Intel Parallel Inspector Thread Checker" . Página visitada em 29/05/2009 .
- ^ Yuan Lin. "Detecção de corrida de dados e deadlock com o Sun Studio Thread Analyzer" (PDF) . Página visitada em 29/05/2009 .
- ^ Intel. "Intel Parallel Inspector" . Página visitada em 29/05/2009 .
- ^ David Worthington. "A Intel aborda o ciclo de vida de desenvolvimento com o Parallel Studio" . Arquivado do original em 28/05/2009 . Página visitada em 26/05/2009 .
- ^ McGraw, Gary ; Viega, John . "Faça o seu software se comportar: Jogando os números: Como fazer batota no jogo online" . Arquivado do original em 13/03/2008 . Página visitada em 2007-07-02 .
- ^ "Categorias de determinismo na linguagem de programação Mercury" . Arquivado do original em 03/07/2012 . Retirado 2013-02-23 .
- ^ "Modos de predicado de Mercúrio" . Arquivado do original em 03/07/2012 . Página visitada em 2013-02-25 .
- ^ "Representando a falha usando a mônada Maybe" .
- ^ "A classe MonadPlus" .