Projeto e Análise de Algoritmos - Aula 06 - Solução de recorrências (Parte II)

[Música] lomba olá pessoal sejam bem vindos à nossa festa aula de projeto e análise algoritmo nessa aula veremos alguns outros métodos para resolver a recorrência olha passada vimos o teorema mestre nessa hora veremos um método interação água a recorrência e o método de substituição então queremos fazer queremos fazer uma recorrência o que significa isso obter uma fórmula fechada para tvn que deu o valor da função diretamente em termos de seu argumento por exemplo queremos fazer a seguinte recorrência teve uma igual a 1 e terena igual a 2 vezes terem meios mais dois para igual a

2 487 porque quer um detalhe aqui não é porque a gente não coloca aqui o 3 por exemplo com o 3 a qual eu não seria bem definida porque teria mostrei de três meios que vai dar 1.5 e situação não vai estar definirá para 1.5 por exemplo serve só para número inteiro bom se a gente quiser uma fazer uma tabela dessa função para ver que valor é realmente tdn tem para cada um dos tempos e dos valores eram impossíveis a gente poderia fazer o seguinte então voltei depois de ser 12 48 e 62 64 vão

tentar calcular o valor do bpn eu sei que te deu no caso base aqui depois para é igual a 2 eu sei que eu tenho que aprender a aplicar em situação de aqui então vamos colocar aqui 22 vezes e meio enquanto n 6 venceu 12 vezes tv1 quanto vai receber um valor 12 meses 12 mais 24 fazemos o mesmo para o seguinte valor 4 quero saber quanto é ter e 4 vamos aqui a expressão vai ser 2 vezes t2 enquanto e tv 2 e 4 2 e 6 4 e 8 mais dois de se impor

diante a gente pode calcular os outros valores da tabela se olhamos um pouquinho nos valores que calculamos agora e vamos ter aqui e talvez a gente consiga com sorte encontrar uma expressão que represente o tn a gente poderia tentar a nossa - e aqui é mais ou menos três vezes o valor de n vai dar 24 é mais ou menos três vezes o valor dele sei vai dar 48 é mais ou menos três vezes o valor de 32 vai dar 96 só que não é exatamente esse valor se a gente calcular por exemplo por exemplo

três em -2 a gente ouviu mais ou menos será isso a gente vai encontrar os mesmos valores para os assentados quer dizer que tem uma grande possibilidade que a solução dada essa recorrência de que seja 3 n -2 certo de acordo com a nossa tabelinha e as contas que fizemos então eu acho que tvn e 3m nos 2 será que isso é verdade a gente pode ter errado na pontinha vamos deixar isso em aberto ainda vamos ver um método que nos permite encontrar uma solução que o método da interação ele consiste em expandir a equação

da recorrência istoé e ter a recorrência e escrevê la como uma somatória termos que dependem apenas de m vamos ver como fazer isso como que funciona a partir de um centro vamos fazer o mesmo exercício anterior na interação o único que temos que fazer é copiar a mesma conseguiu recorrência o que seria aqui na interação 2 o que vamos fazer é expandir essa expressão daqui são bons para interação 2 tentamos expandir-se impressão de que o que teve e mails terena e meio então vamos substituir aqui no lugar de n e meios que vai ficar 2

dct dn meio dividido por dois que da n4 mais dois então essa parte aqui foi expandida por isso a parte amarela aqui se você mostrar as contas são 172 elevada ao quadrado tdn rio por 4 2 nesses 24 mais 26 o mesmo para interessa 3 e agora o que vamos expandir é ter n4 tomamos para interação 3 o que fazemos substituímos aqui na fórmula no lugar de nino vamos colocar em quartos vai ficar dois meses tvn 4 / 2 na cidade de nenhum centavo mais dois e demais se que o calcinha como estava na internação

anterior fazendo as contas temos um elevado ao cubo pdn dividam por ou então que seria 2 elevado ao cubo mais 14 se olharmos aqui identificamos algumas características em comum veja aqui por exemplo elevado a 2 e aqui também ser levado a 2 na interação dois aqui elevado a 3 e levá-lo a 3 na interação 3 é uma coisa que também precisamos identificar barcelo na interação porém sempre o que significa esse doido porque 5614 que olha mais ou menos a gente poderia calcular a interação 2 possui levar o 2 ao cubo vai dar oito interação 3

levou o povo vai dar 2 elevado a 3 que seria 2 elevado a 4 na verdade vai dar 2 248 22 16 ok tá muito parecido a esse valor e aqui esse valor do saque porém está exato se a gente tirar dois a gente vê que dá o valor certo então podemos substituir esses números por num caso e de três em três anos e levar 4 - 2 no caso e traz em 2006 levando 3 - 2 porque estamos fazendo isso estamos tentando identificar como seria essa expressão para um caso o genérico para interação e

