Análise de algoritmos_A2

Prévia do material em texto

Atividade 2
A comparação precisa, entre algumas funções, envolve um esforço para descobrir elementos intermediários, que podem ressaltar os limites assintóticos procurados. Esse trabalho vai possibilitar o emprego da notação Theta de maneira precisa.
 
Sabe-se que a função log(n!) é limitada superiormente pela função nlog(n). Com base nisso, assinale a alternativa que indica uma afirmação verdadeira sobre a relação assintótica entre essas duas funções.
Resposta certa. É preciso verificar se log(n!) = O(nlog(n)). Então,
log(n!) = log (1 × 2 × … × n)
                        = log 1 + log 2 + … + log n
                        = log 1 + … + log n/2 + … + log n           
                        = log(n/2) + log(n/2 + 1) + … + log n (metade maior da soma)
                        = log(n/2) + log(n/2) + … + log(n/2)
                        = log(n/2 × n/2 × … × n/2) (n/2 vezes)
                        = log(n/2)n/2
                               = (n/2)log(n/2)          (constante c = 1/2)
                        = O(nlog(n))
Portanto, log(n!) = T(nlog(n)).
O limite assintótico superior da soma das duas funções é O(nlog(n!)).
Como log(n!) = O(nlogn), então nlogn ≤ clog(n!) para algum c > 0.
Se log(n!) ≤ log(n/2)n/2, então nlog(n) também limita log(n!) inferiormente.
A soma dos n/2 últimos termos de log(n!) é menor que log(n/2)n/2.
Uma constante c = ½ valida o limite assintótico inferior de log(n!).
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 
1
         
 Fale com Tutor(a)  
 Comentários
Atividade 2
A descrição da complexidade de um algoritmo, por meio da notação Theta, é geralmente obtida a partir da análise feita sobre os passos executados por ele. No entanto, nem sempre o código implementado está acessível, nem os detalhes do algoritmo são conhecidos. Em casos assim, é preciso observar o seu
desempenho, quando submetido a entradas de diferentes tamanhos. Considere a seguinte tabela contendo os dados coletados dos tempos de execução de um algoritmo.
Assinale a alternativa que apresente a melhor aproximação do comportamento assintótico do algoritmo, em termos da notação Theta.
Resposta incorreta. Observe como o tempo de execução do algoritmo varia de acordo com o aumento do tamanho da entrada e procure encontrar a função que melhor se ajusta a esse comportamento. Para facilitar a identificação da função, uma boa estratégia é plotar os valores em um plano cartesiano.
Θ(log(n)).
Sua resposta (incorreta)
Θ(n).
Θ(1).
Θ(n3).
Θ(n2).
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 

2
        
 Fale com Tutor(a)  
 Comentários
Atividade 2
Relações de recorrência possibilitam que um problema seja modelado a partir de si mesmo, considerando instâncias de menor tamanho. A cada iteração de uma recorrência, o problema em análise é reduzido até o limite de um caso base.
 
Considerando essas informações e o conteúdo estudado, analise a sequência de números a seguir S = ( 1, 2, 22, 23, ..., 2n, …) e assinale a alternativa que apresenta a recorrência correta para S.
Resposta correta. Todos os elementos de S são potências de 2. Logo, o termo geral da sequência é 2n e o caso geral da recorrência precisa envolver uma potência desse tipo, ou seja, T(n – 1) x 2. Além disso, é preciso definir o caso base da relação. Como o primeiro elemento de S é 1, o caso base pode ser expresso como T(0) = 1. Portanto,
para n = 4, a sequência de S seria obtida como:
 
T(4) = 2 × T(3)
T(3) = 2 × T(2)
T(2) = 2 × T(1)
T(1) = 2 × T(0)
T(0) = 1
Logo, S = ( T(0), 2 × T(1), 2 × T(2), 2 × T(3), 2 × T(4) )
              = (1, 2, 4, 8, 16) = (1, 21, 22, 23, 24) para n = 4.
T(n) = T(n – 1) + n, se n ≥ 1 e T(n) = 2, se n = 1.
T(n) = T(n/2) + n, se n ≥ 1 e T(n) = 1, se n = 0.
T(n) = 2n × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 1.
T(n) = T(n – 1) + 2, se n ≥ 1 e T(n) = 1, se n = 0.
T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0.
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 
 
3
       
 Fale com Tutor(a)  
 Comentários
Atividade 2
Árvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites são expressos por meio da notação Theta e oferecem um poderoso recurso para a análise do desempenho de algoritmos.
 
