ESTRUTURAS DE DADOS PROVA 0 BUSINESS AS USUAL

RAUL H.C. LOPES

1. Introdução

Esta prova foi elaborada para ser resolvida em uma hora. A prova deve ser resolvida individualmente, sendo permitida consulta a notas de aula. Todas as questões têm o mesmo peso.

2. As questões

Questão 1. Seja P.S o conjunto de todos os subconjuntos de S e #S, o número de elementos de S. Prove que P.S = 2^{#S}. Dica: Qualquer subconjunto de um conjunto de n elementos pode ser representado por uma seqüência de n booleanos, cada um indicando se determinado elemento do conjunto original ocorre ou não no subconjunto em questão. Questão 2. Veja a função a seguir.

   gcd (m,n) = if m < n
               then gcd(m,n-m)
               else if m > n
               then gcd(m-n,n)
               else m

Prove que, se a e b são inteiros maiores do que zero, gdc(a, b) termina e produz o maior divisor comum de a e b. Questão 3. Considere a definição a seguir.

F_{0} =0
F_{1} =1
F_{n} =F_{n−1} + F_{n−2}, para n > 1

Prove que, para todo n inteiro (n ≥ 0), F_{n} < 2^{n}.

3. ...I’ll say when it’s the end!

... and Aunt Sally she come in, and when we got back se was standing on top of the bed raising Cain, and the rats was doing what they could to keep off the dull times for her.