UNIVESP - 2021 - Gabarito - Prova - Fundamentos Matemáticos da Computação

Prévia do material em texto

GABARITO 
DISCIPLINA 
EEM001 - Fundamentos Matemáticos da 
Computação 
APLICAÇÃO 
14/04/2021 
CÓDIGO 
DA PROVA P013/P014 
 
QUESTÕES OBJETIVAS 
 
Questão 1.1 
Dada as proposições 𝑃(𝑥): 2𝑥 > 𝑥 e 𝑄(𝑦): 𝑦 < 3, para 𝑥, 𝑦 ∈ ℕ, e as seguintes expressões representadas 
em termos de quantificadores: 
 
I. (∃! 𝑥 ∈ ℕ) 𝑃(𝑥) 
II. (∀𝑦 ∈ ℕ) 𝑄(𝑦) 
 
A respeito dos valores lógicos das expressões I e II, é correto afirmar que: 
a) I e II são verdadeiras. 
b) I é verdadeira e II é falsa. 
c) I é falsa e II é verdadeira. 
d) I e II são falsas. 
e) nenhuma das alternativas anteriores. 
 
RESOLUÇÃO 
A resposta correta é: I e II são falsas. 
 
Justificativa 
A respeito de 𝑃(𝑥): 2𝑥 > 𝑥, temos que tal expressão é sempre verdadeira para “qualquer que seja” o 
𝑥 ∈ ℕ. Logo, é falso afirmar que “existe um único” 𝑥 que atende a desigualdade mostrada. 
Em relação a 𝑄(𝑦): 𝑦 < 3 é verdadeira para 𝑦 ∈ {0,1,2} ⊂ ℕ, ou seja, é falso afirmar que a proposição 
será verdadeira para qualquer 𝑦 natural. 
 
 
Questão 1.2 
Seja 𝐴 = {1,2,3,4} e a relação 𝑅 sobre 𝐴 tal que 𝑅 = {(1,1), (1,2), (2,3), (3,2), (4,4)}. Quais pares devem ser 
adicionados à 𝑅 para que esta relação se torne transitiva? 
a) (2,2), (3,3) 
b) (1,3), (2,2) 
c) (1,3), (1,4) 
d) (3,1), (4,1) 
e) Nenhuma das alternativas anteriores 
 
RESOLUÇÃO 
A resposta correta é: Nenhuma das alternativas anteriores. 
 
 
 
 
Justificativa 
𝑅 será transitiva se, para qualquer 𝑥, 𝑦, 𝑧 ∈ 𝐴, se os pares (𝑥, 𝑦) e (𝑦, 𝑧) estão em 𝑅, (𝑥, 𝑧) também deve 
estar. Ao verificar, de modo exaustivo, conclui-se que os pares (1,3), (2,2) e (3,3) devem ser 
simultaneamente adicionados à 𝑅 a fim de torná-la transitiva. 
 
 
Questão 1.3 
Bino deve fazer um frete que levará tubaína até as cidades de Araraquara, Assis, Bauru, Ilha Solteira, 
Presidente Prudente, Ribeirão Preto, Rio Claro e São José dos Campos. Quantos trajetos Bino pode 
fazer, independentemente da localização ocupada por cada uma destas cidades, desde que assuma 
São José dos Campos como ponto de início, Presidente Prudente como fim do trajeto e visite cada 
cidade uma única vez? 
a) 8! 
b) 6! 
c) 
8!
6!
 
d) 
8!
2!
 
e) Nenhuma das alternativas anteriores 
 
RESOLUÇÃO 
A resposta correta é: 6! 
 
Justificativa 
O problema de frete/sequência apresentado deve passar por 8 cidades, cujo início e fim é definido e 
fixo. Nestas condições, 6 das 8 cidades podem ser visitadas em qualquer ordem desejada, 
independente da distância e posição geográfica que ocupam. Logo, a quantidade de trajetos será igual 
ao número de permutações envolvendo 6 elementos, ou seja, “6!”. 
 
 
Questão 1.4 
A respeito da “conexidade” dos grafos 𝐺 e 𝐻, cujas matrizes de adjacência 𝐴𝐺 e 𝐴𝐻 são apresentadas 
abaixo, é correto afirmar que: 
 
𝐴𝐺 =
(
 
 
0 1 0 0 0
1 0 0 1 1
0 0 0 0 1
0 1 0 0 0
0 1 1 0 0)
 
 
; 𝐴𝐻 =
(
 
 
0 0 0 1 0
0 0 0 0 1
0 0 0 0 1
1 0 0 0 0
0 1 1 0 0)
 
 
 
 
a) 𝐺 e 𝐻 são conexos. 
b) apenas 𝐺 é conexo. 
c) apenas 𝐻 é conexo. 
d) 𝐺 e 𝐻 não são conexos. 
e) Nenhuma das alternativas anteriores. 
 
