Prova N2 - Análise de Algoritmos pdf

Prévia do material em texto

Prova N2 - ANÁLISE DE ALGORITMOS
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 log 2(n).
II. Cada nível k da árvore de recursão é composto por 2 k subproblemas.
III. O algoritmo tem complexidade da ordem de O(nlog 2)
IV. A recursão pode ser descrita pela função T(n) = T(2 n) + n.
 
Está correto apenas o que se afirma em:
2. 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.
3. A análise de complexidade do método de ordenação por inserção direta leva a duas funções distintas, dependendo do caso analisado. No pior caso, o domínio assintótico é dado pela função f(n) = (n 2 - n)/2; enquanto que, no melhor caso, a função é g(n) = n - 1.
 
Com base nessas funções e levando em conta as definições relacionadas à notação Ômega, responda: por que é possível afirmar que f(n) = Ω(g(n))?
4. 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 é log 3(n).
IV. O tamanho dos subproblemas decresce a um fator de 2/3.
 
Está correto apenas o que se afirma em:
5. 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:
6. Diversas estratégias são conhecidas para a ordenação de dados na memória principal. Uma delas é implementada pelo algoritmo Merge Sort que usa uma abordagem de divisão e conquista. Seu comportamento assintótico pode ser descrito tendo como base o número de comparações realizadas durante o processo de ordenação.
 
Nesse contexto, analise as asserções a seguir e a relação proposta entre elas.
 
I. O número de comparações realizadas pelo algoritmo Merge Sort pode ser delimitado tanto superior como inferiormente.
Porque:
II. Para um vetor de N posições, o seu processo de ordenação usa entre (1/2) NlogN e NlogN comparações.
7. O teorema mestre apresenta importantes resultados, que podem ser aplicados para a descrição do comportamento assintótico de algoritmos modelados por recorrências. Porém, a sua correta utilização depende da identificação de qual dos três casos podem ser empregados e da satisfação das condições exigidas por ele.
 
Considerando essas informações e conteúdo estudado, analise as asserções a seguir e a relação proposta entre elas.
 
I. Um algoritmo modelado com a recorrência T(n) = 2T(n/2) + 10n pode ter seu limite assintótico definido através da aplicação do teorema mestre.
Porque:
II. Como as condições do segundo caso do teorema são satisfeitas, a complexidade do algoritmo é dada por Θ(n).
 
A seguir, assinale a alternativa correta.
8. O algoritmo de ordenação por inserção direta é baseado no aninhamento de dois laços, que vão, a cada iteração, conduzindo a chave de maior valor para a sua posição correta. Considere o seguinte vetor, que precisa ser ordenado via inserção direta:
 
15        5          4          18        12        19        14        10        8          20
 
Indique a alternativa que apresenta o vetor parcialmente ordenado após os quatro primeiros passos dos algoritmos terem sido executados.  
9. 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:
10. 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.