Gabarito FMC Prova

Prévia do material em texto

GABARITO 
DISCIPLINA 
COM150 - Fundamentos Matemáticos para Computação 
APLICAÇÃO 
03/12/2020 
CÓDIGO 
DA PROVA P001/P002 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
Usando o teorema mestre, assinale a alternativa que contém a ordem de grandeza para a relação de 
recorrência abaixo. 
 
S(n)=81S(n/3)+n4 para n>1 
S(1)=1 para n=1. 
 
a) Θ(nlogn) 
b) Θ(n4logn) 
c) Θ(n4) 
d) Θ(n) 
e) Θ(n3) 
 
RESOLUÇÃO 
A resposta correta é: Θ(n4logn). 
 
Justificativa 
Para S(n)=aS(n/b)+nc, usamos o teorema mestre, em que: 
Se a < bc ⇒ S(n)= Θ(nc) 
Se a = bc ⇒ S(n)= Θ(nclogn) 
Se a > bc ⇒ S(n)= Θ(nlogba) 
 
Temos f(n)=n3, a=81, b=3 e c=4: 𝑎 = 81 = 34 
Assim, 𝑆(𝑛) = 𝛩(𝑛4𝑙𝑜𝑔𝑛). 
 
 
Questão 1.2 
Considere as sentenças abaixo. 
 
i. Todos os nós são adjacentes em um grafo completo com n>1, em que n é o número de nós. 
ii. Arcos repetidos ocorrem em um ciclo dentro de um grafo. 
iii. Uma árvore binária completa tem todos os nós filhos presentes no último nível da árvore. 
 
a) Apenas i é verdadeira. 
b) Apenas ii é verdadeira. 
c) Apenas iii é verdadeira. 
d) Apenas i e ii são verdadeiras. 
e) Apenas ii e iii são verdadeiras. 
 
RESOLUÇÃO 
A resposta correta é: Apenas i é verdadeira. 
 
Justificativa 
i. Correta. Trata-se da definição de um grafo completo. 
ii. Incorreta. No caminho definido em um ciclo, apenas o nó de início e fim se repetem. Não há arcos 
repetidos. 
iii. Incorreta. Uma árvore binária cheia (e não completa) tem todos os nós filhos presentes no último 
nível da árvore. 
 
 
Questão 1.3 
Assinale a alternativa correta, considerando as sentenças abaixo sobre os grafos G1 e G2. 
i. No grafo G1, há caminho de Euler e não há circuito hamiltoniano. 
ii. No grafo G2, não há caminho de Euler e há circuito hamiltoniano. 
iii. No grafo G1, não há caminho de Euler e no grafo G2 há circuito hamiltoniano. 
 
a) Apenas i está correta. 
b) Apenas ii está correta. 
c) Apenas iii está correta. 
d) Apenas i e ii estão corretas. 
e) Apenas ii e iii estão corretas. 
 
RESOLUÇÃO 
A resposta correta é: Apenas i e ii estão corretas. 
 
Justificativa 
No grafo G1, temos: 
grau(1) = 2 (grau do nó 1), grau(2)=2, grau(3)=2, grau(4)=3, grau(5)=1 e grau(6)=2 
Temos apenas dois nós ímpares (com grau ímpar). Logo, há um caminho euleriano que começa e 
termina nos nós ímpares. 
Por outro lado, não há arco ligando os nós 5 e 6, por isso, não é possível encontrar um ciclo contendo 
todos os nós do grafo. Logo, não há circuito hamiltoniano em G1. 
No grafo G2, temos: 
grau(1) = 3 (grau do nó 1), grau(2)=2, grau(3)=2, grau(4)=3, grau(5)=3 e grau(6)=5 
Temos mais que dois nós ímpares (com grau ímpar). Logo, não há um caminho euleriano. 
Por outro lado, há um ciclo contendo todos os nós do grafo. Logo, há circuito hamiltoniano. 
1, {1,2}, 2, {2,3}, 3, {3,4}, 4, {4,5}, 5, {5,6}, 6{6,1}, 1. 
Questão 1.4 
Assinale a alternativa que contém as justificativas corretas para os itens i, ii e iii indicados na 
demonstração abaixo. Dica: cada item (i, ii e iii) deve indicar a regra de inferência ou equivalência 
lógica correta, ou seja, que justifique o resultado daquela linha a partir das anteriores. 
 
(∀x)([P(x)]’∨ [Q(x)]′) ∧ [(∀x)([R(x)]’ ∨ [P(x)]’)]’ → (∃x)(Q(x)→R(x)) 
 
