Mat Disc Parte06

Prévia do material em texto

1
Universidade Federal do Vale do São Francisco
Curso de Engenharia da Computação
Prof. Jorge Cavalcanti
jorge.cavalcanti@univasf.edu.br
www.univasf.edu.br/~jorge.cavalcanti
www.twitter.com/jorgecav
Matemática Discreta - 06
2
Recursividade e relações de recorrência
3
Definições Recorrentes
 Uma definição onde o item a ser definido aparece como 
parte da definição é chamada de definição recorrente ou 
definição por recorrência ou ainda definição por 
indução.
 Como definir algo em torno de si mesmo?
1. Uma base, ou condição básica, onde alguns casos simples
(pelo menos um) do item que está sendo definido são dados
explicitamente.
2. Um passo de indução ou recorrência, onde novos casos do
item que está sendo definido são dados em função dos casos
anteriores.
 O item 1 nos dá o começo, fornecendo casos simples e 
concretos.
 O item 2 nos permite construir novos casos, a partir dos 
simples e ainda outros casos a partir desses novos e assim 
por diante.
Recursividade e Relações de Recorrência
4
Sequências definidas por Recorrência
 Uma sequência S é uma lista de objetos que 
são numerados em uma determinada ordem.
 Existe um primeiro objeto, um segundo e 
assim por diante.
 S(k) denota o k-ésimo objeto da sequência.
 Uma sequência é definida por recorrência 
nomeando-se o primeiro valor (ou alguns 
primeiros) na sequência e depois definindo os 
demais valores subsequentes em termos dos 
valores anteriores.
Recursividade e Relações de Recorrência
5
Sequências definidas por Recorrência
 Ex. 01:A seqüência S é definida por recorrência por
1.S(1) = 2
2.S(n) = 2S(n -1) para n  2
Pela proposição 1, S(1) = 2. Depois, pela proposição 2, o 
segundo objeto em S é S(2) = 2S(1) = 2(2)=4.
Novamente, pela proposição 2, S(3)=2S(2) = 2(4) = 8.
Continuando desse modo, vemos que a sequência S é:
2, 4, 8, 16, 32...
 Uma regra como a da proposição 2, que define um 
valor de uma sequência em termos de um ou mais 
valores anteriores é uma relação de recorrência.
Recursividade e Relações de Recorrência
6
Sequências definidas por Recorrência
 Ex. 02:A seqüência T é definida por recorrência por
1.T(1) = 1
2.T(n) = T(n -1) + 3 para n  2
 Escreva os cinco primeiros valores da sequência T.
 Ex. 03: A famosa sequência de Fibonacci é uma 
sequência de números definida por recorrência por:
F(1) = 1
F(2) = 1
F(n) = F(n-2) + F(n-1), para n>2
 Nesse caso, são dados os dois primeiros valores e relação 
de recorrência define o n-ésimo valor em termos dos dois 
valores precedentes.
 Na sua forma mais geral, a relação de recorrência é a 
soma de F em seus dois valores anteriores.
 Ex. 04: Escreva os oito primeiros valores da sequência 
de Fibonacci.
Recursividade e Relações de Recorrência
7
Sequências definidas por Recorrência
 Ex. 05: Prove diretamente que, na sequência de 
Fibonacci, a fórmula F(n+4)=3F(n+2) – F(n), para todo n 
 1, é verdadeira.
A relação de recorrência da sequência de Fibonacci pode 
ser escrita como: F(n+2)=F(n)+F(n+1) ou,
F(n+1) = F(n+2) – F(n) (1)
Logo, F(n+4)=F(n+2)+F(n+3)
F(n+4)=F(n+2)+F(n+2)+F(n+1) //Reescrevendo F(n+3)
F(n+4)=F(n+2)+ F(n+2)+[F(n+2)-F(n)] // de (1)
F(n+4)=3F(n+2)-F(n)
Recursividade e Relações de Recorrência
8
Sequências definidas por Recorrência
 Ex. 06: Prove diretamente que, na sequência de 
Fibonacci, a fórmula F(n+1)+F(n-2) = 2F(n), para todo n 
 3, é verdadeira.
