Diferenças entre edições de "Algoritmo probabilístico"

Da Thinkfn
(→‎Definição)
(→‎Máquinas de Turing probabilísticas)
 
(11 edições intermédias não estão a ser mostradas.)
Linha 1: Linha 1:
−
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.
+
Um '''algoritmo probabilístico''' é um [[algoritmo]] que utiliza a [[probabilidade]] como parte da sua lógica. Na prática, isso significa que a máquina que implementa o algoritmo deve ter acesso a 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 resulta necessariamente no mesmo estado final.
  
 
== Definição ==
 
== Definição ==
 +
Para demonstrar os exemplos a seguir deve-se assumir um modelo. Um computador inicia o seu trabalho sempre num estado inicial ''Q<sub>0</sub>'' e, dada uma sequência de símbolos de entrada, esta máquina passará a outros estados. Numa máquina clássica não-probabilística, as transições dependem apenas da sequência de símbolos, ou seja, dado um estado ''Q<sub>n</sub>'', a transição deste para um outro estado é sempre a mesma ao receber o mesmo símbolo.
  
−
Para demonstrar os exemplos a seguir deve-se assumir um modelo. Um computador inicia seu trabalho sempre num estado inicial ''Q<sub>0</sub>'' 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, as transições dependem apenas da seqüência de símbolos, ou seja, dado um estado ''Q<sub>n</sub>'', a transição deste para um outro estado é sempre a mesma dado o recebimento do mesmo símbolo.
+
Num algoritmo probabilístico, uma mesma sequência de entrada não leva sempre a um mesmo estado final. Isso acontece porque as transições entre estados dependem além do estado actual e do símbolo recebido, também de uma ''escolha aleatória''. Imagine-se, 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.
−
 
+
−
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 ==
 
== 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.
+
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 dar respostas erradas. Para esses casos os algoritmos probabilísticos podem ser bastante úteis.
  
−
Para ilustrar esta motivação pode-se usar o exemplo de um busca. Dado um [[array|vetor]] de tamanho <tex>n</tex> preenchido uniformemente com os elementos <tex>\lbrace a, b \rbrace</tex>, o problema consiste em encontrar um <tex>a</tex> dentro do mesmo. A forma mais óbvia de executar tal busca é checar cada uma das posições do vetor. Usando este algoritmo checaremos, no pior caso da entrada (vetor ordenado), <tex>n / 2</tex> posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rápido que isso para todos os casos de entrada.
+
Para ilustrar esta motivação pode-se usar o exemplo de um busca. Dado um [[array|vector]] de tamanho ''n'' preenchido uniformemente com os elementos {''a, b''}, o problema consiste em encontrar um ''a'' dentro do mesmo. A forma mais óbvia de executar esta busca é verificar cada uma das posições do vector. Usando este algoritmo são verificadas, no pior caso da entrada (vector ordenado), ''n''/2 posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rapidamente 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.
+
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 vector, teremos uma alta probabilidade de encontrar rapidamente o valor desejado para qualquer que seja a entrada. Resta apenas uma pequena probabilidade de que o factor aleatório demore para terminar a busca, mas isso não depende da entrada.
  
 
== Programação ==
 
== 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 ''S<sub>n</sub>'' e símbolo de entrada ''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.
  
−
Uma máquina probabilística pode ser vista como uma particularidade das [[Máquina de estados finita não determinística|máquinas não determinísticas]]. O não-determinismo implica que a máquina pode seguir vários caminhos dados o par: estado <tex>S_n</tex> e símbolo de entrada <tex>X</tex>. 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'', &nbsp; ''x := random(S)''. Esta instrução diz respeito à escolha aleatória de um elemento do conjunto ''S'' para a atribuição da variável ''x''.
−
 
+
−
Para a implementação de algoritmos probabilísticos uma importante definição é a ''instrução de atribuição aleatória'', <tex>x := random(S)</tex>. Esta instrução diz respeito a escolha aleatória de um elemento do conjunto <tex>S</tex> para a atribuição da variável <tex>x</tex>.
+
  
 
== Modelos ==
 
