Exercícios de Fixação 04 - Divisão e Conquista

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 04
Divisão e Conquista
 1. Suponha que esteja escolhendo entre os seguintes algoritmos:
 a) Algoritmo A resolve problemas dividindo-os em quatro subproblemas de metade do
tamanho, solucionando cada subproblema recursivamente e, então, combinando as
soluções em tempo linear.
 b) Algoritmo B resolve problemas de tamanho n resolvendo recursivamente dois
subproblemas de tamanho n – 1 e, então, combinando as soluções em tempo constante.
 c) Algoritmo C soluciona problemas de tamanho n dividindo-os em nove subproblemas de
tamanho n/3, resolvendo recursivamente cada subproblema e, então, combinando as
respostas em tempo O(n2).
Qual o tempo de execução de cada um dos algoritmos? Qual você escolheria? 
 2. O seguinte algoritmo é uma solução para o problema da ordenação:
algumMetodoSort(A; p; r)
se p < r
então q   ← (p + r)/2
algumMetodoSort(A; p; q)
algumMetodoSort(A; q+1; r)
intercala(A; p; q; r)
intercala rearranja o vetor A[p..r] em ordem crescente supondo que os subvetores A[p..q] e
A[q+1..r] são ambos crescentes. Sendo assim, responda:
a. O algoritmo se baseia em divisão e conquista? Justifique. 
b. Efetue a análise da complexidade assintótica do algoritmo. Nota: Calcule T(n) e
determine a sua complexidade.
 3. Para todo número natural n ≥ 1, o piso do logaritmo de n na base 2, denotado por lgn é o
único número natural tal que 2k ≤ n < 2k+1. O seguinte algoritmo recursivo recebe um número
natural n ≥ 1 e devolve lgn.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
pisoDeLog(n){
se n = 1 entao devolva 0
senao devolva pisoDeLog(n/2)+1
}
Sendo assim, responda:
a. O algoritmo é baseado em divisão-e-conquista? Justifique.
b. Efetue a análise da complexidade assintótica do algoritmo.
 4. Considere o algoritmo F, a seguir.
_______________________________________
Entrada: inteiro não negativo
if n = 0
return 1
else
return F(n­1) + F(n­1)
_____________________________________________________
a. O que o algoritmo calcula?
b. Quantas vezes a operação básica é executada? Estabeleça um somatório ou uma relação
de recorrência para indicar o número de vezes que a operação básica é executada e
resolvam este somatório ou relação de recorrência sem simplificações. Se houver casos
diferentes, resolva sempre para o pior caso. 
c. Qual é a complexidade assintótica do algoritmo?
d. Este algoritmo utiliza Divisão e Conquista? Justifique.
 5. Determine o que se pede, considerando o método recursivo, a seguir:
public static int recursiva(int n){
if (n <= 0) return 1;
else return (recursiva(n­1) + recursiva(n­1));
}
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 a) O que o método recursivo faz? 
 b) O método utilizou divisão e conquista? 
 c) Determine a complexidade assintótica do método. 
 6. Muitas das recorrências que acontecem na análise de algoritmos de divisão e conquista têm
a forma F(n) = aF(n/b) + cnk para F(n) assintoticamente não decrescente, a, b, k , a ≥ 1,
b ≥ 2, k ≥ 0, e c. Nessas condições, de acordo com o Teorema Mestre
• Se loga/logb > k, então F(n) está em (nloga/logb)
• Se loga/logb = k, então F(n) está em (nklogn)
• Se loga/logb < k, então F(n) está em (nk)
Considere os algoritmos A, B e C, que são descritos respectivamente pelas equações de recorrência:
FA(n) = 8F(n/4) + n
FB(n) = 4F(n/2) + n2
FC(n) = 2F(n/4) + n3
Dado que lg2 = 1, lg4 = 2 e lg8 = 3, como se pode comparar a ordem de complexidade  dos
algoritmos A, B e C?
 a) (FA) > (FB) > (FC)
 b) (FA) < (FB) < (FC)
 c) (FA) > (FB) < (FC)
 d) (FA) < (FB) > (FC)
	Lista de Exercícios de Fixação 04