Aula 5 - Recorrência

Prévia do material em texto

Recorrência
Prof. Diego Brandão
Centro Federal de Educação Tecnológica Celso Suckow da Fonceca (CEFET/RJ)
Departamento Acadêmico de Informática (DEPIN)
11 de Abril de 2019
Diego Brandão (CEFET/RJ) Matemática Discreta 1 / 30
Roteiro
1 Sequências
2 Somatórios
3 Produtórios
4 Relações de recorrência
Diego Brandão (CEFET/RJ) Matemática Discreta 2 / 30
Sequências
Sequência
Uma sequência S é uma lista ordenada de elementos (objetos, eventos, etc.):
S = S(1), S(2), ..., S(n), S(n + 1), ...
onde S(k), k ≥ 1, denota o k-ésimo elemento de S.
Exemplo: S = 2, 4, 8, 16, 32, ...
Sequências são estruturas matemáticas importantes no estudo de algoritmos,
particularmente em estruturas de repetições e recursão.
Diego Brandão (CEFET/RJ) Matemática Discreta 3 / 30
Sequências - terminologia
Terminologia relevante relativa a sequências:
Termo: cada elemento de uma sequência.
Exemplo: a1, a2, a3, . . . , an.
Índice ou subscrito: indica a posição do termo na seqüência.
Exemplo: O número 3 no termo a3 indica o terceiro elemento da sequência.
Seqüência finita: possui um conjunto finito de termos.
Seqüência infinita: possui um conjunto infinito de termos.
Fórmula explícita ou fórmula geral: é a regra que mostra como os valores de ak
podem ser obtidos a partir de k.
Diego Brandão (CEFET/RJ) Matemática Discreta 4 / 30
Sequência - exemplo
Seja a sequência infinita a1, a2, a3, . . . definida pela fórmula explícita a seguir:
ak =
k
k + 1
, k ≥ 1.
Os três primeiros termos dessa sequência podem ser calculados da seguinte forma:
a1 =
1
1 + 1
=
1
2
a2 =
2
2 + 1
=
2
3
a3 =
3
3 + 1
=
3
4
Diego Brandão (CEFET/RJ) Matemática Discreta 5 / 30
Sequência - exemplo
Seja a seqüência c0, c1, c2, . . . definida pela fórmula explícita
cj = (−1)j, para inteiros j ≥ 0
Esse é um exemplo de seqüência alternante, pois seus elementos oscilam dentro de
um conjunto finito de valores. No exemplo acima, esse conjunto de valores é {-1, 1}.
Diego Brandão (CEFET/RJ) Matemática Discreta 6 / 30
Sequência - exemplo
A fórmula explícita para a sequência
1,
−1
4
,
1
9
,
−1
16
,
1
25
, · · ·
pode ser
ak =
(−1)k+1
k2
, para inteiros k ≥ 1
ou
ak =
(−1)k
(k + 1)2
, para inteiros k ≥ 0
Em geral, não existe somente uma única fórmula explícita para representar os termos
de uma sequência.
Diego Brandão (CEFET/RJ) Matemática Discreta 7 / 30
Roteiro
1 Sequências
2 Somatórios
3 Produtórios
4 Relações de recorrência
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 30
Notação Big-sigma
A notação big-sigma usa a letra Grega Σ (Sigma) para denotar a soma de termos de
uma sequência de forma sucinta, por meio da especificação dos valores inicial e final
de um índice:
a1 + a2 + · · ·+ am =
m∑︁
j=1
aj
Diego Brandão (CEFET/RJ) Matemática Discreta 9 / 30
Somatórios - exemplos
3∑︁
i=1
i2 =
12 + 22 + 32 = 14
5∑︁
i=2
4i = 4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) = (2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
3∑︁
i=1
i2 = 12 + 22 + 32 = 14
5∑︁
i=2
4i = 4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) = (2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
3∑︁
i=1
i2 = 12 + 22 + 32 = 14
5∑︁
i=2
4i =
4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) = (2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
3∑︁
i=1
i2 = 12 + 22 + 32 = 14
5∑︁
i=2
4i = 4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) = (2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
3∑︁
i=1
i2 = 12 + 22 + 32 = 14
5∑︁
i=2
4i = 4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) =
(2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
3∑︁
i=1
i2 = 12 + 22 + 32 = 14
5∑︁
i=2
4i = 4 · 2 + 4 · 3 + 4 · 4 + 4 · 5 = 56
8∑︁
i=3
(2i−4) = (2·3−4)+(2·4−4)+(2·5−4)+(2·6−4)+(2·7−4)+(2·8−4) = 42
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 30
Somatórios - exemplos
1− 1
2
+
1
3
− 1
4
+ ... +
(−1)n
n + 1
=
n∑︁
k=0
(−1)k
k + 1
1
n
+
2
n + 1
+
3
n + 2
+ ... +
n + 1
2n
=
n∑︁
k=0
k + 1
n + k
1
1× 2 +
1
2× 3 +
1
3× 4 + . . . +
1
n× (n + 1) =
n∑︁
i=1
1
(i)(i + 1)
Diego Brandão (CEFET/RJ) Matemática Discreta 11 / 30
Somatórios - exemplos
Alguns somatórios possuem uma fórmula fechada. Alguns exemplos:
n∑︁
i=1
i =
n(n + 1)
2
n∑︁
i=1
i2 =
1
6
n(n + 1)(2n + 1)
∞∑︁
i=1
1
i2
=
𝜋2
6
n∑︁
k=1
(︂
k
k + 1
− k + 1
k + 2
)︂
=
1
2
− n + 1
n + 2
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 30
Somas telescópicas
Seja {ai} uma sequência de números. Então, em geral,
S =
n−1∑︁
i=1
(ai − ai+1)
= (a1 − a2) + (a2 − a3) + ... + (an−2 − an−1) + (an−1 − an)
= (a1 − an)
Por meio de uma simples mudança de variáveis, perceba que é também verdade que
N∑︁
n=1
(an − an−1) = aN − a0.
Esse tipo de soma, em que termos subsequentes se cancelam mutuamente, deixando
apenas o primeiro e o último termos, é denominada soma telescópica (telescoping
sum).
Diego Brandão (CEFET/RJ) Matemática Discreta 13 / 30
Somatórios e análise de algoritmos
Uma técnica de análise de algoritmos é baseada em somatórios. Por exemplo,
considere o programa a seguir:
1 int main()
2 {
3 for (int k=0; k < n; k++)
4 {
5 ip += u[k] * v[k];
6 }
7 return 0;
8 }
De forma simplista, podemos considerar que ip += u[k] * v[k] é uma única
operação. Sendo assim, a complexidade de tempo desse trecho de código é:
n−1∑︁
k=0
1 = n
Diego Brandão (CEFET/RJ) Matemática Discreta 14 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c =
cn
n∑︁
i=1
cxi = c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c = cn
n∑︁
i=1
cxi = c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c = cn
n∑︁
i=1
cxi =
c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c = cn
n∑︁
i=1
cxi = c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c = cn
n∑︁
i=1
cxi = c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Somatórios - algumas propriedades
n∑︁
i=1
c = cn
n∑︁
i=1
cxi = c
n∑︁
i=1
xi
n∑︁
i=1
(xi + yi) =
n∑︁
i=1
xi +
n∑︁
i=1
yi
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 30
Roteiro
1 Sequências
2 Somatórios
3 Produtórios
4 Relações de recorrência
Diego Brandão (CEFET/RJ) Matemática Discreta 16 / 30
Notação Big-pi
A notação big-pi usa a letra Grega Π (Pi) para denotar sucintamente o produto dos
termos de uma sequência, por meio da especificação dos valores inicial e final de um
índice:
a1 × a2 × · · · × am =
m∏︁
j=1
aj
Diego Brandão (CEFET/RJ) Matemática Discreta17 / 30
Produtórios - exemplos
3∏︁
y=0
(y− 1) = −1× 0× 1× 2
n∏︁
k=1
k2 ̸= 1
2
n(n + 1)
n∏︁
k=1
1
k
=
1
1
× 1
2
× . . .× 1
n
n∏︁
k=1
1
k2
=
1
1
× 1
4
× . . .× 1
n2
Diego Brandão (CEFET/RJ) Matemática Discreta 18 / 30
Produtórios - algumas propriedades
n∏︁
i=1
bi = b1 × b2 × b3 × . . .× bn
n∏︁
i=1
b = bn
n∏︁
i=1
cbi = cb1 × cb2 × cb3 × . . .× cbn = cn
n∏︁
i=1
bi
n∏︁
i=1
i = 1× 2× 3× . . .× n = n!
log
n∏︁
i=1
xi = log x1 + log x2 + log x3 + . . . + log xn =
n∑︁
i=1
log xi
n∏︁
i=1
xiyi = x1y1 · x2y2 · x3y3 · . . . · xnyn =
(︃
n∏︁
i=1
xi
)︃(︃
n∏︁
i=1
yi
)︃
Diego Brandão (CEFET/RJ) Matemática Discreta 19 / 30
Roteiro
1 Sequências
2 Somatórios
3 Produtórios
4 Relações de recorrência
Diego Brandão (CEFET/RJ) Matemática Discreta 20 / 30
Sequências recursivas
Sequência recursiva
Uma sequência recursiva é uma sequência definida por meio da apresentação
explícita de seu(s) primeiro(s) elemento(s) e da apresentação implícita dos demais
elementos em função dos elementos anteriores.
Por exemplo, a sequência
S = 2, 4, 8, 16, 32, ...
é recursiva pois podemos definí-la da seguinte forma:
1 S(1) = 2
2 S(n) = 2× S(n− 1), para n ≥ 2.
Uma regra como a número 2 acima, na qual se define um valor da seqüência a partir
de um ou mais valores anteriores, é chamada de relação de recorrência.
Diego Brandão (CEFET/RJ) Matemática Discreta 21 / 30
Relação de recorrência
Relação de recorrência
Uma relação de recorrência é aquela cuja definição faz referência a si própria. Para
que a relação recorrente esteja bem definida, isto é, a fim de sua definição não ser
circular, é preciso que satisfaça as seguintes propriedades:
1. Existem argumentos, ditos valores base, nos quais a relação não se refere a ela
mesma;
2. Cada vez que a relação se referir a si própria, o argumento da relação se
aproxima de um valor base.
A ordem de uma relação de recorrência é a diferença entre o maior e o menor
subscritos dos termos da sequência na equação.
Diego Brandão (CEFET/RJ) Matemática Discreta 22 / 30
Relação de recorrência - exemplos
Exemplo 1 - função fatorial
Na sequência produzida por esta função, o n-ésimo termo é igual ao termo anterior
vezes n.
n! =
{︂
1 se n = 0
n(n− 1)! se n > 0
Outra forma de definir a função é por maio de seu termo geral, Fn:
Fn = n× Fn−1
A condição inicial é F0 = 1.
Diego Brandão (CEFET/RJ) Matemática Discreta 23 / 30
Relação de recorrência - exemplos
Exemplo 1 - função fatorial
Na sequência produzida por esta função, o n-ésimo termo é igual ao termo anterior
vezes n.
n! =
{︂
1 se n = 0
n(n− 1)! se n > 0
Outra forma de definir a função é por maio de seu termo geral, Fn:
Fn = n× Fn−1
A condição inicial é F0 = 1.
Diego Brandão (CEFET/RJ) Matemática Discreta 23 / 30
Relação de recorrência - exemplos
Exemplo 2 - Sequência de Fibonacci
Fn =
{︂
n se n = 0 ou n = 1
Fn−1 + Fn−2 se n ∈ N− {0, 1}
Outra forma de definir a sequência de Fibonacci:
Fn = Fn−1 + Fn−2
ou
Fn − Fn−1 + Fn−2 = 0
As condições iniciais são F0 = 0,F1 = 1.
Diego Brandão (CEFET/RJ) Matemática Discreta 24 / 30
Relação de recorrência - exemplos
Exemplo 2 - Sequência de Fibonacci
Fn =
{︂
n se n = 0 ou n = 1
Fn−1 + Fn−2 se n ∈ N− {0, 1}
Outra forma de definir a sequência de Fibonacci:
Fn = Fn−1 + Fn−2
ou
Fn − Fn−1 + Fn−2 = 0
As condições iniciais são F0 = 0,F1 = 1.
Diego Brandão (CEFET/RJ) Matemática Discreta 24 / 30
Relação de recorrência - exemplos
Exemplo 3 - função de Ackermann
A função de Ackermann, definida para inteiros não negativos m e n, é
A(m, n) =
⎧⎪⎨⎪⎩
n + 1 se m = 0
A(m− 1, 1) se m > 0 e n = 0
A(m− 1,A(m, n− 1)) se m > 0 e n > 0.
Essa função cresce assustadoramente rápido. Por exemplo, A(1, 2) = 4, mas A(4, 2) é
um número tal que possui 19.729 dígitos!
Diego Brandão (CEFET/RJ) Matemática Discreta 25 / 30
Solução de uma relação de recorrência
Solução de uma relação de recorrência
Uma sequência é uma solução de uma relação de equivalência se seus termos
satisfazem a relação de recorrência. Uma relação de recorrência pode ter múltiplas
soluções, mas uma relação com condições iniciais possui apenas uma solução. Em
geral, resolver um relação de recorrência significa encontrar uma forma fechada para
o termo geral da sequência. Há duas estratégias para resolver uma relação de
recorrência (que não são aplicáveis a todos os casos):
Recursiva: usamos a expressão geral da relação de recorrência de maneira
“topdown” para diminuir os índices envolvidos até alcançarmos as condições
iniciais.
Iterativa: usamos a expressão geral da relação de recorrência de maneira
“building-up” para derivar mais e mais elementos da sequência, até que o
elemento correspondente ao índice desejado tenha sido alcançado.
Diego Brandão (CEFET/RJ) Matemática Discreta 26 / 30
Exemplo
1. Seja uma sequência {ai}i∈N determinada pela relação de recorrência
an = 3an−1 + 2an−2 (*)
e pelas condições iniciais
a0 = 1, a1 = 2 . (**)
Calcule a4 recursivamente.
Solução. Recursivamente, usamos (*) repetidamente (“topdown”) para diminuir os
índices envolvidos até que todos alcancem os das condições iniciais. Sendo assim
a4 = 3a3 + 2a2 usou (*) para n = 4
= 3(3a2 + 2a1) + 2a2 usou (*) para n = 3
= 11a2 + 6a1
= 11(3a1 + 2a0) + 6a1
= 39a1 + 22a0
= 39× 2 + 22× 1 = 100 . usou (**)
Diego Brandão (CEFET/RJ) Matemática Discreta 27 / 30
Exemplo
1. Seja uma sequência {ai}i∈N determinada pela relação de recorrência
an = 3an−1 + 2an−2 (*)
e pelas condições iniciais
a0 = 1, a1 = 2 . (**)
Calcule a4 recursivamente.
Solução. Recursivamente, usamos (*) repetidamente (“topdown”) para diminuir os
índices envolvidos até que todos alcancem os das condições iniciais. Sendo assim
a4 = 3a3 + 2a2 usou (*) para n = 4
= 3(3a2 + 2a1) + 2a2 usou (*) para n = 3
= 11a2 + 6a1
= 11(3a1 + 2a0) + 6a1
= 39a1 + 22a0
= 39× 2 + 22× 1 = 100 . usou (**)
Diego Brandão (CEFET/RJ) Matemática Discreta 27 / 30
Exemplo
2. Seja uma sequência {ai}i∈N determinada pela relação de recorrência
an = 3an−1 + 2an−2 (*)
e pelas condições iniciais
a0 = 1, a1 = 2 . (**)
Calcule a4 iterativamente.
Solução. Iterativamente, usamos (*) repetidamente (“building-up”) para derivar mais
e mais elementos até que o índice desejado tenha sido alcançado. Sendo assim
a0 = 1 ,
a1 = 2 ,
a2 = 3a1 + 2a0 = 8 ,
a3 = 3a2 + 2a1 = 28 , usou (*) para n = 3
a4 = 3a3 + 2a2 = 100 . usou (*) para n = 4
Diego Brandão (CEFET/RJ) Matemática Discreta 28 / 30
Exemplo
2. Seja uma sequência {ai}i∈N determinada pela relação de recorrência
an = 3an−1 + 2an−2 (*)
e pelas condições iniciais
a0 = 1, a1 = 2 . (**)
Calcule a4 iterativamente.
Solução. Iterativamente, usamos (*) repetidamente (“building-up”) para derivar mais
e mais elementos até que o índice desejado tenha sido alcançado. Sendo assim
a0 = 1 ,
a1 = 2 ,
a2 = 3a1 + 2a0 = 8 ,
a3 = 3a2 + 2a1 = 28 , usou (*) para n = 3
a4 = 3a3 + 2a2 = 100 . usou (*) para n = 4
Diego Brandão (CEFET/RJ) Matemática Discreta 28 / 30
Exemplo
3. Seja f (n) para n ∈ N dada pela relação de recorrência
f (n + 1) = 2 f (n), n ∈ N, n ≥ 1
f (1) = 1 (condição inicial).
Encontre a solução f (n).
Solução.
f (n + 1) = 2 · f (n)
= 2 · 2 · f (n− 1) = 22 · f (n− 1) =
= 22 · 2 · f (n− 2) = 23 f (n− 2)
= . . .
= 2k+1 · f (n− k)
Fazendo k = n− 1 na última expressão acima, temos:
f (n + 1) = 2(n−1)+1 f (n− (n− 1)) ⇔ f (n + 1) = 2n
Sendo assim, f (n) = 2n−1
Diego Brandão (CEFET/RJ) Matemática Discreta 29 / 30
Exemplo
3. Seja f (n) para n ∈ N dada pela relação de recorrência
f (n + 1) = 2 f (n), n ∈ N, n ≥ 1
f (1) = 1 (condição inicial).
Encontre a solução f (n).
Solução.
f (n +1) = 2 · f (n)
= 2 · 2 · f (n− 1) = 22 · f (n− 1) =
= 22 · 2 · f (n− 2) = 23 f (n− 2)
= . . .
= 2k+1 · f (n− k)
Fazendo k = n− 1 na última expressão acima, temos:
f (n + 1) = 2(n−1)+1 f (n− (n− 1)) ⇔ f (n + 1) = 2n
Sendo assim, f (n) = 2n−1
Diego Brandão (CEFET/RJ) Matemática Discreta 29 / 30
Exemplo
4. Seja f (n) para n ∈ N dada pela relação de recorrência
f (n) = n f (n− 1), n ∈ N, n ≥ 1
f (0) = 1 (condição inicial).
Encontre a solução f (n).
Solução. Aqui, podemos aplicar o método recursivo:
f (n) = n f (n− 1) se n ≥ 1
= n (n− 1) f (n− 2) se n ≥ 2
= n (n− 1) (n− 2) f (n− 3) se n ≥ 3
= . . .
= n (n− 1) (n− 2) · · · 2 · 1 · f (0)
= n! · f (0) = n! · 1 = n!
Sendo assim, f (n) = n!
Diego Brandão (CEFET/RJ) Matemática Discreta 30 / 30
Exemplo
4. Seja f (n) para n ∈ N dada pela relação de recorrência
f (n) = n f (n− 1), n ∈ N, n ≥ 1
f (0) = 1 (condição inicial).
Encontre a solução f (n).
Solução. Aqui, podemos aplicar o método recursivo:
f (n) = n f (n− 1) se n ≥ 1
= n (n− 1) f (n− 2) se n ≥ 2
= n (n− 1) (n− 2) f (n− 3) se n ≥ 3
= . . .
= n (n− 1) (n− 2) · · · 2 · 1 · f (0)
= n! · f (0) = n! · 1 = n!
Sendo assim, f (n) = n!
Diego Brandão (CEFET/RJ) Matemática Discreta 30 / 30
	Sequências
	Somatórios
	Produtórios
	Relações de recorrência