por exemplo então agora já sabemos mais ou menos como seria para internação em si para interação 3d levado a 3 aqui para interação iguais elevado aí e nesse caso de que vai ser levado à e mais um não vemos como seria a nossa equação na iss uma interação vai ficar 2 elevado aí tdn meios nenê dividiu por 2 elevado aí mais elevado aí mais um menos dois tá bom mas se a gente continuar a se expandido expandido expandindo a gente nunca vai parar então queremos saber quando é que isso vai parar quando que essa expressão

vai parar no caso vá se ele vai parar quando ele consiga chegar no caso baixo então vamos resolver quando vou chegar no caso vá sei quando vou parar que o mesmo quando essa expressão de khimki foi a última que calculamos cheguei no caso vá se ou seja quando o tn dividida por dois elevado aí seja igual até de 10 a moça que então o que temos que fazer e e colocar essas duas expressões que o olhar ela então vai ficar e meio ele viveu por dois levaram a igual a partir daí a gente pode calcular

quanto quanto é o valor de n n vai ser igual a 2 elevado aí ei vai ser igual a 1 mm isso vamos usar depois para fazer o cálculo final e agora se substituindo isso na fórmula de interação e vamos obter o seguinte aqui está nossa forma fórmula de interação e quem sabe aqui vamos tentar substituir o q2 e levado a i2 elevar o iene vão substituir aqui porém como a gente já colocou para chegar no caso vá se ter e não deviam pôr 2 elevado aí vai ser igual à tv um conceito irmãos e

suporte te deum aqui em c2 elevado aí mais um é o mesmo que falhar dois esses dois elevado aí mas eu sei que dois elevado aí então é isso aqui na verdade e 2 vence vai ficar mais 21 22 e 23 agora podemos falar que tvn é igual a 3 - 2 portanto tvn ttm resultado que encontrei está correto porque a gente fez vários vários pontinhos no meio mas será que está correto uma outra opção para calcular a fã do cinema e conhecendo a recorrência que o arco a água e de recorrentes essa forma de

resolver uma recorrência eu tenho para estimar a solução é o que ela vai fazer e vai representar uma árvore o desenvolvimento da recorrência essa forma permite visualizar melhor o que acontece quando a recorrência integrada na árvore cada ano vai representar um sub problema o que vamos fazer para calcular o tempo total vai ser calcular a soma atual nível e depois a somali todos os níveis temos aqui um centro a mesma equação que estamos resolvendo pensa nessa aula josé tvn igual a 2 c d e e mails mais dois vamos agora fazer uma árvore tá primeiro

pegamos a primeiro tempo tn ok vou estar no nível zero só tem uma folha na minha agora vou expandir isso eu tenho que te vê e nem dois meses tvn meios mais dois eu vou substituir stn por dois e vou criar dois arcos o paraná terena e meio se eu tivesse aqui 3d e mail criaria três arcos se eu tivesse 80 e meio eu criaria 18 arco vamos resolver isso 22 teve e meio aqui vai ser substituído por dois e vou criar dois arcos ac2 pb e mail cv e mail quantas folhas ou e calculando

essa tabelinha que enquanto vou fazendo árvore quantas folhas eu tenho tenho 2 enquanto que a minha somatória do nível severo e 2002 aqui e assim continuamos agora vou expandir tv e meio terreno e meio ele vai ser 2 esteve em quatros mais dois então substituir esse por dois e vou criar mais dois arcos aqui é certo que seria antena 4 o mesmo faço com o ramal do lado quantas folhas eu tenho aqui eu vou ter dois e levar o coração quatro folhas e continuamos agora vou expandir ter n quartos vai dar 2 vezes esteve no

quarto devia por 2 ou seja dois meses terem oitavos mais dois é constituído por dois e mais dois anos tb n dão por 8 seria 2 1 e igualou o quanto eu tenho aqui eu tenho 2 468 não te levar o álcool está a e esquecidas uma história quanto tem na somatória anterior eu tenho dois nem 24 matou 2 468 não escutar porque a gente está fazendo isso porque afinal o consumo de tempo vai ser a soma de toda essa coluna que estamos calculado tá aí fazemos uma coisa similar a um método interação tá vamos

tentar e está que acontecem interação ricci - um emmy internacional e vamos tentar generalizar o que acontece na interação e então vou ter aqui te dividir tvn / 2 elevado aí vou ter um monte de folhas aqui quantas folhas eu voltei eu posso generalizar aqui não sei que aqui eu tenho 2 a 0 aqui nesse nível tenho 2 a 1 neste domingo no engenhão 2 a 2 nesse 2 a 3 portanto nível eu vou ter dois aí folha tá e aí a gente vai se fazer a mesma pergunta quando isso vai parar quando vou parar

