Projeto e Análise de Algoritmos - Divisão e Conquista - Método da Substituição

[Música] bom pessoal é nessa aula então né que nem o havia comentado na aula passada a gente começa a ver né métodos aí para a gente poder resolver equações de recorrência tá então nessa aula aqui a gente vai ver o método da substituição então conforme a gente comentou lá na outra aula né é com intuito né de obter esses limites né A gente vai ver na verdade três metros tá então só lembrando né o método da substituição que a gente vai ver nessa aula que que a gente vai fazer a gente começa isso por um

limite assim tópico por uma determinada recorrência tá então a gente usa a indução matemática né Para a gente mostrar que essa suposição tá correta é isso daqui que a gente vai ver na aula de hoje tá e nas próximas duas aulas né a gente fala então do método da árvore de recursão e fala também depois do método mestre bom então é o método da substituição é ele tem basicamente duas etapas aí para a gente aplicar ele tá então na primeira etapa que que eu vou fazer na primeira etapa eu vou supor uma solução para ter

dinheiro é uma função né para ter dinheiro assim tática tá e a gente vai substituir essa função na solução da equação de recorrência tá a gente vai pegar essa essa suposição e substituir ela dentro da equação de recorrência tá E aí né usando a indução matemática a gente vai tentar determinar Quais são as constantes né para que a nossa suposição esteja correta ou se ela de fato está correta eu consigo encontrar essas constantes né que mostra que de fato aquela é a solução correta para aquela recorrência Tá então vamos dar uma olhada num exemplo Então

imagina aqui que a gente tivesse essa equação de recorrência Então eu tenho aqui que tgn é 2T n sobre 2 + n tá então eu vou supor aqui inicialmente né que T de n é odn tá então a gente precisa agora usar a indução matemática né para primeiro mostrar o caso base né e depois para um valor k entre um iene Então vamos começar com caso base tá então no caso base normalmente a gente vai assumir que ter de um igual a um Então se a gente agora pegar na nossa equação né então que que

eu tô dizendo aqui eu tô dizendo que tgm É menor né que CGN logn e eu tô dizendo que isso é verdade para n = 1 né então tô dizendo que T de um tem que ser menor né a uma constante vezes log de 1 tá só que a gente sabe que log de um isso daqui é igual a zero ou seja um tem que ser menor que zero né tô dizendo que T de um que vale um é menor do que zero bom isso quer dizer o que né que na verdade não funcionou aí

o nosso primeiro teste tá só que aqui existe uma sutileza né porque o que a gente tá tentando mostrar aqui a gente tá tentando mostrar que tem higiene é og n o game tá ou seja isso daqui é o limitante assintótico né Ele tem ele é válido para valores elevados de gênero não tô preocupado em valores pequenos tá Então na verdade eu tenho que esse limitante ele tem que ser válido a partir de um determinado valor N zero né Por uma constante ser positiva e eu tenho interesse para esse limitante né geralmente para valores bem

elevados de n Então vamos escolher o valor dois agora tá então vamos supor T de dois vamos ver se a partir do valor 2 ele passa a ser válido né então agora se eu substituir né na minha expressão então eu vou ter o que que duas vezes T de um mais n que agora vai ser igual ao que duas vezes um mais dois né então substituindo aqui nessa equação isso tem que ser menor do que ser multiplicado por 2 log na base 2 tá e log de 2 a gente sabe que é um né então

eu tô dizendo aqui que quatro tem quatro tem que ser menor do que duas vezes c bom isso é verdadeiro né para qualquer ser maior ou igual a 2 bom pessoal então vamos dar uma olhada no método da substituição através de um exemplo Então imagina aqui que a gente tá né com a nossa equação de recorrência essa daqui né Igual dois tgn sobre dois mais n tá e eu vou assumir aqui inicialmente que tgn é odn on tá então a gente precisa agora usar indução matemática né para determinar as constantes e mostrar né que a

nossa suposição funciona bom então primeira coisa que a gente precisa mostrar é o caso base né ou seja T de um então eu vou assumir Aqui que teve um é igual a um tá então se ter de um é igual a um né e ter dinheiro é de n o HN Então tgn tem que ser menor né que CN logn tá de um eu tô assumindo que é igual né e clog n no caso aqui um eu vou ter o quê logaritmo de 1 = 0 né então como T de um é um e log

