[Música] Olá pessoal é na aula de hoje então a gente vai falar da indução matemática tá na verdade ela já apareceu para gente né lá na primeira aula quando a gente foi provar a correto de João algoritmo né eu comentei com vocês né que o que a gente tava os passos que a gente estava realizando ali né o passo de inicialização o passo de manutenção ele estavam relacionados com a indução matemática tá então a gente vai ver hoje né que além né da do auxílio na prova de corretor de ainda são Matemática também é uma
ferramenta importante aí na parte de projeto de algoritmos tá ela através da indução matemática ela vai me dar os passos para que eu possa construir algoritmos que a gente vai ver que normalmente são recursivos Inclusive a gente vai fazer o exemplo de um algoritmo na aula de hoje tá então vamos dar uma olhadinha nisso tudo bom então para a gente começar a falar de indução matemática né a gente começa aqui primeiro com é um exemplo né só para a gente é capturar a ideia que tá por trás da indução matemática tá então é meio que
um exercício né que esse exemplo disso né imagina que você tá numa escada né que é infinitamente alto tá e você quer saber se você é capaz de chegar a um degrau bastante alto nessa escada tá então Suponha que você faz a seguinte hipótese sobre a sua capacidade de conseguir subir nessa escada Então primeiramente né você Suponha que você consegue alcançar o primeiro degrau da escada e depois você supõe né que chegando a um degrau você sempre capaz de alcançar o próximo degrau a gente percebe aqui né se a proposição um e a condição Anal
2 foi ambas verdadeiras né Que que isso vai me levar né então você consegue chegar no primeiro degrau da escada bom dado que você tá no primeiro degrau você consegue chegar no próximo dado que você tá no próximo você consegue chegar no outro então é o que você acabou de mostrar né se essas duas posições estiverem corretas é que de fato você consegue chegar a qualquer degrau dessa escada tá então a indução matemática que nem a gente vai ver ela segue Exatamente Essa Ideia Desse exemplo aqui da escada Tá então vamos olhar isso mais de
perto Então a gente vai falar aqui de dois princípios né Agora nós vamos formalizar o primeiro princípio da edição matemática e depois a gente vai falar do segundo princípio da edição matemática tá então a gente pode utilizar naquela ideia da escada lá para provar né é propriedades matemáticas né que de um determinado problema que a gente tenha tá então formalmente né O que que estabelece o primeiro princípio da edição matemática né para uma proposição na forma peniana a gente já vai ver um exemplo daqui a pouco tá onde n é um número inteiro positivo tá
então para provar que PGN é verdadeiro para qualquer n né lembra da escada lá para qualquer degrau então primeiro eu preciso provar que pedir uma verdade né seria o nosso primeiro degrau lá na escada tá e eu preciso dado que eu tô num determinado degrau né ou seja se pedir cá é verdade então eu preciso provar que dedicar mais na verdade se eu conseguir fazer isso então tá aprovado que pedir é verdadeira também tá só que é uma questão né que se coloca aqui na indução matemática a gente precisa saber desde o início né Qual
que é a forma exata né da propriedade quem que é obediente que a gente tá querendo mostrar aí tá então a indução matemática Ela não é uma demonstração exploratória tá então a gente precisa né saber desde o início né O que que a gente tá querendo provar né A gente só vai confirmar né se aquela conjectura tá correta tá Então vamos pegar aqui um primeiro exemplo agora é aplicando né O primeiro exemplo matemática né então esse primeiro exemplo aqui imagina né que a gente tá preocupado né com a árvore genealógica da família Silva né então
problema diz o seguinte pra gente né olha o ancestral Silva lá atrás né casou e teve dois filhos e ocorre algo nessa família né Toda vez né que nascem filhos né Cada filho tem mais dois filhos né Então né que a gente percebe é que o número de descendentes Uma Geração parece ser dois na n né porque a cada geração né o número de descendentes dobra tá então eu quero provar que isso é verdade Então olha só para a gente fazer isso né a gente tem que seguir né Três Passos né que tem a ver
com o que a gente acabou de discutir lá atrás então primeiro eu preciso provar né o passo básico né pedir um né provar que ele é verdadeiro depois eu vou supor que eu tô impedir e preciso provar que P de k + 1 é verdade também tá Então olha só como que ficaria para a gente né então aqui o primeiro passo que que a gente tem P1 né é são os primeiros descendentes né que que a gente viu lá aqui lá a primeira geração foram dois filhos né mas dois é igual a 2 elevado a
primeira né é 2 elevado a n né só que agora com ele sendo igual a um bom então tá aprovado aqui é o caso base de fato se verifica é verdade né então utilizando aquela forma de fato eu consigo chegar né no caso base tá depois eu vou assumir que eu tô na caes Uma Geração né e eu preciso provar então né que a KS mais uma geração ela pode ser descrita através de dois na k + 1 né bom eu tô aqui na caes Uma Geração né então eu tô assumindo que ela representada né
eu consigo calcular o número de descendentes com como sendo dois na k e a gente viu que a cada geração que que ocorre Dobra o número de descendentes né então na geração k + 1 eu vou ter o quê duas vezes o número de descendentes que eu tinha na geração PK que é duas vezes dois na cá que na verdade é o que dois na k + 1 né então eu acabei de mostrar que se eu verifico pecar pecar mais um é verdade também é isso né conclui né a nossa demonstração então é Aquela nossa
primeira sessão né que PGN = 2 na n ela é válida para qualquer valor de n tá bom vamos falar agora o segundo princípio da indução matemática tá que acontece em algumas situações é difícil da gente mostrar isso daqui tá se pecar é verdade pecar Mais na verdade então existe né o segundo princípio que dependendo do problema que eu tenho às vezes é mais interessante utilizar ele e o que que diz né Ele diz o seguinte ele muda aqui na segunda proposição né e ele supõe que se pede R é verdadeiro né ou seja agora
não tô falando mais de predicar mas não tô falando de um intervalo né eu tô dizendo de um p de R onde esse R aqui né é um valor entre um e k né então eu a minha proposição é que é PDF verdadeira para todo inteiro é entre um né e cá e aí eu só preciso provar aqui dedicar mais um continua sendo válido tá então em alguma situações isso pode ser interessante a gente vai ver um exemplo na sequência aqui tá Então olha só eu imagino aqui né que a gente tem uma linguagem de
programação né que foi projetada com a seguinte convenção para operação de multiplicação tá então o que que é a convenção um único fator ele não precisa usar parentes tá mas se eu fizer o produto entre dois fatores né a vezes B eu sempre preciso utilizar um par de parênteses tá então por exemplo esse produto aqui de vários fatores né ele poderia ser escrito com tanto que eu sempre respeite né Eu tenho um número par de parentes para cada multiplicação que eu fizer entre fatores né ele poderia ser escrito dessa forma ou poderia ser escrito dessa
forma aqui tá e o que que a gente quer mostrar né a gente quer mostrar que qualquer produto pode ser escrito com um número par de parênteses Então vamos utilizar né o segundo princípio da indução para tentar demonstrar isso daí tá bom então primeiro a gente precisa provar o caso base né então o caso base o que que é né para um único fator a gente vive para um único fator eu não preciso de parentes ou seja 0 parênteses é um número par Então tá aprovado aqui o caso básico Tá bom agora a gente vai
utilizar né aquela segunda sessão lá para permitir a gente provar né pecar mais um tá então o que que eu vou supor aqui tá eu vou supor né que qualquer produto de R fatores né que era né a premissa lá da linguagem pode ser escrito com um número par de Paris tá então considera por exemplo né que eu tenho um produto P com K mais um fatores tá então é esse cara que eu tô interessado em mostrar tá então p né esse produto ficar mais um fatores eu posso decompor ele né em dois produtos né
um produto s e um produto T onde o produto S tem R1 fatores onde esse R1 é menor do que k tá e t tem R2 fatores onde R2 também é menor do que k né O que está sendo dito aqui e de tal forma que R1 + R2 seja igual a k + 1 então pela hipótese da indução né ST cada um deles tem um número par de parênteses e portanto peca mais um também vai ter um número par né porque eu vou utilizar dois parênteses agora para fazer esse produto né então é o
que tá sendo mostrado aqui então é o produto de um número R de fatores com R entre 1 e k né tem um número par de parênteses eu tô pegando aqui um produto de R um fator chamando de S eu sei que ele tem um número par de parentes pegando um outro produto de R2 fatores chamando de T eu sei que ele também tem um número par de parentes e sei que a quantidade de fatores R1 + R2 é exatamente ficar mais um né e agora eu tô escrevendo né esse produto como sendo S vezes
T né E aí eu tô usando os dois parentes lá que a gente viu no início do enunciado da nossa linguagem né qual que era a restrição lá para a gente representar multiplicação tá então eu tenho um número de parênteses R1 que é para o número de parênteses R2 que é mais dois parentes então de fato o meu número de Paris tá então aqui a gente usou o segundo princípio da indução matemática bom e como que a gente pode usar esse resultado então para utilização em algoritmos né bom a primeira é maneira é através né
para mostrar corre-tude né aquilo que eu comentei com vocês no início da aula lá né então a gente inclusive utilizou lá quando a gente utilizou as variantes de laço né então quando a gente a inicialização corresponde ao caso básico a gente acabou de falar aqui né e a manutenção que eu respondi exatamente ao k + 1 né o próximo passo bom só que a novidade para a gente nessa aula é isso daqui né que a indução ela pode ser utilizada aí né no projeto de algoritmos tá então o processo ele Vai resultar em algoritmos recursivos
que não comentei com vocês lá no início da aula tá algoritmos são algoritmos que fazem chamada a si mesmo tá em boa parte dos casos é relativamente simples ou converter um algoritmo recursivo em um algoritmo interativo a gente inclusive vai fazer isso na aula de hoje tá frequentemente esses algoritmos eles são eficientes embora eles estão casos né aqueles não sejam tá e um benefício imediato né que é o uso né correto da técnica né nos dá a prova de corretor de do algoritmo né porque o que que vai acontecer a gente vai partir da indução
matemática que é uma prova matemática de que aquilo tá correto e a partir dessa indução é que eu vou construir o meu algoritmo a gente vai ver na sequência aqui né Cada eu vou pegar lá o caso base o caso base vai virar né uma parte no algoritmo eu vou pegar né a prova de ficar mais um aquilo vai virar outro pedaço do meu olho tá a gente vai ver isso na sequência então se eu fizer isso né como eu já provendo essa matemática né isso daí me auxilia na prova de corretor de do meu
algoritmo Então olha só quando a gente aplica o processo de indução na construção de algoritmo a gente tem que a resolução do caso base da recursão corresponde ao caso base da indução os passos de recursão a recorrência né as chamadas correspondem a aplicação da hipótese P de cá então predicar Mais não é verdade também tá e a execução completa da recursão corresponde exatamente ao fazer né a determinação da solução do meu problema tá aqui só para a gente formalizar né que a gente tá falando aqui de recorrência recursivo né recorrência é uma expressão né que
descreve uma função em termos dela mesmo a gente vai ter ainda essa semana uma aula que a gente vai falar só de recorrência tá aqui é só para a gente ter uma primeira formalização Então olha só vamos tentar então criar um algoritmo utilizando indução matemática para calcular o valor de um polinômio de grau m tá Então imagina que eu tenho um polinômio aqui de grau m né e eu quero eu tenho um valor de X né Eu quero saber qual que é o valor daquele polinômio por uma entrada que eu vou entregar para aquele algoritmo
né então o que que eu vou fazer aqui eu vou escrever um algoritmo que recebe essa essas entradas né Aos coeficientes recebe um valor de x e vai tentar determinar Qual que é o valor do polinômio tá então por hipóteses que que a gente vai assumir né que qualquer polinômio de grau m né ou seja na verdade que a gente está definindo ele pode ser calculado a partir dessa expressão aqui tá ou seja PGN a somatório né de igual a 1 atm de a i -1x na i-1 bom então a gente primeiro precisa mostrar aqui
o primeiro passo né o caso base bom o caso base o que que é quando eu tenho somente um coeficiente né P1 seria f de zero né teria somente a zero aqui nem de Fato né se eu aplicar agora isso nessa expressão né que a gente tá assumindo eu vou ter aqui o que somatória de um até um de um menos um vai dar zero x na zero é um que vai dar a na 0 x 0 que é igual a zero então de fato o caso base se confirma aqui nessa situação agora que que
eu vou assumir agora eu vou assumir que eu tô né um polinômio com K coeficientes ele pode ser descrito através dessa expressão aqui né e agora eu preciso mostrar que um com k + 1 também é válido dessa expressão tá então preciso agora mostrar k + 1 Mas quem que vai ser p de k+1 aqui né na verdade P de k + 1 é o valor o próximo valor do próximo passo é obtido de pecar mas o coeficiente né multiplicado por x na ordem né do próximo elemento do meu do meu polinômio tá Então na
verdade é o valor de pecar mais a KX elevado a k Então é isso daqui na verdade se eu jogar para dentro desse somatório né incluir esse valor simplesmente vai aparecer esse k + 1 aqui para mim então de fato P dedicar mais um é somatório de i = 1 até a + 1 já de -1x - 1 tá então tá aqui tá aprovado né dedicar mais um bom agora a gente precisa usar esses resultados aí para construir o nosso algoritmo tá então o que que a gente vai fazer aqui né Então a partir da
aplicação do primeiro princípio do san a gente obtém o que o caso base vai nos dar condição né para condição base para iniciar a recursão tá a gente pode realizar a recursão através da própria chamada do algoritmo né a gente tudo isso a gente vai fazer na sequência tá e a gente percebeu que através daquela construção inclusive quando a gente fez o dedicar mais um né que a cada chamada né é somado que exatamente esse valor aqui né a LX na L né para eles uma chamada tá então a gente vai utilizar esses resultados agora
para construir o nosso algoritmo Então olha só então para calcular né o valor né de um polinômio f de m dessa forma aqui então a gente supõe né que vai ser fornecido para o algoritmo né a ordem do polinômio M um vetor com valor dos coeficientes né de a zero até a m tá e o valor de X né que eu quero calcular eu quero calcular o polinômio para um determinado valor de X tá então tá aqui né Então essa daqui são as entradas do meu polinômio bom olha só ó o caso base aparecendo aqui
lembra o caso base da indução o que que a gente viu no caso base o que que é meu polinômio é igual a zero não é olha ele aqui ó então o que que acontece se m for igual a zero o algoritmo simplesmente devolve a zero quem que é a zero a zero é exatamente o primeiro coeficiente do polinômio ótimo agora vamos supor né que a gente tá querendo calcular um polinômio que não é de grau zero né um grau maior do que zero daí entra né exatamente a questão da recursividade então só para a
gente só dá uma limpada aqui para a gente enxergar melhor então o que que vai acontecer aqui se M não é igual a zero que que eu faço eu chamo o próprio algoritmo olha aqui ó quem que ele devolve ele devolve calcula polinômio quem quer calcula polinômio é o próprio algoritmo aqui ó ele tá fazendo uma chamada ele mesmo mas com detalhe ele tá passando um grau do polinômio ao menos então a cada chamada recursiva eu vou decrementando o grau do polinômio Então na verdade eu tenho aqui o grau M chama né o polinômio de
grau m - 1 m -2 e menos três e ele vai caminhando aqui no sentido da recursão até ele chegar lá no caso base até que ele vai chegar uma hora que vai ser zero ele vai cair exatamente na situação no caso base e aí o que acontece essa chamada essa chamada aqui então retorna a zero para a próxima chamada e essa chamada Aqui vai retornar o que a zero mas a um X não vai retornar para cá essa daqui vai retornar o quê a 0 + 1 x 1 + a2x^2 e assim eu vou
retornando até eu chegar na solução Inicial né que corresponde de fato ao cálculo do meu polinômio como um todo tá ok então vocês veem que a gente aplicou né exatamente né os passos da indução para a gente poder construir aqui o nosso algoritmo recursivo tá bom e vamos dar uma olhada como que ficaria uma versão interativa desse algoritmo Então a gente tem aqui de novo né agora tem uma versão interativa ou seja algoritmo não tá fazendo uma chamada ele mesmo né tá fazendo uma chamada recursiva tá então eu tenho aqui o caso base né então
nesse a minha função né o valor do polinômio ele começa com a zero né então se ele for igual a 0 simplesmente devolve o a zero se não né eu entro nesse laço aqui e vou executar esse laço que de um ATM né utilizo aqui esse xn inicializei com um aqui na verdade é uma variável auxiliar ele corresponde a x depois x ao quadrado depois x Ao Cubo né e assim até x na M né então a gente percebe que a cada passo aqui ó eu vou fazendo x vezes O Valor anterior dele tá e
qual que vai ser o valor do polinômio né aqui na verdade a gente tem uma recursão né eu tenho que F vai ser o quê o último valor calculado de F mais aquela parcela aí x na ele naquele momento tá então ele vai fazer isso até chegar em M E aí eu tenho o valor final né do meu polinômio tá então a gente tem aqui né na verdade esse f igual a f mais a x na n corresponde àquela Nossa expressão que a gente viu lá do PK mais um igual APK + akx bom pessoal
era isso que eu queria contar para vocês hoje falar da indução matemática como ferramenta e não só de corretor de mas também né da parte de projeto de algoritmos tá ela vai aparecer ainda várias vezes para gente a gente vai utilizar um temática aí em outras estratégias que a gente vai ver ao longo do curso né mas a ideia era que vocês capturassem né o significado né e a implementação da indução matemática e a aplicação dela tanto na parte de análise de corretor de quanto de projeto de algoritmos é isso pessoal até a próxima aula
então [Música] [Música]
