Jump to content

Turbine o seu Perfil

Confira a atualização e participe do clube!
Clique e saiba mais

Junte-se ao Clube de Membros VIP

Tenha destaque e diversos benefícios!
Confira Aqui

Acesse nosso Discord

Conheça nossos canais interativos
Confira Aqui
Notícia
  • Adquira já o seu VIP!
Arkanun1000

Algoritmo probabilístico

Recommended Posts

Algoritmo probabilístico

 

 

Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica. Na prática, isso significa que a máquina que implementa o algoritmo deve acessar um gerador de números pseudo-aleatórios. O algoritmo utiliza bits aleatórios como um guia para o seu comportamento. Diferente dos algoritmos convencionais, um algoritmo probabilístico, dada uma mesma sequência de entrada, não necessariamente leva a um mesmo estado final.

 

Definição

Para demonstrar os exemplos a seguir deve-se assumir um modelo. Um computador inicia seu trabalho sempre num estado inicial 41937118a9dc51ed18df28fe84c067c84a34733f e, dado uma seqüência de símbolos de entrada, esta máquina passará a outros estados. Numa máquina clássica não-probabilística (determinista), as transições dependem apenas da seqüência de símbolos, ou seja, dado um estado 503d0af3998f76cd4eaf8b3cc5e8834e254cb71b, a transição deste para um outro estado é sempre a mesma dado o recebimento do mesmo símbolo.

 

Em um algoritmo probabilístico, uma mesma seqüência de entrada não leva sempre a um mesmo estado final de computação. Isso acontece porque as transições entre estados dependem além do estado atual e do símbolo recebido, também de uma escolha aleatória. Imagine, num caso simplificado que, além de ler um símbolo para decidir o próximo passo de computação, a máquina ainda "lance uma moeda" para decidir se passa ou não ao próximo estado.

 

 

Motivação

O estudo de algoritmos computacionais geralmente busca soluções baseadas nos resultados do pior caso. Isso significa que uma solução é classificada dado o seu desempenho na execução de uma tarefa no seu pior caso. Mas em vários outros problemas, o estudo do desempenho no caso médio já é o suficiente. Ou seja, quando um algoritmo geralmente resolve um problema melhor que qualquer outro. Estas soluções podem até mesmo ter uma probabilidade pequena de retornar respostas erradas. Para esses casos os algoritmos probabilísticos podem ser bastante úteis.

 

Para ilustrar esta motivação pode-se usar o exemplo de uma busca. Dado um vetor de tamanho a601995d55609f2d9f5e233e36fbe9ea26011b3b preenchido uniformemente com os elementos d81ebea08fd5ab8e12d86fd14357c3f5f6c7e4b3 , o problema consiste em encontrar um ffd2487510aa438433a2579450ab2b3d557e5edc dentro do mesmo. A forma mais óbvia de executar tal busca é verificar cada uma das posições do vetor. Usando este algoritmo verificaremos, no pior caso da entrada (vetor ordenado), 95c3931a3fa03cc98cfacd2c49a7ca35b96eaa9b posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rápido que isso para todos os casos de entrada.

 

Neste mesmo problema, pode-se fazer uso de um algoritmo probabilístico muito simples para melhorar este resultado. Caso pesquisemos aleatoriamente as posições do vetor, teremos uma alta probabilidade de encontrar rapidamente o valor desejado para qualquer que seja a entrada. Resta apenas uma pequena probabilidade de que a o fator aleatório demore para terminar a busca, mas isso independe da entrada.

 

 

Programação

Uma máquina probabilística pode ser vista como uma particularidade das máquinas não determinísticas. O não-determinismo implica que a máquina pode seguir vários caminhos dados o par: estado 9f049ac28d4ac8097b625f9d71c1f22b2ebd1bc4 e símbolo de entrada 68baa052181f707c662844a465bfeeb135e82bab. A diferença deste modelo para o da máquina probabilística é que este último escolhe aleatoriamente o caminho a seguir, enquanto aquele, ao menos teoricamente, busca o melhor caminho dentro de todas as possibilidades.

 

Para a implementação de algoritmos probabilísticos uma importante definição é a instrução de atribuição aleatória, 9798a48f5857116f30dd8aeb7a0a821556cb1093 . Esta instrução diz respeito a escolha aleatória de um elemento do conjunto 4611d85173cd3b508e67077d4a1252c9c05abca2 para a atribuição da variável 87f9e315fd7e2ba406057a97300593c4802b53e4 .

 

 

Modelos

Autômatos finitos probabilísticos

Não existe apenas uma representação para a teoria de autômato finito. Uma delas apresenta um modelo baseado em matrizes que é particularmente interessante, neste caso, pois a evolução da representação de autômatos finitos para autômatos finitos probabilísticos é muito clara. Seguem as três principais características:

 

  • Para cada símbolo 87f9e315fd7e2ba406057a97300593c4802b53e4 do alfabeto existe uma matriz de transição 1ffb6beda78e4e8a06810b7923be306ef5376c3b que expressa as probabilidades de transição entre estados dado a leitura do símbolo 87f9e315fd7e2ba406057a97300593c4802b53e4;
  • Os estados são representados através de vetores coluna;
  • Pode-se calcular a aceitabilidade de uma palavra xyz com a seguinte fórmula: 85fb08558017aef37929aaad67d1afefde1a35af.

Os autômatos finitos são um caso particular dos autômatos finitos probabilísticos para transições com probabilidade 0 (para transição não possível) ou 1 (para transição possível). Ou seja, a decisão é executada com 100% de certeza. Vejamos um exemplo:

 

