Fundamentos de Programação e Estruturas de Dados - Lista de Exercícios -

1. Análise de alguns algoritmos simples

Exercício 1 : Contagem de iterações Analise o algoritmo abaixo, e diga qual será o valor de k, ao final de sua execução.

DETERMINA_K (n)

k ← 0 loop externo para i variando de 1 até n faça

para j variando de 1 até i faça loop interno k ← k + 1

devolva k Solução: Quando i assume o valor 1, o loop mais interno incrementa k

exatamente 1 vez. Quando i valer 2, k será incrementado duas vezes. E assim por diante, até que, na última iteração do loop mais externo i deverá assumir valor igual a n, e então o loop mais interno deverá incrementar k um total de n vezes.

Assim, o valor de k será : k = 1 + 2 + . . . + ( n – 1 ) + n

Observe que k segue uma P.A. (progressão aritmética) de n termos, cujo 1º termo é igual a 1, e o último termo vale exatamente n.

2)1( +=∴ nnk

Exercício 2 : O cálculo de T(n) Analise o mesmo algoritmo do exercício anterior, e determine quanto tempo ele consome para executar.

Solução: Imagine que cada linha, quando executada, consome tempo

exatamente igual a 1. Para ver quanto tempo o algoritmo levará para executar, basta somar o total de vezes que cada linha será executada.

linha contagem

1 + 2 + . . . + n

1

2 + 3 + . . . + ( n + 1 )

k ← 0 para i variando de 1 até n faça para j variando de 1 até i faça

k ← k + 1

n + 1

H. Senger 17/4/2004 - 1

Assim,

23)(2

4622

342)(

223)1(1)(

21

2)1(2)1(1)(

)1(1)(

2

222

22

1

1

2

++=∴

++=

+++++=

++

++++=

++

+++++=

++++= ∑∑+

nnnT

nnnnnnnnT

nnnnnnT

nnnnnnT

iinnTnn

Exercício 3 : Algoritmos com séries de termos Conforme se sabe, podemos obter uma boa aproximação para o cálculo de exp(x) (isto é, ex ) através da série de somas parciais :

!...

!3!21

32

nxxxxs

n

n +++++=

Na verdade, trata-se apenas de uma aproximação, pois

)exp(lim xSnn=

∞→

Veja um algoritmo para calcular exp(x), com um limite de precisão que interrompe o cálculo após o n-ésimo termo.

EXP (x,n) S ← 1 para i de 1 até n faça /* calcula n termos da série */

num ← 1 den ← 1

para j de 1 ate i faça /* calcula numerador e o denominador */ num ← num * x /* num ← xi */ den ← den * j /* den ← i! */

S ← S + num / den devolva S

H. Senger 17/4/2004 - 2

PEDE-SE : a) Simule o algoritmo para os valores de : x = 2 e n = 3 b) Determine o tempo de execução do algoritmo, T(n) : (Resolvido)

x n i j num den S

linha contagem

n 1 + 2 + . . . + n 1 + 2 + . . . + n 2 + 3 + . . . + ( n + 1 ) n

1

n

S ← 1 para i de 1 até n faça

num ← 1 den ← 1 para j de 1 ate i faça

num ← num * x den ← den * j

S ← S + num / den

n + 1

Assim,

23213

23)(

24133

2384)(

222342)(

21

21

2)1(242)(

)1(1)(

2

2222

222

11

1

2

++=∴

++=

+++++++=

++

++

+++=

++

++

++++=

++++++++= ∑∑∑+

nnnT

nnnnnnnnnnT

nnnnnnnnT

nnnnnnnnT

niiinnnnTnnn

Exercício 4 : Melhoria do algoritmo para exp(x) É possível melhorar a eficiência do cálculo de exp(x). Vamos rever a série :

!...

!3!21

32

nxxxxs

n

n +++++=

H. Senger 17/4/2004 - 3

Observamos que o cálculo da série com n termos pode ser escrita na forma :

nn TTTs ++++= ...1 21 , onde cada Ti é um termo da série, e pode ser determinado a partir de seu anterior Ti-1:

1,*1

1

⟩∀=

=

− iixTT

xT

ii

Vejamos então uma nova versão do algoritmo :

EXP (x,n) T ← 1 S ← T para i de 1 até n faça /* calcula n termos sa série */ T ← T * x / i

S ← S + T devolva S

PEDE-SE : a) Simule o novo algoritmo para os valores de : x = 2 e n = 3 b) Determine o te

H. Senger

x n i T S

mpo de execução do novo algoritmo, T(n) :

17/4/2004 - 4

2. Notação Ο (Ó grande), Ω (ômega) e Θ (theta)

Exercício 5 : Dê um significado para as notações assintóticas Ο, Ω e Θ. Diga o que significa cada uma delas. Dica: Uma interpretação gráfica pode ajudar bastante.

