Atividade 02 (1)

Prévia do material em texto

Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
Θ(n).
Θ(n2).
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.
Pergunta 2
O cálculo de complexidade é parte essencial do projeto e da análise de
algoritmos. Uma ferramenta chave usada nesta atividade é a notação Theta (Θ).
Ela oferece uma maneira objetiva de descrever o comportamento assintótico de
algoritmos e possibilita a comparação da eficiência entre eles.
 
Considerando as funções T1(n) = log2n + n e T2(n) = n, analise as asserções a
seguir e a relação proposta entre elas.
 
I. Um algoritmo A2 com uma complexidade T2 tem uma eficiência computacional
melhor que um algoritmo A1 com complexidade T1.
0 em 1 pontos
1 em 1 pontos
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
Porque:
II. A função T1 tem limite assintótico dado por T1(n) = Θ(T2(n)).
 
A seguir, assinale a alternativa correta.
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
Resposta correta. É preciso observar que n = O(log2n + n).
Adicionalmente, temos que verificar se log2n + n = O(n), ou seja,
log2n + n ≤ cn, c > 0. Como log2n ≤ n (pois n ≤ 2n), temos que log2n +
n ≤ 2n, tomando c = 2 e n ≥ 1. Portanto, T1(n) = Θ(T2(n)).
Pergunta 3
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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:
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 verdadeiras, e a II é uma
justificativa correta da I.
Resposta incorreta. Basta aplicar a definição de limite assintótico
para a recorrência e identificar se as afirmações e relação entre
elas são verdadeiras.
0 em 1 pontos
Pergunta 4
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
Saber analisar uma recorrência a partir da descrição de um dado problema, é
importante para a correta avaliação da complexidade do algoritmo que será
projetado. E o entendimento de como cada subproblema é expandido deve ser
parte integrante dessa análise. Considere um algoritmo recursivo que, dada uma
entrada de tamanho n, divide a entrada em 2 (dois) subproblemas de
tamanho n/2, resolve cada um recursivamente e, por fim, combina as duas
partes em um tempoO(n).
 
Em relação ao comportamento recursivo e ao limite assintótico desse algoritmo,
analise as afirmativas a seguir (o tempo de execução do algoritmo para uma
entrada de tamanho n será denotado por T(n)).
 
I. A árvore de recursão gerada pelo algoritmo terá tamanho log2(n).
II. Cada nível k da árvore de recursão é composto por 2k subproblemas.
III. O algoritmo tem complexidade da ordem de O(nlog2)
IV. A recursão pode ser descrita pela função T(n) = T(2n) + n.
 
Está correto apenas o que se afirma em:
I, II e III.
I, II e III.
Resposta correta. Seja k = {1, 2, …, K} denotar os níveis da árvore
de recursão. Neste caso, k = 1 corresponde ao problema original
de tamanho n, k = 2 é o primeiro nível da recursão com dois
subproblemas de tamanho n/2 e, seguindo a expansão, no nível K,
teremos 2k subproblemas, cada um com tamanho n/2k e, no nível
K, os subproblemas terão tamanho 1. Isso quer dizer que a altura
da árvore será dada por log2(n). A recursão pode ser descrita pela
função T(n) = 2T(n/2) + O(n). Logo, os subproblemas serão de tamanho
1. Após K ≤ log2(n), níveis recursivos e o tempo para resolver cada
subproblema de tamanho 1 será de O(1). Além disso, para um
subproblema de tamanho n, há o tempo extra de combinação O(n).
Então, no nível de recursão k, haverá o custo extra de 2k × O(n/2k)
= O(n). Portanto, a complexidade do algoritmo será de T(n) =
O(nlog(n)).
Pergunta 5
Á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.
1 em 1 pontos
1 em 1 pontos
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
A árvore de recursão apresentará altura de valor igual (n/a)
+ 1.
A árvore de recursão apresentará altura de valor igual (n/a)
+ 1.
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
 = Ω(n2).
Pergunta 6
Resposta Selecionada: 
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.
{1/n,17,〖log〗^2 (n),log(n^20 ),n^2 √n,n^3/log(n) }.
0 em 1 pontos
Resposta Correta: 
Comentário
da resposta:
{1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
Resposta incorreta. Inicialmente, faça uma comparação, duas a
duas, das funções cujo fator de crescimento é mais próximo. Daí,
aplique operações algébricas para identificar qual função limita
superiormente a outra.
Pergunta 7
Resposta Selecionada: 
Resposta Correta: 
Comentário da
resposta:
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çãodo 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:
II e IV.
II e IV.
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.
Pergunta 8
É comum que algoritmos sejam fracionados em múltiplos procedimentos que,
quando executados de maneira conjunta, têm seus resultados parciais
combinados para gerar a solução final. Essa divisão tem impacto direto no
cálculo da complexidade do algoritmo. Um algoritmo ALG é composto de dois
1 em 1 pontos
0 em 1 pontos
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
subalgoritmos ALGA e ALGB, que devem ser executados sequencialmente –
ALGA seguido de ALGB. No entanto, dada uma função f(n), ambos
subalgoritmos podem ser otimizados de forma que ALGA rode a uma taxa de
Θ(f(n)) e ALGB à taxa de Θ(n/f(n)).
 
Considerando esse cenário, analise as asserções a seguir e a relação proposta
entre elas.
 
I. O tempo de execução geral de ALG pode ser minimizado através da escolha
de uma função .
Porque:
II. Como ambos subalgoritmos ALGA e ALGB, são executados sequencialmente,
a função vai apresentar a menor taxa de crescimento no algoritmo completo.
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 verdadeiras, e a II é uma
justificativa correta da I.
Resposta incorreta. Analise como as propriedades da notação
Theta podem ser aplicadas de forma a guiar as escolhas de uma
função f.Avalie se o tempo de execução do algoritmo pode ser, de
fato, minimizado através de alguma f particular.
Pergunta 9
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
porn.
 
Agora, assinale a alternativa que apresenta a sequência correta:
1 em 1 pontos
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
V, V, F, F.
V, V, F, F.
~ 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).
Pergunta 10
Resposta
Selecionada:
Resposta Correta:
Comentário da
resposta:
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.
Uma constante c = ½ valida o limite assintótico inferior de
log(n!).
Uma constante c = ½ valida o limite assintótico inferior de
log(n!).
Resposta certa. É preciso verificar se log(n!) = Ω(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)
 = Ω(nlog(n))
Portanto, log(n!) = Θ(nlog(n)).
1 em 1 pontos
Sábado, 22 de Maio de 2021 16h50min14s BRT