de um É zero né eu tô afirmando então que um é menor do que zero tá então a gente percebe aqui que a princípio né falhou aqui o caso base para a gente tá mas aí a gente tem que observar né que na verdade o que que a gente tá tentando provar a gente tá tentando provar que tem dinheiro tá mas para definição né da notação assintótica o que que ocorre aqui na verdade isso tem que ser verdade não para todo ele isso tem que ser verdade por uma constante positiva c e para um n

maior ou igual um determinado ele zero tá não é para todo ele né então vamos tentar agora né vamos manter o nosso caso base vamos ver se para um n né Maior por exemplo igual a dois né ele passa a ser válido né que vai me interessar dali pra frente tá Então olha só se eu pegar agora T de dois né então eu tenho que ter de dois aplicando aqui nessa equação vai ser duas vezes T de um que a gente tá dizendo que é um mas n n no caso aqui vai ser dois então

eu vou ter duas vezes um mais dois que é igual a 4 tá então isso tem que ser menor o que que n log n né n = 2 então c duas vezes log de 2 né log de 2 na base 2 dá 1 então eu tô dizendo que aqui quatro tem que ser menor ou igual a duas vezes c né bom isso é verdade para qualquer ser maior ou igual a 2 tá então é de Fato né eu posso usar o t igual como caso básico para ele de dois né funciona e agora a

gente vai testar para eles maiores do que dois bom então a gente precisa provar agora que isso daqui continua válido né para valores de k aqui né maiores igual a 2 menor que n tá então lembrando a nossa hipótese Inicial é que T de n né é o odn ou seja então ele tem que ser menor que ser de n log n tá e eu tenho aqui deixa eu só limpar aqui para ficar mais claro da gente enxergar e eu tenho né que a minha equação de recorrência T de n = 2 + n então

que que eu preciso fazer eu preciso agora substituir na equação de recorrência né ou a função que eu tô supondo que é solução então eu tenho que que dois ter Gene sobre dois mas ele né que corresponde aqui a minha equação de recorrência ela tem que ser menor né do que o que ser só que aqui eu tenho T de n sobre dois então vai ser c né 2c de n sobre 2 log de n sobre 2 tá então só expandindo agora eu tenho duas vezes n dividido por 2 vai dar C vezes n né

e log de n sobre dois né log da divisão né é a diferença dos logaritmos né então eu posso escrever isso simplesmente como log de n menos log de 2 né log de dois na base 2 é 1 Então vou ficar com CN que multiplica log de n e que multiplica menos um né então eu vou mais n né então eu vou ter [Música] então com isso né O que que a gente tem eu tenho que ter de n né até agora eu mostrei que T de n é menor ou igual a CN logn menos

c n + n tá então o que que a gente precisa a gente precisa mostrar porque na verdade eu tô afirmando que ter dinheiro é menor que CN Então eu preciso mostrar como eu sei que tgn é menor do que isso daqui então eu preciso mostrar que isso daqui é menor ou igual a CN né E aí por consequência ter dinheiro vai ser menor ou igual a CNH tá e a gente observa aqui né facilmente analisando essa expressão né como aqui eu tenho um sinal negativo não é para qualquer valor maior ou igual a 1

né Essa parcela aqui vai ficar negativa e vai subtrair de CN E logn e esse valor aqui então vai ficar menor do que simplesmente c n login tá então para qualquer valor aí maior ou igual a 1 né de fato T de n é menor do que se n log n tá no entanto lembra que isso tem que ser válido né também para o caso base e lá no caso base a gente viu né que a gente conseguiu mostrar que ele era válido para ser maior ou igual a 2 tá então o que que eu

posso afirmar Finalmente né eu posso afirmar então que tgn é de fato menor que c n logn ou seja ele é o dien logn tá para qualquer n maior ou igual a 2 e para uma constante ser maior ou igual a 2 né Ou seja tgn é tá então com isso a gente termina né a de mostrar que de fato tediane é hodiene ou ADN bom mas aí a pergunta que a gente faz né É como fazer uma boa suposição de TDM né porque que aconteceu a hora que eu comecei a resolver eu já disse

olha a t DN é igual a n logn né é o on tá mas como é que como é que eu faço essa esse Chute Inicial vamos dizer assim nessa essa suposição inicial para tentar mostrar depois que aquilo de fato é verdade ou não Tá então a resposta é a seguinte né não existe uma metodologia tá então normalmente né muitas vezes né você vai utilizar intuição ou às vezes você pode acontecer de você utilizar né um que você já resolveu uma outra equação de recorrência que é parecida com aquela E aí você vai no mesmo

