Algoritmo de markov

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1347 palavras )
  • Download(s) : 0
  • Publicado : 23 de abril de 2013
Ler documento completo
Amostra do texto
Algoritmo

de

Markov

Introdução

Introdução Algoritmo de Markov..................................................................................................3
Exemplo........................................................................................................................................3Definição.......................................................................................................................................3
Exemplo.........................................................................................................................................4
Definição.......................................................................................................................................4Exemplo........................................................................................................................................5
Bibliografia....................................................................................................................................6

Algoritmo de Markov
Um dos novos procedimentos para lidar com a resolução de problemas foi proposta pelo matemático russo AA Markov nosprimeiros anos da década de 50 com o que chamou de algoritmos normais, e que chamamos de algoritmo Markov. O tipo geral de problema Markov é atacado a partir do processamento de cadeias de símbolos: dada uma seqüência de A, B, transformá-lo em uma sucessão mecânica. Este problema é uma abstração de muitos dos nossos problemas comuns. Por exemplo, o problema de adicionar dois números a e b pode serconsiderado o problema de transformar a seqüência de "a + b" em uma seqüência "c" representa a soma de a e b. O problema da aquisição de informações pode ser pensado como o problema de transformar seqüências que representam os requisitos eo conjunto de documentos, representando as seqüências que satisfazem os documentos necessários.
Ao transformar uma sucessão não necessita, em geral, operar sobretoda a sequência (que pode ser arbitrariamente de comprimento) de uma só vez, mas apenas sobre uma porção pequena adjacente ele. Portanto, supor que o dispositivo que você tem que usar esses algoritmos é capaz de reconhecer instâncias de uma determinada seqüência dentro de uma determinada seqüência. Essas aparições podem ser muitos e, na verdade, poderia até mesmo se sobrepõem. Se nós distinguir umaaparição especial de uma subanillo, marcamos com asteriscos.
Exemplo. O ratatattat palavra contém três ocorrências da seqüência tat, ou seja, ra * tat * attat, rato * tat tat ​​* e * Ratatat * tat. A partir dessas aparências, os dois primeiros têm uma sobreposição de uma carta.
Considere estas ocorrências como se eles são numerados e referem-se a ocorrência mais à esquerda de uma seqüência de Aem uma seqüência B como a primeira ocorrência de A para B. Devemos chamar a atenção para uma sequência muito particular, a saber, a sequência de vazio, o que não contém qualquer símbolo. Desempenha um papel análogo ao conjunto vazio.Se uma dada sequência A contém símbolos n, a sequência de vazio é considerado como tendo n +1 aparências em A: antes do primeiro símbolo (o primeiro aparecimento deU), após o último, e entre cada um dos dois símbolos adjacentes.
As transformações que compõem o algoritmo de Markov é substituir a primeira ocorrência da sequência, tal como especificado na sequência indicada por uma outra sequência especificada B. Um algoritmo de Markov é, em seguida, numa sucessão de transformações, que são preparadas uma forma que explicita. Neste ponto, parece que umalgoritmo de Markov poderia muito bem continuar a aplicar essas alterações sempre ou pode fazer uma pausa porque nenhuma das transformações podem ser aplicadas à sequência que estamos considerando. Nós também seria capaz de precipitar explicitamente algoritmo o processo, se para um dado tempo. Portanto, temos dois tipos de transformações definidas abaixo.
Definição. Considere sequências de símbolos...
tracking img