Exercício 6 : (resolvido) Supondo que f(n)=3n, encontre uma função g(n), tal que f(g(n))=g(f(n))=n. Em outras palavras, encontre uma função g, tal que y=f(x) se e somente se x=g(y).

Solução: Uma possível resposta para o problema é a função g(n)=n/3. Posso provar isso, mostrando que f(g(n))=3g(n)=3*n/3=n e g(f(n))=g(3n)=3n/3=n.

Exercício 7 : Para os diversos valores de f(n) abaixo, encontre uma função g(n), tal que f(g(n))=g(f(n))=n. a) n+7 b) 7n c) n/5 d) n4 e) n1/4 f) n-1 g) n-5 h) 7n i) 7-log

5n

Exercício 8 : Prove que são verdadeiras (ou que são falsas) as afirmações abaixo. a) n=Ο(n2)

Solução: Isso é fácil de provar. Basta encontrar c (c > 0) tal que n ≤ c n2 para algum n inteiro e positivo que seja suficientemente grande (ou seja, acima de um certo n0). Assim, se fizermos c = 1, a expressão será válida para quaisquer valores de n≥1.

A resposta pode ser dada, por exemplo, desta forma: n pode ser Ο(n2), pois

n ≤ c n2 para c = 1 e para todo n≥1 (ou seja, n0 = 1). Obs.: Para provar que uma função f é O(g) você deve mostrar os valores de c e

n0 . O professor irá corrigir a questão verificando se realmente a relação n ≤ c n2 é verdadeira para todo n ≥ n0.

b) n2 =Ο(n) Solução: Para provar isso, seria necessário encontrar c tal que

n2 ≤ c n para algum n grande, acima de um certo n0 Vamos supor que esse c existe. Então, podemos trabalhar um pouco sobre essa desigualdade e concluir que

c ≥ n Mas isso é impossível, pois não pode existir um valor constante c que seja maior do que n, para n suficientemente grande.

RESPOSTA : Quando uma função f NÃO É O(g), a resposta deve ser um pouco diferente : n2 não pode ser Ο(n), pois não existe a constante inteira e positiva c que satisfaz a relação n2 ≤ c n.

H. Senger 17/4/2004 - 5

c) n2+3n-5=Ο(n2) d) n2=Ο(n2+3n-5) e) n2=Ο(n3) f) n3=Ο(n2) g) n2+3n-5=Ο(n3) h) 4n2+n-5=Ο(n) i) nn=Ο(n!) j) n5=Ο(2n) (Resolvido)

Solução: Esta prova é um pouco diferente das anteriores, pois envolve funções polinomiais e exponenciais (n5 é uma função polinomial, pois pode ser escrita forma a0.n0 + a1.n1 + ... e 2n é uma função exponencial, pois tem a variável n como expoente). Qualquer função polinomial tem crescimento assintótico menor do que qualquer função exponencial. Essa afirmativa baseia-se no fato de que

para todas as constantes a e b reais, tal que a > 1. Na prática, você não precisa desse blá blá blá todo. Apenas dê um exemplo de c e n0 que satisfazem a relação.

0lim =∞→ n

b

n an

k) 10n=Ο(n2) l) 2n3=Ο(2n) m) lg n=Ο(n)

Exercício 9 : (resolvido) Prove que são verdadeiras (ou que são falsas) as afirmações abaixo. a) 1/2n2-3n=Θ( n2)

Solução: 1/2n2-3n é realmente Θ( n2) se conseguirmos achar os valores n0, c1 e c2, tais que :

c1 . n2 ≤ ½ n2 – 3 n ≤ c2 . n2, para todo n > n0

Para descobrir c1 e c2 vamos dividir a expressão acima por n2, e então teremos

c1 ≤ ½ – 3/ n ≤ c2 Tomando o lado direito da desigualdade, e fazendo n ≥ 1 teremos os valores de

c1 ≤ 1/14 e c2 ≥ ½, que validam a expressão. Para provar, basta analisar o comportamento da desigualdade. Como só interessam valores inteiros e positivos para c1 e c2, temos que considerar n ≥ 7.

Ou então, fazendo n ≥ 7 teremos que ½-3/n assume valores no intervalo [1/14, ½[

Portanto, c1 = 1/14, c2 = ½ e n0 = 7

Exercício 10 : (resolvido) Prove ou desprove que 6n3=Θ (n2).

H. Senger 17/4/2004 - 6

Solução : Se 6n3=Θ (n2), então devem existir c1 e c2 tal que c1 . n2 ≤ 6 n3 ≤ c2 . n2, para todo n > n0

Se analisarmos a segunda desigualdade, ou seja,

6 n3 ≤ c2 . n2

então, teremos que 6 ≤ c2 . n2/ n3

6 ≤ c2 ./ n Isso é impossível, se pensarmos em n realmente grande, pois c2 teria de ser

maior do que 6n, e nesse caso c2 não seria uma constante, mas teria de ser maior, à medida que n cresce.

H. Senger 17/4/2004 - 7