AD1 1 2020 2 - Fundamentos de Algoritmo para Computação GABARITO

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito AD1-1 Segundo Semestre de 2020
Nome -
Assinatura -
Questões:
1. (1,0)
(a) Dado o conjunto A = {0, {∅}, ∅}, determine o conjunto de partes
de A, P (A).
Resposta: O conjunto das partes de A, P (A), é o conjunto de todos os sub-
conjuntos de A. Logo,
P (A) = {∅, {0}, {{∅}}, {∅}, {0, {∅}}, {0, ∅}, {{∅}, ∅}, {0, {∅}, ∅}}
(b) Dados os conjuntos:
A = {x ∈ Z | (x3 + 1)(2x− 20) ≤ 0}
B = {x ∈ Z | |2x− 3| ≤ 14, x ≥ −4}
C = {x ∈ Z | x é divisível por 3, 0 < x ≤ 14};
pede-se calcular (A ∩B)4 C. Justifique.
Resposta: A notação 4 representa a operação de diferença simétrica. Assim,
dados dois conjuntos X,Y , a diferença simétrica entre X e Y é dada por:
X4 Y = (X ∪ Y )− (X ∩ Y ). Para solucionar a questão vamos, inicialmente,
enumerar os elementos dos conjuntos A,B e C.
Em A, primeiramente analisaremos as raízes da equação (x3 +1)(2x−20) = 0
para depois identificarmos as soluções da inequação da questão. Note que
x = −3 e x = 10 são as raízes da equação (x3 + 1)(2x− 20) = 0. O esboço do
gráfico da função f(x) = (x3 + 1)(2x − 20) pode ser observado na Figura 1.
Note que, para qualquer valor inteiro entre −3 e 10 a função f(x) assume
valores negativos. Portanto, A = {−3,−2,−1, 0, 1, 2, . . . , 10}.
Figura 1: Esboço do gráfico da função f(x) = (x
3
+1)(2x−20) que tem raízes
−3 e 10.
Em B temos que resolver a inequação modular |2x− 3| ≤ 14, onde x ≥ 4. Se
|2x− 3| ≤ 14, então −14 ≤ 2x− 3 ≤ 14, donde −11 ≤ 2x ≤ 17. Logo, −112 ≤
x ≤ 172 . Entretanto, como x ≥ −4 e x ∈ Z, B = {−4,−3,−2,−1, 0, 1, 2, . . . 8}.
Em C temos os inteiros positivos divisíveis por 3 menores ou iguais a 14.
Note que todo número divisível por 3 (também dito múltiplo de 3) pode ser
escrito como 3m, onde m é um número inteiro. Logo, C = {x ∈ Z | x =
3m,m ∈ Z,m ≤ 4} = {3, 6, 9, 12}.
Para concluirmos a questão, (A ∩ B) = {−3,−2,−1, 0, 1, 2, . . . , 8}. Resta
fazer a diferença simétrica com o conjunto C. (A∩B)4C = ((A∩B)∪C)−
((A ∩B) ∩ C).
((A ∩B) ∪ C) = {−3,−2,−1, 0, 1, 2, . . . , 8, 9, 12}
((A ∩B) ∩ C) = {3, 6}
Logo, (A ∩B)4 C = {−3,−2,−1, 0, 1, 2, 4, 5, 7, 8, 9, 12}.
2. (1.5) Mostre pelo Princípio da Indução Matemática que:
1
1×3 +
1
3×5 +
1
5×7 + · · ·+
1
(2k−1)(2k+1) =
k
2k+1
para todo número natural n ≥ 1.
Resposta: Seja P (n) : 11×3 +
1
3×5 +
1
5×7 + · · · +
1
(2n−1)(2n+1) =
n
2n+1 para todo
número natural n ≥ 1.
Base da Indução: Vamos mostrar que P (1) é verdadeira. Como 11×3 =
1
3 e
1
2×1+1 =
1
3 temos que P (1)verdadeira.
Hipótese da Indução: Suponha que P (k) : 11×3+
1
3×5+
1
5×7+· · ·+
1
(2k−1)(2k+1) =
k
2k+1 seja verdadeira para todo k ∈ N.
Passo Indutivo: Vamos mostrar que se P (k) é verdadeira, então P (k + 1) :
1
1×3 +
1
3×5 +
1
5×7 + · · ·+
1
(2k+1)(2k+3) =
k+1
2k+3 é verdadeira.
1
1× 3
+
1
3× 5
+
1
5× 7
+ · · ·+ 1
(2k − 1)(2k + 1)︸ ︷︷ ︸
H.I.
+
1
(2k + 1)(2k + 3)
=
k
2k + 1
+
1
(2k + 1)(2k + 3)
=
k(2k + 3) + 1
(2k + 1)(2k + 3)
=
2k2 + 3k + 1
(2k + 1)(2k + 3)
=
(2k + 1)(k + 1)
(2k + 1)(2k + 3)
=
k + 1
2k + 3
Logo, pelo PIM, temos que P (n) : 11×3 +
1
3×5 +
1
5×7 + · · ·+
1
(2n−1)(2n+1) =
n
2n+1 é
verdadeira para todo número natural n ≥ 1.
3. (1.5) Usando os Princípios aditivo e multiplicativo determine quantos números de
3 dígitos são maiores que 390 e:
(a) têm todos os dígitos diferentes. Justifique. Resposta: Vamos dividir em casos:
• Começam por 3
Neste caso, como queremos números maiores que 390, temos a casa das
centenas fixa com o algarismo 3 e a casa das dezenas fixa com o algarismo
9. Para a casa das unidades restam 7 possibilidades, pois removemos o
0 o 3 e o 9. Portanto, temos 7 números maiores que 390.
• Não começam por 3
Para a casa das centenas temos 6 possibilidades, pois não podemos contar
com o 0, 1, 2 ou 3. Para a casa das dezenas temos 9 possibilidades, pois só
não podemos contar com o algarismo usado nas centenas. Por fim, para
as unidades restam 8 possibilidades, pois não podemos contar com os dois
algarismos previamente utilizados. Assim pelo P.M. temos 6×9×8 = 432
números de 3 algarismos que não começam por 3 e são maiores que 390.
Para finalizar, utilizaremos o P.A. pois os dois casos anteriores são mutua-
mente excludentes. Logo, temos 432 + 7 = 439 números com 3 algarismos
maiores que 390.
(b) não têm dígitos iguais a 1, 3 ou 5. Justifique.
Resposta: Nenhum número que comece por 3 ou 5 deve ser computado. Vamos
analisar, portanto, os casos onde o algarismo das centenas é 4 ou maior 5. Para
as centenas temos 5 possibilidades, 7 possibilidades para as dezenas e 7 para
as unidades. Assim, temos, pelo P.M, 5×7×7 = 245 números de 3 algarismos
maiores que 390 e que não possuem os algarismos 1, 3 ou 5.
(c) têm as propriedades (a) e (b) simultaneamente. Justifique.
Resposta: Neste caso, novamente nenhum número que comece por 3 ou 5
deve ser computado. Para as centenas continuamos com 5 possibilidades,
contudo para as dezenas temos 6 possibilidades, pois não podemos utilizar
o algarismo usado nas centenas e para as unidades temos 5 possibilidades,
pois não podemos utilizar os dois algarismos usados para centenas e dezenas.
Assim, pelo P.M, temos 5 × 6 × 5 = 150 números de 3 algarismos distintos
maiores do que 390 e que não possuem algarismos 1, 3 ou 5.