Lista de exercicio 3 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinicius Barcelos Silva 
Matricula: 108251 
Lista 3 
 
3.1­3  
Primeiro vamos definir a função max ( f(n), g(n)), vamos definir a função h(n) = max ( f(n), g(n)). Agora: 
h(n) = { f(n) se f(n)   g(n)≥  
h(n) = { g(n) se f(n) < g(n) 
 
Tendo que f(n) e g(n) são assintoticamente positivos, existe um   tal que f(n)   0 e g(n)   0 para todo n n0 ≥ ≥ ≥  
.n0   
Assim, para todo n    , f(n) + g(n)   f(n)   0 e f(n) + g(n)  g(n)   0.≥ n0 ≥ ≥   ≥ ≥  
Uma vez que para qualquer n particular, h(n) é f(n) ou g(n), logo temos que f(n) + g(n)   h(n)   0, com isso≥ ≥  
mostramos que  h(n) = max ( f(n), g(n))   c2( f(n) + g(n)) para todo n    . Tendo c2 = 1 na definição de ≤ ≥ n0 Θ
. 
 
Da mesma maneira temos que para qualquer n particular, h(n) é maior que f(n) e g(n), tendo para todo n  ≥  
 , 0   f(n)   h(n) e o 0   g(n)   h(n). Com a adição destes dois diferentes, produzimosn0 ≤ ≤ ≤ ≤   
0   f(n) + g(n) < 2h (n), equivalente à 0 <= ( f(n) + g(n)) / 2   h(n), que mostramos que≤ ≤   
h(n) = max ( f(n), g(n))   c1( f(n) + g(n)) para todo n    . Tendo c1 = 1/2 na definição de  .≥ ≥ n0 Θ  
 
 
3.1­4 
 mas O (2  )2n+1 =   2n     = (2  ).2 2n / O n  
Temos que mostrar que  , agora temos que encontrar uma constante c,  > 0 tal queO (2  )2n+1 =   2n n0   
0     c     para todo n    .≤ 2n+1 ≤ •  2 n ≥ n0  
Desde que   para todo n, podemos assim satisfazer a definição com c = 2  e   = 1.2  2 2n+1 =   •   2n n0  
Assim mostramos que  , assumindo que existem constantes c ,   > 0 tal que 2 2n = (2  )  / O n n0  
0     c     para todo n     .≤ 2n ≤ •  2 n ≥ n0  
Portanto,   . Mas a constante não é maior que todos os   , assim provamos    2    2    2   2 2n =   n •   n ≤ c •   n ⇒ 2 n ≤ c  2 n  
por contradição que a hipótese não é verdadeira. 
 
3.1­7 
Temos que: 
o: limite superior que não é assintoticamente restrito 
ω: limite inferior que não é assintoticamente restrito 
Se o limite “o” tentendo para o infinito é igual a 0 e o limite “ω” tentendo para o infinito é igual ao infinito, 
temos que a intersecção de o(g(n)) com ω(g(n)) é vazia. 
 
 
 
 
 
 
3.2­3 
(I) Para o(g(n)) = (f(n) : para qualquer constante c > 0, existe uma constante  
 > 0 tal que 0   f(n) < c . g(n) para todo n )n0 ≤ ≥ n0  
Portanto 0   o( ) < n! .≤ nn  
 
(II) Para ω(g(n)) = (f(n) : para qualquer constante c > 0, existe uma constante   > 0 tal quen0   
0  c . g(n) < f(n) para todo n    ).≤ ≥ n0  
Portanto 0   n! < ω( ) .≤ 2n  
 
 
3.2­5 
lg(lg   n) > lg (lg n)• •  
 
 
A.1­1 
 = ((2 (2n​­1) + (n­​1)*(2 k­​1))n) / 2∑ 
 
• •  
 
A.1­7 
O produto finito 2   é uma progressão geométrica que varia de acordo com o k.• 4k