caminho né Então imagina que por exemplo né que a gente tem uma situação com esse tipo de equação de recorrência é bem parecida com o que a gente acabou de resolver né Então nesse caso aqui que eu podia fazer eu já podia partir dessa expressão aqui né que foi a expressão que a gente encontrou que a gente tava resolvendo a nossa recorrência ali né E aí a gente consegue mostrar facilmente que por um ser maior do que 10 né de fato tign vai ser é menor do que n ou n é lógico que precisa provar

o caso base né tá que tá como exercício vocês quiserem fazer depois em casa né mas eu já já parto né de algo que eu já conheço né na verdade se vocês olharem aquela recorrência né que a gente acabou de olhar é ela é muito próxima da recorrência do próprio me ajude que a gente viu né E lá no médio sorte a gente tinha visto que ele era o higiene login tá então muitas vezes a gente vai utilizar já um conhecimento de um outro de um outro problema que a gente resolveu de uma equação muito

parecida então uma outra está uma outra estratégia né a gente fazer o que a gente utilizar um TN Mais folgado né porque que acontece na verdade eu tenho uma uma equação de recorrência que eu não sei ainda qual que é a solução dela e eu tô procurando um limitante superior para ela né então quanto mais distante esse esse limitante aqui é vamos dizer assim maior seria a chance de dar certo né então eu posso se eu não tenho muita certeza eu posso utilizar um limitante Mais folgado né E aí se ele der certo eu posso

vir tentando aproximar né porque lembra que nem a gente já comentou em aulas anteriores quanto mais próximo do que de fato né é a minha função ter dinheiro melhor é o meu limitante tá então por exemplo o nosso caso ali a gente sabe né que ele é o quadrado né assim praticamente é maior do que ele então em vez de eu ter partido direto para ele eu poderia ter testado ele ao quadrado né ao quadrado e aí se tivesse dado certo teria dado né porque como ele é ódio ele também é o adn² né então

deu certo aí eu pego e tento restringir um pouco mais né aí eu te bom uma outra possibilidade né às vezes que que a gente pode fazer às vezes uma substituição de variáveis também pode ajudar a resolver a recorrência né Então imagina que por exemplo essa situação vamos porque eu quero resolver essa recorrência aqui que é do tipo TDM igual dois t de raiz quadrada de n + log n né bom se eu fizer uma substituição de variáveis ou seja se você é que n é igual a 2 elevado a m e definir que S

de m como sendo T de dois na M E substituir que que vai acontecer na verdade é assim GM vai ser dois de T raiz quadrada de dois na Mr √2 na M é 2 elevado a m sobre 2 né e eu vou ficar com log de m sobre 2 então eu vou ter que S de m é simplesmente 2s de m sobre dois mais M que é uma recorrência que a gente já conhece né que a gente resolveu tá bom E aí eu sei que o valor para S de m seria o de m

log M então o que que eu preciso fazer agora agora eu preciso voltar né então eu sei que m é log n então aonde tiver M agora lá na minha anotação sintática vou trocar por log de n né então o que que eu tenho aqui eu tenho que ter dinheiro é T de dois na M que é igual a s de m que é o de m logm então onde tem M eu vou trocar por log de n então vai ficar o de log de n log de log tá então seria uma outra situação aí

que às vezes uma substituição de variáveis né é facilita a resolução do nosso problema tá Em algumas situações a gente na próxima aula a gente vai falar sobre árvore de recursão né É muitas vezes a gente utiliza né o método da árvore de recursão justamente para ter essa primeira função esse primeiro palpite que depois a gente válida ele através do método da substituição Inclusive a gente vai fazer isso na próxima aula tá porque quando a gente usa a árvore de recursão a gente pode ser um pouco menos rigoroso matematicamente então às vezes né tem um

problema que eu tô meio desconfiado que a solução é de um determinado jeito às vezes eu aplico o primeiro o método de recursão né chego numa função e aí eu testo ela através do método da substituição tá também é uma abordagem possível aí bom pessoal então era isso que eu queria contar para vocês né então a gente vê essa primeira ferramenta né do método da substituição para resolver recorrência e na próxima aula então a gente fala né da árvore de recursão e fala também do método mestre né como outras estratégias aí para a gente resolver

equações de recorrência Tá ok então até a próxima aula pessoal [Música] [Música]