Da relação de Recorrência:
F(n+1)=F(n-1) + F(n) e
F(n)=F(n-1)+F(n-2) 
= F(n-1)+F(n) + F(n-2) = [F(n-1)+F(n-2)] + F(n)
=F(n)+ F(n) = 2F(n)
Observar que só é válida porque n  3. 
Recursividade e Relações de Recorrência
9
Sequências definidas por Recorrência
 Ex. 07: Prove diretamente que, na sequência de 
Fibonacci, a fórmula F(n+3)=2F(n+1) + F(n), para todo n 
 1, é verdadeira.
Recursividade e Relações de Recorrência
10
Operações definidas por Recorrência
 Certas operações comuns em objetos podem ser 
definidas de forma recorrente, conforme os exemplos 
a seguir:
 Ex. 08: Uma definição recorrente da operação de 
exponenciação an de um número real não nulo a, onde 
n é um inteiro não negativo é: 
1. a0=1
2. an=(an-1)a para n1
 Ex. 09: Uma definição recorrente para a multiplicação 
de dois inteiros positivos m e n é:
1. m(1) = m
2. m(n) = m(n-1) + m para n2
Recursividade e Relações de Recorrência
11
Resolvendo Relações de Recorrência
 Tomando por base novamente o Exemplo 01
 Ex.01: A seqüência S é definida por recorrência por
 S(1) = 2 (1)
 S(n) = 2S(n -1) para n  2 (2)
 Como:
S(1) = 2 = 21
S(2) = 4 = 22
S(3) = 8 = 23
S(4) = 16 = 24
e assim por diante, vemos que
S(n) = 2n (3)
 É possível calcular diretamente S(n) sem ter que 
calcular explicitamente ou por recorrência.
Recursividade e Relações de Recorrência
Solução em 
forma fechada 
para a relação de 
recorrência (2) 
sujeita à condição 
básica (1)
12
Resolvendo Relações de Recorrência
 Relações de recorrência são usadas em programas 
computacionais, estudos de decaimento químico, 
crescimento populacional etc.
 Seria bom encontrar sempre soluções fechadas!
 Uma técnica para resolver relações de recorrência é 
uma abordagem do tipo “expandir, conjecturar e 
verificar”.
 Essa técnica usa repetidamente a relação de recorrência 
para expandir a expressão a partir do n-ésimo termo até 
que se tenha uma idéia da forma geral.
 Após obtida a forma geral, a conjectura é provada por 
indução matemática.
Recursividade e Relações de Recorrência
13
Resolvendo Relações de Recorrência
 Ex. 10: Considere novamente a seqüência S 
 S(1) = 2 (1)
 S(n) = 2S(n -1) para n  2 (2)
 Desconsiderando que já sabemos a solução fechada, 
vamos usar a abordagem de expandir, conjecturar e 
verificar para encontrar a solução.
 A relação S(n) = 2S(n -1) estabelece que um elemento S 
pode ser substituído por duas vezes o elemento anterior.
 Seguindo essa receita, expandimos para n, n-1, n-2, assim 
por diante:
 S(n) = 2S(n -1)
 = 2[2S(n -2)] = 22S(n-2)
 = 22[2S(n-3)] = 23S(n-3)
 Olhando o padrão que está se formando, conjecturamos 
que, após k expansões, a equação tem a forma:
S(n) = 2kS(n-k)
Recursividade e Relações de Recorrência
14
Resolvendo Relações de Recorrência
 Ex. 10: Forma geral da expansão:
S(n) = 2kS(n-k)
 A expansão dos elementos de S em função dos 
elementos anteriores pára quando n-k=1 (significa que 
estamos com o último e o penúltimo elemento da 
relação).
 n-k =1 então, k=n-1 e nesse ponto temos:
 S(n) = 2n-1S[n-(n-1)] = 2n-1S(1)
 2n-1(2) = 2n que é a solução em forma fechada
 A solução encontrada é apenas a conjectura, que 
precisa ser confirmada, ou seja devemos provar que 
S(n)=2n para n 1.
 Provaremos usando a indução matemática.
Recursividade e Relações de Recorrência
15
Resolvendo Relações de Recorrência
 Ex. 10: Provar que S(n) = 2n para n 1.
1. Base da indução S(1) = 21 é verdadeiro
2. Hipótese da indução S(k) = 2k
3. Devemos provar que S(k+1) = 2k+1
S(k+1) = 2S(k)
S(k+1) =2(2k)
S(k+1) =2k+1 – Isso prova que a solução fechada 
encontrada está correta.
Recursividade e Relações de Recorrência