A2 - Análise de Algoritmos - Respondido

Prévia do material em texto

1. 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:
	
	
	III e IV.
	
	
	II e III.
	
	
	I e II.
	
	
	I, II e III.
	
	
	II e IV.
1 pontos   
PERGUNTA 2
1. 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.
	
	
	Θ(1).
	
	
	Θ(n).
	
	
	Θ(n2).
	
	
	Θ(n3).
	
	
	Θ(log(n)).
1 pontos   
PERGUNTA 3
1. 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.
	
	
	O limite assintótico superior da soma das duas funções é O(nlog(n!)).
	
	
	Se log(n!) ≤ log(n/2)n/2, então nlog(n) também limita log(n!) inferiormente.
	
	
	Como log(n!) = O(nlogn), então nlogn ≤ clog(n!) para algum c > 0.
	
	
	Uma constante c = ½ valida o limite assintótico inferior de log(n!).
	
	
	A soma dos n/2 últimos termos de log(n!) é menor que log(n/2)n/2.
1 pontos   
PERGUNTA 4
1. 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^3/log(n) ,n^2 √n}.
	
	
	{1/n,17,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/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^2 √n,n^3/log(n) }.
1 pontos   
PERGUNTA 5
1. 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:
	
	
	I, II e III.
	
	
	I e II.
	
	
	II e III.
	
	
	II e IV.
	
	
	III e IV.
1 pontos   
PERGUNTA 6
1. 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.
	
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	
	
	A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
	
	
	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 verdadeiras, mas a II não é uma justificativa correta da I.
	
	
	As asserções I e II são proposições falsas.
1 pontos   
PERGUNTA 7
1. 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, mas a II não é uma justificativa correta da I.
	
	
	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.
	
	
	A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
1 pontos   
PERGUNTA 8
1. É 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.
	
	
	As asserções I e II são proposições falsas.
	
	
	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 verdadeiras, mas a II não é uma justificativa correta da I.
	
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	
	
	A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
1 pontos   
PERGUNTA 9
1. 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 paraa(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:
	
	
	V, F, V, F.
	
	
	F, F, V, V.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
	
	
	V, V, F, F.
1 pontos   
PERGUNTA 10
1. 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, F, V, V.
	
	
	V, F, V, F.
	
	
	V, V, F, V.
	
	
	F, V, F, V.