Os métodos de Knuth-Morris-Pratt (KMP) e de Boyer-Moore (BM)...

Alternativa correta: B - busca em cadeias.

Vamos entender o motivo pelo qual essa alternativa é a correta e por que as outras estão incorretas.

Os algoritmos Knuth-Morris-Pratt (KMP) e Boyer-Moore (BM) são amplamente utilizados em computação para resolver o problema da busca de padrões em cadeias de caracteres. Estes algoritmos são fundamentais para situações em que é necessário localizar uma sequência específica de caracteres (chamada de "padrão") dentro de um texto maior.

Para resolver a questão, é essencial entender que:

• KMP otimiza a busca evitando comparações redundantes.
• BM utiliza heurísticas inteligentes para saltar posições no texto, tornando a busca geralmente mais rápida.

Justificativa das alternativas:

B - busca em cadeias. Esta alternativa é correta porque tanto o algoritmo KMP quanto o BM são especificamente desenhados para buscar padrões em cadeias de caracteres. Estas técnicas são essenciais quando a busca eficiente em grandes textos é necessária.

A - busca binária. A busca binária é um algoritmo usado para encontrar um elemento em uma lista ordenada, dividindo repetidamente a porção da lista que poderia conter o elemento, até que o alvo seja encontrado. Isso não tem relação direta com os algoritmos KMP e BM.

C - ordenação de vetores por inserção. A ordenação por inserção é um algoritmo simples de ordenação que constrói a lista final uma peça de cada vez, inserindo cada novo elemento na posição correta. Novamente, não tem relação com KMP ou BM.

D - ordenação de vetores por seleção. A ordenação por seleção é um algoritmo de ordenação que seleciona repetidamente o menor (ou maior) elemento da lista e o coloca na posição correta. Este método também não é relacionado aos algoritmos de busca em cadeias KMP e BM.

E - ordenação de vetores por troca. A ordenação por troca (como o Bubble Sort) ordena uma lista comparando repetidamente os elementos adjacentes e trocando-os se estiverem na ordem errada. Assim como as opções anteriores, este método não está relacionado aos algoritmos KMP e BM.

Concluindo, os algoritmos KMP e BM são ferramentas poderosas no campo da busca de padrões em cadeias de caracteres, o que torna a alternativa B a correta.

Esses métodos são algoritmos de busca em cadeias. Seja T o texto e P o parâmetro procurado em T, o método BM consegue evitar comparações entre P e uma boa parte dos caracteres em T. O único problema desse algoritmo é que ele trabalha com um alfabeto limitado. O método KMP evita o desperdício de informações que ocorrem em outros algoritmos. Possui pré-processamento de P, permitindo que nenhum caractere seja reexaminado.


Fonte: http://ticnapratica.blogspot.com/2010/05/logica-e-estrutura-de-dados.html