Resumêra

Questão 1 (Média): Sobre definição recorrente, qual alternativa descreve corretamente o conceito?

1.50 Média

A) É uma definição de conjunto sem ordem imposta. B) É uma definição que não usa nenhum caso base. C) É uma definição na qual o item definido aparece na definição (regra recursiva). D) É apenas uma fórmula fechada sem recorrência. E) Não envolve indução para demonstrações.

Resposta correta: C) É uma definição na qual o item definido aparece na definição (regra recursiva).

Observação: esse é o cerne de uma definição recursiva — há uma base + uma regra que utiliza o próprio objeto definido.

Questão 2 (Difícil): Qual é a relação de recorrência típica da sequência de Fibonacci?

2.50 Difícil

A) F_n = F_{n-1} + F_{n-2} B) F_n = F_{n-1} - F_{n-2} C) F_n = F_{n-2} + F_{n-3} D) F_n = F_{n-1} · F_{n-2} E) F_n = 2F_{n-1}

Resposta correta: A) F_n = F_{n-1} + F_{n-2}.

Explicação: pela definição clássica, cada termo é a soma dos dois anteriores, com F1 = F2 = 1.

Questão 3 (Difícil): O que significa indução forte?

2.50 Difícil

A) Assume somente o caso base para provar para todos n. B) Assuma que a propriedade vale para todos r entre 1 e k; prove para k+1. C) Não envolve hipótese de indução. D) É o mesmo que indução simples. E) Prova apenas por contradição.

Resposta correta: B) Assuma que a propriedade vale para todos r entre 1 e k; prove para k+1.

Observação: indução forte utiliza a hipótese de que a propriedade vale para todo r ≤ k, e não apenas para k.

Questão 4 (Extrema): Considere uma relação de recorrência do tipo T(n) = 2T(n/2) + n (divide e conquista). Qual é a complexidade temporal típica?

3.50 Extrema

A) O(n) B) O(n log n) C) O(n^2) D) O(2^n) E) O(log n)

Resposta correta: B) O(n log n).

Justificativa: para T(n) = 2T(n/2) + n, pelo Teorema Mestre, T(n) = Θ(n log n).

Definições Recorrentes e Algoritmos Recursivos

Questões de Conteúdo