Trabalho de Cana

Prévia do material em texto

Universidade Federal do Ceará
Departamento de Computação
Construção e Análise de Algoritmos
Trabalho de Implementação 1
Relembre o Algoritmo 1 da Questão 4 da Lista 1, descrito abaixo:
Questão 4 da Lista 1 Considere o algoritmo NumRecursivo(N) abaixo. Determine o valor retornado
em notação assintótica.
Algorithm 1 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/10c) + N
end if
retorne Valor
(i) Implemente esse algoritmo na linguagem de sua preferência e monte uma curva com pelo menos 1000
valores retornados desse algoritmo para valores de N de 100.000 em 100.000.
Ou seja, N = 105, 2 · 105, 3 · 105, 4 · 105, . . ..
(ii) Na Lista 1, é pedido para provar que o número retornado pelo algoritmo é da ordem assintótica
de Θ(n · log(n)). Com os dados da curva que você obteve no parágrafo anterior, tente estimar qual seria a
melhor base B do logaritmo de modo que o número retornado seja aproximadamente ≈ n logB(n).
(Dica: Obter uma curva de bases e tirar a média).
(iii) Finalmente, tente fazer alguma conta teórica (sem usar as curvas geradas) que dê uma boa estimativa
para essa base B do logaritmo e compare com o valor obtido no parágrafo anterior.
(Dica: indução matemática ignorando casos bases).
Repita esse procedimento anterior para os seguintes Algoritmos 2 a 7:
Algorithm 2 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c) + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/15c) + N
end if
retorne Valor
Algorithm 3 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/30c) + N
end if
retorne Valor
Algorithm 4 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/15c) + NumRecursivo(bN/15c) + N
end if
retorne Valor
Algorithm 5 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/12c) + NumRecursivo(bN/12c) + N
end if
retorne Valor
Algorithm 6 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c) + NumRecursivo(bN/5c)
Valor = Valor + NumRecursivo(bN/5c) + NumRecursivo(bN/5c) + N
end if
retorne Valor
Algorithm 7 inteiro NumRecursivo(inteiro N)
Valor = 0 //(Valor é uma variável local)
if N > 1 then
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + NumRecursivo(bN/6c) + NumRecursivo(bN/6c) + NumRecursivo(bN/6c)
Valor = Valor + N
end if
retorne Valor
2
Figura 1: Exemplos de curvas a serem geradas
3
1 Solução do item (iii) do Algoritmo 1
Faremos a estimativa para a melhor base do logaritmo através de uma indução sem caso base:
Fixe N inteiro grande e seja T (N) o tempo do Algoritmo 1. Suponha que T (N ′) ≈ N ′ · logB N ′ para todo
N ′ < N . Queremos provar que também vale para N , ou seja, T (N) ≈ N · logB N . Vamos tentar estimar o
valor de B para que isso ocorra.
Do Algoritmo 1, temos que:
T (N) = 2 · T (N/5) + 3 · T (N/6) + T (N/10) + N
Pela hipótese da indução, temos que:
T (N) ≈ 2 ·
(
N
5
logB
N
5
)
+ 3 ·
(
N
6
logB
N
6
)
+
(
N
10
logB
N
10
)
+ N
T (N) ≈ 2N
5
(
logB N − logB 5
)
+
N
2
(
logB N − logB 6
)
+
N
10
(
logB N − logB 10
)
+ N
T (N) ≈
(
2N
5
logB N +
N
2
logB N +
N
10
logB N
)
+
(
N − 2N
5
logB 5 −
N
2
logB 6 −
N
10
logB 10
)
T (N) ≈
(
2
5
+
1
2
+
1
10
)
·N logB N + N ·
(
1 − 2
5
logB 5 −
1
2
logB 6 −
1
10
logB 10
)
T (N) ≈
(
4
10
+
5
10
+
1
10
)
·N logB N + N ·
(
1 − logB 52/5 − logB 61/2 − logB 101/10
)
T (N) ≈ N · logB N + N ·
(
1 − logB
(
52/5 · 61/2 · 101/10
))
Portanto, para que T (N) ≈ N · logB N , temos que B = 52/5 · 63/6 · 101/10.
Portanto B = 5.870345.
Observação: Note que essa não é uma conta oficial de indução matemática, visto que não tem caso base e
a aproximação ≈ não está bem definida. Além disso, a hipótese de indução é muito forte, forçando igualdade
T (N ′) ≈ N ′ · logB N ′ para todo N ′ < N , o que não ocorre (basta verificar os exemplos nos gráficos). Então,
formalmente falando, essa conta nem está correta. Mas, na prática, ela funciona sim e podemos considerar o
B como sendo mesmo a base teórica, pois podemos provar por indução matemática 100% correta seguindo
a mesma estrutura dessa conta que, para N suficientemente grande, T (N) < N · logb N para base b < B e
T (N) > N · logb N para base b > B. Resumindo, esta conta não está formalmente correta, mas nos retorna
o que queremos de fato: a base B teórica. Veja na figura seguinte como a curva T (N)/N adere bem ao
gráfico do logaritmo na base B.
4
Figura 2: Outro exemplo de curva a ser gerada (agora comparando com a base B teórica)
5
Construção e Análise de Algoritmos
Trabalho de Implementação 1
Victória Tomé Oliveira
1Departamento de Computação – Universidade Federal do Ceará (UFC)
Fortaleza – CE – Brasil
1. Questão 4
Considere os algoritmos NumRecursivo(N) determinou-se o valor retornado em notação
assintótica.
Inicialmente, implementou-se um algoritmo na linguagem C++ e, a partir disto foi
gerada uma curva de cada algoritmo para valores de N de 100.000 em 100.000.
A seguir, temos o código do algoritmo 1, para os demais algoritmos foi utilizado o
mesmo código, apenas modificando os parâmetros.
1 #include <iostream>
2 #include <fstream>
3 #include <cmath>
4 #include <ctime>
5 #include <climits>
6 #include <windows.h>
7
8 using namespace std;
9
10 void Questao4(int N);
11
12 int intQuestao4;
13
14 int main() {
15 int i,N;
16 ofstream arq;
17 arq<<fixed;
18 arq.open("questao4.txt");
19 arq<<"N\tT(N)\tN*log(N,10)\tN*log(N,6)\tN*log(N,5)"<<endl;
20
21 cout<<endl;
22 for (int i=10000; i<=3000000; i+=10000) {
23 intQuestao4 = 0;
24 Questao4(i);
25 arq<<i<<"\t"<<intQuestao4<<"\t"<<(int)(i*log(i)/log(10))
<<"\t"<<(int)(i*log(i)/log(6))<<"\t"<<(int)(i*log(i)/
log(5))<<"\t"<<endl;
26 }
27 arq.close();
28 cout << "<Questao4> Ok: ver arquivo questao4.txt" << endl;
29
30 }
31
32 void Questao4(int N) {
33 if (N<=1)
34 return;
35 intQuestao4 = intQuestao4 + N;
36 Questao4(N/5);
37 Questao4(N/5);
38 Questao4(N/6);
39 Questao4(N/6);
40 Questao4(N/6);
41 Questao4(N/10);
42 }
Na Lista 1, é foi pedido para provar que o núumero retornado pelo algoritmo é da
ordem assintótica de Θ(n·log(n)). A partir dos gráficos gerados a partir do algoritmo em
C++ a melhor base para os algoritmos 1, 2, 3, 4, 6 e 7 é Θ(n · logn6 ), entretando o algoritmo
5 tem base Θ(n · logn5 ). Nas Figuras a seguir é possı́vel observar os gráficos.
Faz-se a estimativa para a melhor base do logaritmo através de uma indução sem
caso base. Fixou-se o N inteiro grande e seja T(N) o tempo do Algoritmo. Suponha que
T (N) ≈ N ′ · logBN ′ para todo N ′ < N . Provando que também vale para N, ou seja,
T (N) ≈ N · logBN . Foi estimado o valor de B para que isso ocorra.
1.1. Algoritmo 1
Figura 1. Algoritmo 1.
Figura 2. Gráfico do Algoritmo 1.
Para o Algoritmo 1, tem-se que:
T (N) ≈ 2T (N
5
) + 3T (N
6
) + T (N
10
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 2(N
5
logB
N
5
) + 3(N
6
logB
N
6
) + (N
10
logBN
10
) + N
T (N) ≈ 2N
5
(logBN − logB5) + 3N6 (logBN − logB6) +
N
10
(logBN − logB10) +N
T (N) ≈ (2N
5
logBN +
3N
6
logBN +
N
10
logBN) + (N − 2N5 logB5 −
3N
6
logB6 −
N
10
logB10)
T (N) ≈ (2N
5
+ 3N
6
+ N
10
)logBN + N(1 − 25 logB5 −
3
6
logB6 − 110 logB10)
T (N) ≈ (2
5
+ 3
6
+ 1
10
)NlogBN + N(1 − logB5
2
5 − logB6
3
6 − logB10
1
10 )
T (N) ≈ ( 4
10
+ 5
10
+ 1
10
)NlogBN + N(1 − logB5
2
5 − logB6
3
6 − logB10
1
10 )
T (N) ≈ (10
10
)NlogBN + N(1 − logB5
2
5 − logB6
3
6 − logB10
1
10 )
T (N) ≈ NlogBN + N(1 − logB(5
2
5 · 6 36 · 10 110 )
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 5
2
5 · 6 36 · 10 110
Conclui-se que, B ≈ 5, 87
1.2. Algoritmo 2
Figura 3. Algoritmo 2.
Figura 4. Gráfico do Algoritmo 2.
Para o Algoritmo 2, tem-se que:
T (N) ≈ 3T (N
5
) + 2T (N
6
) + T (N
15
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 3(N
5
logB
N
5
) + 2(N
6
logB
N
6
) + (N
15
logB
N
15
) + N
T (N) ≈ 3N
5
(logBN − logB5) + 2N6 (logBN − logB6) +
N
15
(logBN − logB15) +N
T (N) ≈ (3N
5
logBN +
2N
6
logBN +
N
15
logBN) + (N − 3N5 logB5 −
2N
6
logB6 −
N
15
logB15)
T (N) ≈ (3N
5
+ 2N
6
+ N
15
)logBN + N(1 − 35 logB5 −
2
6
logB6 − 115 logB15)
T (N) ≈ (3
5
+ 2
6
+ 1
15
)NlogBN + N(1 − logB5
3
5 − logB6
2
6 − logB15
1
15 )
T (N) ≈ (18
30
+ 10
30
+ 2
30
)NlogBN + N(1 − logB5
3
5 − logB6
2
6 − logB15
1
15 )
T (N) ≈ (30
30
)NlogBN + N(1 − logB5
3
5 − logB6
2
6 − logB15
1
15 )
T (N) ≈ NlogBN + N(1 − logB(5
3
5 · 6 26 · 15 115 )
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 5
3
5 · 6 26 · 15 115
Conclui-se que, B ≈ 5, 71
1.3. Algoritmo 3
Figura 5. Algoritmo 3.
Figura 6. Gráfico do Algoritmo 3.
Para o Algoritmo 3, tem-se que:
T (N) ≈ 4T (N
5
) + T (N
6
) + T (N
30
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 4(N
5
logB
N
5
) + (N
6
logB
N
6
) + (N
30
logB
N
30
) + N
T (N) ≈ 4N
5
(logBN − logB5) + N6 (logBN − logB6) +
N
30
(logBN − logB30) + N
T (N) ≈ (4N
5
logBN+
N
6
logBN+
N
30
logBN)+(N− 4N5 logB5−
N
6
logB6−N30 logB30)
T (N) ≈ (4N
5
+ N
6
+ N
30
)logBN + N(1 − 45 logB5 −
1
6
logB6 − 130 logB30)
T (N) ≈ (4
5
+ 1
6
+ 1
30
)NlogBN + N(1 − logB5
4
5 − logB6
1
6 − logB30
1
30 )
T (N) ≈ (24
30
+ 5
30
+ 1
30
)NlogBN + N(1 − logB5
4
5 − logB6
1
6 − logB30
1
30 )
T (N) ≈ (30
30
)NlogBN + N(1 − logB5
4
5 − logB6
1
6 − logB15
1
30 )
T (N) ≈ NlogBN + N(1 − logB(5
4
5 · 6 16 · 30 130 ))
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 5
4
5 · 6 16 · 30 130
Conclui-se que, B ≈ 5, 47
1.4. Algoritmo 4
Figura 7. Algoritmo 4.
Figura 8. Gráfico do Algoritmo 4.
Para o Algoritmo 4, tem-se que:
T (N) ≈ T (N
5
) + 4T (N
6
) + 2T (N
15
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ (N
5
logB
N
5
) + 4(N
6
logB
N
6
) + 2(N
15
logB
N
15
) + N
T (N) ≈ N
5
(logBN − logB5) + 4N6 (logBN − logB6) +
2N
15
(logBN − logB15) +N
T (N) ≈ (N
5
logBN +
4N
6
logBN +
2N
15
logBN) + (N − N5 logB5 −
4N
6
logB6 −
2N
15
logB15)
T (N) ≈ (N
5
+ 4N
6
+ 2N
15
)logBN + N(1 − 15 logB5 −
4
6
logB6 − 215 logB15)
T (N) ≈ (1
5
+ 4
6
+ 2
15
)NlogBN + N(1 − logB5
1
5 − logB6
4
6 − logB15
2
15 )
T (N) ≈ ( 6
30
+ 20
30
+ 4
30
)NlogBN + N(1 − logB5
1
5 − logB6
4
6 − logB15
2
15 )
T (N) ≈ (30
30
)NlogBN + N(1 − logB5
1
5 − logB6
4
6 − logB15
2
15 )
T (N) ≈ NlogBN + N(1 − logB(5
1
5 · 6 46 · 15 215 )
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 5
1
5 · 6 46 · 15 215
Conclui-se que, B ≈ 6, 53
1.5. Algoritmo 5
Figura 9. Algoritmo 5.
Figura 10. Gráfico do Algoritmo 5.
Para o Algoritmo 5, tem-se que:
T (N) ≈ 5T (N
6
) + 2T (N
12
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 5(N
6
logB
N
6
) + 2(N
12
logB
N
12
) + N
T (N) ≈ 5N
6
(logBN − logB6) + 2N12 (logBN − logB12) + N
T (N) ≈ 5N
6
logBN +
2N
12
logBN) + (N − 5N6 logB6 −
2N
12
logB12)
T (N) ≈ (5N
6
+ 2N
12
)logBN + N(1 − 56 logB6 −
2
12
logB12)
T (N) ≈ (5
6
+ 2
12
)NlogBN + N(1 − logB6
5
6 − logB12
2
12 )
T (N) ≈ (10
12
+ 2
12
)NlogBN + N(1 − logB6
5
6 − logB12
2
12 )
T (N) ≈ (12
12
)NlogBN + N(1 − logB6
5
6 − logB12
2
12 )
T (N) ≈ NlogBN + N(1 − logB(6
5
6 · 12 212 )
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 6
5
6 · 12 212
Conclui-se que, B ≈ 6, 73
1.6. Algoritmo 6
Figura 11. Algoritmo 6.
Figura 12. Gráfico do Algoritmo 6.
Para o Algoritmo 6, tem-se que:
T (N) ≈ 5T (N
5
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 5(N
5
logB
N
5
) + N
T (N) ≈ 5N
5
(logBN − logB5) + N
T (N) ≈ 5N
5
logBN + (N − 5N5 logB5)
T (N) ≈ 5N
5
NlogBN + N(1 − 55 logB5)
T (N) ≈ 5
5
NlogBN + N(1 − logB5
5
5 )
T (N) ≈ NlogBN + N(1 − logB5
5
5 )
T (N) ≈ NlogBN + N(1 − logB(51))
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 5
1.7. Algoritmo 7
Figura 13. Algoritmo 7.
Figura 14. Gráfico do Algoritmo 7.
Para o Algoritmo 7, tem-se que:
T (N) ≈ 6T (N
6
) + N
Pela hipótese da indução, tem-se que:
T (N) ≈ 6(N
6
logB
N
6
) + N
T (N) ≈ 6N
6
(logBN − logB6) + N
T (N) ≈ 6N
6
logBN + (N − 6N6 logB6)
T (N) ≈ 6N
6
NlogBN + N(1 − 66 logB6)
T (N) ≈ 6
6
NlogBN + N(1 − logB6
6
6 )
T (N) ≈ NlogBN + N(1 − logB6
6
6 )
T (N) ≈ NlogBN + N(1 − logB(61))
Portanto, para que T (N) ≈ NlogBN , temos que B ≈ 6
	Questão 4
	Algoritmo 1
	Algoritmo 2
	Algoritmo 3
	Algoritmo 4
	Algoritmo 5
	Algoritmo 6
	Algoritmo 7