ANALISE DE ALGORITMOS - ATIVIDADE 1 Unidades de Estudo 1 e 2

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Atividade 1: Unidades de Estudo 1 e 2
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 e II.
· Resposta correta
I, II e III.
· II e IV.
· II e III.
· III e IV.
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:
· 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 verdadeira, e a II é uma proposição falsa.
· Resposta correta
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
· 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.
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).
· Resposta correta
Θ(n2).
· Θ(log(n)).
· Θ(n3).
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, mas a II não é uma justificativa correta da I.
· 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, e a II é uma justificativa correta da I.
· As asserções I e II são proposições falsas.
· Resposta correta
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
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) }.
· Resposta correta
{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) }.
· {1/n,17,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}.
· {17,1/n,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}.
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, V, F, V.
· F, F, V, V.
· V, F, V, F.
· Resposta correta
V, V, F, F.
· V, V, F, V.
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
· A relação pode ser classificada como homogênea.
· Resposta correta
O k-ésimo termo da relação é da forma T(n – k) + 3k.
· O caso base da relação tem complexidade linear.
· A relação tem limite assintótico superior O(n2).
· O termo independente da relação pode ser substituído por n3, sem interferência no seu comportamento assintótico.
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.
· I e III.
· Resposta correta
II e IV.
· II e III.
· III e IV.
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:
· F, V, F, V.
· Resposta correta
F, F, V, V.
· V, F, V, F.
· V, V, F, F.
· V, V, F, V.
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:
· F, V, F, V.
· F, F, V, V.
· Resposta correta
V, F, V, F.
· V, V, F, F.
· V, V, F, V.
image1.png
image2.jpeg