CEDERJ-AD1-1-1-2020(4)

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
AD1-1 Primeiro Semestre de 2020
Nome -
Assinatura -
Questões:
1. (0,9)
(a) Considere os conjuntos A = ∅ e B = {∅}.
(a1) Determine o conjunto de partes de A e o conjunto de partes
de B, P (A) e P (B) respectivamente. Justifique.
(a2) Verifique se cada uma das afirmações:
{∅} ∈ P (A) e {∅} ∈ P (B)
é verdadeira ou falsa. Se for verdadeira prove, se for falsa
justifique.
(b) Verifique se a seguinte afirmação é verdadeira ou falsa. Se for
verdadeira prove, se for falsa justifique:
(A△ B)△ C ⊆ (A ∪ B ∪ C)− (A ∩B ∩ C)
sendo A,B e C conjuntos quaisquer e A△B é a diferença simétrica
de A e B, isto é A△ B = (A−B) ∪ (B − A).
2. (0,5) Encontre a fórmula de n(A △ B) em termos de n(A), n(B) e
n(A∩B), usando a propriedade A△B = (A∪B)−(A∩B). Justifique.
3. (1.7) Mostre pelo Princípio da Indução Matemática que:
(a) 13 +23 +33 + · · ·+ n3 = n
2(n+1)2
4
para todo número natural n ≥ 1.
(b) 1 + 2 + 3 + · · ·+ n < n2 para todo número natural n ≥ 2.
4. (1.4) Usando os Princípios aditivo e multipliado determine a quantidade
de números comprendidos entre 0 e 10000 que verificam:
(a) os dígitos são todos diferentes sendo que os dígitos pares e os ímpa-
res aparecem alternados. Por exemplo, os números 0, 10, 23, 1034
devem ser contados mas não 13 ou 241. Justifique;
(b) os dígitos podem estar repetidos mas não têm 2 (dois) dígitos
consecutivos iguais. Por exemplo, 1010 deve ser contado mas não
110. Justifique.