análise de algoritmos - atividade 02

Prévia do material em texto

O desempenho no pior caso de um algoritmo pode ser descrito por meio do uso da notação de 
complexidade assintótica. Esse é o caso de algoritmos que solucionam problemas de tamanho n, que
tem seu tamanho reduzido a cada iteração.
 
Analise o algoritmo a seguir:
Algoritmo A
Entrada: Inteiro de valor positivo
Saída: Valor 1 se o valor informado for 1
1. se n = 1 então
2. retornar 1
3. senão
4. retornar 2 × A(n/2) + 1
 
Considerando essas informações e o algoritmo apresentado, analise as afirmativas a seguir e 
assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) A solução fechada da recorrência para o algoritmo pode ser descrita pela função T(n) = (n – 1) 
+ c, em que c é uma constante positiva.
II. ( ) O algoritmo gera subproblemas, cujos tamanhos são ¼ do tamanho do subproblema da 
iteração anterior.
III. ( ) O algoritmo tem como chamada recursiva um comando que gera subproblemas de tamanho 
n/2.
IV. ( ) O limite superior da recorrência que descreve o algoritmo pode ser expressa por T(n) = 
O(log(n)).
 
Agora, assinale a alternativa que apresenta a sequência correta:
V, V, F, F.
V, V, F, V.
V, F, V, F.
F, F, V, V.
F, V, F, V.
1 pontos 
PERGUNTA 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.
{17,1/n,log(n^20 ),〖log〗^2 (n),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〗^2 (n),log(n^20 ),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(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
1 pontos 
PERGUNTA 3
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:
I e II.
II e IV.
III e IV.
II e III.
I e III.
1 pontos 
PERGUNTA 4
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
O termo independente da relação pode ser substituído por n3, sem interferência no seu 
comportamento assintótico.
A relação pode ser classificada como homogênea.
O k-ésimo termo da relação é da forma T(n – k) + 3k.
A relação tem limite assintótico superior O(n2).
O caso base da relação tem complexidade linear.
1 pontos 
PERGUNTA 5
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.
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 verdadeira, e a II é uma proposição falsa.
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.
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.
1 pontos 
PERGUNTA 6
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:
V, V, F, F.
F, V, F, V.
F, F, V, V.
V, F, V, F.
V, V, F, V.
1 pontos 
PERGUNTA 7
Á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.
O custo de todos os nós (subproblemas) a cada nível é T(a).
Tomando T(n) ≥ cn2, T(n) = Ω(n2), se a for igual a 1.
Se T(n) ≤ cn2, então T(n) = O(n2) para qualquer valor de a e n.
A recorrência pode ser classificada como homogênea.
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
1 pontos 
PERGUNTA 8
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:
F, F, V, V.
F, V, F, V.
V, F, V, F.
V, V, F, F.
V, V, F, V.
1 pontos 
PERGUNTA 9
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).
Θ(log(n)).
Θ(n3).
Θ(n2).
Θ(1).
PERGUNTA 10
Relações de recorrência possibilitam que um problemaseja 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.
 PERGUNTA 10
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.
T(n) = 2n × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 1.
T(n) = T(n/2) + n, se n ≥ 1 e T(n) = 1, se n = 0.
T(n) = T(n – 1) + n, se n ≥ 1 e T(n) = 2, se n = 1.
T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0.
T(n) = T(n – 1) + 2, se n ≥ 1 e T(n) = 1, se n = 0.
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 Selecionada: 
II e IV.
Resposta Correta: 
II e IV.
Comentário da 
resposta: 
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.
1.
Á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 Selecionada: 
A árvore de recursão apresentará altura de valor igual (n/a) +
1.
Resposta Correta: 
A árvore de recursão apresentará altura de valor igual (n/a) +
1.
Comentário da
resposta: 
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).
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 Selecionada: 
{1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
Resposta Correta: 
{1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
Comentário 
da resposta: 
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) é Θ(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.
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 Selecionada: 
V, V, F, F.
Resposta Correta: 
V, V, F, F.
Comentário 
da resposta: 
~ 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).
É 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 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.
Resposta 
Selecionada: 
 
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, e a II é uma
justificativa correta da I.
Comentário da 
resposta: 
Resposta correta. Como os dois subalgoritmos são executados
sequencialmente, o tempo de execução total de ALG será dado por
Θ(f(n) + n/f(n)) = Θ(max{ f(n), n/f(n) }).
Para que esse valor seja minimizado, é preciso definir f(n), de tal
maneira que ambas as partes sejam iguais, ou seja:
f(n)=n/f(n) →(f(n))^2=n→f(n)=√n
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 
Selecionada: 
 
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, e a II é uma
justificativa correta da I.
Comentário da resposta: 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)
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 Selecionada: 
O k-ésimo termo da relação é da forma T(n – k) +
3k.
Resposta Correta: 
O k-ésimo termo da relação é da forma T(n – k) +
3k.
Comentário 
da resposta: 
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 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 Selecionada: 
V, F, V, F.
Resposta Correta: 
V, F, V, F.
Comentário da 
resposta: 
~ 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
                               = Ω(n2)
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 Selecionada: 
Θ(n2).
Resposta Correta: 
Θ(n2).
Comentário da 
resposta: 
Resposta correta. Cada vez que a entrada tem o seu tamanho dobrado de
tamanho, o tempo de execução do algoritmo aumenta a um fator de,
aproximadamente, 4. Então, dentre as opções disponíveis, a ordem assintótica
mais próxima para o algoritmo é Θ(n2). 
O limite assintótico de algoritmos recursivos pode ser estimado com boa precisão,
através da modelagem via árvores de recursão. Para isso, os termos recursivos
desempenham papel chave para o entendimento de como o algoritmo se comporta a
cada iteração. 
 
Considerando que um algoritmo é modelado pela recursão T(n) = T(n/3) + T(2n/3) + cn,
onde c é uma constante, analise as afirmativas a seguir.
 
I. A árvore de recursão mostra que o custo de cada nível é cn.
II. O limite assintótico inferior do algoritmo é Ω(nlog(n)).
III. O caminho mais curto entre a raiz e um nó folha é log3(n).
IV. O tamanho dos subproblemas decresce a um fator de 2/3.
 
Está correto apenas o que se afirma em:
Resposta Selecionada: 
I, II e 
III.
Resposta Correta: 
I, II e 
III.
Comentário 
da resposta: 
Resposta correta. Como os termos recursivos são divididos por 3, cada
subproblema tem seu tamanho decrementado a um fator de 3. Porém,
cada nível tem um acréscimo de cn termos, o que corresponde ao custo
de cada nível. Para a definição do limite inferior do custo do algoritmo
temos, cn(log3(n)) + 1 ≥ cnlog3(n) = (c/log(3))nlog(n) = Ω(nlog(n)).