Considere a recursão T(n) = T(n - a) + T(a) + cn, onde a ≥ 1 e c > 0 são constantes, e assinale a alternativa que indica uma afirmação correta a respeito de sua análise.
Resposta correta. Como a cada nível da árvore o tamanho dos subproblemas é reduzido de a, serão gerados (n/a) + 1 níveis até o fim da recorrência. Como a recorrência tem um termo independente T(1), ela é classificada como heterogênea. Se T(n) = cn2, teremos
T(n)    = c(n – a)2 + ca + cn
                        = cn2 – 2can + ca + cn
                        = cn2 – c(2an - a – n)                      (para a < ½ e n > 2a)
                        = cn2 – cn
                        = cn2
                        = O(n2).
Se, T(n) = cn2, temos
T(n)    = c(n – a)2 + ca + cn
                        = cn2 – 2can + ca + cn
                        = cn2 – c(2an - a – n)          (para a < 1 e n > 2a)
                        = cn2 + cn
                        = cn2
                        = O(n2).
Tomando T(n) ≥ cn2, T(n) = Ω(n2), se a for igual a 1.
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
Resposta correta
O custo de todos os nós (subproblemas) a cada nível é T(a).
A recorrência pode ser classificada como homogênea.
Se T(n) ≤ cn2 então T(n) = O(n2) para qualquer valor de a e n
 PRÓXIMA QUESTÃO 
Próximo 
  
4
      
 Fale com Tutor(a)  
 Comentários
Atividade 2
A definição do limite assintótico auxilia no entendimento sobre como as funções delimitam umas às outras, superior e/ou inferiormente. No entanto, há relações em que a identificação das constantes que cauterizam esses limites demanda manipulações algébricas mais elaboradas. Supondo r e s inteiros não-negativos, com
r < s,e tomando c ≠ 0, o seguinte resultado é comprovadamente verdadeiro: .
 
A partir dessas informações, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) A partir da desigualdade ns ≤ ns + cnr, é possível atestar que ns = O(ns + cnr) para c > 0.
II. ( ) A validade da relação é condição para que o limite ns = O(ns + ns + cnr) seja verificado.
III. ( ) O limite assintótico ns + cnr = O(ns) é verificado tanto para r < s como para s < r.
IV. ( ) Se c < 0, então ns + cnr = O(ns) para qualquer que seja o valor assumido por n.
 
Agora, assinale a alternativa que apresenta a sequência correta:
~ Resposta correta. Primeiro, vamos considerar o caso c > 0. Para n = 0, temos ns = ns + cnr e, portanto, ns = O(ns + cnr). Por outro lado, como r < s, para qualquer n = 0, temos que ns + cnr e = ns + cns = (1 + c)ns, portanto ns + cnr = O(ns). Agora, é preciso considerar o caso c < 0. Então, para n = 0, temos que cnr e = 0 e, portanto, ns + cnr = ns,
implicando em ns + cnr = O(ns). Por outro lado, sabendo que , temos ns – r = -2c > 0, implicando em ns – r + 2c = 0. Logo, ns < ns + nr(ns – r + 2c) = 2(ns + cnr), e, portanto, ns = O(ns + cnr).
F, F, V, V.
V, V, F, V.
F, V, F, V.
V, V, F, F.
Resposta correta
V, F, V, F.
 PRÓXIMA QUESTÃO 
Próximo 
   
5
     
 Fale com Tutor(a)  
 Comentários
Atividade 2

A eficácia do método de substituição tem dependência intrínseca da proposição de uma boa solução (bom “palpite”), para a recorrência, e a verificação da solução é feita por indução matemática. Neste caso, o caso base com o passo indutivo deve ser avaliado.
 
Considerando a recorrência T(n) = T(n - 1) + T(n/2) + n, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) O limite assintótico superior de T(n) é O(2n).
II. ( ) Se T(n) ≤ c2n - 4n, então T(n) ≤ c(2n - 1 + 2n/2) - 4n, para n ≥ 0 e c > 0.
III. ( ) O limite assintótico inferior de T(n) é Ω(n2)
IV.( ) Se T(n) ≥ cn2 e c ≤ ½, então T(n) ≤ cn2 + (1 - 2c)n + c.
 
Agora, assinale a alternativa que apresenta a sequência correta:
~ Resposta correta. Supondo que T(n) = c2n – 4n para c > 0, temos pelo método da substituição:
T(n)    = c2n-1 – 4(n – 1) + c2n/2 - 4n/2 + n
                        = c(2n – 1 + 2n/2) – 5n + 4     (para n = 1/4)
                        = c(2n – 1 + 2n/2) – 4n            (para n = 2)
                        = c(2n – 1 + 2n - 1) – 4n
                        = c2n – 4n                 
                        = O(2n)
Agora, supondo T(n) = cn2 pelo método da substituição, temos:
T(n)                = c(n – 1)2 + c(n/2)2 + n
                        = cn2 – 2cn + c + cn2/4 + n
                        = (5/4)cn2 + (1 – 2c)n + c
                        = cn2 + (1 – 2c)n + c           (para c = ½)
                        = cn2
                               = O(n2)
