Projeto e Análise de Algoritmos - EEM002 Gabarito 30 09 2020

Prévia do material em texto

GABARITO 
DISCIPLINA 
EEM002 - Projeto e Análise de Algoritmos 
APLICAÇÃO 
30/09/2020 
CÓDIGO 
DA PROVA P005/P006 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
Dado o algoritmo abaixo, assinale a alternativa que indica a quantidade, em função de n, de 
atribuições que serão realizadas na execução do algoritmo. 
 
ALGORITMO (n) 
1 soma = 0 
2 i = 1 
3 enquanto i <= n faça 
4 soma = soma + i 
5 i = i + 1 
6 retorne soma 
 
a) 2n+2 
b) n+1 
c) 2n+1 
d) n+2 
 
RESOLUÇÃO 
A resposta correta é: 2n+2 
 
Justificativa 
A primeira e a segunda linhas possuem uma atribuição cada e são executadas uma vez. Na terceira 
linha não há atribuições. Na quarta e na quinta linhas são executadas duas atribuições para cada 
iteração do loop. Total: 2+ 2n 
 
 
Questão 1.2 
Dadas as seguintes funções, indique a ordem delas de acordo com o crescimento para valores de n 
grandes. 
 
f(n) = log (10000n) 
g(n) = n2 + 10 
h(n) = 21000n 
 
a) f(n) < g(n) < h(n) 
b) f(n) < h(n) < g(n) 
c) g(n) < f(n) < h(n) 
d) g(n) < h(n) < f(n) 
 
RESOLUÇÃO 
A resposta correta é: f(n) < h(n) < g(n) 
 
Justificativa 
Função logarítmica tem menor taxa de crescimento e função polinomial depende do expoente de n. 
 
 
Questão 1.3 
Dado um algoritmo com a seguinte equação de recorrência: T(n) = 3T(n/2) + O(n). Podemos dizer que: 
a) o algoritmo divide o problema em dois subproblemas com um terço de tamanho cada. 
b) a etapa de conquista do algoritmo tem complexidade linear. 
c) o algoritmo leva O(n) para realizar as etapas de divisão e combinação. 
d) em cada etapa, o algoritmo chama uma recursão com 2/3 do tamanho de n. 
 
RESOLUÇÃO 
A resposta correta é: a etapa de conquista do algoritmo tem complexidade linear. 
 
Justificativa 
É chamado recursivamente três vezes o mesmo algoritmo com metade do tamanho de n. Após essa 
fase de divisão, é realizada a etapa de combinação (conquista), que leva O(n). 
 
 
Questão 1.4 
Sobre algoritmos de ordenação, considere as seguintes sentenças: 
 
1. O Quicksort tem complexidade de tempo linear, no melhor caso. 
2. O Mergesort tem complexidade de tempo quadrática, no pior caso. 
3. O Heapsort tem complexidade de espaço Θ (1). 
 
Assinale a alternativa que apresenta a sequência correta: 
a) F - V - V 
b) F - F - V 
c) F - F - F 
d) V - V - V 
 
RESOLUÇÃO 
A resposta correta é: F - F - V 
 
Justificativa 
O Quicksort tem complexidade O(n log n), no melhor caso. 
O Mergesort tem complexidade O(n log n), em qualquer caso. 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Utilize o teorema mestre para resolver a seguinte equação de recorrência: T(n) = 2T(n/2) + Θ(n). 
 
RESOLUÇÃO 
Para essa recorrência, temos: a = 2, b = 2 e f(n) = Θ(n). 
Além disso, logba = log22 = 1. 
Dos três casos possíveis, apenas o 2 é aplicável, já que f(n) = Θ(nlogba). 
Aplicando o caso 2, temos: 
f(n) = Θ(nlogba) = Θ(n). Portanto, T(n) = Θ(nlogba logn) = Θ(n log n). 
 
Rubricas | critérios de correção 
50% caso o aluno acerte o resultado final. 
50% caso o aluno acerte o caso do teorema mestre. 
 
 
Questão 3 
Demonstre que n3 + n é Ω(n). 
 
RESOLUÇÃO 
Falar que n3 + n é Ω(n) equivale a dizer que: 
- Existe uma constante c e um valor inicial n0, tal que n3 + n >= cn. 
- Escolhendo um valor para n0 que seja maior ou igual a 1 e c = 1, podemos satisfazer a condição 
acima. Desse modo, temos que n3 + n > 1.n para qualquer valor de n >= 1. Assim, n3 + n é Ω(n). 
 
Rubrica | critérios de correção 
O aluno pode chegar a outra prova (principalmente se escolher outros valores para c e n0). Nesse caso, 
verificar se os cálculos estão corretos.