1. (∀x)([P(x)]’∨ [Q(x)]′) 
2. [(∀x)([R(x)]’ ∨ [P(x)]’)]’ 
3. (∀x)([P(x)]→[Q(x)]′) i 
4. (∃x)([R(x)]’ ∨ [P(x)]’)’ ii 
5. (∃x)(R(x) ∧ P(x)) 
6. [P(u)]→[Q(u)]′) iii 
7. R(u)∧P(u) 
8. R(u) 
9. P(u) 
10. [Q(u)]’ iv 
11. [Q(u)]’∨R(u) 
12. Q(u)→R(u) 
13. (∃x)(Q(x)→R(x)) 
 
 
a) i - linha 1, equivalência condicional 
ii - linha 2, [(∃x)A(x) ] ’ ⇔ (∀x)[A(x)]’ 
iii - linha 3, particularização universal 
iv - linhas 6 e 9, modus ponens. 
b) i - linha 1, equivalência condicional 
ii - linha 2, [(∃x)A(x) ] ’ ⇔ (∀x)[A(x)]’ 
iii - linha 3, particularização existencial 
iv - linhas 6 e 9, modus ponens. 
c) i - linha 1, equivalência condicional 
ii - linha 2, [(∀x)A(x) ] ’ ⇔ (∃x)[A(x)]’ 
iii - linha 3, particularização universal 
iv - linhas 6 e 9, modus ponens. 
d) i - linha 1, equivalência condicional 
ii - linha 2, De morgan 
iii - linha 3, particularização universal 
iv - linhas 6 e 9, modus tollens. 
e) i - linha 1, conjunção 
ii - linha 2, [(∃x)A(x) ] ’ ⇔ (∀x)[A(x)]’ 
iii - linha 3, particularização existencial 
iv - linhas 6 e 9, modus ponens. 
 
 
RESOLUÇÃO 
A resposta correta é: 
i - linha 1, equivalência condicional 
ii - linha 2, [(∀x)A(x) ] ’ ⇔ (∃x)[A(x)]’ 
iii - linha 3, particularização universal 
iv - linhas 6 e 9, modus ponens. 
 
Justificativa 
Segue passo a passo a demonstração: 
(∀x)([P(x)]’∨ [Q(x)]′) ∧ [(∀x)([R(x)]’ ∨ [P(x)]’)]’ → (∃x)( Q(x)→R(x)) 
 
1. (∀x)([P(x)]’∨ [Q(x)]′) hip 
2. [(∀x)([R(x)]’ ∨ [P(x)]’)]’ hip 
3. (∀x)([P(x)]→[Q(x)]′) linha 1, equivalência condicional 
 (A’∨B)⇔(A→B) 
4. (∃x)([R(x)]’ ∨ [P(x)]’)’ linha 2, [(∃x)A(x) ] ’ ⇔ (∀x)[A(x)]’ 
5. (∃x)(R(x) ∧ P(x)) linha 4, De Morgan (A∨B)’⇔(A’∧B’) 
6. [P(u)]→[Q(u)]′) linha 3, particularização universal 
 De (∀x)A(x), infere A(u) (ver restrições) 
7. R(u)∧P(u) linha 4, particularização existencial 
De (∃x)A(x), infere A(u) (ver restrições) 
8. R(u) linha 7, simplificação 
De A∧B, infere A e B 
9. P(u) linha 7, simplificação 
10. [Q(u)]’ linhas 6 e 9, modus ponens 
De A, A→B infere B 
11. [Q(u)]’∨R(u) linhas 8 e 10, adição 
De A, infere A∨B 
12. Q(u)→R(u) linha 11, equivalência condicional 
13. (∃x)(Q(x)→R(x)) linha 12, generalização existencial (ver restrições) 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Prove por indução que 6n-1 é divisível por 5 para n inteiro positivo. 
 
RESOLUÇÃO 
Passo base da indução: 
n=1, temos 61-1=6-1=5 ok 
Hipótese de indução: suponha válido para n=k, 
n=k, temo 6k-1=5.a, a inteiro. 
Passo indutivo: provar para n=k+1 
n=k+1, vamos provar que 6k+1-1=5.b, b inteiro 
 
Temos: 
 6k+1-1=6k.6-1 
 =(5.a+1).6-1, pela hipótese de indução 6k-1=5a ⇔6k=5a+1 
 =30a+6-1=30a+5 
 =5(6a+1)=5b 
Logo, 6k+1-1=5b, b inteiro. 
 
Rubricas | critérios de correção 
Atribuir até 80% da nota se o aluno utilizou a hipótese de indução corretamente, mesmo sem ter 
concluído a demonstração. 
Atribuir no máximo 20% se o aluno resolveu apenas o passo base da indução. 
 
 
Questão 3 
Encontre a fórmula fechada para a relação de recorrência abaixo: 
 
S(1)=1 
S(n)=S(n-1) + 5n, n≥2 
 
Dica: Utilize a fórmula 
𝑆(𝑛) = 𝑐𝑛−1𝑆(1) + ∑ 𝑐𝑛−𝑖𝑔(𝑖)
𝑛
𝑖=2
 
 
 
RESOLUÇÃO 
c=5, g(n)=5n 
 
T(n)=5n-1S(1)+ [5n-2.g(2)+5n-3.g(3)+5n-4.g(4)+...+50.g(n)] 
 =5n-1.1+ [5n-2.52+5n-3.53+5n-4.54+...+50.5n] 
 =5n-1+ [5n+5n+5n+...+5n] 
 =5n-1+ (n-1).5n n-1 termos 5n 
 
 =5n(1/5 + n-1) 
 =5n-1.(5n-4) 
 
Rubricas | critérios de correção 
Descontar até 70%, se a fórmula apresentada não foi utilizada corretamente e os passos não foram 
detalhados como apresentado acima. 
Descontar até 30% por pequenos erros de cálculo.