Exercicios de Fixação 03 - Análise de Algoritmos de Busca - Gabarito

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 03
Análise de Algoritmos de Busca
1. Considere as técnicas de pesquisa sequencial, pesquisa binária e pesquisa baseada em
hashing. Descreva as vantagens e desvantagens de cada uma dessas técnicas, indicando em
que situações, são de fato viáveis;
Sequencial Binária Hashing
Vantagem Simplicidade Eficiência Eficiência
Desvantagem Custo elevado Arranjo deve estar ordenado Não recupera em ordem
2. Explique por que a busca binária:
a. É mais eficiente do que a busca sequencial.
Em cada passo da busca sequencial, ao comparar a chave de busca com a próxima chave do
conjunto, diminuímos o tamanho do problema em uma unidade. Na busca binária, a cada passo,
diminuímos pela metade o tamanho do problema. Assim, no pior caso, quando a chave de busca não
está na lista, a busca sequencial pode levar até n comparações (n é o tamanho da lista), enquanto a
busca binária levaria lgn comparações.
b. Só pode ser efetuada em um array.
Num array ordenado, temos acesso direto à sua mediana por meio dos seus índices. Ao somar os
índices das extremidades e dividir por dois, obtemos o endereço do valor mediano. Isso só é
possível quando (a) temos acesso a eles e (b) eles são consecutivos. 
3. Considere a lista linear sequencial de inteiros no vetor, a seguir.
2 4 6 8 10 12 14 16
 
a. Considerando o método da busca binária:
1. Quantas comparações (e com quais chaves) são necessárias na busca pelo valor 15?
Compara-se com as chaves 8, 12, 14 e 16 (4 comparações) 
2. Idem para o inteiro 6.
Compara-se com as chaves 8, 4 e 6 (3 comparações) 
b. Considerando a Busca Sequencial: 
100
50
200
300
400
150
250
350
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
1. Quantas comparações (e com quais chaves) são necessárias pelo valor 15?
Compara-se com as chaves 2, 4, 6, 8, 10, 12, 14 e 16 (8 comparações)
2. Idem para o inteiro 6.
Compara-se com as chaves 2, 4 e 6 (3 comparações) 
c. Generalize o número máximo de comparações na Busca Binária e na Busca Sequencial,
considerando o tamanho do vetor igual a n. 
Na busca binária lgn e na busca sequencial n.
4. Suponha que você tenha uma árvore binária na qual estão armazenadas uma chave em cada
nodo. Suponha também que a árvore foi construída de tal maneira que, ao caminhar nela na
ordem central, as chaves são visitadas em ordem crescente. Sendo assim, qual propriedade
entre as chaves deve ser satisfeita para que isso seja possível?
Todos os registros com chaves menores estão na subárvore esquerda e todos aqueles com chaves
maiores estão na subárvore direita.
5. Em uma tabela hash com 100 entradas, as colisões são resolvidas usando listas encadeadas.
Para reduzir o tempo de pesquisa, decidiu-se que cada lista seria organizada como uma
árvore binária de pesquisa sem balanceamento. A função utilizada é h(k) = k mod 100.
Infelizmente, as chaves inseridas seguem o padrão ki = 50i, onde ki corresponde à i-ésima
chave inserida.
a. Mostre a situação da tabela após a inserção de ki, com i = 1, 2, …, 8 (esquematize);
K1 = 50 mod 100 = 50
K2 = 100 mod 100 = 0
K3 = 150 mod 100 = 50
K4 = 200 mod 100 = 0
K5 = 250 mod 100 = 50
K6 = 300 mod 100 = 0
K7 = 350 mod 100 = 50
K8 = 400 mod 100 = 0
0
50
99
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
b. Considerando a busca nessa tabela hash, qual é a complexidade para o pior caso?
O pior caso depende da solução utilizada para o tratamento das colisões (no caso, árvore binária de
pesquisa sem balanceamento). Com isso, caímos no seu pior caso, ou seja, T(n) = n/2 → O(n).
6. Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de
suas chaves e em técnicas de tratamento de colisões. As funções de dispersão transformam
chaves em endereços-base da tabela, ao passo que o tratamento de colisões resolve conflitos
em casos em que mais de uma chave é mapeada para um mesmo endereço-base da tabela.
Suponha que uma aplicação utilize uma tabela de dispersão com 23 endereços-base (índices
de 0 a 22) e empregue h(x) = x mod 23 como função de dispersão, em que x representa a
chave do elemento cujo endereço-base deseja-se computar. Inicialmente, essa tabela de
dispersão encontra-se vazia. Em seguida, a aplicação solicita uma sequência de inserções de
elementos cujas chaves aparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95.
a. Apresente o conjunto das chaves envolvidas em colisões.
b. Assuma que a tabela de dispersão trate colisões por meio de encadeamento exterior.
Esboce a tabela de dispersão para mostrar seu conteúdo após a sequência de inserções
referida.
[Similar à questão anterior]
7. Qual é o pior tempo para inserir n elementos em uma tabela hashing inicialmente vazia, com
colisões sendo resolvidas por listas encadeadas? Qual seria o melhor caso?
Pior caso seria T(n) = n e o melhor caso, T(n) = 1.
8. Considerando que as chaves inseridas em um Hashing não provocaram colisão,
independente do algoritmo, podemos dizer que a pesquisa por uma chave na tabela será de
ordem de complexidade constante, ou seja, T(n) = 1? Podemos dizer que este algoritmo é
ótimo? Justifique.
Sim. O algoritmo é ótimo, pois o acesso à chave é direto.
	Lista de Exercícios de Fixação 03