Busca de palavra em texto Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Busca de palavra em texto – Teoria dos Grafos e Análise de Algoritmos
Exercícios
1. O algoritmo de busca tradicional de Boyer-Moore depende de um pequeno
número de comparações de caracteres e grandes mudanças realizadas no texto
durante a busca.
O algoritmo de Boyer-Moore:
I. funciona corretamente apenas com a tabela de símbolos ruins para orientar as
mudanças de padrão.
II. não funciona corretamente apenas com a tabela de símbolos ruins para orientar
as mudanças de padrão.
III. funciona corretamente apenas com a tabela de sufixos bons para orientar as
mudanças de padrão.
IV. não funciona corretamente apenas com a tabela de sufixos bons para orientar as
mudanças de padrão.
Está o que se afirma em:
Resposta correta.
E. I e IV, apenas.
O algoritmo de Boyer-Moore não funcionaria corretamente apenas com a
tabela de sufixos bons para orientar as mudanças de padrão, pois a tabela de
símbolos ruins é necessária.
A tabela de símbolos ruins é a única usada pelo algoritmo se o primeiro par de
caracteres   não   corresponder.   Por   isso o   algoritmo   de   Boyer-Moore   pode
sobreviver apenas com a tabela de deslocamento de símbolos ruins para orientar
as mudanças de padrão.
2. Considere o texto "aaaaaaaaaaa". Quantas vezes o padrão "aaa" é encontrado
pela busca com o algoritmo de Boyer-Moore?
Você acertou!
A. Nove vezes.
Etapas para você saber quantas correspondências existem no texto: A primeira
etapa do Algoritmo de Boyer-Moore é pré-processar o padrão, gerando tabelas de
deslocamento que permitem que o algoritmo avance em condições favoráveis. A
tabela de deslocamento com caractere ruim calcula onde a próxima posição no
padrão a pesquisa deve se mover depois de não encontrar um caractere de texto.
Se um caractere de texto não estiver no padrão, mude o padrão para além do
caractere.
A correspondência de padrões Boyer-Moore foi concluída com 9
correspondências e 36 comparações.
3. Considere o texto "Busca de palavra em texto." Quantas comparações são feitas
com o algoritmo de Boyer-Moore para a busca do padrão?
Resposta correta.
B. Vinte e nove comparações.
Etapas  para  você saber  quantas  correspondências  e  comparações  existem no
texto: a primeira etapa do algoritmo de Boyer-Moore é pré-processar o padrão,
gerando   tabelas   de   deslocamento   que   permitam   ao   algoritmo   avançar   em
condições favoráveis.
A tabela de deslocamento com caractere ruim calcula onde na próxima posição no
padrão a pesquisa deve se mover depois de não encontrar um caractere de texto.
Se um caractere de texto não estiver no padrão, mude o padrão para além do
caractere. A correspondência de padrões Boyer-Moore foi concluída com 3
correspondências e 29 comparações.
4. O algoritmo de Boyer-Moore varre os caracteres do padrão da direita para a
esquerda, começando com o mais à direita, depois fazendo as comparações da
direita para a esquerda.
O que o algoritmo faz no caso de uma incompatibilidade, ou seja, uma combinação
incompleta de todo o padrão?
Você acertou!
A. O algoritmo usa duas funções pré-computadas para deslocar a janela para a direita.
O algoritmo usa duas funções pré-computadas para deslocar a janela para a
direita. O algoritmo Boyer-Moore usa a função de sufixo bom e uma função de
sufixo ruim para calcular  a nova posição de comparação,  deslocando P para a
direita e tomando o máximo desses dois valores.
O Algoritmo Boyer-Moore  é   rápido  no  caso de um alfabeto  maior.  Ele  usa as
informações obtidas nessa tentativa para descartar o maior número possível de
posições do texto onde a string não pode corresponder.
Sua ideia básica é: primeiro P e T se alinham à esquerda numa janela de tentativa.
Da direita para a esquerda, os caracteres em P são comparados aos caracteres
correspondentes em T. Se todos os caracteres forem correspondidos, o algoritmo
será encerrado com sucesso. Em caso de incompatibilidade, o algoritmo calcula a
distância de P até o deslocamento para a direita. A string de padrão P muda para a
direita e inicia uma nova rodada de tentativa de correspondência no momento da
correspondência de padrão.
5. Os algoritmos de correspondência de strings incluem o algoritmo de força bruta
(BF), o algoritmo Knuth-Morris-Pratt (KMP) e o algoritmo Boyer-Moore (BM), alguns
dos algoritmos de pesquisa mais famosos. Todos eles executam os passos de
busca de padrões com algumas semelhanças.
Qual alternativa representa uma semelhança entre esses algoritmos?
Resposta correta.
D. Os algoritmos escaneiam o texto pela janela. Cada janela tem o mesmo comprimento
do padrão a ser pesquisado e é igual a m.
Os algoritmos de correspondência de strings incluem o algoritmo de força bruta
(BF), o algoritmo Knuth-Morris-Pratt (KMP) e o algoritmo Boyer-Moore (BM).
Todos esses algoritmos  funcionam da seguinte  forma: eles escaneiam o texto
pela janela; cada janela tem o mesmo comprimento do padrão a ser
pesquisado e é igual a m.
O   início   da   pesquisa   por   comparação   da   janela   de   caracteres   começa   com
caracteres do padrão; esse processo é denominado "tentativa". Esses algoritmos
mudam a janela para a direita para que a pesquisa de correspondência possa ser
encontrada em outro lugar no comprimento do texto.
Repetem todos os passos anteriores até chegar ao final do texto, pois o objetivo
desses   algoritmos   é   encontrar   todas   as   correspondências   no   texto;   se   forem
encontradas, retornam a declaração de não haver padrão no texto.
	Busca de palavra em texto – Teoria dos Grafos e Análise de Algoritmos
	Exercícios