AP1 FAC 2012 2 Gabarito

Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Gabarito AP1 - Segundo Semestre de 2012
Nome Assinatura -

Observações:
1. Prova sem consulta e sem uso de máquina de calcular. Se necessário deixe o resultado indicado, como um produto ou quociente ou potência de números inteiros ou fatoriais.
2. Resultado sem indicação de como foi obtido, não será considerado.
3. Use caneta para preencher o seu nome e assinar nas folhas de questões e nas folhas de respostas.
4. Você pode usar lápis para responder as questões.
5. Ao final da prova devolva as folhas de questões e as de respostas.
6. Todas as respostas devem ser transcritas nas folhas de respostas. As respostas nas folhas de questões não serão corrigidas.

Questões:
1. (1.2) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) ∅ ∈ A para todo conjunto A.
Resposta: Falsa. Como o conjunto vazio não é elemento de todo conjunto, temos que a afirmação é falsa. Seria correto afirmar que
∅ ⊆ A, visto que ∅ é subconjunto de qualquer conjunto.
(b) A − (B ∪ C) = (A − B) ∪ (A − C), para todos os conjuntos A, B e C.
Resposta: Falsa. Sejam A = {1, 2, 3, 4}, B = {2, 4, 5, 7}, C =
{2, 3, 5, 6}. Observe que B ∪ C = {2, 3, 4, 5, 6, 7} e que A − (B ∪
C) = {1}. Por outro lado, A − B = {1, 3} e A − C = {1, 4} e, consequentemente, (A − B) ∪ (A − C) = {1, 3, 4}. Logo, A − (B ∪
C) = (A − B) ∪ (A − C).
2. (1.5) Mostre por indução matemática que:
1

1
2

0

+2

1
2

1

+3

1
2

2

+· · ·+n

n−1

1
2

= 4−

n+2 para todo natural n ≥ 1.
2n−1

Observação: Indique claramente os passos da indução.
Resposta: Seja
P (n) : 1

1
2

0

+2

1
2

1

1
2

+3

2

+ ··· + n

para todo natural n ≥ 1. base da indução: Para n=1 temos
1

1
2

1−1

=1

1
2

n−1

=4−

n+2
2n−1

e

1+2
=4−3=1
21−1

4−
.
Logo, P (1) é verdadeira.

hipótese de indução: Vamos supor que
1
2

P (k) : 1

0

+2

1

1
2

1
2

+3

2

+· · ·+k

1
2

k−1

= 4−

k+2
para