Em teoria da computação, o algoritmo de Markov,, Short paper sobre os algoritmos 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.
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: 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. Use o primeiro de todos os padrões encontrados para substituir o matching mais à esquerda em s pela sua respectiva substituição. Se a regra aplicada é conclusiva, pare. Retorne ao passo 1 e continue.
Exemplos
Os seguintes exemplos mostram o operacional básico de um algoritmo de Markov.
Primeiro exemplo
Regras
“M” -> “maçã” “B” -> “bolsa” “L” -> “loja” “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:
“Eu comprei uma B de maçãs da L.” “Eu comprei uma bolsa de maçãs da L.” “Eu comprei uma bolsa de maçãs da loja.” “Eu comprei uma bolsa de maçãs do meu irmão.”
Parando devido à falta de padrões encontrados.
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.
Regras
“|0” -> “0||” “1” -> “0|” “0”-> ””
Cadeia de entrada
“101”
Execução
Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações:
“0|01” "00||1" "00||0|" "00|0|||" "000|||||" "00|||||" "0|||||" "|||||"
Novamente parando devido à falta de padrões encontrados.
Ligações externas Simulador do algoritmo de Markov
Categoria:Teoria da computação