Algoritmo de Markov

Em teoria da computação, o algoritmo de Markov, nomeado assim em homenagem à Andrei Markov, é um sistema de reescrita de cadeias que lança mão de regras de gramáticas para operar sobre cadeias de símbolos. Os algoritmos de Markov se mostraram Turing-completos, o que garante que eles provêm um modelo geral de computação e que podem representar qualquer expressão matemática.[carece de fontes]?

Algoritmo

As Regras constituem-se de uma sequência de pares de cadeias, usualmente presentes na forma padrão->substituição. Algumas regras podem ser conclusivas.

Dada uma cadeia de entrada s:

  1. Verifique as Regras com uma abordagem top-down, para verificar quantos padrões podem ser encontrados em s
Caso nenhum padrão seja encontrado, pare.
  1. Use o primeiro de todos os padrões encontrados para substituir o matching mais à esquerda em s pela sua respectiva substituição.
  2. Se a regra aplicada é conclusiva, pare.
  3. Retorne ao passo 1 e continue.[carece de fontes]?

Exemplos

Os seguintes exemplos mostram o operacional básico de um algoritmo de Markov.

Primeiro exemplo

Regras

  1. “M” -> “maçã”
  2. “B” -> “bolsa”
  3. “L” -> “loja”
  4. “da loja” -> “do meu irmão”

Cadeia de entrada

“Eu comprei uma B de Ms da L.”

Execução

Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações:

  1. “Eu comprei uma B de maçãs da L.”
  2. “Eu comprei uma bolsa de maçãs da L.”
  3. “Eu comprei uma bolsa de maçãs da loja.”
  4. “Eu comprei uma bolsa de maçãs do meu irmão.”

Parando devido à falta de padrões encontrados.[carece de fontes]?

Segundo exemplo

Estas regras mostram um caso mais interessante. Elas transformam números binários em suas representações unárias. Neste exemplo, o número 101 será reescrito como 5 barras consecutivas.[carece de fontes]?

Regras

  1. “|0” -> “0||”
  2. “1” -> “0|”
  3. “0”-> ””

Cadeia de entrada

“101”

Execução

Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações:

  1. “0|01”
  2. "00||1"
  3. "00||0|"
  4. "00|0|||"
  5. "000|||||"
  6. "00|||||"
  7. "0|||||"
  8. "|||||"

Novamente parando devido à falta de padrões encontrados.

Referências

  1. ↑ , Short paper sobre os algoritmos de Markov

Ligações externas

Simulador do algoritmo de Markov