PAA_ListaEncPre1_Gab (2)

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
PROJETO E ANÁLISE DE ALGORITMOS 
 
GABARITO - 1ª LISTA DE EXERCÍCIOS DE PROJETO E ANÁLISE DE 
ALGORITMOS 
 
1. Quais os passos necessários para elaborar um algoritmo eficiente? Explique-os. 
(vale 2,0) 
Passo 1: Análise do Problema - A análise do problema é uma etapa importante, 
pois permite uma compreensão do que se pretende e facilita o compartilhamento 
com outros pesquisadores. 
Passo 2: Concepção do Algoritmo - A concepção é uma etapa criativa. Nesta fase, 
podem ser aplicadas as principais técnicas de projeto de algoritmos, as quais serão 
estudadas posteriormente. 
Passo 3: Análise de Eficiência - Por outro lado, o algoritmo pode estar correto, 
mas não ser eficiente. A busca por algoritmos eficientes é de suma importância, 
pois uma pequena alteração no algoritmo poderá trazer grande melhoria no 
desempenho do mesmo. 
Passo 4: Verificação e Refinamento - A verificação é uma etapa importante para 
garantir que o algoritmo trabalhe corretamente e faça o que deve fazer. O 
refinamento consiste em introduzir alterações no algoritmo com vistas a torná-lo 
correto e melhorar sua eficiência em tempo de execução e/ou espaço de memória 
utilizada. 
2. Para cada função f(n) e cada tempo t na tabela a seguir, determine o maior 
tamanho n de um problema que pode ser resolvido no tempo t, supondo-se que o 
algoritmo para resolver o problema demore f(n) milissegundos. 
 1 seg 1 min 1 hora 1 dia 1 mês 
log n 3 4,778 6,556 7,936 11,413 
N 10
3
 6 x 10
4
 6² x 10
5
 864 x 10
5
 2592 x 10
8
 
n² (10
3
)² = 10
6 
(6 x 10
4
)² (6² x 10
5
)² (864 x 10
5
)² (2592 x 10
8
)² 
n³ (10
3
)³ = 10
9
 (6 x 10
4
)³ (6² x 10
5
)³ (864 x 10
5
)³ (2592 x 10
8
)³ 
2
n 
2
1000 
2
60000 
2
3600000
 2
86400000
 2
259200000000
 
 
1 seg = 10
3
 milissegundos 
log 10
3
 = 3 
1 min = 60 x 10
3
 milissegundos = 6 x 10
4
 milissegundos 
1 hora = 3600 x 10
3
 milissegundos = 36 x 10
5
 milissegundos = 6² x 10
5
 
1 dia = 24 horas = 24 x 3600 x 10
3
 milissegundos = 86.400 x 10
3 
= 864 x 10
5 
1 mês = 30 dias = 30 x 864 x 10
5
 milissegundos = 2592 x 10
8
 
3. Dois algoritmos gastam n² dias e n³ segundos, respectivamente, para resolverem 
uma instância de tamanho n. Em alguma situação o algoritmo quadrático é 
melhor do que o algoritmo cúbico? Justificar formalmente. 
1 dia = 24h = 24 x 3600s = 86.400s 
Desta forma n² dias = 86.400 n² segundos então na situação em que c = 86.400 
teremos 86.400 n² ≤ c x n³, para n ≥ 1, 86.400 n² ≤ 86.400 n³. 
 
4. Suponha dois algoritmos A e B, com funções de complexidade de tempo a(n) = n²- 
n + 549 e b(n) = 49n + 49, respectivamente. Determine quais valores de n 
pertencentes ao conjunto dos números naturais para os quais A leva menos tempo 
para executar do que B. 
Para n = 1, temos f(1) = 1² - 1 + 549 = 549 e g(1) = 49x1 + 49 = 98 
Não existe valor de n natural tal que o algoritmo A leva menos tempo para 
executar do que o algoritmo B. 
 
5. É verdade que n² - 600n + 246 = O(n²)? Justifique. 
Sim, porque existe uma constante c > 0, tal que para n suficientemente grande, ou 
a partir de um certo n0, n  n0 , n² - 600n + 246 ≤ c. n². Basta escolher um 
qualquer, por exemplo, c = 2, n0 = 1, temos n  1, 1² - 600x1 + 246 = -353 < 2 x 1² 
= 2. 
 
6. É verdade que n² - 600n + 246 = O(n)? Justifique. 
Não, porque não existe uma constante c > 0 tal que para n suficientemente grande 
n² - 600n + 246 ≤ c.n. 
 
7. É verdade que n² + 200n + 66 = (n³)? Justifique. 
Não, porque não existe uma constante c > 0, tal que para n suficientemente 
grande, c. n³ ≤ n
2
 + 200n + 66. 
 
8. Considere a equação de recorrência a seguir, definindo T(n): 