== Modelos ==
−
=== Autômatos finitos probabilísticos ===
+
=== 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 [[Matriz (matemática)|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:
+
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 <tex>x</tex> do [[alfabeto]] existe uma matriz de transição <tex>M_x</tex> que expressa as ''probabilidades'' de transição entre estados dado a leitura do símbolo <tex>x</tex>;
 
* Para cada símbolo <tex>x</tex> do [[alfabeto]] existe uma matriz de transição <tex>M_x</tex> que expressa as ''probabilidades'' de transição entre estados dado a leitura do símbolo <tex>x</tex>;
−
* Os estados são representados através de [[Array|vetores]] coluna;
+
* Os estados são representados através de [[Array|vectores]] coluna;
 
* Pode-se calcular a aceitabilidade de uma palavra ''xyz'' com a seguinte fórmula: <tex>P_{(xyz)} = q_{inicial}^T \cdot M_x \cdot M_y \cdot M_z \cdot q_{final}</tex>.
 
* Pode-se calcular a aceitabilidade de uma palavra ''xyz'' com a seguinte fórmula: <tex>P_{(xyz)} = q_{inicial}^T \cdot M_x \cdot M_y \cdot M_z \cdot q_{final}</tex>.
  
−
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:
+
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
+
; 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:
+
Um autómato que reconhece as palavras binárias com o formato ''00*11*00*'' pode ser escrito assim:
  
 
Os estados:
 
Os estados:
Linha 42: Linha 40:
 
0
 
0
 
\end{bmatrix}
 
\end{bmatrix}
−
; q_1 =
+
{,}\quad q_1 =
 
\begin{bmatrix}
 
\begin{bmatrix}
 
0 \\
 
0 \\
Linha 49: Linha 47:
 
0
 
0
 
\end{bmatrix}
 
\end{bmatrix}
−
; q_2 =
+
{,}\quad q_2 =
 
\begin{bmatrix}
 
\begin{bmatrix}
 
0 \\
 
0 \\
Linha 56: Linha 54:
 
0
 
0
 
\end{bmatrix}
 
\end{bmatrix}
−
; q_3 = q_{final} =
+
{,}\quad q_3 = q_{final} =
 
\begin{bmatrix}
 
\begin{bmatrix}
 
0 \\
 
0 \\
Linha 62: Linha 60:
 
0 \\
 
0 \\
 
1
 
1
−
\end{bmatrix}
+
\end{bmatrix}.
 
</tex>  
 
</tex>  
  
Linha 74: Linha 72:
 
0 & 0 & 0 & 1\\
 
0 & 0 & 0 & 1\\
 
\end{bmatrix}
 
\end{bmatrix}
−
; M_1 =
+
{,}\quad M_1 =
 
\begin{bmatrix}
 
\begin{bmatrix}
 
0 & 0 & 0 & 0\\
 
0 & 0 & 0 & 0\\
Linha 88: Linha 86:
  
 
<tex>
 
<tex>
−
P_{(010)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_0M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 1 & 0 & 0\end{pmatrix} \cdot M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 1 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 1
+
P_{(010)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_0M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 1 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 1 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 1
 
</tex>
 
</tex>
  
Linha 94: Linha 92:
  
 
<tex>
 
<tex>
−
P_{(10)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 0
+
P_{(10)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0
 
</tex>
 
</tex>
  
−
; No caso do autômato finito probabilístico
+
; 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 ''possibilidades'' para 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.
+
O mesmo modelo acima pode ser modificado para um autómato finito probabilístico mudando apenas as matrizes de ''possibilidades'' para 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 num dado estado e recebido um símbolo é sempre 1.
  
 
Podemos modificar as matrizes de transição da seguinte forma:
 
Podemos modificar as matrizes de transição da seguinte forma:
Linha 109: Linha 107:
 
0 & 0 & 0 & 1\\
 
0 & 0 & 0 & 1\\
 
\end{bmatrix}
 
\end{bmatrix}
−
; M_1 =
+
{,}\quad M_1 =
 
\begin{bmatrix}
 
\begin{bmatrix}
 
0 & 0 & 0 & 0\\
 
0 & 0 & 0 & 0\\
Linha 118: Linha 116:
 
</tex>
 
</tex>
  
−
Os exemplo de aceitação e rejeição passam a não ser mais exatos, mas sim, a retornar uma probabilidade de aceitação:
+
Os exemplos de aceitação e rejeição passam a não ser mais exactos, mas sim, a retornar uma probabilidade de aceitação:
  
 
PROBABILIDADE DE ACEITAÇÃO:
 
PROBABILIDADE DE ACEITAÇÃO:
  
 
<tex>
 
<tex>
−
P_{(010)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_0 M_1 M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0.2 & 0.8 & 0 & 0\end{pmatrix} \cdot M_1 M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0.12 & 0.68 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0.12 & 0.068 & 0.612\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 0.612
+
P_{(010)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_0 M_1 M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0.2 & 0.8 & 0 & 0\end{bmatrix} \cdot M_1 M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0.12 & 0.68 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0.12 & 0.068 & 0.612\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0.612
 
</tex>
 
</tex>
  
Linha 129: Linha 127:
  
 
<tex>
 
<tex>
−
P_{(10)} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix} \cdot M_1M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \cdot M_0 \cdot \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = \begin{pmatrix}0 & 0 & 0 & 0\end{pmatrix} \begin{pmatrix}0 \\0 \\0 \\1\end{pmatrix} = 0
+
P_{(10)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0
 
</tex>
 
</tex>
  
Linha 135: Linha 133:
  
 
=== Máquinas de Turing probabilísticas ===
 
=== Máquinas de Turing probabilísticas ===
−
Uma Máquina de Turing Probabilística <tex>M</tex> é 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.
+
Uma Máquina de Turing probabilística <tex>M</tex> é 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 <tex>w</tex> é gerado o caminho de execução (ramificação) <tex>b</tex>, e neste, foram dados <tex>k</tex> lançamentos de moeda, então a probabilidade do caminho é dada por: <tex>P[b] = 2^{-k}</tex>. Já a probabilidade de aceitação da entrada <tex>w</tex> é dada por: <tex>P[M aceita w] = \sum P[b]</tex>, ou seja, a soma de todos os caminhos de execução que aceitam a palavra <tex>w</tex>. Adicionalmente, temos que: <tex>P[M rejeita w] = 1 - P[M aceita w]</tex>.
+
Se na computação de uma entrada <tex>w</tex> é gerado o caminho de execução (ramificação) <tex>b</tex> e, neste, foram dados <tex>k</tex> lançamentos de moeda, então a probabilidade do caminho é dada por: <tex>P[b] = 2^{-k}</tex>. Já a probabilidade de aceitação da entrada <tex>w</tex> é dada por: <tex>P[M aceita w] = \sum P[b]</tex>, ou seja, a soma de todos os caminhos de execução que aceitam a palavra <tex>w</tex>. Adicionalmente, temos que: <tex>P[M rejeita w] = 1 - P[M aceita w]</tex>.
  
 
A máquina <tex>M</tex> 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: <tex>0 \le \epsilon < 0.5</tex>. Desta forma, diz-se que <tex>M</tex> reconhece uma linguagem <tex>A</tex> com probabilidade de erro <tex>\epsilon</tex> se:  
 
A máquina <tex>M</tex> 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: <tex>0 \le \epsilon < 0.5</tex>. Desta forma, diz-se que <tex>M</tex> reconhece uma linguagem <tex>A</tex> com probabilidade de erro <tex>\epsilon</tex> se:  
Linha 208: Linha 206:
  
 
[[Categoria:Estatística]]
 
[[Categoria:Estatística]]
−
[[Categoria:Algoritmos]]
 
 
[[Categoria:Teoria das probabilidades]]
 
[[Categoria:Teoria das probabilidades]]

Edição atual desde as 08h00min de 18 de fevereiro de 2008

Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte da sua lógica. Na prática, isso significa que a máquina que implementa o algoritmo deve ter acesso a 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 resulta necessariamente no mesmo estado final.

Definição

Para demonstrar os exemplos a seguir deve-se assumir um modelo. Um computador inicia o seu trabalho sempre num estado inicial Q0 e, dada uma sequência de símbolos de entrada, esta máquina passará a outros estados. Numa máquina clássica não-probabilística, as transições dependem apenas da sequência de símbolos, ou seja, dado um estado Qn, a transição deste para um outro estado é sempre a mesma ao receber o mesmo símbolo.

Num algoritmo probabilístico, uma mesma sequência de entrada não leva sempre a um mesmo estado final. Isso acontece porque as transições entre estados dependem além do estado actual e do símbolo recebido, também de uma escolha aleatória. Imagine-se, 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 dar respostas erradas. Para esses casos os algoritmos probabilísticos podem ser bastante úteis.

Para ilustrar esta motivação pode-se usar o exemplo de um busca. Dado um vector de tamanho n preenchido uniformemente com os elementos {a, b}, o problema consiste em encontrar um a dentro do mesmo. A forma mais óbvia de executar esta busca é verificar cada uma das posições do vector. Usando este algoritmo são verificadas, no pior caso da entrada (vector ordenado), n/2 posições. A verdade é que nenhum algoritmo determinístico termina esta tarefa mais rapidamente 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 vector, teremos uma alta probabilidade de encontrar rapidamente o valor desejado para qualquer que seja a entrada. Resta apenas uma pequena probabilidade de que o factor aleatório demore para terminar a busca, mas isso não depende 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 Sn e símbolo de entrada 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 := random(S). Esta instrução diz respeito à escolha aleatória de um elemento do conjunto S para a atribuição da variável x.

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 x do alfabeto existe uma matriz de transição M_x que expressa as probabilidades de transição entre estados dado a leitura do símbolo x;
  • Os estados são representados através de vectores coluna;
  • Pode-se calcular a aceitabilidade de uma palavra xyz com a seguinte fórmula: P_{(xyz)} = q_{inicial}^T \cdot M_x \cdot M_y \cdot M_z \cdot q_{final}.

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: q_0 = q_{inicial} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} {,}\quad q_1 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} {,}\quad q_2 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} {,}\quad q_3 = q_{final} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.


As matrizes de transição: M_0 = \begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1\\ \end{bmatrix} {,}\quad M_1 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

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

ACEITAÇÃO:

P_{(010)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_0M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 1 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 1 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 1

REJEIÇÃO:

P_{(10)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0

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 possibilidades para 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 num dado estado e recebido um símbolo é sempre 1.

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

M_0 = \begin{bmatrix} 0.2 & 0.8 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0.1 & 0.9\\ 0 & 0 & 0 & 1\\ \end{bmatrix} {,}\quad M_1 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0.15 & 0.85 & 0\\ 0 & 0 & 0.95 & 0.05\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

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

PROBABILIDADE DE ACEITAÇÃO:

P_{(010)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_0 M_1 M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0.2 & 0.8 & 0 & 0\end{bmatrix} \cdot M_1 M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0.12 & 0.68 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0.12 & 0.068 & 0.612\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0.612

PROBABILIDADE DE ACEITAÇÃO:

P_{(10)} = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \cdot M_1M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \cdot M_0 \cdot \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}0 \\0 \\0 \\1\end{bmatrix} = 0

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 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 é gerado o caminho de execução (ramificação) b e, neste, foram dados k lançamentos de moeda, então a probabilidade do caminho é dada por: P[b] = 2^{-k}. Já a probabilidade de aceitação da entrada w é dada por: P[M aceita w] = \sum P[b], ou seja, a soma de todos os caminhos de execução que aceitam a palavra w. Adicionalmente, temos que: P[M rejeita w] = 1 - P[M aceita w].

A máquina M 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: 0 \le \epsilon < 0.5. Desta forma, diz-se que M reconhece uma linguagem A com probabilidade de erro \epsilon se:

\begin{cases} w \in A \to P[M aceita w] \ge 1 - \epsilon \\ w \notin A \to P[M rejeita w] \ge 1 - \epsilon \end{cases}

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 = polin(n)) M_1 que opera com erro \epsilon, existe uma máquina equivalente M_2 que opera com uma probabilidade de erro de 2^{-polin(n)}. Isto pode ser provado dado que M_2 pode simular a máquina 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.

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

Referências


Smallwikipedialogo.png

Esta página usa conteúdo da Wikipedia. O artigo original estava em Algoritmo_probabilístico. Tal como o Think Finance neste artigo, o texto da Wikipedia está disponível segundo a GNU Free Documentation License.

Obtida de "https://www.thinkfnwiki.com/wiki/index.php?title=Algoritmo_probabilístico&oldid=7611"