Os métodos de Knuth-Morris-Pratt (KMP) e de Boyer-Moore (BM)...
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
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.