RESOLUÇÃO 
A resposta correta é: apenas 𝐺 é conexo. 
 
 
Justificativa 
Para fins de organização, considere que cada linha/coluna da matriz corresponde a um dos vértices 
em {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}. Seguindo essa organização, obtemos a seguinte representação: 
 
 
 
Podemos observar que no grafo 𝐻 nem todo par de vértices está conectado por um passeio qualquer, 
logo, 𝐻 não é conexo. Segundo esta mesma justificativa, 𝐺 é caracterizado como um grafo conexo. 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Com uso do princípio da indução finita, prove que ∑ (2𝑖 + 1) = 𝑛2 + 2𝑛𝑛𝑖=1 , para 𝑛 natural maior ou igual 
a 1. 
 
RESOLUÇÃO 
Inicialmente, verificamos os casos base da indução para 𝑛 = 1, 2 e 3: 
𝑛 = 1 ⇒∑(2𝑖 + 1)
1
𝑖=1
= 3 = 12 + 2 ⋅ 1 
𝑛 = 2 ⇒∑(2𝑖 + 1)
2
𝑖=1
= 3 + 5 = 22 + 2 ⋅ 2 
𝑛 = 3 ⇒∑(2𝑖 + 1)
3
𝑖=1
= 3 + 5 + 7 = 32 + 2 ⋅ 6 
 
os quais seguem a forma 𝑛2 + 2𝑛 , conforme observado. 
 
Supondo que para um dado 𝑛 é verdade que ∑ (2𝑖 + 1)𝑛𝑖=1 = 𝑛
2 + 2𝑛; devemos provar que a mesma 
propriedade permanece válida para 𝑛 + 1. Para tal, desenvolvemos: 
∑(2𝑖 + 1)
𝑛+1
𝑖=1
= (∑(2𝑖 + 1)
𝑛
𝑖=1
) + (2(𝑛 + 1) + 1) = 𝑛2 + 2𝑛 + 2𝑛 + 2 + 1 = 
= (𝑛2 + 2𝑛 + 1) + (2𝑛 + 2) = (𝑛 + 1)2 + 2(𝑛 + 1) 
 
Assim, fica provado que ∑ (2𝑖 + 1)𝑛𝑖=1 = 𝑛
2 + 2𝑛 qualquer 𝑛 natural maior ou igual a 1. 
 
Rubricas | critérios de correção 
No caso de provas incompletas, em que o aluno mostra apenas a verificação de validade dos casos 
base, devem ser atribuídos apenas 20% da pontuação. A pontuação total (100%) deve acontecer 
diante da apresentação dos casos base e demonstração de validade da expressão para 𝑛 + 1. 
 
 
Questão 3 
Seja 𝑓(𝑥) = 3𝑥 + 2 e 𝑔(𝑥) =
1
𝑥
 funções com domínio e imagem sobre o conjunto dos números reais 
positivos e não nulo. Determine 𝑔−1 ∘ 𝑓−1(𝑥). 
 
RESOLUÇÃO 
A questão compreende a composição entre as inversas de 𝑓 e 𝑔. Para alcançar tal composição, antes é 
necessária a obtenção das inversas 𝑓−1 e 𝑔−1. 
 
Partindo de 𝑓(𝑥) = 3𝑥 + 2, obtemos sua inversa fazendo: 
 
3𝑥 + 2 = 𝑦 ⇔ 𝑥 =
𝑦 − 2
3
 
Com um ajuste de notação: 
𝑓−1(𝑥) =
𝑥 − 2
3
 
Analogamente, para 𝑔(𝑥) = 1/𝑥: 
1
𝑥
= 𝑦 ⇔ 𝑥 =
1
𝑦
 
Logo: 
𝑔−1(𝑥) =
1
𝑥
 
 
Por fim, a composição 𝑔−1 ∘ 𝑓−1(𝑥) é expressa por: 
𝑔−1 ∘ 𝑓−1(𝑥) =
1
𝑥 − 2
3
=
3
𝑥 − 2
 
sendo 𝑥 ≠ 2. 
 
 
Rubricas | critérios de correção 
Como critério de correção, devem ser contabilizados 25% de pontuação caso determinada 𝑓−1(𝑥); 25% 
de pontuação caso determinada 𝑔−1(𝑥). Os 50% da pontuação remanescente são atingidos com a 
composição correta entre as inversas de 𝑓 e 𝑔. 
 
A resolução deste problema pode ainda ser alcançado via (𝑓 ∘ 𝑔)−1(𝑥), isto é, calculando a inversa da 
composição 𝑓 ∘ 𝑔, já que (𝑓 ∘ 𝑔)−1(𝑥) = 𝑔−1 ∘ 𝑓−1(𝑥).