ANÁLISE DE ALGORITMOS - N2

Prévia do material em texto

1. 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. 
 
• As asserções I e II são proposições falsas. 
• 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. 
• 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. 
 
2. 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 tem limite assintótico superior O(n 2). 
✓ O k-ésimo termo da relação é da forma T(n – k) + 3k. 
• O caso base da relação tem complexidade linear. 
• O termo independente da relação pode ser substituído por n 3, sem interferência no seu 
comportamento assintótico. 
• A relação pode ser classificada como homogênea. 
 
3. 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. 
 
• As asserções I e II são proposições falsas. 
✓ 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. 
• 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. 
 
4. A análise do comportamento assintótico de funções é uma técnica comumente utilizada para 
a avaliação do desempenho de algoritmos. Uma maneira de expressar as relações 
identificadas neste tipo de análise é por meio da notação O. O uso dessa notação estabelece 
uma métrica objetiva para comparação entre algoritmos. 
 
Considerando essas informações e o conteúdo estudado, analise as afirmativas de acordo 
com essa técnica utilizada para indicar um limite superior para funções. 
 
I. 2 n+1 = O(2 n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)). 
III. n 2/10 = O(n) 
IV. 6n 3 = O(n 2) 
 
Está correto apenas o que se afirma em: 
 
• II e III. 
• I e III. 
• II e IV. 
• III e IV. 
✓ I e II. 
 
5. 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. 
 
• 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!). 
• Se log(n!) ≤ log(n/2) n/2, então nlog(n) também limita log(n!) inferiormente. 
• A soma dos n/2 últimos termos de log(n!) é menor que log(n/2) n/2, 
• O limite assintótico superior da soma das duas funções é O(nlog(n!)). 
 
6. 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. 
 
• Θ(log(n)). 
• Θ(n). 
✓ Θ(n 2). 
• Θ(n 3). 
• Θ(1). 
 
7. Uma das operações computacionais utilizadas para medir a complexidade dos algoritmos de 
ordenação é o número de comparações realizadas com a chave que está sendo 
reposicionada. No entanto, esta não é a única operação que pode ser empregada. O número 
de movimentações efetuadas entre as chaves em ordenação também constitui outra 
operação relevante a ser analisada. 
 
Considerando o número de movimentações entre chaves, efetuadas pelo método de 
ordenação por inserção direta, analise as asserções a seguir e a relação proposta entre elas. 
 
I. O comportamento assintótico do algoritmo é invariante em relação ao tipo de operação 
elementar considerada - seja o número de comparações com a chave em reposicionamento 
ou o número de movimentações entre chaves. 
Porque: 
II. A contagem do número de operações básicas, realizadas no pior caso do algoritmo, resulta 
em um mesmo valor, assim como acontece em seu melhor caso, independentemente do tipo 
de operação considerada. 
 
A seguir, assinale a alternativa correta. 
 
• As asserções I e II são proposições falsas. 
✓ 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 II. 
• 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. 
 
8. 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(n 2) é 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(n 2 - 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: 
 
• II e III. 
• I e III. 
✓ II e IV. 
• III e IV. 
• I e II. 
 
9. Verificar que determinada operação ou afirmação matemática é válida para qualquer valor 
positivo é uma técnica muito utilizada para garantir os corretos procedimentos 
computacionais. Assim, depois do projeto de certo algoritmo de ordenação, observou-se que 
a contagem do número de comparações feitas para ordenar um vetor de n posições poderia 
ser descrita pelo somatório: 
 
 
 
Com basenessas informações, analise as afirmativas a respeito da aplicação da técnica de 
indução matemática para verificar a validade dessa contagem, para qualquer valor n positivo, 
e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. ( ) Pelo uso da hipótese de indução com n = k e k > 0, a seguinte expressão intermediária 
pode ser obtida: k2 + 2( k + 1) - 1. 
II. ( ) No passo de indução, o uso da hipótese indutiva depende de uma expansão que 
decremente o índice do somatório. 
III. ( ) Tomando como caso base n = 0, a demonstração pode ser desenvolvida a partir da 
hipótese de indução. 
IV. ( ) Para validar o somatório tendo como passo de indução n = k +1 e k > 0, é preciso concluir 
que a soma será dada por k +1. 
 
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. 
 
10. O algoritmo Quick Sort é considerado um dos mais eficientes na operação de ordenação de 
dados em memória principal. Um aspecto crítico do algoritmo é a escolha do elemento para 
atuar como pivô em cada iteração. Essa escolha tem impacto direto na eficiência do 
algoritmo. Considerando as seguintes modificações no algoritmo: 
. A estratégia de escolha do pivô é a seleção do elemento na primeira posição do 
vetor; 
. A primeira posição do vetor tem índice zero; 
. Ao término da iteração (cruzamento dos índices), o pivô é trocado com o elemento 
na posição atual do índice iniciado na extremidade à direita do vetor. 
 
Considerando essas informações e conteúdo estudado, assinale a alternativa correta a 
respeito da execução do Quick Sort sobre o vetor 5, 3, 1, 9, 8, 2, 4, 7. 
 
• As metades à esquerda e à direita do vetor demandam o mesmo número de chamadas 
recursivas para serem ordenadas. 
• Após a ordenação da metade à esquerda do vetor, a metade à direita já se encontra ordenada. 
✓ Na primeira iteração, são feitas três trocas de posições de elementos. 
• O elemento 5 sofre duas mudanças de posição até alcançar a posição definitiva. 
• O elemento 2 é o último pivô escolhido durante a ordenação da metade à esquerda do vetor 
original.