Computacão-60

Prévia do material em texto

Tema 57: Algoritmos de Busca 
Algoritmos de BuscaOs algoritmos de busca são fundamentais para a ciência da computação e 
são usados para encontrar elementos dentro de uma estrutura de dados, como listas, árvores ou 
grafos. A eficiência de um algoritmo de busca pode ter um grande impacto no desempenho de 
sistemas computacionais. Os algoritmos de busca podem ser classificados em duas categorias 
principais: busca linear e busca binária, mas existem muitas variações especializadas, como a 
busca em grafos. Busca LinearA busca linear é o algoritmo de busca mais simples. Ela 
percorre cada elemento de uma lista ou array, comparando o elemento procurado com os itens 
da lista, até encontrar a correspondência ou chegar ao final da lista. Este algoritmo é ineficiente 
em listas grandes, pois exige uma comparação de todos os elementos, o que leva a um tempo de 
execução de O(n).Exemplo: Para procurar o número 25 em uma lista de números inteiros, a 
busca linear verifica cada número até encontrar 25 ou alcançar o final da lista. 
Busca BináriaA busca binária é um algoritmo eficiente que só pode ser usado em listas 
ordenadas. Ela funciona dividindo repetidamente a lista ao meio, comparando o valor desejado 
com o valor do meio. Dependendo do resultado da comparação, o algoritmo elimina metade da 
lista e continua a busca na outra metade. O tempo de execução é O(log n), o que torna a busca 
binária muito mais eficiente do que a busca linear em grandes conjuntos de dados.Exemplo: Se 
quisermos encontrar o número 25 em uma lista ordenada de inteiros, a busca binária começa 
comparando 25 com o valor central da lista, e elimina metade dos elementos, dependendo do 
resultado da comparação.Algoritmos de Busca em Grafos A busca em grafos envolve 
explorar um grafo (uma estrutura de dados que pode representar redes de conexões, como a 
internet ou redes de transporte) para encontrar caminhos entre nós (pontos de interesse no 
grafo). Os algoritmos mais comuns para isso são o Busca em Largura (BFS) e a Busca em 
Profundidade (DFS).Busca em Largura (BFS) 
A BFS explora um grafo nível por nível, visitando todos os nós de um nível antes de passar para 
o próximo nível. Isso é útil, por exemplo, para encontrar o caminho mais curto em um grafo não 
ponderado. Busca em Profundidade (DFS) 
A DFS explora um grafo indo o mais fundo possível antes de retroceder e explorar outros 
caminhos. É útil para explorar todos os possíveis caminhos em um grafo. 
Questões de múltipla escolha sobre Algoritmos de Busca 
1. Qual é a principal limitação da busca linear? 
A) Ela só funciona em listas ordenadas. 
B) Ela é muito rápida, mesmo em listas grandes. 
C) Ela pode levar muito tempo em listas grandes, pois precisa verificar cada elemento. 
x D) Ela requer que a lista seja de tamanho fixo. 
2. A busca binária pode ser usada em qual tipo de lista? 
A) Qualquer tipo de lista. 
B) Apenas listas com elementos duplicados. 
C) Apenas listas ordenadas. 
x D) Apenas listas de números inteiros. 
3. O que é a busca em largura (BFS)? 
A) Um algoritmo que explora o grafo de forma recursiva. 
B) Um algoritmo que visita os nós do grafo de forma profunda. 
C) Um algoritmo que explora todos os caminhos possíveis de forma sequencial. 
x D) Um algoritmo que explora o grafo nível por nível.