EXERCICIO 2 - CORRIGIDO

Text Material Preview

• Pergunta 1 
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: 
• 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. 
 
 
• Pergunta 2 
1 em 1 pontos 
 
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 Selecionada: 
Uma constante c = ½ valida o limite assintótico inferior de log(n!). 
Resposta Correta: 
Uma constante c = ½ valida o limite assintótico inferior de log(n!). 
Comentário da 
resposta: 
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)). 
 
• 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 
 
É 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 5 
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 6 
1 em 1 pontos 
 
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 tempo O(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: 
 
Resposta Selecionada: 
I, II e III. 
Resposta Correta: 
I, II e III. 
Comentário 
da resposta: 
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çãoT(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 7 
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ão nesta 
ordem. 
 
 
• Pergunta 8 
1 em 1 pontos 
 
Á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). 
 
 
• Pergunta 9 
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 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)