No caso do autômato finito

Um autômato que reconhece as palavras binárias com o formato 00*11*00* pode ser escrito assim:

 

Os estados:

2a6f11f550d867262b502021cdaa996de342ef89

 

 

As matrizes de transição:

5702746b98b7452c42dab5620878b67dc0cc7c50

 

 

Um exemplo de aceitação e rejeição:

 

ACEITAÇÃO:

 

d0c5411e5cd4e8724f0a3b631b23d286d26b8f99

 

REJEIÇÃO:

 

4c2a38ec34caa4eb5ff95b1216c2fedcf49a755e

 

No caso do autômato finito probabilístico

O mesmo modelo acima pode ser modificado para um autômato finito probabilístico mudando apenas as matrizes de possibilidadespara que seja de probabilidades. Com isso ao invés de receber apenas os valores 0 e 1, podem existir valores no intervalo [0,1] desde que as linhas somem sempre 1, ou seja, as probabilidades de execução em um dado estado e recebido um símbolo é sempre 1.

 

Podemos modificar as matrizes de transição da seguinte forma:

 

3a1dca91711579bc4e0cff36a19e51f15b28ba66

 

Os exemplo de aceitação e rejeição passam a não ser mais exatos, mas sim, a retornar uma probabilidade de aceitação:

 

PROBABILIDADE DE ACEITAÇÃO:

 

623184f69d0ccc09ce9dd3546a392e3e7e7812a3

 

PROBABILIDADE DE ACEITAÇÃO:

 

4c2a38ec34caa4eb5ff95b1216c2fedcf49a755e

 

E agora passamos a ter uma possibilidade de erro na aceitação da linguagem inicialmente descrita 00*11*00*

 

Máquinas de Turing probabilísticas

Uma Máquina de Turing Probabilística f82cade9898ced02fdd08712e5f0c0151758a0dd é um tipo de Máquina de Turing não-determinística que possui passos de transição chamados de lançamento-de-moeda, dando a máquina duas possibilidades a cada transição.

 

Se na computação de uma entrada 88b1e0c8e1be5ebe69d18a8010676fa42d7961e6 é gerado o caminho de execução (ramificação) f11423fbb2e967f986e36804a8ae4271734917c3, e neste, foram dados c3c9a2c7b599b37105512c5d570edc034056dd40 lançamentos de moeda, então a probabilidade do caminho é dada por: f67d1bae9b0a44ad7f90042c4a7f5661292c582f. Já a probabilidade de aceitação da entrada 88b1e0c8e1be5ebe69d18a8010676fa42d7961e6 é dada por:73d842a54589cd6fc6e32d75b25ed0fcae70e538, ou seja, a soma de todos os caminhos de execução que aceitam a palavra 88b1e0c8e1be5ebe69d18a8010676fa42d7961e6. Adicionalmente, temos que: fd6b8d9146e29ec3180bf52a2d971b0a2d8afdb5.

 

A máquina f82cade9898ced02fdd08712e5f0c0151758a0dd continua reconhecendo linguagens apenas quando aceita todas as palavras da mesma e rejeita no caso contrário. Mas a uma Máquina de Turing Probabilística é permitido uma pequena probabilidade de erro: d8316e34941e5a0891c6a74b2aef14c2f39c0d9breconhece uma linguagem 7daff47fa58cdfd29dc333def748ff5fa4c923e3 com probabilidade de erro c3837cad72483d97bcdde49c85d3b7b859fb3fd2 se:

 

44b013af6374eb318d76fa854f8e6aabb5030967

 

Ganhos (complexidade)

BPP

Classe das linguagens que são reconhecidas por uma máquina de Turing probabilística (em tempo polinomial) com um erro no interval [0, 0.5). Este erro pode ser diminuído exponencialmente utilizando o lema da aplicaficação. Este lema diz que para toda máquina de Turing probabilística (em tempo polinomial = 5324b2d326979916046a59681a2bef6b07f0c637) 577d686fc81d1d1eb3ae54e78aeee8957baf6718 que opera com erro c3837cad72483d97bcdde49c85d3b7b859fb3fd2, existe uma máquina equivalente 0d5d4dffae5ee0db4cc433e252ee9ed7530e5cf0 que opera com uma probabilidade de erro de 826d698f8fe9af346b1dd3511da8488e914222f0. Isto pode ser provado dado que 0d5d4dffae5ee0db4cc433e252ee9ed7530e5cf0 pode simular a máquina 577d686fc81d1d1eb3ae54e78aeee8957baf6718, executá-la um número polinomial de vezes e fazer uma escolha majoritária entre as respostas computadas. Existe um algoritmo probabilístico para teste de primalidade pertencente a BPP.

RP

 

Classe das linguagens que são reconhecidas por uma máquina de Turing probabilística (em tempo polinomial) no qual as entradas pertencentes a linguagem são aceitas com probabilidade de no mínimo 0.5 e entradas não pertencentes a linguagem são rejeitadas com probabilidade 1. Este tipo de erro, denominado erro de um único lado, é muito comum nos algoritmos probabilísticos. Nesta classe também é possível a redução exponencial do erro cometido.

 

ZPP

Engloba os problemas que possuem algoritmos que resolvem em tempo polinomial (no caso médio) e dão sempre uma resposta correta, mesmo que possam não parar em alguns casos.

 

 

Aplicações

Sistemas

Problemas

 

Fonte: https://pt.wikipedia.org/wiki/Algoritmo_probabilístico

  • Like 1

 

 

qRXaV1L.png

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.

×
×
  • Create New...