Slide - Relações de Recorrência - 2022-1

Rela¸c˜oes de Recorrˆencia Jeroen van de Graaf DCC - UFMG T´opicos Rela¸c˜oes de Recorrˆencia (1) Indentificar e definir uma recorrˆencia (7.1) (2) Resolver recorrˆencias homogˆeneas (7.2) (3) Resolver recorrˆencias heterogˆeneas (7.2) (4) Resolver recorrˆencias tipo Divis˜ao e Conquista (7.3) Sequˆencias recursivas • Numa rela¸c˜ao de recorrˆencia para a sequˆencia {ai} o termo an ´e expressa em um ou mais termos pr´evios. • Exemplo: a sequˆencia definida por      d0 = 2; d1 = 5; dn = 5dn−1 − 6dn−2 tem f´ormula fechada dn = 2n + 3n • Fibonacci:      f0 = 0; f1 = 1; fn = fn−1 + fn−2 Seq¨uˆencias definidas recursivamente • Exemplo (Rosen 7.1.3) Juros compostos: — um valor de 10 000 reais ´e deposito numa poupan¸ca — taxa de 11 % ao ano — qual o valor depois de 30 anos? P1 = 1.11P0 P2 = 1.11P1 = 1.112P0 ... Pn = 1.11nP0 portanto P30 = 1.1130P0 = 228 922.97 Modelagem usando rela¸c˜ao de recorrˆencia Edouard Lucas (1842–1891), matem´atico francˆes. Propˆos o jogo “Torre de Hanoi” em 1883. Escreveu o trabalho de matem´atica recreativa R´ecr´eations Math´ematiques em quatro volumes (1882–94) que se tornou um cl´assico. Torre de Hanoi Exemplo (Rosen 7.1.5) • Objetivo: – Transferir toda a torre para uma das outras varetas, movendo um disco de cada vez, mas nunca movendo um disco maior sobre um menor. • Solu¸c˜oes particulares: – Seja Tn o n´umero m´ınimo de movimentos para transferir n discos de uma vareta para outra de acordo com as regras definidas no enunciado do problema. – N˜ao ´e dif´ıcil observar que: T0 = 0 [nenhum movimento ´e necess´ario] T1 = 1 [apenas um movimento] T2 = 3 [trˆes movimentos usando as duas varetas] Torre de Hanoi • Generaliza¸c˜ao da solu¸c˜ao: – Para trˆes discos, a solu¸c˜ao correta ´e transferir os dois discos do topo para a vareta do meio, transferir o terceiro disco para a outra vareta e, finalmente, mover os outros dois discos sobre o topo do terceiro. – Para n discos: 1. Transfere-se os n − 1 discos menores para outra vareta (por exemplo, a do meio), requerendo Tn−1 movimentos. 2. Transfere-se o disco maior para a outra vareta (um movimento). 3. Transfere-se os n − 1 discos menores para o topo do disco maior, requerendo-se Tn−1 movimentos novamente. Torre de Hanoi • rela¸c˜ao de recorrˆencia para este problema pode ser expressa por: T0 = 0 Tn = 2Tn−1 + 1, para n > 0 Torre de Hanoi Para pequenos valores de n temos: n 0 1 2 3 4 5 6 Tn 0 1 3 7 15 31 63 Esta sequˆencia pode ser expressa por Tn = 2n − 1. Torre de Hanoi Supondo que os monges troquem um disco por segundo, o universo vai acabar em 264 − 1 = 18 446 744 073 709 551 615 segundos, ou seja, em 18 446 744 073 709 551 615/(60 · 60 · 24 · 365) ≈ 584 942 417 355 anos. Estrat´egia para resolu¸c˜ao A recorrˆencia da Torre de Hanoi aparece em v´arias aplica¸c˜oes de todos os tipos. Normalmente, existem trˆes etapas para achar uma forma fechada para o valor de Tn: 1. Analisar pequenos casos. Com isto podemos ter um entendimento melhor do problema e, ao mesmo tempo, ajudar nos dois passos seguintes. 2. Achar e provar uma recorrˆencia para o valor de Tn. 3. Achar e provar uma forma fechada para a recorrˆencia. Linhas no plano Exemplo • Problema: – Qual ´e o n´umero m´aximo de regi˜oes Ln determinado por n retas no plano? ➜ Lembre-se que um plano sem nenhuma reta tem uma regi˜ao, com uma reta tem duas regi˜oes e com duas retas tˆem quatro regi˜oes. 4 1 2 1 L = 2 1 1 2 1 2 3 L = 4 0 L = Linhas no plano n Ln recorrˆencia 0 1 1 2 1 + 1 = L0 + 1 2 4 2 + 2 = L1 + 2 3 7 4 + 3 = L2 + 3 4 11 7 + 4 = L3 + 4 n Ln Ln−1 + n A sequência de Fibonacci FIBONACCI NUMBERS Leonardo of Pisa (ca. 1200) wondered how many pairs of rabbits would be produced in the nth generation, starting from a single pair and supposing that any pair of rabbits of one generation produces one pair of rabbits for the next generation and one for the generation after that, and then they die. FIGURE 4.22 A pair of rabbits and their progeny. FIGURE 4.23 Forming the Fibonacci numbers. A sequência de Fibonacci A sequˆencia de Fibonacci A sequˆencia de Fibonacci ´e dada pela recorrˆencia      f0 = 0; f1 = 1; fn = fn−1 + fn−2 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, · · · Curiosidade: ´E poss´ıvel provar que fn+1fn−1 − f 2 n = (−1)n A sequˆencia de Fibonacci Repare que calcular f (n) recursivamente d´a um desempenho horr´ıvel, porque nas chamdas recursivas h´a muitas repeti¸c˜oes: f (5) = f (4) + f (3) = (f (3) + f (2)) + f (3) = (f (2) + f (1)) + f (2)) + (f (2) + f (1)) = ((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1) = 5 Eliminar a recurs˜ao e calcular uma f´ormula fechada d´a um algoritmo mais eficiente. Uma f´ormula exata para Fibonacci A sequˆencia de Fibonacci ´e dada pela recorrˆencia      f0 = 0; f1 = 1; fn = fn−1 + fn−2 Uma f´ormula exata para a sequˆencia de Fibonacci ´e fn = 1 √ 5( 1+ √ 5 2 )n − 1 √ 5( 1− √ 5 2 )n = 1 √ 5φn − 1 √ 5ψn = 1 √ 5(1.61803398)n − 1 √ 5(−0.61803398)n Contando strings de tamanho n que n˜ao contˆem 00 Exemplo (Rosen 7.1.6) Determine quantos strings bin´arios de tamanho 0, 1, 2, 3...n n˜ao cont´em o substring 00 (dois 0s consecutivos) Tamanho: Strings # Strings 0: ε a0 = 1 1: 0, 1 a1 = 2 2: 01, 10, 11 a2 = 3 3: 010, 011, 101, 110, 111 a3 = 5 Contando strings de tamanho n que não contêm 00 Defina a_n como o número de strings binários de tamanho n não contém o substring 00. Então a_{n-1} = # strings de tamanho n-1 que não contém 00; etc. Contando strings de tamanho n que não contêm 00 Defina a_n como o número de strings binários de tamanho n não contêm o substring 00. Então a_{n-1} = # strings de tamanho n-1 que não contêm 00; etc. Dois casos a considerar: ► String termina em 1 Acrescentando um 1 não muda a propriedade de ter dois 0s consecutivos: b_1 . . . b_{n-1} 1 #=a_{n-1} A contribuição a a_n neste caso é de a_{n-1}; Contando strings de tamanho n que não contêm 00 Defina a_n como o número de strings binários de tamanho n não contêm o substring 00. Então a_{n-1} = # strings de tamanho n-1 que não contêm 00; etc. Dois casos a considerar: ► String termina em 1 Acrescentando um 1 não muda a propriedade de ter dois 0s consecutivos: b_1 . . . b_{n-1} 1 #=a_{n-1} A contribuição a a_n neste caso é de a_{n-1}; ► String termina em 0 Os dois últimos símbolos não podem ser 00, portanto na verdade o string termina em 10. b_1 . . . b_{n-1} 10 #=a_{n-2} Os primeiros n-2 símbolos podem ser qualquer string que não ten dois 0s consecutivos.. Portanto, a contribuição a a_n neste caso é de a_{n-2} Contando strings de tamanho n que não contêm 00 Os dois casos geram dois subconjuntos mutuamente disjuntos, representados pela primeira relação de recorrência abaixo: (1) a_n = a_{n-1} + a_{n-2} relação de recorrência (2) a_0 = 1 a_1 = 2 Condições iniciais Contando strings de tamanho n que não contêm 00 Os dois casos geram dois subconjuntos mutuamente disjuntos, representados pela primeira relação de recorrência abaixo: (1) \quad a_n = a_{n-1} + a_{n-2} \quad \text{relação de recorrência} (2) \quad a_0 = 1 \quad a_1 = 2 \quad \text{Condições iniciais} Então Fibonacci, mas partindo de 1 (e não de 0). Contando c´odigos decimais com n´umero par de 0s ▶ Consideramos c´odigos decimais d1 . . . dn, i.e. c´odigos cujos s´ımbolos s˜ao d´ıgitos. Queremos calcular an, o n´umero de c´odigos de tamanho n que tˆem um n´umero par de 0s (NPZ) ▶ Para n = 1 temos que a1 = 9 j´a que d1 = 1,2,3,4,5,6,7,8 ou 9 tem NPZ (zero ´e um n´umero par). ▶ Para n > 1 qualquer, vamos considerar o ´ultimo d´ıgito, dn. Consideramos dois casos: 1. dn ̸= 0 2. dn = 0 Contando c´odigos decimais com n´umero par de 0s ▶ Consideramos c´odigos decimais d1 . . . dn, i.e. c´odigos cujos s´ımbolos s˜ao d´ıgitos. Queremos calcular an, o n´umero de c´odigos de tamanho n que tˆem um n´umero par de 0s (NPZ) ▶ Para n = 1 temos que a1 = 9 j´a que d1 = 1,2,3,4,5,6,7,8 ou 9 tem NPZ (zero ´e um n´umero par). ▶ Para n > 1 qualquer, vamos considerar o ´ultimo d´ıgito, dn. Consideramos dois casos: 1. dn ̸= 0 2. dn = 0 Contando c´odigos decimais com n´umero par de 0s ▶ Consideramos c´odigos decimais d1 . . . dn, i.e. c´odigos cujos s´ımbolos s˜ao d´ıgitos. Queremos calcular an, o n´umero de c´odigos de tamanho n que tˆem um n´umero par de 0s (NPZ) ▶ Para n = 1 temos que a1 = 9 j´a que d1 = 1,2,3,4,5,6,7,8 ou 9 tem NPZ (zero ´e um n´umero par). ▶ Para n > 1 qualquer, vamos considerar o ´ultimo d´ıgito, dn. Consideramos dois casos: 1. dn ̸= 0 2. dn = 0 Contando códigos decimais com número par de 0s 1. Se d_n = 1, temos a seguinte situação: d_1 \ldots d_{n-1} 1 \underbrace{\phantom{d_1 \ldots d_{n-1} }}_{a_{n-1}} Então se d_1 \ldots d_{n-1} tem NPZ então d_1 \ldots d_{n-1} 1 tem NPZ. Ou seja, a contribuição a a_n por códigos terminando em 1 é a_{n-1}. Mesmo raciocínio para códigos terminando em 2, 3, 4, 5, 6, 7, 8, 9. Então a contribuição total neste caso é 9 \cdot a_{n-1}. 2. Se d_1 \ldots d_n termina em 0, então d_1 \ldots d_{n-1} não tem NPZ. d_1 \ldots d_{n-1} 0 \underbrace{\phantom{d_1 \ldots d_{n-1} }}_{a_{n-1}^c} Pelo Princípio do Complemento, quantidade de códigos ímpares = total menos quantidade NPZ, então a_{n-1}^c = 10^{n-1} - a_{n-1}. Contando códigos decimais com número par de 0s 1. Se d_n = 1, temos a seguinte situação: d_1 \ldots d_{n-1} 1 \underbrace{\phantom{d_1 \ldots d_{n-1} }}_{a_{n-1}} Então se d_1 \ldots d_{n-1} tem NPZ então d_1 \ldots d_{n-1} 1 tem NPZ. Ou seja, a contribuição a a_n por códigos terminando em 1 é a_{n-1}. Mesmo raciocínio para códigos terminando em 2, 3, 4, 5, 6, 7, 8, 9. Então a contribuição total neste caso é 9 \cdot a_{n-1}. 2. Se d_1 \ldots d_n termina em 0, então d_1 \ldots d_{n-1} não tem NPZ. d_1 \ldots d_{n-1} 0 \underbrace{\phantom{d_1 \ldots d_{n-1} }}_{a_{n-1}^c} Pelo Princípio do Complemento, quantidade de códigos ímpares = total menos quantidade NPZ, então a_{n-1}^c = 10^{n-1} - a_{n-1}. Portanto, a recorrência obtida é a_n = 9a_{n-1} + (10^{n-1} - a_{n-1}) = 8a_{n-1} + 10^{n-1} T´opicos Rela¸c˜oes de Recorrˆencia (1) Indentificar e definir uma recorrˆencia (2) Resolver recorrˆencias homogˆeneas (3) Resolver recorrˆencias heterogˆeneas (4) Resolver recorrˆencias tipo Divis˜ao e Conquista Classificar rela¸c˜oes de recorrˆencia lineares • (Rosen Exemplo 7.2.1) As seguintes RdR s˜ao lineares, homogˆeneas, com coeficientes constantes, de grau 1, 2 e 5, respectivamente: Pn = (1.11)Pn−1 fn = fn−1 + fn−2 an = an−5 • Forma geral: an = c1an−1 + c2an−2 + . . . ckan−k • (Rosen Exemplo 7.2.2) an = an−1 + a2 n−2 n˜ao ´e linear Tn = 2Tn−1 + 1 n˜ao ´e homogˆenea Bn = nBn−1 n˜ao tem coeficientes constantes Verificar uma solução de uma relações de recorrência lineares Método Substituir a solução candidata na equação e verificar se é verdadeira ou falsa. • (Rosen Exemplo 7.1.2) Considere \[a_n = 2a_{n-1} - a_{n-2}\] Verifica-se \[ a_n = 3n \text{ é uma solução, porque } 3n = 2(3(n-1)) - 3(n-2) = 6n - 6 - 3n + 6 \] \[ a_n = 2^n \text{ não é uma solução porque } 2^n \neq 2 \cdot 2^{n-1} - 2^{n-2} \] \[ a_n = 5 \text{ é uma solução porque } 5 = 2 \cdot 5 - 5 \] Linear Se \(a_n^{(1)}\) e \(a_n^{(2)}\) são soluções, então qualquer combinação linear \(\alpha_1 a_n^{(1)} + \alpha_2 a_n^{(2)}\) também é uma solução. Os valores dos \(\alpha\)'s são determinados pelas condições iniciais. M´etodo para encontrar todas as solu¸c˜oes de uma RdR linear heterogˆenea de grau 2 Estrat´egia geral Os exemplos (juros compostos, Fibonacci) mostram que, em geral, as solu¸c˜oes s˜ao do tipo an = xn, o que justifica o M´etodo a seguir. Passo 1: Substitua an → xn; an−1 → xn−1 etc. Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x2 + · · · = 0 Passo 3: Determine as ra´ızes caracter´ısticas r1, r2, · · · . Passo 4: Se as ra´ızes s˜ao distintas, a equa¸c˜ao an = α1r n 1 + α2r n 2 representa todas as poss´ıveis solu¸c˜oes. Passo 5: Use as condi¸c˜oes iniciais para calcular α1 e α2 e reescreva a solu¸c˜ao Passo 6: Verifique a solu¸c˜ao. Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.3) Considere an = an−1 + 2an−2 com a0 = 2 e a1 = 7. Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = xn−1 + 2xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 2 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.3) Considere an = an−1 + 2an−2 com a0 = 2 e a1 = 7. Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = xn−1 + 2xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 2 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.3) Considere an = an−1 + 2an−2 com a0 = 2 e a1 = 7. Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = xn−1 + 2xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 2 = 0 Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − x − 2 = 0 ⇒ (x − 2)(x + 1) = 0 ⇒ r = 2 ∨ r = −1 . Passo 4: Agora a equa¸c˜ao an = α12n + α2(−1)n representa todas as poss´ıveis solu¸c˜oes. Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − x − 2 = 0 ⇒ (x − 2)(x + 1) = 0 ⇒ r = 2 ∨ r = −1 . Passo 4: Agora a equa¸c˜ao an = α12n + α2(−1)n representa todas as poss´ıveis solu¸c˜oes. Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \(\alpha_1\) e \(\alpha_2\) e reescreva a solução: \[ \begin{cases} a_0 = 2 = \alpha_1 2^0 + \alpha_2 (-1)^0 = \alpha_1 + \alpha_2 \\ a_1 = 7 = \alpha_1 2^1 + \alpha_2 (-1)^1 = 2\alpha_1 - \alpha_2 \end{cases} \] então \(\alpha_1 = 3; \alpha_2 = -1\) portanto obtemos \[a_n = 3 \cdot 2^n - (-1)^n\] Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \(\alpha_1\) e \(\alpha_2\) e reescreva a solução: \[ \begin{cases} a_0 = 2 = \alpha_1 2^0 + \alpha_2 (-1)^0 = \alpha_1 + \alpha_2 \\ a_1 = 7 = \alpha_1 2^1 + \alpha_2 (-1)^1 = 2\alpha_1 - \alpha_2 \end{cases} \] então \(\alpha_1 = 3; \alpha_2 = -1\) portanto obtemos \[a_n = 3 \cdot 2^n - (-1)^n\] Passo 6: Verifique a solução para um \(n\) diferente: para \(n = 2\) a nova fórmula dá \[ a_2 = 3 \cdot 2^2 - (-1)^2 = 12 - 1 = 11 \] enquanto a recorrência original também dá \[ a_2 = a_1 + 2 \cdot a_0 = 7 + 2 \cdot 2 = 11 \] Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.4 – Fibonacci) Considere fn = fn−1 + fn−2 com f0 = 0 e f1 = 1. Passo 1: Substitua an → xn; an−1 → xn−1 etc. x2 = x + 1 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 1 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.4 – Fibonacci) Considere fn = fn−1 + fn−2 com f0 = 0 e f1 = 1. Passo 1: Substitua an → xn; an−1 → xn−1 etc. x2 = x + 1 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 1 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.4 – Fibonacci) Considere fn = fn−1 + fn−2 com f0 = 0 e f1 = 1. Passo 1: Substitua an → xn; an−1 → xn−1 etc. x2 = x + 1 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica: x2 − x − 1 = 0 Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − x − 1 = 0 Baskara d´a r1,2 = −b ± √ b2 − 4ac 2a = 1 ± √1 − 4 · 1 · −1 2 = 1 ± √ 5 2 Passo 4: Agora a equa¸c˜ao fn = α1(1 + √ 5 2 )n + α2(1 − √ 5 2 )n representa todas as poss´ıveis solu¸c˜oes. Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − x − 1 = 0 Baskara d´a r1,2 = −b ± √ b2 − 4ac 2a = 1 ± √1 − 4 · 1 · −1 2 = 1 ± √ 5 2 Passo 4: Agora a equa¸c˜ao fn = α1(1 + √ 5 2 )n + α2(1 − √ 5 2 )n representa todas as poss´ıveis solu¸c˜oes. Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \( \alpha_1 \) e \( \alpha_2 \) e reescreva a solução: \[ \begin{cases} f_0 = 1 = \alpha_1 + \alpha_2 \\ f_1 = \alpha_1 \left(\frac{1+\sqrt{5}}{2}\right) + \alpha_2 \left(\frac{1-\sqrt{5}}{2}\right) \end{cases} \] então \( \alpha_1 = \frac{1}{\sqrt{5}} ; \alpha_2 = -\frac{1}{\sqrt{5}} \) portanto obtemos \[ f_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \] Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \( \alpha_1 \) e \( \alpha_2 \) e reescreva a solução: \[ \begin{cases} f_0 = 1 = \alpha_1 + \alpha_2 \\ f_1 = \alpha_1 \left(\frac{1+\sqrt{5}}{2}\right) + \alpha_2 \left(\frac{1-\sqrt{5}}{2}\right) \end{cases} \] então \( \alpha_1 = \frac{1}{\sqrt{5}} ; \alpha_2 = -\frac{1}{\sqrt{5}} \) portanto obtemos \[ f_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \] Passo 6: Verifique a solução para um \( n \) diferente: para \( n = 2 \) a nova fórmula dá \[ a_2 = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^2 - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^2 \] \[ = \frac{1}{4\sqrt{5}}(1 + 5 + 2\sqrt{5} - (1 + 5 - 2\sqrt{5})) \] \[ = \frac{1}{4\sqrt{5}}(4\sqrt{5}) \] \[ = 1 \] enquanto a recorrência original também dá \[ f_2 = f_1 + f_0 = 1 + 0 = 1 \] Resolver rela¸c˜oes de recorrˆencia lineares M´etodo para encontrar todas as solu¸c˜oes de uma RdR linear homogˆenea de grau 2: (1) Substitua an → xn; an−1 → xn−1 etc. (2) Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x2 + · · · = 0 (3) Determine as ra´ızes caracter´ısticas r1, r2, · · · . (4) Se existe apenas uma ra´ız r com multiplicidade dois, a equa¸c˜ao an = α1r n + α2nr n representa todas as poss´ıveis solu¸c˜oes. (5) Use as condi¸c˜oes iniciais para calcular α1 e α2 e reescreva a solu¸c˜ao (6) Recomendado: verifique a solu¸c˜ao. Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.5) Considere an = 6an−1 − 9an−2 com a0 = 1 e a1 = 6 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 9xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x2 − 6x + 9 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.5) Considere an = 6an−1 − 9an−2 com a0 = 1 e a1 = 6 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 9xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x2 − 6x + 9 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.5) Considere an = 6an−1 − 9an−2 com a0 = 1 e a1 = 6 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 9xn−2 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x2 − 6x + 9 = 0 Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − 6x + 9 = (x − 3)2 = 0 ⇒ r = 3 com multiplicidade k = 2. Passo 4: A equa¸c˜ao an = α13n + α2n3n representa todas as poss´ıveis solu¸c˜oes. Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x2 − 6x + 9 = (x − 3)2 = 0 ⇒ r = 3 com multiplicidade k = 2. Passo 4: A equa¸c˜ao an = α13n + α2n3n representa todas as poss´ıveis solu¸c˜oes. Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \( \alpha_1 \) e \( \alpha_2 \) e reescreva a solução: \[ \begin{cases} a_0 = 1 = \alpha_1 \\ a_1 = 6 = \alpha_1 \cdot 3^1 + 1 \cdot \alpha_2 \cdot 3^1 \end{cases} \] então \( \alpha_1 = 1 ; \alpha_2 = 1 \) portanto obtemos \[ a_n = 3^n + n 3^n \] Resolver relações de recorrência lineares Passo 5: Use as condições iniciais para calcular \( \alpha_1 \) e \( \alpha_2 \) e reescreva a solução: \[ \begin{cases} a_0 = 1 = \alpha_1 \\ a_1 = 6 = \alpha_1 \cdot 3^1 + 1 \cdot \alpha_2 \cdot 3^1 \end{cases} \] então \( \alpha_1 = 1; \alpha_2 = 1 \) portanto obtemos \[ a_n = 3^n + n3^n \] Passo 6: Verifique a solução para um \( n \) diferente: para \( n = 2 \) a nova fórmula dá \[ a_2 = 3^2 + 2 \cdot 3^2 = 9 + 18 = 27 \] enquanto a recorrência original dá \[ a_2 = 6a_1 - 9a_0 = 6 \cdot 6 - 9 \cdot 1 = 36 - 9 = 27 \] Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.6) Considere an = 6an−1 − 11an−2 + 6an−3 com a0 = 2 e a1 = 5 e a2 − 15 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 11xn−2 + 6n−3 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x3 − 6x2 + 11x − 6 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.6) Considere an = 6an−1 − 11an−2 + 6an−3 com a0 = 2 e a1 = 5 e a2 − 15 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 11xn−2 + 6n−3 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x3 − 6x2 + 11x − 6 = 0 Resolver rela¸c˜oes de recorrˆencia lineares (Rosen Exemplo 7.2.6) Considere an = 6an−1 − 11an−2 + 6an−3 com a0 = 2 e a1 = 5 e a2 − 15 Passo 1: Substitua an → xn; an−1 → xn−1 etc. xn = 6xn−1 − 11xn−2 + 6n−3 Passo 2: Divida pela menor potˆencia de x e determine a equa¸c˜ao caracter´ıstica x3 − 6x2 + 11x − 6 = 0 Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x3 − 6x2 + 11x − 6 = (x − 1)(x − 2)(x − 3) = 0 ⇒ r = 1 ∨ r = 2 ∨ r = 3 com multiplicidade k = 2. Passo 4: A equa¸c˜ao an = α11n + α22n + α33n representa todas as poss´ıveis solu¸c˜oes. Resolver rela¸c˜oes de recorrˆencia lineares Passo 3: Determine as ra´ızes caracter´ısticas r1, r2. x3 − 6x2 + 11x − 6 = (x − 1)(x − 2)(x − 3) = 0 ⇒ r = 1 ∨ r = 2 ∨ r = 3 com multiplicidade k = 2. Passo 4: A equa¸c˜ao an = α11n + α22n + α33n representa todas as poss´ıveis solu¸c˜oes. Resolver rela¸c˜oes de recorrˆencia lineares Passo 5: Use as condi¸c˜oes iniciais para calcular α1, α2 e α3      a0 = 2 = α1 + α2 + α3 a1 = 5 = α1 + α2 · 2 + α3 · 3 a2 = 15 = α1 + α2 · 4 + α3 · 9 donde deduzimos que α1 = 1, α2 = −1, α3 = 2. Reescreva a solu¸c˜ao: an = 1n − 2n + 2 · 3n Passo 6: Verifique a solu¸c˜ao para um n diferente: para n = 3 a nova f´ormula d´a a3 = 13 − 23 + 2 · 33 = 47 enquanto a recorrˆencia original d´a a3 = 6a2 − 11a1 + 6a0 = 6 · 15 − 11 · 5 + 6 · 2 = 90 − 55 + 12 = 47 Resolver rela¸c˜oes de recorrˆencia lineares Passo 5: Use as condi¸c˜oes iniciais para calcular α1, α2 e α3      a0 = 2 = α1 + α2 + α3 a1 = 5 = α1 + α2 · 2 + α3 · 3 a2 = 15 = α1 + α2 · 4 + α3 · 9 donde deduzimos que α1 = 1, α2 = −1, α3 = 2. Reescreva a solu¸c˜ao: an = 1n − 2n + 2 · 3n Passo 6: Verifique a solu¸c˜ao para um n diferente: para n = 3 a nova f´ormula d´a a3 = 13 − 23 + 2 · 33 = 47 enquanto a recorrˆencia original d´a a3 = 6a2 − 11a1 + 6a0 = 6 · 15 − 11 · 5 + 6 · 2 = 90 − 55 + 12 = 47 Resolver rela¸c˜oes de recorrˆencia lineares RESUMO ▶ Uma ra´ız r com multiplicidade 1: an = α1r n ▶ Uma ra´ız r com multiplicidade 2: an = α1r n + α2nr n ▶ Uma ra´ız r com multiplicidade 3: an = α1r n + α2nr n + α3n2r n ▶ Uma ra´ız r com multiplicidade 4: an = α1r n + α2nr n + α3n2r n + α4n3r n ▶ Ra´ızes distintas com multiplicidades: somar estas solu¸c˜oes. T´opicos Rela¸c˜oes de Recorrˆencia (1) Indentificar e definir uma recorrˆencia (2) Resolver recorrˆencias homogˆeneas (3) Resolver recorrˆencias heterogˆeneas (4) Resolver recorrˆencias tipo Divis˜ao e Conquista Resolver relações de recorrência lineares heterogêneas MÉTODO: \[ a_n = \underbrace{c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_n a_{n-k}}_{\text{parte homogênea}} + \underbrace{F(n)}_{\text{função de apenas } n} \] 1. Resolva a parte homogênea; chame a solução \( a_n^{(hom)} \) Resolver relações de recorrência lineares heterogêneas MÉTODO: \[ a_n = \underbrace{c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_n a_{n-k}}_{\text{parte homogênea}} + \underbrace{F(n)}_{\text{função de apenas } n} \] 1. Resolva a parte homogênea; chame a solução \( a_n^{(hom)} \) 2. Encontre uma solução particular da RdR heterogênea, usando os seguintes heurísticas: - Se \( F(n) \) é um polinômio de grau 1, 2, 3, define \( a_n^{(part)} = A + Bn + Cn^2 + Dn^3 \) e encontre \( A, B, C, D. \) Resolver relações de recorrência lineares heterogêneas MÉTODO: an = c1an−1 + c2an−2 + · · · + cnan−k + parte homogênea F(n) função de apenas n 1. Resolva a parte homogênea; chame a solução an(hom) 2. Encontre uma solução particular da RdR heterogênea, usando os seguintes heurísticas: ▶ Se F(n) é um polinômio de grau 1, 2, 3, define an(part) = A + Bn + Cn2 + Dn3 e encontre A, B, C, D. ▶ Se F(n) = βn, define an(part) = Cβn e encontre C. Resolver relações de recorrência lineares heterogêneas MÉTODO: an = c1an−1 + c2an−2 + · · · + cnan−k + parte homogênea F(n) função de apenas n 1. Resolva a parte homogênea; chame a solução an(hom) 2. Encontre uma solução particular da RdR heterogênea, usando os seguintes heurísticas: ▶ Se F(n) é um polinômio de grau 1, 2, 3, define an(part) = A + Bn + Cn2 + Dn3 e encontre A, B, C, D. ▶ Se F(n) = βn, define an(part) = Cβn e encontre C. 3. A solução total é a soma das duas partes: an(het) = an(hom) + an(part) Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.10) Considere an = 3an−1 + 2n com a1 = 3 Parte homogˆenea A parte hom. da recorrˆencia ´e an = 3an−1 que tem solu¸c˜ao a(hom) n = α3n Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.10) Considere an = 3an−1 + 2n com a1 = 3 Parte homogˆenea A parte hom. da recorrˆencia ´e an = 3an−1 que tem solu¸c˜ao a(hom) n = α3n Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.9) Considere an = 3an−1 + 2n com a1 = 3 Solu¸c˜ao particular Dado que a parte n˜ao hom. F(n) = 2n, ´e um polinˆomio de grau 1, chutamos p(n) = cn + d e resolvemos para achar c, d: an = 3an−1 + 2n =⇒ cn + d = 3(c(n − 1) + d) + 2n =⇒ cn + d = 3cn − 3c + 3d + 2n =⇒ 2cn − 3c + 2d + 2n = 0 =⇒ (2c + 2)n + 2d − 3c = 0 ent˜ao c = −1, d = −3/2 Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.9) Considere an = 3an−1 + 2n com a1 = 3 Solu¸c˜ao heterogˆenea a(het) n = a(hom) n + a(part) n ent˜ao a(het) n = α3n − n − 3 2 Para determinar α, substituimos agora a condi¸c˜ao inicial: a1 = 3 = α · 31 − (1) − 3/2 donde segue que α = 11 6 . Solu¸c˜ao total A solu¸c˜ao procurada ´e portanto an = 11 6 · 3n − n − 3 2 Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.11) Considere an = 5an−1 − 6an−2 + 7n Parte homogˆenea A parte hom. da recorrˆencia ´e an = 5an−1 − 6an−2 que tem solu¸c˜ao a(hom) n = α13n + α22n Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.11) Considere an = 5an−1 − 6an−2 + 7n Parte homogˆenea A parte hom. da recorrˆencia ´e an = 5an−1 − 6an−2 que tem solu¸c˜ao a(hom) n = α13n + α22n Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.11) Considere an = 5an−1 − 6an−2 + 7n Solu¸c˜ao particular Dado que a parte n˜ao hom. F(n) = 7n, ´e uma fun¸c˜ao exponencial, chutamos p(n) = C · 7n e resolvemos para achar C: an = 5an−1 − 6an−2 + 7n =⇒ C · 7n = 5C · 7n−1 − 6C · 7n−2 + 7n =⇒ 49C · 7n−2 = 35C · 7n−2 − 6C · 7n−2 + 49 · 7n−2 =⇒ 49C = 35C − 6C + 49 ent˜ao C = 49 20. Resolver rela¸c˜oes de recorrˆencia lineares heterogˆeneas (Rosen Exemplo 7.2.9) Considere an = 5an−1 − 6an−2 + 7n Solu¸c˜ao heterogˆenea a(het) n = a(hom) n + a(part) n ent˜ao a(het) n = α13n + α22n + 49 20 · 7n N˜ao h´a condi¸c˜ao inicial dado, ent˜ao essa tb ´e a solu¸c˜ao final. T´opicos Rela¸c˜oes de Recorrˆencia (1) Indentificar e definir uma recorrˆencia (2) Resolver recorrˆencias homogˆeneas (3) Resolver recorrˆencias heterogˆeneas (4) Resolver recorrˆencias tipo Divis˜ao e Conquista Divis˜ao e Conquista Divis˜ao e Conquista ´e uma estrat´egia recursiva de se resolver um problema computacional: (a) Divide a instˆancia em partes (b) Chame o algoritmo recursivamente (c) Combine os resultados parciais para obter o resultado geral Exemplos (Rosen 7.3.1–5): problema computacional complexidade busca bin´aria f (n) = f (n/2) + 2 m´aximo/m´ınimo de uma sequˆencia f (n) = f (n/2) + 2 merge sort M(n) = 2M(n/2) + n multiplica¸c˜ao r´apida de inteiros f (2n) = 3f (n) + Cn multiplica¸c˜ao r´apida de matrizes f (2n) = 7f (n) + 15n2/4 Algumas recorrências básicas: Caso 1 f(n) = f(n/2) + 1 (n ≥ 2) f(1) = 0 (n = 1) Vamos supor que: n = 2^k ⟷ k = lg n Resolvendo por expansão temos: f(2^k) = f(2^(k−1)) + 1 = (f(2^(k−2)) + 1) + 1 = (f(2^(k−3)) + 1) + 1 + 1 ⋮ = (f(2) + 1) + 1 + · · · + 1 = (f(1) + 1) + 1 + · · · + 1 = 0 + 1 + · · · + 1 k = k f(n) = lg n Algumas recorrˆencias b´asicas: Caso 2 f (n) (1) = 2f ( n 2 ) + n (n ≥ 2) f (1) (2) = 0 (n = 1) Vamos supor que n = 2k ↔ k = lg n. Resolvendo por expans˜ao temos: f (2k) (1) = 2f (2k−1) + 2k (1) = 2(2f (2k−2) + 2k−1) + 2k = 22f (2k−2) + 2 · 2k (1) = 22(2f (2k−3) + 2k−2) + 2 · 2k = 23f (2k−3) + 3 · 2k ... ... (1) = 2kf (2k−k) + k · 2k = 2kf (1) + k · 2k (2) = 2k · 0 + k · 2k = k · 2k ent˜ao f (n) = lg n · n = n lg n Mudança de variável Exemplo (BB 4.7.10) Considere a recorrência T(n) = {1 if n = 1 3T(n/2) + n if n é uma potência de 2 Mudança de variável Exemplo (BB 4.7.10) Considere a recorrência T(n) = {1 if n = 1 3T(n/2) + n if n é uma potência de 2 Para resolver vamos substituir n = 2^k ⟷ k = lg n, definindo uma nova variável, t_k = T(2^k) Isso é util porque n/2 se torna 2^k/2 = 2^{k-1}. Mudança de variável Exemplo (BB 4.7.10) Considere a recorrência T(n) = {1 if n = 1 3T(n/2) + n if n é uma potência de 2 Para resolver vamos substituir n = 2^k ⟷ k = lg n, definindo uma nova variável, t_k = T(2^k) Isso é util porque n/2 se torna 2^k/2 = 2^{k-1}. Portanto obtemos T(2^k) = 3T(2^{k-1}) + 2^k ⟷ t_k = 3t_{k-1} + 2^k ⟷ t_k - 3t_{k-1} - 2^k = 0 Mudan¸ca de vari´avel A recorrˆencia tk − 3tk−1 − 2k = 0 tem r1 = 3 como raiz da parte homogˆenea e r2 = 2 como solu¸c˜ao particular ent˜ao tk = α13k + α22k. Substituindo tk = T(2k) de volta obtemos T(n) = α13lg n + α22lg n = α1nlg 3 + α2n Sabendo que T(1) = 1 e T(2) = 3T(1) + 2 = 5, obtemos as equa¸c˜oes α1 + α2 = 1 (n = 1) 3α1 + 2α2 = 5 (n = 2) e podemos resolver α1 = 3; α2 = −2 Mudan¸ca de vari´avel A recorrˆencia tk − 3tk−1 − 2k = 0 tem r1 = 3 como raiz da parte homogˆenea e r2 = 2 como solu¸c˜ao particular ent˜ao tk = α13k + α22k. Substituindo tk = T(2k) de volta obtemos T(n) = α13lg n + α22lg n = α1nlg 3 + α2n Sabendo que T(1) = 1 e T(2) = 3T(1) + 2 = 5, obtemos as equa¸c˜oes α1 + α2 = 1 (n = 1) 3α1 + 2α2 = 5 (n = 2) e podemos resolver α1 = 3; α2 = −2 Mudan¸ca de vari´avel A recorrˆencia tk − 3tk−1 − 2k = 0 tem r1 = 3 como raiz da parte homogˆenea e r2 = 2 como solu¸c˜ao particular ent˜ao tk = α13k + α22k. Substituindo tk = T(2k) de volta obtemos T(n) = α13lg n + α22lg n = α1nlg 3 + α2n Sabendo que T(1) = 1 e T(2) = 3T(1) + 2 = 5, obtemos as equa¸c˜oes α1 + α2 = 1 (n = 1) 3α1 + 2α2 = 5 (n = 2) e podemos resolver α1 = 3; α2 = −2 Teorema Mestre Recorrˆencias da forma f (n) = af ( n b ) + g(n), onde a ≥ 1 e b > 1 s˜ao constantes e f (n) ´e uma fun¸c˜ao assintoticamente positiva podem ser resolvidas usando o Teorema Mestre. Note que neste caso n˜ao estamos achando a forma fechada da recorrˆencia mas sim seu comportamento assint´otico. Teorema Mestre Recorrˆencias da forma f (n) = af ( n b ) + g(n), onde a ≥ 1 e b > 1 s˜ao constantes e f (n) ´e uma fun¸c˜ao assintoticamente positiva podem ser resolvidas usando o Teorema Mestre. Note que neste caso n˜ao estamos achando a forma fechada da recorrˆencia mas sim seu comportamento assint´otico. Teorema 7.3.1 (a) Seja f uma fun¸c˜ao crescente que satisfaz: f (n) = af ( n b ) + c sempre que n ´e divis´ıvel por b onde a ≥ 1, c > 0 s˜ao reais e b ≥ 2 ´e um inteiro. Ent˜ao f (n) ∈    O(log n) se a = 1 O(nlogb a) se a > 1 (b) Ainda, quando n = bk podemos encontrar a solu¸c˜ao exata f (n) = C1nlogb a + C2 com C1 = f (1) + c/(a − 1) e C2 = −c/(a − 1) Teorema 7.3.1 (a) Seja f uma fun¸c˜ao crescente que satisfaz: f (n) = af ( n b ) + c sempre que n ´e divis´ıvel por b onde a ≥ 1, c > 0 s˜ao reais e b ≥ 2 ´e um inteiro. Ent˜ao f (n) ∈    O(log n) se a = 1 O(nlogb a) se a > 1 (b) Ainda, quando n = bk podemos encontrar a solu¸c˜ao exata f (n) = C1nlogb a + C2 com C1 = f (1) + c/(a − 1) e C2 = −c/(a − 1) Teorema 7.3.1 Exemplo (Rosen 7.3.6) Considere f (n) = 5f (n/2) + 3 com f (1) = 7 Estime f se for uma fun¸c˜ao crescente. Solu¸c˜ao Usando o Teorema com a = 5, b = 2, c = 3 vemos que, se n = bk, ent˜ao f (n) = C1nlogb a + C2 = C1bk·logb a + C2 = (f (1) + c/(a − 1)) · ak + (−c/(a − 1)) = (7 + 3/4) · 5k − 3/4 Teorema 7.3.1 Exemplo (Rosen 7.3.6) Considere f (n) = 5f (n/2) + 3 com f (1) = 7 Estime f se for uma fun¸c˜ao crescente. Solu¸c˜ao Usando o Teorema com a = 5, b = 2, c = 3 vemos que, se n = bk, ent˜ao f (n) = C1nlogb a + C2 = C1bk·logb a + C2 = (f (1) + c/(a − 1)) · ak + (−c/(a − 1)) = (7 + 3/4) · 5k − 3/4 Teorema 7.3.1 Exemplo (Rosen 7.3.7) A complexidade da busca bin´aria ´e f (n) = f (n/2) + 2 Estime f , que ´e uma fun¸c˜ao crescente. Solu¸c˜ao Usando o Teorema com a = 1, b = 2, c = 2, obtemos que f (n) ∈ O(n) j´a que a = 1. Teorema 7.3.1 Exemplo (Rosen 7.3.7) A complexidade da busca bin´aria ´e f (n) = f (n/2) + 2 Estime f , que ´e uma fun¸c˜ao crescente. Solu¸c˜ao Usando o Teorema com a = 1, b = 2, c = 2, obtemos que f (n) ∈ O(n) j´a que a = 1. Teorema Mestre (7.3.2) Seja f uma fun¸c˜ao crescente que satisfaz: f (n) = af ( n b ) + cnd sempre que n = bk, onde k ≥ 1, b ≥ 2 s˜ao inteiros e a ≥ 1, c > 0, d ≥ 0 s˜ao reais. Ent˜ao f (n) ´e            O(nd) se a < bd O(nd log n) se a = bd O(nlogb a) se a > bd Teorema Mestre (7.3.2) Exemplo (Rosen 7.3.9) A complexidade de Merge Sort ´e menor que M(n) onde M(n) = 2M(n/2) + n Estime M. Solu¸c˜ao Usando o Teorema com a = 2, b = 2, c = 1, d = 1, obtemos que M(n) ∈ O(n log n) Teorema Mestre (7.3.2) Exemplo (Rosen 7.3.9) A complexidade de Merge Sort ´e menor que M(n) onde M(n) = 2M(n/2) + n Estime M. Solu¸c˜ao Usando o Teorema com a = 2, b = 2, c = 1, d = 1, obtemos que M(n) ∈ O(n log n) Teorema Mestre (7.3.2) Exemplo (Rosen 7.3.10) A complexidade da multiplica¸c˜ao r´apida de inteiros ´e f (n) = 3f (n/2) + Cn Estime M. Solu¸c˜ao Usando o Teorema com a = 3, b = 2, c = C, d = 1, obtemos que f (n) ∈ O(nlog2 3) = O(nlg 3) ≈ O(n1.585) ⊊ O(n2) Teorema Mestre (7.3.2) Exemplo (Rosen 7.3.10) A complexidade da multiplica¸c˜ao r´apida de inteiros ´e f (n) = 3f (n/2) + Cn Estime M. Solu¸c˜ao Usando o Teorema com a = 3, b = 2, c = C, d = 1, obtemos que f (n) ∈ O(nlog2 3) = O(nlg 3) ≈ O(n1.585) ⊊ O(n2)