Gabarito - UNIVESP - 2021 - Prova - Projeto e Análise de Algoritmos

Prévia do material em texto

GABARITO 
DISCIPLINA 
EEM002 - Projeto e Análise de Algoritmos 
APLICAÇÃO 
21/09/2021 
CÓDIGO 
DA PROVA P015 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
Observe as seguintes funções abaixo: 
f(n) = 2100 
g(n) = n2 + 250log n 
h(n) = 210n 
 
Assinale a alternativa que indica a ordem das funções acima de acordo com o crescimento para valores 
de n grandes. 
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) 
e) h(n) < f(n) < g(n) 
 
RESOLUÇÃO 
A resposta correta é: “f(n) < h(n) < g(n).” 
 
JUSTIFICATIVA 
A função f(n) é uma constante, h(n) é linear e g(n) é quadrática. Para valores grandes de n, a ordem de 
crescimento é f(n) < h(n) < g(n). 
 
 
Questão 1.2 
Em relação à ordem de crescimento das funções, assinale com V (verdadeiro) ou F (falso) as afirmações 
abaixo: 
( ) Funções cúbicas crescem a uma taxa maior que funções quadráticas. 
( ) Funções exponenciais são as que possuem maior taxa de crescimento. 
( ) Funções logarítmicas possuem uma taxa de crescimento menor que as lineares. 
( ) Funções do tipo n log n crescem mais rápido do que lineares. 
 
A sequência correta de preenchimento dos parênteses, de cima para baixo, é: 
a) V-V-V-V. 
b) V-V-F-F. 
c) F-F-V-V. 
d) V-F-V-F. 
e) F-V-F-V. 
 
RESOLUÇÃO 
A resposta correta é: “V-V-V-V.” 
JUSTIFICATIVA 
Todas estão corretas. 
 
 
Questão 1.3 
Para valores grandes de n, assinale a alternativa correta em relação à ordem de crescimento das funções: 
a) 250 < n log3 2 < n 
b) 2n < n3 < 1000n 
c) 0.5n5 < 3n/2 < 1010n 
d) 3100 < 2n < log n3 
e) 1010n < 250 < 1010n2 
 
RESOLUÇÃO 
A resposta correta é: 250 < n log3 2 < n 
 
JUSTIFICATIVA 
A primeira função é constante e não possui taxa de crescimento. Já a segunda é equivalente a n0,63... e 
a terceira é linear (n1). As demais alternativas não obedecem à regra: constante < logarítmica < linear < 
quadrática < polinomial < exponencial. 
 
 
Questão 1.4 
Assinale a alternativa que indica a complexidade da seguinte equação de recorrência: 
T(n) = 16T(n/4) + n2 
a) Θ(n) 
b) Θ(n log n) 
c) Θ(n2 log n) 
d) Θ(n2) 
e) Θ(n3) 
 
RESOLUÇÃO 
A resposta correta é: “Θ(n2 log n).” 
 
JUSTIFICATIVA 
Para essa recorrência, podemos aplicar o caso 2 do teorema mestre. Pela equação de recorrência, temos 
a = 16, b = 4 e f(n) = n2. Além disso, logba = log416 = 2. Como nlogba = f(n), então podemos aplicar o caso 
2: T(n) = Θ(nlogba log n) = Θ(n2 log n). 
 
 
Questão 1.5 
Assinale com V (verdadeiro) ou F (falso) nas afirmações abaixo, dado um algoritmo com a seguinte 
equação de recorrência T(n) = 2T(n/3) + O(n2): 
( ) o algoritmo divide o problema em dois subproblemas com 1/3 do tamanho em cada. 
( ) a etapa de divisão do algoritmo tem complexidade linear. 
( ) o algoritmo sob análise não possui funções recursivas. 
( ) as etapas de divisão e combinação têm complexidade quadrática. 
A sequência correta de preenchimento dos parênteses, de cima para baixo, é: 
a) V-F-F-V. 
b) V-V-V-V. 
c) F-F-V-V. 
d) V-V-F-F. 
e) F-V-V-F. 
 
RESOLUÇÃO 
A resposta correta é: “V-F-F-V.” 
 
JUSTIFICATIVA 
O algoritmo possui duas chamadas recursivas com 1/3 dos elementos em cada chamada. As etapas de 
divisão e combinação são O(n2). 
 
 
Questão 1.6 
Assinale a alternativa que indica a complexidade da seguinte equação de recorrência: 
T(n) = 8T(n/2) + Θ(n2) 
 
a) Θ(log n) 
b) Θ(n log n) 
c) Θ(n) 
d) Θ(n2) 
e) Θ(n3) 
 
RESOLUÇÃO 
A resposta correta é: Θ(n3) 
 
JUSTIFICATIVA 
Para essa recorrência, podemos aplicar o caso 1 do teorema mestre. Pela equação de recorrência, temos: 
a = 8, b = 2 e f(n) = n2. Além disso, logba = log28 = 3. Aplicando o caso 1, temos: f(n) = Θ(n3-e), para algum 
e > 0. Fazendo e = 1, temos: f(n) = O(n3-e) = O(n3-1) = O(n2). Assim, T(n) = Θ(n 
 
 
Questão 1.7 
Sobre a estrutura heap e o Heapsort, considere as afirmativas abaixo: 
I. Heap é uma árvore binária em que os nós da subárvore da esquerda devem ser menores que os da 
subárvore da direita. 
II. O Heapsort possui complexidade linear de espaço. 
III. A manutenção da propriedade de heap consiste em fazer rotações na árvore a fim de que a ordem 
entre subárvore esquerda e subárvore da direita seja mantida. 
 
Das afirmações listadas acima, as que estão corretas são: 
a) I, II e III. 
b) I e II. 
c) II e III. 
d) Apenas II. 
e) Nenhuma está correta. 
 
RESOLUÇÃO 
A resposta correta é: Apenas II. 
 
JUSTIFICATIVA 
I. Heap é uma árvore binária, mas a relação de ordem é apenas entre a raiz e seus filhos. Caso seja uma 
max-heap, a raiz deve ser maior ou igual aos filhos; e se for uma min-heap, a raiz deve ser menor ou 
igual aos filhos. 
III. A manutenção não realiza rotações na árvore: apenas é feita a troca das chaves da raiz e um dos 
filhos. 
 
 
QUESTÃO DISSERTATIVA 
 
Questão 2 
Sobre algoritmos de ordenação, informe se as sentenças abaixo são falsas ou verdadeiras. Justifique 
sua resposta quando for falsa. 
a) O Mergesort possui complexidade O(n) no melhor caso. 
b) O Quicksort possui complexidade O(n log n) no pior caso. 
c) Qualquer algoritmo de ordenação baseado em comparações possui complexidade Ω(n log n). 
d) O Radixsort possui complexidade O(n log n) no melhor caso. 
e) Qualquer algoritmo de ordenação baseado em comparações possui limite superior de Ω(n log 
n). 
 
RESOLUÇÃO 
a) Falso. O Mergesort possui complexidade O(n log n) em qualquer caso. 
b) Falso. O Quicksort possui complexidade O(n2) no pior caso. 
c) Verdadeiro 
d) O Radixsort, por não ser baseado em comparações, possui complexidade linear. 
e) Qualquer algoritmo de ordenação baseado em comparações possui limite inferior de Ω(n log n). 
 
RUBRICAS | CRITÉRIOS DE CORREÇÃO 
20% para cada sentença classificada corretamente. 
10% para sentenças classificadas corretamente mas sem justificativa.