Conceito
Em muitos problemas de recorrência, é útil “expandir” a relação até observar o padrão que surge ao longo das iterações. A ideia é abrir a recorrência mantendo os termos para enxergar como a expressão evolui com o passo de iteração (n, n-1, n-2, ...).
Exemplo 1 – Gerações
Observação prática
Para chegar à forma fechada, muitas vezes é suficiente expandir até o passo-base (quando k = n-1, por exemplo) e então concluir pela indução. Em exercícios de prova, use a técnica “supõe e verifique” para demonstrar a forma fechada escolhida.
Exemplo 2 – Recorrência linear de primeira ordem
2.1 Recorrência de primeira ordem com coeficientes constantes
Forma geral: T_n = C · T_{n-1} + G(n), com C constante e G(n) função dada (G(n) = 0 para homogênea).
Exemplos rápidos
2.2 Recorrência de segunda ordem com coeficientes constantes (hiper/ não homogênea)
Forma geral (homogênea): T_n = a · T_{n-1} + b · T_{n-2}, com coeficientes constantes a, b.
Forma fechada envolve raízes r1 e r2 da equação característica: r^2 − a r − b = 0. Se r1 ≠ r2, a solução é T_n = α · r1^n + β · r2^n, onde α e β são determinados pelas condições iniciais. Se houver repetição de raízes, usa-se uma forma ajustada com n · r^n.
Exemplo rápido
2.3 Recorrência de segunda ordem com não-homogênea (coef. constantes)
Nesse caso, a solução é a soma da solução homogênea com uma solução particular que depende de g(n). A dedução formal envolve métodos padrão (variação de parâmetros, ou ansatz). O livro traz a expressão fechada completa, com o par de raízes e parâmetros determinados pelas condições iniciais.
Observação: a ideia-chave é transformar a recorrência em uma forma cuja solução depende de raízes de um polinômio característico e de termos de particular para o componente não-homogêneo.
Relação típica: T(n) = a · T(n/b) + g(n), com n>1, t. inicial T(1)=constante. A ideia é comparar o custo total ao longo da árvore de recursão para obter a forma fechada (ou a ordem assintótica).
Como usar a abordagem da aula
Exemplo comentado da aula
Resumo rápido da ideia
Divide o problema, resolve subproblemas, e combina resultados com um custo adicional g(n). A forma fechada nasce do balanço entre o número de folhas da árvore de recursão e o custo de fusão em cada nível.
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.
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.
Resposta correta: A) Θ(n log n)
Justificativa: para T(n) = 2 T(n/2) + n, pelo Teorema Mestre, a solução é Θ(n log n).
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.
A LUNAS e ALUNOS do curso de Fundamentos Matemáticos para a Computação.
Neste vídeo aula, eu vou continuar abordando relações de reconhecia.
Mesquas, a gente vai estar vendo dentro das relações de reconhecia, a obtenção de fórmulas fechadas.
Para isso vou começar pela técnica quando isso cominhe verifique.
Em seguida, nós já vamos trabalhar com fórmulas disponíveis para obter essa solução.
E nesse contexto, nós lembramos aqui que já tinha visto essa questão da fórmula fechada, por exemplo, aqui nesse caso das gerações.
Nós tinha um inferido que a relação de reconhecia poderia ser representada por uma fórmula fechada do tipo 2 elevado a ele.
Só que para essa relação de reconhecia, só que para a gente poder provar que essa forma fechada é válida para essa relação de reconhecia, nós tinha um esquilo inferido essa forma fechada de alguma maneira considerando problema e depois demonstrar isso por indução.
Nós vamos de certa forma continuar seguindo esse espaço.
Só que nós vamos fazer isso de uma maneira mais bem estabelecida.
E aí, entrou dentro do abordagem do tipo expanda suponho e verifique.
No caso, nós vamos basicamente expandir a relação de reconhecia até chegar numa expressão que a gente pode supor com a forma fechada para aquela relação.
E em seguida verificar a validade dela por indução.
Bom, então, novamente vamos pegar esse caso aqui que nós já conhecemos, que é o da gerações.
Quando nós expandimos, vamos começar pela expansão.
O que significa expandir? A gente abre essa expressão mais mantendo os termos.
Por que mantendo os termos? Para que a gente possa ver qual resultado que está se apresentando.
Então, por exemplo, quando eu expando o SN1 para duas vezes SN2, que seguindo a regra da relação de reconhecia, eu estou vendo que estou acumulando um quadrado, 2 ao quadrado.
Quando eu faço isso novamente para a N igual to N minus 3, eu já chego numa expressão com 2 elevado ao cú.
E assim sucessivamente, o que me leva a inferir que quando eu retiro um número, um número aqui do N, eu estou tendo esse número representado na potência, ou seja, para N minus k, eu vou ter 2 elevado a k.
Bom, só que isso aqui é uma conjectura que nem a gente tinha feito antes naquele gravo, dizendo que é 2 elevado a N.
Para eu chegar na forma fechada, o que eu faço? Eu vou conseguir expandir esse termo que no máximo até S1.
Que nesse caso seria representado por um valor k igual a N minus 1.
Repare que se eu fizer N minus N minus 1, eu vou obter S1.
Então, eu posso expandir isso aqui até chegar ao passo base, com muito toda a relação de reconhecia.
Nesse caso, então, eu vou continuar se eu fizer a substituição da expressão que eu estou inferindo para k.
Por N minus 1 no lugar do k, eu vou chegar nesse termo 2 elevado a N, que nós já tinha visto naquele desenho.
Agora, então, suponho vale 2 elevado a N para N, maior ou igual a 1.
E o que vai acontecer? Eu vou suponhu isso verificar e assim verificar por indução considerando que esse Sn é uma relação de reconhecia que segue esta rega, essas regas.
Bom, então, nesse caso, eu começo para N igual a 1, eu verifico que usando essa forma, eu obteno o valor inicial da minha relação de reconhecia, que é 2, perfeito.
Agora, eu suponho vale do para N igual a k.
Então, nesse caso, eu vou ter vale do para N igual a k, a expressão que eu estou supondo, e vou provar para k mais 1.
E agora, eu posso usar tanto a relação de reconhecia com uma hipótese de indução para provar para N igual a k mais 1.
Usando a relação de reconhecia, eu sei que Sk mais 1 é 2 vezes Sk.
E pela hipótese de indução Sk, eu consigo escrever com 2 elevado a k, o que me leva 2 elevado a k mais 1 logo, a minha forma é Sn vale, ela é, pode ser representada a minha relação de reconhecia Sn, pode ser representada pela forma fechada 2 elevado a N para N, maior ou igual a 1, provei isso por lição.
Agora, vamos pegar uma outra expressão, essa forma fechada para ter 1 igual a 1, tem 1 igual a tn, menos 1, mais 3 para a N, maior ou igual a 2.
Nesse caso, quando eu vou expandir a mesma coisa, eu vou expandir mantendo os ternos de modo que eu possa perceber, a expressão está se desenhando.
Então, nesse caso, eu recomendo sempre fazer por passos, mas é por etapas bem escritas, já não vai direto ao termo, eu não sei que você já tem essa cada expressão, vai expandindo, e aí os poucos você vai vendo uma relação entre o valor que você está se obtraindo e esse ter um que está sobrando aqui.
Então, observe que eu vou tendo aqui 9, quando foi 3, 12, quando foi 4, 6, quando foi 2, o que me leva a inferir o que, que para tn, menos 2, eu estou obtendo para a expansão aqui relacionada ao tn, menos 1, mais 3, quando eu faço a próxima expansão para 2, eu vou ter tn, menos 2, mais 2 vezes 3.
No caso seguinte, eu tenho tn, menos 3, mais 3 vezes 3, e n, menos 4, 4 vezes 3.
Então, eu estou sempre mantendo aquele 3 multiplicando pelas vezes que eu estou fazendo a recorção, vezes eu estou andando a recorção.
Então, eu tenho uma chamada recorcida, então eu tenho que eu posso inferir que para tn, menos k, eu vou ter k vezes 3.
Só que, nesse caso, eu preciso agora, depois de ter feito as k expansões que me apresentaram, uma possível fórmula, eu fecho ela com n igual a k, a k igual a n, menos 1, para chegar no passo base.
Então, eu sempre espando até o passo base.
Nesse caso, para k igual a n, menos 1, eu vou ter tn aqui o que me leva pela expansão que eu estou obtendo, uma expressão do tipo, eu vou ter aqui n, menos 1, mais n, menos 1 vezes 3, jogando n, menos 1 no lugar do k.
Fazendo as contas, eu observe, então, que eu estou chegando na expressão, que é 3n, menos 2.
Bom, vamos supor essa expressão como verdadeira, para n, maior que 0, n, maior e igual 1.
Então, no caso agora, eu já tenho em condições de supor.
Então, eu vou supor que o meu tn é igual a 3n, menos 2, para n, maior que 0.
Nesse caso, para verificar, vamos aplicar a indução, sabendo que tende, segue, a relação de recorrência, e aí eu tenho que para n igual 1, meu tn vai valer pela expressão, um, o que bate com o passo base dessa relação t.
Para n igual a k, eu supo em verdadeira, eu me hipótese de indução.
Agora, para n igual a k, mais 1, vamos provar.
Eu vou ter que ter para n igual a k, mais 1, vai ser igual a tk, mais 3.
Eu estou usando o mesmo cada expansão, mas é que só, para uma questão de manter coerência, como eu já havia explicado de indução.
Para n igual a k, mais 1, eu vou ter essa expressão pela relação de recorrência.
Pela hipótese de indução, eu sei que o meu tk é 3k, menos 2.
Mais 3.
Isso aqui me leva a 3k, mais 1, que não é bem que eu queria.
Eu queria 3 vezes k mais 1, menos 2.
Como é que eu vou chegar nisso? Bom, o que é 1? Eu posso simplesmente usar uma abordagem mais agressiva.
Eu quero que apareça 3, aqui, para eu põe evidência e obter k mais 1.
Então, eu soumo 3 e subtale 3.
Não, eu derei a igualdade.
Então, eu trouco que bem simples, que aí você somando 3 e retirando 3, o que vai acontecer? Coloco 3 em evidência e menos 3.
Mais 1 vai me dar o 2, que eu queria.
Você pode bolar uma outra maneira de fazer isso, desde que você obedeça a igualdade aqui.
Então, eu preciso somar isso de 3, 3.
Não até a igualdade.
Isso aqui continua válido na sequência da demonstração, chegando na tese que eu queria, que era provar essa expressão para k mais 1.
3k mais 1, menos 2.
Bom, só aqui, não necessariamente você precisa resolver, só usando a espada de suponha e verifique.
Se o exercício pedir na prova, uma atividade, para usar a espada de suponha e verifique, utiliza.
Mas em alguns casos, pode cair aberto do tipo usar uma fórmula para a solução.
Então, a relação de reconhecia, a gente consegue inferir algumas fórmulas para ela, no caso, por exemplo, da relação de reconhecia linear.
Mas a gente tem algumas condições.
Uma relação de reconhecia linear, numa relação de reconhecia linear, os valores anteriores na definição estão na primeira potência.
Ou seja, eu tenho que todos os valores que aparecem nessa relação, eu percebo que a n, menos 2, n, menos 1, não está nada em função de uma divisão, que está no tempo quadrado ou algo do tipo.
O que está além disso, se eu falar que essa relação de reconhecia linear, que pode ser de expressa com coeficientes que estão em função de n, se eu sequ esse coeficiente, são constantes tipo A, B, C, são valores constantes, eu tenho uma relação de reconhecia com coeficientes constantes.
Eu vou dizer que uma relação de reconhecia, ela é de primeira ordem, quando ela recorre apenas a n, menos 1, não teria o n, menos 2, o n, menos calho, e assim sucessivamente.
E eu besseado que a gente ainda tem esse termo genn, que eu não comentei.
Bom, considerando, então, uma relação de reconhecia linear de primeira ordem com coeficientes constantes, que é essa expressão, nós vamos dizer que ela é homogênia, quando GDN vale zero para todo o n, quando GDN não tem essa, a gente não tem essa expressão de GDN zero.
E aí ela recaim essa expressão com coeficientes constantes de primeira ordem.
Bom, uma fórmula para a relação de reconhecia linear, de primeira ordem homogênia ou um n, segue essa expressão.
A dedução dessa expressão está no livro, eu não vou apresentá-la aqui por uma questão de tempo, infelizmente.
Então vamos ver como usar essa fórmula para facilitar nossa vida.
Então você não precisa expandir isso, pode verificar.
Você precisa lembrar da fórmula e usar ela.
Bom, nessa fórmula eu tenho, nessa relação de reconhecia eu tenho coeficientes constantes 2, e GN vale zero.
Ela é homogênia.
Isso significa que dentro dessa expressão aqui, que a minha fórmula fechada para essa relação de reconhecia, eu tenho o meu C vale 2, ele fica elevado a n de menos 1, o meu S1.
Mas o somatório de 2 até n de C elevado a n, menos 1, que eu acabei não colocando aqui o 2.
Para destacar o GN que vale zero.
Então, observe que na verdade, independente do valor, esse somatório virou zero.
E aquela nossa fórmula fechada da geração, ela é obtida facilmente através dessa expressão.
Vamos pegar outra que tinha o Tn menos 1 mais 3.
A mesma coisa, o meu C vale 1, só que aqui o meu GN é uma função constante valendo 3.
Nesse caso, quando eu substituo na fórmula, eu vou ter o meu 1 elevado a n menos 1, que vai dar o próprio 1, aqui dentro também do somatório, um elevado a n menos 1 no somatório, vai dar 1.
E eu tenho 3 sendo somado de 2 até n.
Então, aqui fora eu vou ter 1 vezes o T1, que é 1.
E aqui dentro do somatório é fácil, você nem precisa demonstrar isso, tem aqui que esse somatório eu dou somando 3 várias vezes, na verdade, de 2 até n, significa que eu sou meio 3, n menos 1, vezes.
Então, eu tenho 3 vezes n menos 1.
É o resultado desse somatório.
Eu uso isso aqui, não preciso demonstrar isso.
E eu chego na expressão 3n menos 2, que nós obtivemos antes pelo método espaldo, isso está em verifique.
Uma relação de recorrença lineal de segunda ordem com coeficientes constantes, ela vai ter mais esse termo, mais uma constante para esse termo.
Então, você tem 1n menos 2, porque é de segunda ordem com coeficientes constantes.
E nesse caso, aqui nós estamos assumindo ela como homogênia.
A gente não tem homogênia.
Tudo bem? O livro foi deduzida a expressão, nesse caso, da seguinte forma.
Eu recomendo novamente você desolhar e eu não vou apresentar por uma questão de tempo a dedução disso aqui.
E nós também vamos focar apenas no uso.
Dado que essa é a formula fechada, como que essa é a formula fechada? Bom, r e r2 são raízes de unico ação composta por ter ao quadrado menos, o segundo coeficiente aqui é o a e o último coeficiente independente é o b.
Então, eu tenho o quadrado menos a ter menos b.
Vou resolver essa equação para obter as raízes que vão aparecer na forma fechada.
O peio que eles devem satisfazer esse sistema linear aqui.
Então, eu tenho que resolver esse sistema linear para obter os valores de peio, que vão compor aqui essa forma fechada.
Onde eu uso esse uni, esse 2, que vão existir como passo base, já que eu tenho uma relação de reconhecimento de segunda hora.
Então, isso está em plícito que eu vou ter dois valores iniciais.
Bom, dessa forma, usando esta forma fechada, vamos começar com um exemplo.
Eu tenho essa relação aqui.
Eu vou colocar o ave, eu tenho o ave, o b, o ave, o b, o ave, o 3.
Eu vou rejumar o monto a minha equação de segundo grau.
Resolvo elas raízes vão dar 3 e menos 1.
Com a parte agora para a resolução do sistema, com p mais que igual a s1, que vale 3, e p vezes r1, mais que vezes r2, igual a 1, que é o s2.
Resolvendo esse sistema, eu tenho p igual a 1 e k igual a 2.
Agora, é substituído nessa forma fechada.
Então, nesse caso, o que eu vou ter? Vou ter 3 elevado a n menos 1, menos 1 elevado a n menos 1, o peio, que é aqui.
Certo? O que me leva a essa expressãozinha, como forma a fechada para essa relação de reconhecimento de segunda hora com 800 constantes homogéneos? Bom, por último, nós vamos ver a relação de reconhecimento e dividir para conquistar.
Por que a gente está vendo estas formas fechadas? Vamos aparecer principalmente essa, em algoritmos que resolvem problemas com a bordagem de dividir e conquistar.
O que é essa bordade? Você tem um conjunto de dados e você é particionando ele.
Você está dividindo ele em subconjunto para resolver partes menores.
Então, você divida o problema em fatias, porque até você chegar a uma fatia básica que você já tem uma solução privil, e aí vai com ponto, reconponto.
O que é uma reconhecimento? Nesse caso, essas relações vão ser representadas desse jeito aqui.
Voltamos até o nosso gênero, nesse caso, não estamos considerando homogénea.
Então, nesse caso aqui, nós vamos.
.
.
Eu vou deduzir a expressão para vocês, porque nós vamos ver esse tipo de expressão em análise de algoritmos.
Então, acho que essa dedução é melhor que eu explique para vocês.
Por exemplo, aqui, na expressão, geralmente, nesses problemas de dividir para conquistar, você tem a entrada, a espécie.
.
.
A som de como hipótese que é a entrada seria 2 elevado a N.
É representada por uma grandeza, 2 elevado a N.
Isso possibilita essa divisão aqui, o que é uma hipótese razoável.
Então, nesse caso, com essa hipótese, eu posso substituir o meu N por 2 elevado a N.
Isso me leva em chegar a essa expressão como um TN, já que aqui tem função de N, aqui também.
Se a fia aqui é um g de N, só que eu estou deixando nessa forma 2 elevado a N para a gente não esquecer.
Isso me leva a uma relação que é de coeficiente constante de primeira ordem, que nós temos uma forma fechada, já deduzida.
Nós podemos usar ela.
Só que quando nós usamos ela, nós precisamos lembrar que, na verdade, primeiro, tem a melhor bintido em função do anterior com.
.
.
Resultando nessa expressão aqui.
Nessa forma, esse ct0, ele vem para cá.
Ele vem para cá.
Quando eu substitu esse termo por esse, que eu crononto fazendo aqui, na questão de tempo, eu vou ter o C multiplicando esse C, que me leva a C elevado a N.
E os g2 entra no somatório, fazendo esse somatório agora, começar de um ganha mais um termo.
Dessa forma, eu posso agora repare que a expressão ainda está em função de N.
Agora eu vou voltar para o N.
Nesse caso, eu faço que eu sei que N é igual a 2 elevado a N, ou seja, o meu N é logo de N na base 2.
Substituir em do N por log de N, eu tenho essa expressão, que 2 elevado a 0 aqui vai dar 1.
Então, eu tenho essa expressão.
Então, nós temos uma forma fechada para essa expressão, o que vai nos ajudar.
.
.
Para esse caso, de divisão e conquista.
Então, por exemplo, nessa relação de reconhecia, eu tenho, meu c, valendo 2, o meu g, valendo 2n.
Substituindo na expressão, eu tenho 2 elevado a log de N, contê 1, eu tenho 2 multiplicando o meu N, que nesse caso lembre-se que é g de 2 elevado a N, então, o meu N é 2 elevado a N.
E aí, o que eu vou ter em uma expressão como essa? Se vocês observarem aqui, o meu 3 elevado a 1, vali 3, e 2 elevado a log N, N.
Nesse caso, como 2 elevado a log N, N, isso facilita bastante as coisas.
Eu vou ter 3n aqui, e nessa expansão, aqui, quando eu tenho 2 vezes 2 elevado a N, o que vai acontecer? Eu vou ter 2 elevado a N mais 1.
Essa expressão, essa potência, eu separo.
E aí, eu posso repetir a base os somnossos põentes do que eliminui.
Então, agora, eu tenho 2 elevado a log N, e um multiplicado com 2 nesse somatório.
Então, eu posso pôr o 2 para fora no somatório e fico com 2 elevado a log N.
Isso aqui, 2 elevado a log N, é um N que eu vou estar somando log N vezes, porque agora eu comece 1.
Então, eu vou estar somando log N vezes o N, ou seja, essa expressão é 3n mais 2 vezes N log N vezes.
Bom, pessoal, então, é isso.
Assista um vídeo novamente, se tiver em dúvida, o dei uma lida no material da acessão 3.
2, porque o assunto é bastante relevante, por que você de vocês.
Muito obrigada, até a próxima.