1),1(2
0,1
)(
nnT
n
nT 
Demonstre por indução que T(n)=2
n
. (vale 1,0) 
Caso Base: para n = 0, T(0) = 2
0
 = 1 ok 
Hipótese de Indução: Suponha que T(n) vale para um n qualquer, n = k, ou seja, 
T(n) = 2
k
, n ≥ 1 
Passo de Indução: agora provemos que n vale para n = k + 1, n ≥ 1 
Observe que T(k + 1) = 2 xT((k +1) – 1) = 2 x T(k), pela hipótese de indução, 
temos T(k+1) = 2x T(k) = 2x 2
k
 = 2
k+1
, portanto T(n) é verdadeiro para todo n  
N. 
 
9. Usar o método da substituição para provar que a solução de T(n)=T(n/2) + 1 é 
O(logn). 
T(n) = T(n/2) + 1 por hipótese temos: 
T(n) ≤ c x log n/2 + 1 
T(n) ≤ c x log n – log 2 + 1 como log 2 =1 temos 
T(n) ≤ c x log n – 1 + 1 
T(n) ≤ c x log n portanto T(n) = O(logn). 
 
10. Através do Método Mestre, determinar limites assintóticos para as seguintes 
recorrências. 
a) T(n) = 16T(n/4) + n² 
T(n) = aT(n/b) + f(n) 
a = 16, b = 4, f(n) = n² 
𝑛log4 16 = 𝑛2, como f(n) = n² é da ordem Θ(n²) então, pelo Teorema Mestre 
caso ii), T(n) = 16T(n/4) + n = Θ(𝑛log4 16𝑙𝑔𝑛) = Θ(n² lg n) 
 
b) T(n) = 7T(n/3) + n² 
T(n) = aT(n/b) + f(n) 
a = 7, b = 3, f(n) = n² 
𝑛log3 7 = 𝑛1,77, como f(n) = n² não é da ordem Θ(𝑛1,77), então considere  = 
1 e observe que logo f(n) = n² = (nlog3 7+1=𝑛1,89) = (𝑛1,89). Além disso, 
7f(n/3) ≤ c. f(n), ou seja, 7n²/9 ≤ 8/9 x n² para c = 8/9. Pelo Teorema Mestre, 
caso iii), T(n) = 7T(n/3) + n² = Θ(f(n)) = Θ(n²) 
 
c) T(n) = 5T(n/4) + n 
T(n) = aT(n/b) + f(n) 
a = 5, b = 4, f(n) = n 
𝑛log4 5 = 𝑛1,16, como f(n) = n não é da ordem Θ(𝑛1,16), então considere  = 1 
e observe que nlog4 5-1=𝑛log4 4 = 𝑛, logo f(n) = n = O(n). Pelo Teorema 
Mestre, caso i), T(n) = 5T(n/4) + n = Θ(𝑛log4 5) 
 
11. Quanto tempo (em números de operações) é gasto para executar os seguintes 
algoritmos? 
a) Ler (n); essa linha é executada apenas uma vez (1 leitura) 
i  2; essa linha é executada apenas uma vez (1 atribuição) 
Fat  1, essa linha é executada apenas uma vez (1 atribuição) 
Enquanto i  n, faça essa linha é executada n vezes (comparações) 
 Fat  Fat * i; essa linha é executada n-1 (1 atribuição, 1 multiplicação) 
 i  i + 1; essa linha é executada n-1 (1 atribuição, 1 soma) 
 T(n) = n+ 4(n-1) + 3 = 5n – 4 + 3 = 5n -1 operações 
 
b) Para i ←1 até n – 1 faça n – 1 operações 
 Para k ←1 até n – 1 faça (n – 1)x(n – 1) operações 
 S[i, k] ← S[i, k] - S[i, k]* S[i, i]/ S[i, i] 4 x (n – 1)x(n – 1) operações 
 T(n) = n – 1 + 5 x (n² - 2n + 1) = 5n² - 9n + 5 operações 
 
12. Determine o tempo consumido na execução dos algoritmos abaixo: 
a) S  0; T(n) = 1 
Para i  1 até n, faça T(n) = n 
 Para j  2 até n, faça T(n) = n (n -1) [1 + 2] 
 A[i, j]  i + j 
retorne A[i, j]. T(n) = 1 
 T(n) = 1 + n + 3n² -3n + 1 = 3n² - 2n + 2 portanto T(n) = O(n²) 
 
a) Se A[i, i] = 0, então 
Para i  1 até n, faça T1(n) = n 
 Para j  1 até n, faça T1(n) = n² (1+2) = 3n² + n, T1(n) = O(n²) 
 A[i, j]  i + j 
Senão 
Para i  1 até n, faça T2(n) = n (1 + 1) = 2n, T2(n) = O(n) 
 A[i, i]  i 
 T(n) = T1(n) + T2(n) = O(max(n², n))