Resumêra

Q1. Considere a relação de recorrência definida por S n =2S n−1 , com condição inicial S 1 =2. Utilizando o método de expansão e verificação (expanda, suponha e verifique), qual é a forma fechada para essa recorrência?

1.50 pontos Média

A) S_n = 2^n B) S_n = n C) S_n = 2^{n-1} D) S_n = 2^{n+1} E) S_n = 0

Resposta correta: A) S_n = 2^n

Justificativa: com S_1 = 2 e S_n = 2 S_{n-1}, a forma fechada é S_n = 2^n.

Q2. Considere uma relação de recorrência linear de primeira ordem com coeficientes constantes, onde a cada passo é somado um valor fixo. Qual das alternativas representa corretamente uma recorrência desse tipo conforme apresentado no método de obtenção de fórmulas fechadas?

2.50 pontos Difícil

A) T_n = T_{n-1} + 3 B) T_n = 2 T_{n-1} C) T_n = T_{n-1} + n D) T_n = 3n E) T_n = n^2

Resposta correta: A) T_n = T_{n-1} + 3

Justificativa: para T_1 = 1, T_n = 1 + 3(n-1) = 3n - 2; a pergunta tem relação direta com o caso demonstrado na aula. Observe que a forma fechada depende da condição inicial.

Q3. Considere uma relação de recorrência típica de algoritmos de divisão e conquista do tipo T(n)=2T(n/2)+n. Qual é a complexidade assintótica dessa recorrência?

2.50 pontos Difícil

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

Resposta correta: A) Θ(n log n)

Justificativa: para T(n) = 2 T(n/2) + n, pelo Teorema Mestre, a solução é Θ(n log n).

Q4. Em uma relação de recorrência linear homogênea de segunda ordem com coeficientes constantes, qual é a forma geral da solução baseada nas raízes da equação característica associada?

3.50 pontos Extrema

A) T_n = α · r1^n + β · r2^n com r1, r2 raízes de x^2 − a x − b = 0 B) T_n = α · n^2 + β C) T_n = γ · ln(n) D) T_n = δ · n^3 + ε E) T_n = T_1 + ∑_{k=2}^n g(k)

Resposta correta: A) T_n = α · r1^n + β · r2^n com r1, r2 raízes de x^2 − a x − b = 0

Justificativa: para recorrência linear de segunda ordem homogênea com coeficientes constantes, a solução envolve as raízes da equação característica. Os coeficientes α e β são determinados pelas condições iniciais.

Relações de Reconhecimentos e Fórmulas Fechadas

Questões de prática (com pontuação)