AD1 Fundamentos de Algoritmos 2014-1 CEDERJ

1476 palavras 6 páginas
Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Professoras: Susana Makler e Sulamita Klein
Gabarito AP1 - Primeiro Semestre de 2014
Nome Assinatura -

Observações:
1. Prova sem consulta e sem uso de máquina de calcular. Não é necessário fazer as contas. Pode deixar o resultado indicado, como uma soma, ou 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.

1 www.CompCEDERJ.com.br Questões:
1. (1.5)
(a) Considere A = {{∅}, 1}.
(a1 ) Encontre o conjunto de partes de A, P(A).
Resposta: P(A) = {∅, {{∅}}, {1}, {{∅}, 1}}
(a2 ) Determine se a seguinte relação
{∅} ∈ P(A) é verdadeira ou não. Justifique a resposta.
Resposta: Através do conjunto P(A) descrito no item a1 , temos que a afirmação é falsa. Note que ela só seria verdadeira se ∅ ∈ A. Seria correto afirmar que: ∅ ∈ P(A), {{∅}} ∈ P(A), {∅} ⊆ P(A) ou ainda que {∅} ∈ A.
(b) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira. Se for verdadeira, prove, se for falsa justifique.
(b1 ) B − (C ∪ D) = (B − C) ∪ (B − D),
Resposta: Falsa. Observe os Diagramas de Venn da Figura 1.
(b2 ) n(B ∪ C) + n(B ∩ C) > n(B) + n(C), onde B, C e D são conjuntos arbitrários.
Resposta: Falso. Pelo Princípio da Inclusão e Exclusão para dois conjuntos, temos: n(B ∪ C) = n(B) + n(C) − n(B ∩ C).
Logo,
n(B ∪ C) + n(B ∩ C) = n(B) + n(C).
2. (2.0) Considere a sequência a1 , a2 , a3 , · · · definida por: a1 = 3, ak = 7ak−1 para todos os inteiros k ≥ 2.
Mostre por Indução Matemática que an = 3 × 7n−1 para todos os

Relacionados