AAED - Lista de exercícios 2

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Relações de Recorrência
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Seja T (n) a função definida pela recorrência
T (1) = 1
T (n) = T (n− 1) + 2n− 2 para n = 2, 3, 4, 5, . . .
Verifique que a recorrência é honesta, ou seja, de fato define uma função. A partir da árvore
de recorrência, advinhe uma boa delimitação assintótica para T (n). Prove a delimitação pelo
método da substituição.
2. Resolva a recorrência
T (1) = 1
T (n) = T (n− 1) + 2n+ 1 para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
3. Resolva a recorrência
T (1) = 1
T (2) = 2
T (n) = T (n− 2) + 2n+ 1 para n = 3, 4, 5, 6, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
4. Resolva a recorrência
T (1) = 1
T (n) = T (n/2) + 1 para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
5. Resolva a recorrência
T (1) = 1
T (n) = T (bn/2c) + 1 para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
6. Resolva a recorrência
T (1) = 1
T (n) = T (bn/2c) + n para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
7. Resolva a recorrência
T (1) = 1
T (n) = 2 T (bn/2c) + n para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
8. Resolva a recorrência
T (1) = 1
T (n) = 2 T (dn/2e) + n para n = 2, 3, 4, 5, . . .
Desenhe a árvore da recorrência e advinhe uma boa delimitação assintótica para T (n). Prove
a delimitação pelo método da substituição.
9. Mostre, usando o método da substituição, que a solução da recorrência T (n) = 2 T (n/2) +
n, T (1) = 1 está em O(n log n). Mostre também, novamente por substituição, que essa
recorrência está em Ω(n log n), concluindo assim que a recorrência está em Θ(n log n).
10. Use a árvore de recursão para resolver a recorrência T (n) = 3 T (n/2) + 1, T (1) = 1. Sua
solução deve ser assintoticamente restrita. Use o método da substituição para provar o resul-
tado.
11. Use a árvore de recursão para resolver a recorrência T (n) = T (αn)+T ((1−α)n)+n, T (1) = 1,
onde 0 < α < 1. Sua solução deve ser assintoticamente restrita. Use o método da substituição
para provar o resultado.
12. A recorrência TA(n) = 7 TA(n/2)+n
2 descreve o tempo de execução de um algoritmo A. Um
outro algoritmo B tem o tempo de execução descrito pela recorrência TB(n) = a TB(n/4)+n
2.
Qual é o maior valor inteiro para a tal que o algoritmo B seja assintoticamente mais rápido
que A? Justifique.
13. Aplique o Teorema Mestre nas relações de recorrência abaixo, indicando e justificando, para
cada uma, qual caso do Teorema se aplica:
(a) T (n) = 2 T (n/2) + n3.
(b) T (n) = T (9n/10) + n.
(c) T (n) = 16 T (n/4) + n2.
(d) T (n) = 7 T (n/3) + n2.
(e) T (n) = 7 T (n/2) + n2.
(f) T (n) = 2 T (n/4) +
√
n.
14. O Teorema Mestre pode ser aplicado à recorrência T (n) = 4 T (n/2) + n2 log n? Forneça um
limite superior assintótico para essa recorrência. Justifique suas respostas.
15. Resolva a recorrência T (n) = 2 T (
√
n). Sua solução deve ser assintoticamente restrita. Dica:
use mudança de variáveis.
16. Considere o pseudo-código apresentado abaixo. Quantas vezes a comparação “A[r] 6= 0” é
executada? Defina esse número por meio de uma relação de recorrência.
Limpa(A, p, r)
1 se p = r então
2 devolva r
3 senão
4 q ← Limpa(A, p, r − 1)
5 se A[r] = 0 então
6 q ← q + 1
7 A[q]← A[r]
8 devolva q
Forneça uma fórmula exata para a função definida pela recorrência. Em que classe Θ está a
função definida pela recorrência?
17. O tamanho das instâncias de um certo problema é medido por um parâmetro n. Tenho três
algoritmos — A, B e C — para o problema:
• A divide cada instância do problema em cinco subinstâncias de tamanho bn/2c, resolve
as subinstâncias e então combina as soluções em tempo O(n);
• B divide cada instância do problema em duas subinstâncias de tamanho n − 1, resolve
as subinstâncias e então combina as soluções em tempo O(1);
• C divide cada instância do problema em nove subinstâncias de tamanho bn/3c, resolve
as subinstâncias e então combina as soluções em tempo O(n2).
Qual o consumo de tempo de cada um dos algoritmos? Qual dos algoritmos é assintoticamente
mais eficiente no pior caso?
18. Os três algoritmos abaixo calculam corretamente o valor de um inteiro positivo x elevado a
um inteiro positivo n, mas não necessariamente com a mesma eficiência.
Power1(x, n)
1 se n = 0 então
2 devolva 1
3 senão
4 xn′ ← Power1(x, n−1)
5 xn← x · xn′
6 devolva xn
Power2(x, n)
1 se n = 0 então
2 devolva 1
3 senão
4 xn′ ← Power2(x, bn/2c)
5 xn← xn′ · xn′
6 se n mod 2 = 1 então
7 xn← xn · x
8 devolva xn
Power3(x, n)
1 se n = 0 então
2 devolva 1
3 senão
4 xne ← Power3(x, bn/2c)
5 xnd ← Power3(x, bn/2c)
6 xn← xne · xnd
7 r ← n
8 enquanto r ≥ 2 faça
9 r ← r − 2
10 se r = 1 então
11 xn← xn · x
12 devolva xn
Para cada algoritmo, determine:
(a) a relação de recorrência que descreve a complexidade do algoritmo;
(b) uma boa delimitação assintótica para ela a partir da árvore de recorrência; e
(c) a prova de que sua delimitação é correta usando o método da substituição.
19. O algoritmo de Ordenação por Inserção pode ser expresso como um procedimento recursivo
da seguinte forma: para ordenar A[1..n], ordena-se recursivamente A[1..n−1] e então insere-se
A[n] no vetor ordenado A[1..n− 1].
(a) Escreva o pseudo-código da versão recursiva desse algoritmo de ordenação;
(b) Escreva a relação de recorrência para o tempo de execução dessa versão recursiva;
(c) Advinhe uma boa delimitação assintótica para ela usando a árvore de recorrência;
(d) Prove que essa delimitação é correta usando o método da substituição.