Algoritmo de Markov

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde junho de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde junho de 2012).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

Em teoria da computação, o algoritmo de Markov1 , 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Primeiro exemplo[editar | editar código-fonte]

Regras[editar | editar código-fonte]

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

Cadeia de entrada[editar | editar código-fonte]

“Eu comprei uma B de Ms da L.”

Execução[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Cadeia de entrada[editar | editar código-fonte]

“101”

Execução[editar | editar código-fonte]

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. [1], Short paper sobre os algoritmos de Markov

Links externos[editar | editar código-fonte]

Simulador do algoritmo de Markov