Teorema mestre Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Teorema mestre – Teoria dos Grafos e Análise de Algoritmos
Exercícios
1. Relações de recorrência possibilitam que um problema seja modelado a partir de
si próprio, considerando instâncias de menor tamanho. Este é o caso da sequência
de números S = (1, 2, 22, 23, ..., 2n, ...). Assinale a alternativa que apresenta a
recorrência que expressa corretamente a sequência de números S.
Você acertou!
Resposta: A
 (   ) = 2 ×   (   − 1 ) ,     ≥ 1   (   ) = 1 ,     = 0 𝑇 𝑛 𝑇 𝑛 𝑠𝑒 𝑛 𝑇 𝑛 𝑠𝑒 𝑛
2. Um dos métodos amplamente utilizados para a solução de recorrências é
conhecido como o método da substituição. Considerando o uso desse método para
verificar se O(n2) é solução para a recorrência T(n) = T(n - 1) + n é , leia as
assertivas a seguir.
I. Após a construção da desigualdade inicial, o próximo passo envolve a avaliação
de n na solução proposta.
II. Um dos passos da resolução envolve a avalição de uma diferença entre dois
termos elevada à potência de 2.
III. A aplicação do método se inicia com a construção da desigualdade
, onde c > 0.
IV. A conclusão da aplicação do método é que a solução proposta resolve a
recorrência em questão.
Quais são corretas?
Você acertou!
B. II e IV.
A alternativa I é falsa, porque o passo subsequente à construção da desigualdade
corresponde à avaliação de n - 1 segundo a solução proposta.
A alternativa II é verdadeira, porque um dos passos envolve a avaliação do termo
(n - 1)2. 
A alternativa   III  é   falsa.  A aplicação  do método  se   inicia  com a  construção  da
desigualdade  ( ) ≤  (  − 1) 2 +  , com c > 0.𝑇 𝑛 𝑐 𝑛 𝑛
A alternativa IV é verdadeira, porque a aplicação do método implica os seguintes
passos: 
( ) ≤   2 +   ≤  (  − 1) 2 +   =   2 − 2  +   +   =   2 −  (2  − 1) +   ≤  (  2 ). Logo,𝑇 𝑛 𝑐𝑛 𝑛 𝑐 𝑛 𝑛 𝑐𝑛 𝑐𝑛 𝑐 𝑛 𝑐𝑛 𝑛 𝑐 𝑐 𝑂 𝑛
O(n2 ) é a solução para a recorrência. 
3. A eficácia do método de substituição tem dependência intrínseca da proposição 
de uma boa solução (bom "chute") para a recorrência, e a verificação da solução é 
feita por indução matemática. Considerando a seguinte recorrência
marque V para verdadeira e F para falsa para as afirmações a respeito de sua
resolução:
( ) Se uma solução genérica O(♦) é proposta para a recorrência, então uma
desigualdade do tipo
deve ser construída para qualquer valor de c.
( ) Se O(log(n)) é uma solução proposta para a recorrência, então um dos passos do
método envolve a avaliação da diferença log(n) - log2, e o método conclui com a
validação da solução.
( ) Se O(n2) é uma solução proposta para a recorrência, então o passo final do
método vai gerar a expressão
 que confirma a validade da solução.
( ) Se O(n) é uma solução proposta para a recorrência, então a aplicação do método
inicia com a substituição da recorrência pela expressão cn + 1 e conclui com a
validação da solução.
Feito isso, assinale a alternativa que apresenta a sequência correta:
Você acertou!
C. F - V - F - F.
A primeira alternativa é falsa, porque o método de substituição tem a premissa de
valores positivos para a constante c utilizada, ou seja, c > 0. 
A segunda alternativa é verdadeira, porque a aplicação do método para a solução
proposta envolverá os seguintes passos:  ( ) ≤  ( ) + 1 =   (log (   2 )) + 1 =  (log( ) −𝑇 𝑛 𝑐𝑙𝑜𝑔 𝑛 𝑐 𝑛 𝑐 𝑛
2) + 1 =  ( ) −   + 1 ≤  (log( )) Logo, O(log(n)) é solução para a recorrência, e a𝑙𝑜𝑔 𝑐𝑙𝑜𝑔 𝑛 𝑐 𝑂 𝑛
aplicação do método contempla a diferença citada na afirmação, conforme destacado na
resolução. 
A terceira alternativa é falsa, porque, embora a expressão   2 4+1 seja gerada na𝑐𝑛
aplicação do método, essa expressão não pode ser limitada superiormente por n 2 , ou
seja, O(n2 ) não é uma solução para a recorrência. 
A quarta alternativa é falsa, porque, embora a aplicação do método se inicie com a
substituição cn + 1, o método finaliza com a expressão   2+1 , que não pode ser limitada𝑐𝑛
superiormente por n, ou seja, O(n) não é solução para a recorrência. 
4. O teorema mestre constitui outra poderosa ferramenta para a solução de
recorrências. Aplicando o método à recorrência
, o primeiro passo é avaliar a função nlogba, cujo valor é _________.
Comparando o valor dessa função com f(n), conclui-se que f(n) é _____ nlogba.
Nesse caso, o valor assintótico obtido a partir do teorema mestre é dado por _____.
Marque a opção que preenche todas as lacunas:
Resposta correta.
D. nlog42 / limitada superiormente por / nlog42.
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1.
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por
nlog42. Ao se comparar essa função com f(n), tem-se que f(n) = 1 = nlog42 = n0,5
- £ onde £ = 0,5 > 0.
Nesse   caso,   conclui-se   que   f(n)   é   limitada   superiormente   por   nlog42,   o   que
permite a aplicação do caso 1 do teorema mestre. Portanto, o valor assintótico
obtido a partir do teorema é nlog42.
5. Se a recorrência a ser resolvida satisfaz às condições para a aplicação do
teorema mestre, a solução pode ser obtida de forma direta por meio do uso de um
de seus três casos. Para a recorrência
, indique a alternativa correta a respeito do uso do teorema mestre em sua
resolução.
Resposta correta.
E. O uso do teorema leva à aplicação do seu terceiro caso, o que implica T(n) apresentar
um comportamento assintótico de n3.
Os valores dos termos considerados pelo teorema são: a = 4, b =2 e f(n) = n3 . O
primeiro passo é a avaliação do valor de nlogb a = nlog2 4 = n2 . Como f(n) > n2 e f(n) =
n2+£, onde £ = 1 > 0 (£ > 0 é uma pré-condição do teorema), então o terceiro caso do
teorema pode ser aplicado, desde que a condição   (     ) ≤  ( ) seja verificada. Então,𝑎𝑓 𝑛 𝑏 𝑐𝑓 𝑛
 (     ) = 4  (   2 ) = 4  3 8 = 0,5  3 ≤  ( ) =   3 , tomando c = 0,5 < 0 (c < 0 é outra𝑎𝑓 𝑛 𝑏 𝑓 𝑛 𝑛 𝑛 𝑐𝑓 𝑛 𝑐𝑛
pré-condição do teorema).  Como a desigualdade foi  satisfeita,  a  recorrência  pode ser
resolvida com o terceiro caso do teorema mestre. Portanto, o comportamento assintótico
de T(n) é n 3 . 
	Teorema mestre – Teoria dos Grafos e Análise de Algoritmos
	Exercícios