A2 analise de algoritmos

Prévia do material em texto

Curso GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-
14790.01 
Teste ATIVIDADE 2 (A2) 
Status Completada 
Resultado da 
tentativa 
10 em 10 pontos 
 Pergunta 1 
1 em 1 pontos 
 
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: 
 
Resposta Selecionada: 
F, F, V, V. 
Resposta Correta: 
F, F, V, V. 
Comentário 
da resposta: 
Resposta correta. Este algoritmo tem como recursão uma chamada 
a “A(n/2)”, ou seja, a solução de um problema de tamanho igual a 
n é reduzida à solução de um problema de tamanho igual a n/2 mais 
algum tempo constante - k1, para multiplicar o resultado por 2 e 
somar 1. A solução do problema para o caso base é resolvido em 
um tempo constante - k2. Assim, a relação de recorrência que 
descreve o comportamento do algoritmo pode ser descrita pela 
seguinte função: T(n) = 2T(n/2) + k1 (em que k1 é constante) e T(1) 
= k2 (em que k2 é constante). Supondo que T(n) = O ( log n ), pelo 
método da substituição temos 
T(n) ≤ 2log(n/2) + k1 
 = 2(log(n) - log 2) + k1 
 = 2 log(n) - 2 + k1 (k1 < 2) 
≤ 2log(n) 
= O( log n ) 
Logo, a solução da relação de recorrência é T(n) = O ( log n ). 
 
 
 
 Pergunta 2 
1 em 1 pontos 
 
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: 
o T(1) = 1 
o 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. 
 
 
 
 Pergunta 3 
1 em 1 pontos 
 
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)). 
 
 
 
 Pergunta 4 
1 em 1 pontos 
 
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, 2
2
, 2
3
, ..., 2
n
, …) e assinale a alternativa que apresenta 
a recorrência correta para S. 
 
 
Resposta Selecionada: 
T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0. 
Resposta Correta: 
T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0. 
Comentário 
da resposta: 
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. 
 
 
 Pergunta 5 
1 em 1 pontos 
 
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). 
 
 
 
 Pergunta 6 
1 em 1 pontos 
 
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ãonesta ordem. 
 
 
 
 Pergunta 7 
1 em 1 pontos 
 
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. 
 
 
 
 Pergunta 8 
1 em 1 pontos 
 
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) 
 
 
 
 Pergunta 9 
1 em 1 pontos 
 
É 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 
 
 
 Pergunta 10 
1 em 1 pontos 
 
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)