ANÁLISE DE ALGORITMOS

Prévia do material em texto

ANÁLISE DE ALGORITMOS - ATIVIDADE 2
 
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: II e IV.
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.
-----------------------------------------------------------------------------------------------------
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: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
-----------------------------------------------------------------------------------------------------
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: I, II e III.
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) = O(nlog(n)).
-----------------------------------------------------------------------------------------------------
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: F, F, V, V.
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 ).
--------------------------------------------------------------------------------------------------------------------------------
Á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: 
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
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
 = O(n2).
--------------------------------------------------------------------------------------------------------------------------------
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: I, II e III.
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 umcom 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ção T(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)).
--------------------------------------------------------------------------------------------------------------------------------
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, 22, 23, ..., 2n, …) e assinale a alternativa que apresenta a recorrência correta para S.
Resposta: T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0
--------------------------------------------------------------------------------------------------------------------------------
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: 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:
Capturar_20211112113900.JPG
 Assinale a alternativa que apresenta a ordenação correta de forma crescente das funções, em termos da notação Theta.
Resposta: {1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }.
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) é T(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.
--------------------------------------------------------------------------------------------------------------------------------
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: V, F, V, F
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
 = O(n2)