de expandir essa água errou parar quando chegar no caso base ou seja quando essa expressão de aqui seja igual a atendeu é isso que estamos fazendo aqui aí fazemos ou mesmo iguais é o mesmo da semana interação e olhamos é dividido por dois sair a 1 quanto vale e vale 2 elevado aí e vale 9 m ok então como chegar no caso base essas de kim tdn portões sair vão ser substituídas pelo valor do conserto do carro base quanto o valor do carro básico quanto esteve 13 11 é o 1 ou seja essas folhas que

vão ser substituídas por um mas poderia ter um outro sempre que quem seja ter um igual a 20 eu vou substituir então essa folha por 20 então vamos substituir por um t1 como cada uma dela é um calcular quanto no total o nível de nível 2 aí quanto vale cada folhinha valer 1 então quanto tem no total o t2 sair certo e aí eu faço mesmo então agora o faço o último passo que seria fazer a soma de tudo o que eu vou fazer a cabeça coluna aqui que seria 2 tb n vai ser 2

+ 2 a 2 mas nossa 3 mas dois aí cultiva a última das folhas do caso vá se que dois aí para isso vamos precisar agora os algumas somatória que demonstra alguma das aulas anteriores lembra que vimos algumas matérias básicas certo não se olha você certeza de que vai ser então essa parte que amarelo vai ser essa somatória visitar igual a um ataque d2 sacar e temos mais 12 sair daqui agora vamos ver alguma das motoristas irmãos não olha passada temos essa somatória que essa matéria é jogo igual a zero a eni a fórmula dessa

somatória reais idiota é a arena é mais um - onde viveu por a -1 mas tem outras variáveis mas tudo bem o importante é a somatória o único problema que estou vendo aqui é que é essencial a somatória que convenceram enquanto essa somatória de que começa em 1o então tenho que arrumar isso de algum jeito para poder saber qual é o resultado então vamos arrumar isso daqui seu cárcere aguaceiro aqui vai ficar 2 a 0 e 2 a 0 eo então vamos assumir que então agora é a somatória convenceram a se convencer eu tenho que

estar a tirar o 2 a 0 que o alienista o motorista o que estamos fazendo aqui estamos tirando dois acertos e uma vez que já tenham essa expressão aqui que praticamente em cima de kingson que com outras variáveis como com a igual a 2 o jogo igual a ca certo é igual a gente pode aplicar a fórmula diretamente então que vai ser aqui a partida que vai ser 2 elevado em mais ou menos um de isopor 2 - som que eu avaliei 27 substituído então vamos ter essa solução aqui e aí vamos tentar ver qual

é o resultado disso temos aqui dois aí ok eu sei que dois aí n o sítio por n2 aí mais uma agente óbvio que sou e 2 n - 12 - também não sou nenhum então vai ser dividido por um e menos 1 no final que temos no final 3 sem eliminações últimos o mesmo resultado anterior tvn 3 em -2 o terena igual a tdn mas aí de novo estamos com a dúvida será que a gente fez o cálculo direitinho fizemos assuma direitinho será que fizemos o correto a gente encontrou o mesmo resultado com uma

tabela como método de interação e com a água a recorrência 33 100 milhões mas ainda há gente não tem certeza não tem medo que o método da substituição que vai ajudar a gente a ter certeza que realmente o que encontrámos está certo a meta da interação começa com um chute em para o valor de tbn e chutei ele pode vir de qualquer lugar da tabela do metrô interação da árvore ou não sei há alguém falou para você que seria um resultado após você ter esse chute você vai demonstrar por indução que o chico está certo

então fechamos nosso centro o que acontece é mostrar não se conhece na recorrência e alguém já falou que o resultado dessa ocorrência 3 c - 23 - hoje e agora teremos tse verdade não vamos ter que demonstrar isso por emoção em por indução a gente começa pelo caso o bacen usar a hipotensão e finalmente chegar na conclusão então comprar o caça base para é igual para igual a uma mulher teve um igual então vamos lá assumimos que isso aqui é verdade então vamos tentar ver se realmente a vantagem não é quanto te deum vai ser

três vezes 1 - 2 e só dá um opa está certo tv on caso basta funcionam agora vamos para o utilizará a indução né o a hipótese de demissão para o nene maior ou igual a 2 o que vai acontecer tvn igual a 2 tremei os mais velhos vamos assumir vamos supor que ler da ge para qualquer n entre o iene - sul vamos tentar chegar na seleção daqui será que então que podemos assumir para tv e meio e se é verdade sim é menor que me a hipótese de e mail sem substituir que temos

aqui não vai dar 3 é no lugar dele eu vou colocar e mail e da 3m e meios menos 27 vão ser as continhas aí o que vai dar que vai dar 3 n 26 24 23 6 2 a gente conseguiu demonstrar que realmente te den-3 e menos dois em construção um encontramos que realmente era o resultado certo tdn 3 - 2 e portanto tdn ttrn essa foi a nossa sexta aula de projeto e análises e algoritmos em que falamos sobre como resolver outras formas recorrência para que vocês tenham gostado e até a nossa próxima

aula [Música] [Música] [Música] [Música]