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 pseudoaleató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.
Para demonstrar os exemplos a seguir deve-se assumir um modelo. Um computador inicia seu trabalho sempre num estado inicial Q 0 {\displaystyle Q_{0}} e, dado uma sequê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 Q n {\displaystyle Q_{n}} , 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 sequê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.
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 n {\displaystyle n} preenchido uniformemente com os elementos { a , b } {\displaystyle \lbrace a,b\rbrace } , o problema consiste em encontrar um a {\displaystyle a} 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), n / 2 {\displaystyle n/2} posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rápido que isso para todos os casos de entrada.
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 S n {\displaystyle S_{n}} e símbolo de entrada X {\displaystyle X} . 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, x := r a n d o m ( S ) {\displaystyle x:=random(S)} . Esta instrução diz respeito a escolha aleatória de um elemento do conjunto S {\displaystyle S} para a atribuição da variável x {\displaystyle x} .
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: 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: Um autômato que reconhece as palavras binárias com o formato 00*11*00* pode ser escrito assim:
Máquinas de Turing probabilísticas
Uma Máquina de Turing Probabilística M {\displaystyle M} é 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 w {\displaystyle w} é gerado o caminho de execução (ramificação) b {\displaystyle b} , e neste, foram dados k {\displaystyle k} lançamentos de moeda, então a probabilidade do caminho é dada por: P [ b ] = 2 − k {\displaystyle P[b]=2^{-k}} . Já a probabilidade de aceitação da entrada w {\displaystyle w} é dada por: P [ M a c e i t a w ] = ∑ P [ b ] {\displaystyle P[Maceitaw]=\sum P[b]} , ou seja, a soma de todos os caminhos de execução que aceitam a palavra w {\displaystyle w} . Adicionalmente, temos que: P [ M r e j e i t a w ] = 1 − P [ M a c e i t a w ] {\displaystyle P[Mrejeitaw]=1-P[Maceitaw]} .
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 = p o l i n ( n ) {\displaystyle polin(n)} ) M 1 {\displaystyle M_{1}} que opera com erro ϵ {\displaystyle \epsilon } , existe uma máquina equivalente M 2 {\displaystyle M_{2}} que opera com uma probabilidade de erro de 2 − p o l i n ( n ) {\displaystyle 2^{-polin(n)}} . Isto pode ser provado dado que M 2 {\displaystyle M_{2}} pode simular a máquina M 1 {\displaystyle M_{1}} , 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. 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.
