Exercicios de Fixação 04 - Divisão e Conquista - 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 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.
T(n) = 4T(n/2) + n
a = 4, b = 2, log24 = 2, d = 1. Portanto, ao aplicar o Teorema Mestre, temos T(n) = (nlogba) = (n2)
 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.
T(n) = 2T(n-1) + c
 = 2(2T(n-2) + c) + c
 = 4T(n-2) + 3c
 = …
 = 2KT(n-k) + (2K – 1)c, onde n-k =1 → k = n-1
 = 2n-1T(1) + (2n-1 – 1)c
 = 2n-1 + 2n-1c – c → (2n)
 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).
T(n) = 9T(n/3) + n2
Como f(n) = n2 = (nloga
b
) = (nlog3
9
) = (n2), d = 2. Daí, T(n) é (nloga
b
lgn) = (n2lgn).
Qual o tempo de execução de cada um dos algoritmos? Qual você escolheria? 
O algoritmo A, em função de sua complexidade computacional.
 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
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
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. 
Sim, pois se utilizam duas chamadas a algumMetodoSort para metade do tamanho da
entrada (divisão) e há uma rotina de intercalação (conquista) dos resultados obtidos.
b. Efetue a análise da complexidade assintótica do algoritmo. Nota: Calcule T(n) e
determine a sua complexidade.
Seja T(n) o tempo que o algoritmo consome, no pior caso, para processar uma instância
de tamanho n. Então T(n) = T(n/2) + T(n/2) + n = 2T(n/2) + n, cuja complexidade
assintótica é (nlgn).
 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.
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. Sim
b. Efetue a análise da complexidade assintótica do algoritmo. T(1)=0, T(n) = T(n/2) + 1.
Pelo teorema mestre, tem-se, O(lgn).
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 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?
Calcula 2n.
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. 
 S(n) = 1, se n = 0
 S(n) = S(n-1) + S(n-1) + 1, se n > 0
= 2S(n-1) + 1
= 2(2S(n-2) + 1) + 1 = 4S(n-2) + 3
= 2kS(n-k) + 2k - 1 
Quando n-k = 0, k = n.
S(n) = 2n + 2n – 1, portanto... S(n) = 2n+1 - 1 
c. Qual é a complexidade assintótica do algoritmo?
(2n).
d. Este algoritmo utiliza Divisão e Conquista? Justifique.
Não, pois o problema é dividido em subproblemas de tamanho menor, todavia, não são de
aproximadamente a metade do tamanho.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 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));
}
 a) O que o método recursivo faz? Ele efetua a operação de exponenciação 2n.
 b) O método utilizou divisão e conquista? Não
 c) Indique a complexidade assintótica do método. 
T(0) = 1, se n 0
T(n) = 2T(n-1), se n > 0
= 2(2T(n-2)) = 4T(n-2)
= 4(2(T(n-3)) = 8T(n-3)
= …
= 2kT(n-k)
Dado que se n-k = 0, teremos T(0) = 1, k = n. Substituindo, temos:
T(n) = 2nT(0) = 2n → (2n)
 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)
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 b) (FA) < (FB) < (FC)
 c) (FA) > (FB) < (FC)
 d) (FA) < (FB) > (FC)
	Lista de Exercícios de Fixação 04