Atividade 2- Analise de Algoritmos

Prévia do material em texto

· Pergunta 1 
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 2 
1 em 1 pontos
	
	
	
	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.
	
	
	
	
		Resposta Selecionada: 
	
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
	Resposta Correta: 
	
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
	Comentário da resposta: 
	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 
0 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: 
	
A relação tem limite assintótico superior O(n2).
	Resposta Correta: 
	
O k-ésimo termo da relação é da forma T(n – k) + 3k.
	Comentário da resposta: 
	Resposta incorreta. Aplique a definição de recursão e analise o significado de cada termo que compõe esse tipo de função.
 
	
	
	
· Pergunta 4 
0 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: 
	
III e IV.
	Resposta Correta: 
	
II e IV.
	Comentário da resposta: 
	Resposta incorreta. Observe os passos para a validação da solução proposta através do método da substituição.
	
	
	
· Pergunta 5 
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 6 
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)
	
	
	
· Pergunta 7 
0 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 falsas.
	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 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 8 
0 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〗^2 (n),log(n^20 ),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 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 9 
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 10 
0 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: 
	
O limite assintótico superior da soma das duas funções é O(nlog(n!)).
	Resposta Correta: 
	
Uma constante c = ½ valida o limite assintótico inferior de log(n!).
	Comentário da resposta: 
	Resposta incorreta. Aplique a definição da notação de theta para a relação entre as funções, porém observe que metade da definição já é válida. Além disso, cada passo obtido com a definição pode trazer esclarecimentos sobre as afirmações.
	
	
	
Sábado, 12 de Junho de 2021 04h02min01s BRT