A maior rede de estudos do Brasil

Grátis
37 pág.
03-recorrencia

Pré-visualização | Página 1 de 1

Recorrência
Sumário
• Definições Recorrentes
‣ Seqüências, conjuntos e operações 
• Resolução de Relações de Recorrência
Definições Recorrentes
• Uma definição recorrente é uma definição 
onde o item sendo definido aparece como 
parte da definição.
‣ definir algo em termos de si mesmo
• Exemplo: definição recorrente de fatorial
Partes de uma 
Definição Recorrente
• Base (ou condição básica)
‣ casos elementares definidos explicitamente
• Recorrência (ou passo indutivo)
‣ demais casos definidos em função dos casos 
elementares
• Recorrência é uma conceito importante 
que pode ser usado para definir:
‣ seqüências
‣ conjuntos
‣ operações
‣ algoritmos
Seqüências
• Uma seqüência é uma lista ordenada de 
elementos
• Exemplo:
‣ S = 2, 4, 8, 16, 32, ...
‣ S(1) = 2, S(4) = 16
Seqüências Definidas 
por Recorrência
• Uma seqüência é definida por recorrência 
nomeando-se, explicitamente, o primeiro 
elemento na seqüência e depois definindo-
se os demais elementos em termos dos 
anteriores
• Exemplo (S = 2, 4, 8, 16, 32, ...)
‣ S(1) = 2
‣ S(n) = 2 * S(n-1), para n ≥ 2
Exercício
• Escreve os cinco primeiros valores da 
seqüência T definida a seguir
‣ T(1) = 1
‣ T(n) = T(n-1) + 3
Seqüência de Fibonacci
• É uma seqüência de números definida por 
recorrência como a seguir:
‣ F(1) = 1
‣ F(2) = 1
‣ F(n) = F(n-1) + F(n-2), para n ≥ 3
• Escreva os 8 primeiros termos da 
seqüência de Fibonacci.
Conjuntos
• Um conjunto é uma coleção de objetos
‣ não há nenhuma ordem imposta à coleção
• Conjuntos podem ser definidos por 
relações de recorrência.
‣ Base: objetos elementares do conjunto
‣ Recorrência: regra para composição de novos 
objetos do conjunto
Exemplo
• Definição recorrente do conjunto das 
fórmulas proposicionais bem formuladas 
(FBF)
‣ Base: uma proposição é uma FBF
‣ Recorrência: se P e Q são FBFs então P ∧ Q, P ∨ 
Q, P → Q, P′, e P ↔ Q também são FBFs
Operações Definidas 
por Recorrência
• Certas operações podem ser definidas de 
forma recorrente
• Exemplo: definição recorrente da 
exponenciação an
‣ a0 = 1
‣ an = a * an-1, para n ≥ 1
Definições Recorrentes
Seqüência 
Pelo menos o primeiro valor é definido 
explicitamente; os demais valores são 
definidos em termos dos anteriores.
Conjunto
Pelo menos um elemento do conjunto é 
definido explicitamente; os demais 
elementos são construídos a partir de 
elementos que pertencem ao conjunto.
Operação
Um caso trivial (elementar) é definido 
explicitamente; demais casos são calculados 
a partir de casos menores.
Exercícios
• Escreve os cinco primeiros valores da 
seqüência M a seguir:
‣ M(1) = 2
‣ M(2) = 2
‣ M(n) = 2*M(n-1) + M(n-2)
• Considerando a série de Fibonacci, prove 
que F(n+1) + F(n-2) = 2F(n)
Considere a seqüência S definida por recorrência:
S(1) = 2
S(n) = 2*S(n-1)
Existe uma equação na qual podemos substituir o 
valor de n e calcular diretamente o valor de S(n) 
sem ter que calcular os valores anteriores?
Considere a seqüência S definida por recorrência:
S(1) = 2
S(n) = 2*S(n-1)
Existe uma equação na qual podemos substituir o 
valor de n e calcular diretamente o valor de S(n) 
sem ter que calcular os valores anteriores?
S(n) = 2n
Resolvendo Relações 
de Recorrência
• Resolver uma relação de recorrência 
significa encontrar para ela uma solução em 
forma fechada.
• Uma solução em forma fechada para uma 
relação de recorrência sujeita a uma 
condição básica é uma equação na qual 
podemos substituir um valor para calcular 
diretamente o elemento que queremos.
Estratégias para Resolução 
de Recorrências
• Método “expandir, conjecturar e verificar”
• Solução geral
‣ no caso de uma relação de recorrência linear de 
primeira ordem.
“Expandir, conjecturar e 
verificar”
• Consiste em usar repetidamente a relação 
de recorrência para expandir a expressão 
do n-ésimo termo até que seja possível 
perceber uma equação para a solução em 
forma fechada.
• É preciso verificar a equação encontrada
‣ em geral, a verificação pode ser feita por 
indução
Exemplo
• Considere a condição básica e a relação de 
recorrência para a seqüência S a seguir:
‣ S(1) = 2
‣ S(n) = 2 * S(n-1)
• Encontre a solução em forma fechada para 
a relação de recorrência. 
Passo 1: Expandir
S(n) = 2 * S(n-1)
Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)
Passo 2: Conjecturar
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)
Após k, expansões
Passo 2: Conjecturar
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)
...
= 2k * S(n-k)
Após k, expansões
S(n) = 2k * S(n-k)
Podemos continuar com a expansão 
continuamente ou existe um limite para k?
S(n) = 2k * S(n-k)
Podemos continuar com a expansão 
continuamente ou existe um limite para k?
O limite é o caso base S(1), ou seja,
n-k = 1
⇓
k = n-1
S(n) = 2k * S(n-k)
Podemos continuar com a expansão 
continuamente ou existe um limite para k?
O limite é o caso base S(1), ou seja,
n-k = 1
⇓
k = n-1
⇓
S(n) = 2n-1 * S[n-(n-1)] = 2n-1 * S[1] = 2n-1 * 2 = 2n
Passo 3: Verificar
• Por raciocínio indutivo, inferimos que a 
solução em forma fechada é S(n) = 2n.
• Ainda é preciso demonstrar que, de fato, 
S(n) = 2n, para todo n ≥ 1.
‣ podemos fazer isso por indução em n.
Estratégias para Resolução 
de Recorrências
• Método “expandir, conjecturar e verificar”
• Solução geral
‣ no caso de uma relação de recorrência linear de 
primeira ordem.
Recorrência Linear
• Uma relação de recorrência para uma 
seqüência S(n) é denominada linear se os 
valores anteriores de S aparecem na relação 
apenas na primeira potência.
• Forma geral:
‣ S(n) = f1(n)S(n-1)+f2(n)S(n-2)+...+fk(n)S(n-k)+g(n)
Recorrência de 
Primeira Ordem
• Uma relação de recorrência para uma 
seqüência S(n) é de primeira ordem se o 
cálculo do termo n depende apenas do 
termo n-1.
• Forma geral:
‣ S(n) = f1(n) S(n-1) + g(n)
Solução Geral
• Utilizando o método “expandir, conjecturar 
e verificar”, podemos encontrar uma 
solução em forma fechada geral para 
relações de recorrência lineares de 
primeira ordem com coeficientes 
constantes.
• Solução geral para 
‣ S(n) = cn−1S(1) + n�
i=2
cn−1g(i)
S(n) = cS(n− 1) + g(n)
Exemplo
S(n) = cS(n− 1) + g(n)
S(n) = cn−1S(1) +
n�
i=2
cn−1g(i)
⇓
S(n) = 2S(n− 1)
c = 2 e g(n) = 0
⇒
S(n) = 2n−1S(1) +
n�
i=2
2n−10
= 2n−12 +
n�
i=2
0 = 2n−12 + 0 = 2n
Métodos para resolver relações de recorrência
Método Passos
 “Expandir, 
conjecturar e 
verificar”
1.Expandir a recorrência até que seja possível 
inferir um padrão;
2.Determinar o padrão para k = n-1;
3.Demonstrar a fórmula resultante por indução.
Solução Geral
1.Escrever a recorrência na forma
2.Substitua c, S(1) e g(n) na fórmula geral
3.Calcule o somatório para obter a fórmula final
S(n) = cn−1S(1) +
n�
i=2
cn−1g(i)
S(n) = cS(n− 1) + g(n)
Exemplo: Solução Geral
• Considere a seqüência T como definida a 
seguir:
‣ T(1) = 2
‣ T(n) = T(n-1) + n + 1
• Encontre a solução em forma fechada para 
a relação de recorrência, utilizando o 
método da solução geral.