V, V, F, F.
F, F, V, V.
F, V, F, V.
V, V, F, V.
V, F, V, F.
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 
     6     
 Fale com Tutor(a)  
 Comentários
Atividade 2
Soluções fechadas para recursões podem ser validadas pelo método da substituição. Esse método depende da identificação de constantes positivas, que possam ser usadas para delimitar a função cujo comportamento está sendo analisado.
 
Nesse cenário, analise as asserções a seguir e a relação proposta entre elas.
 
I. A recorrência T(n) = 2T(n/2) + n é limitada superiormente por O(nlog(n)).
Porque:
II. É possível definir uma constante positiva c, que torna verdadeira a desigualdade 2c(n/2)log(n/2) + n ≤ cnlog(n/2) + n.
 
A seguir, assinale a alternativa correta:
Resposta correta. A verificação pode ser feita como segue:
T(n)                = cnlog(n)
                        = 2cn(n/2)(log(n/2)) + n     
                        = cnlog(n/2) + n      
                        = cnlog(n) - cnlog(2) + n   
                        = cnlog(n) + (1 - c)n
                        = cnlog(n)
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Resposta correta
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 PRÓXIMA QUESTÃO 
Próximo 
     
7
   
 Fale com Tutor(a)  
 Comentários
Atividade 2
Umas das aplicações da notação Theta (Θ) é estabelecer uma métrica para comparação de funções. Com isso, um dado conjunto de funções pode ser ordenado de maneira a identificar aquelas que têm maior e menor crescimento assintótico.
 
Considerando o seguinte conjuntos de funções:
 Assinale a alternativa que apresenta a ordenação correta de forma crescente das funções, em termos da notação Theta.
Resposta correta. Como n é linear no seu crescimento, a função 1/n decresce rapidamente, o que a torna a função com menor limite assintótico, seguida da função constante 17. Na sequência, como log(n20) = 20log(n) é T(log(n)), temos que ela cresce a uma taxa inferior que seu quadrado, log2(n). Logo, log(n20) e log2(n) são as próximas.
Para a definição das duas últimas funções, é preciso perceber que  cresce a uma taxa superior que log(n). Então, temos que Portanto, as duas últimas funções são  nesta ordem.
{17,1/n,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
{17,1/n,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}.
{1/n,17,〖log〗^2 (n),log(n^20 ),n^2 √n,n^3/log(n) }.
{1/n,17,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}.
{1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 
      
8
  
 Fale com Tutor(a)  
 Comentários
Atividade 2
Um dos métodos amplamente utilizados para a solução de recorrências é conhecido como o método da substituição. Sua aplicação é baseada na proposição de uma solução fechada para a recorrência, seguida de uma validação dessa solução.
 
Considerando o uso desse método para verificar se O(n2) é solução para a recorrência T(n) = T(n - 1) + n, analise as afirmativas 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 avaliação de uma diferença, elevada à potência de 2, entre dois termos.
III. A aplicação do método se inicia com a construção da desigualdade T(n) ≤ c(n2 - n), 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.
Está correto apenas o que se afirma em:
Resposta correta. A aplicação do método implica nos seguintes passos:
T(n)     = T(n – 1) + n          
            = c(n – 1)2 + n
            = cn2 – 2cn + c + n
            = cn2 – n(2c – 1) + c
            = O(n2)
Logo, O(n2) é solução para a recorrência.
I e III.
III e IV.
I e II.
II e III.
II e IV.
Resposta correta
 PRÓXIMA QUESTÃO 
Próximo 
       
9
 
 Fale com Tutor(a)  
 Comentários
Atividade 2
Funções de recorrência podem ser exploradas com várias manipulações algébricas de forma a encontrar uma solução fechada. Isso é particularmente importante para a descrição do comportamento assintótico de algoritmos. No entanto, é fundamental saber reconhecer semelhanças e diferenças entre elas.
 
Considerando a relação de recorrência a seguir, indique a alternativa correta a respeito dela:
T(1) = 1
T(n) = T(n - 1) + 3
Resposta correta. O caso base é constante O(1) e a relação é hetero     gê     nia, podendo apresentar termo independente. Se um termo n3 for acrescido à relação, esse passará a ser seu novo comportamento assintótico, o qual é O(n). Como a cada iteração o termo recursivo      é decrementado de 1, na k-ésima iteração, a relação será
expressa por T(n – k) + 3k.
A relação pode ser classificada como homogênea.
A relação tem limite assintótico superior O(n2).
O caso base da relação tem complexidade linear.
O k-ésimo termo da relação é da forma T(n – k) + 3k.
Resposta correta
O termo independente da relação pode ser substituído por n3, sem interferência no seu comportamento assintótico.
Próximo 
        
10 
 Fale com Tutor(a)  
 Comentários