Programação não determinística

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Uma linguagem de programação não determinística é uma linguagem que pode especificar, em certos pontos do programa (chamados "pontos de escolha"), várias alternativas para o fluxo do programa . Ao contrário de uma instrução if-then , o método de escolha entre essas alternativas não é especificado diretamente pelo programador; o programa deve decidir em tempo de execução entre as alternativas, por meio de algum método geral aplicado a todos os pontos de escolha. Um programadorespecifica um número limitado de alternativas, mas o programa deve depois escolher entre elas. ("Escolha" é, na verdade, um nome típico para o operador não determinístico.) Uma hierarquia de pontos de escolha pode ser formada, com escolhas de nível superior levando a ramificações que contêm opções de nível inferior dentro delas.

Um método de escolha é incorporado em sistemas de retrocesso (como Amb , [1] ou unificação em Prolog ), nos quais algumas alternativas podem "falhar", fazendo com que o programa retroceda e tente outras alternativas. Se todas as alternativas falharem em um determinado ponto de escolha, uma ramificação inteira falhará, e o programa retrocederá ainda mais, para um ponto de escolha mais antigo. Uma complicação é que, como qualquer escolha é provisória e pode ser refeita, o sistema deve ser capaz de restaurar estados de programas antigos desfazendo os efeitos colaterais causados ​​pela execução parcial de uma ramificação que eventualmente falhou.

Outro método de escolha é o aprendizado por reforço, incorporado em sistemas como o Alisp . [2] Nesses sistemas, em vez de retroceder, o sistema acompanha alguma medida de sucesso e aprende quais escolhas geralmente levam ao sucesso e em quais situações (tanto o estado interno do programa quanto a entrada do ambiente podem afetar a escolha). Esses sistemas são adequados para aplicações em robótica e outros domínios em que o retrocesso envolveria a tentativa de desfazer ações realizadas em um ambiente dinâmico, o que pode ser difícil ou impraticável.

Veja também

Referências

  1. ^ "Estrutura e Interpretação de Programas de Computador" .
  2. ^ http://www.cs.berkeley.edu/~russell/papers/aaai02-alisp.pdf [ URL simples PDF ]