Funcoes Geradoras-Analise de Algoritmos e Operacoes

Análise de Algoritmos Berilhes Funções Geradoras Operações sobre Funções Geradoras Ordinária BALANCEAMENTO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então Acz n0 cn zn é a função geradora ordinária de c0 a0 c1 a1 c2 a2 SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11z 1 2 4 8 16 2n Funções Geradoras Operações sobre Funções Geradoras Ordinária BALANCEAMENTO Se Az n0 aₙzⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então Acz n0 cⁿzⁿ é a função geradora ordinária de c⁰a₀ c¹a₁ c²a₂ SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1111 n0 zⁿ 1 1z 1248162ⁿ n0 2ⁿzⁿ 1 12z Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Funções Geradoras Operações sobre Funções Geradoras Ordinária cont ADIÇÃO Se Az n0 aₙzⁿ é a função geradora ordinária de a₀ a₁ a₂ e Bz n0 bₙzⁿ é a FGO de b₀ b₁ b₂ então Az Bz é a FGO de a₀ b₀ a₁ b₁ a₂ b₂ SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1111 n0 zⁿ 1 1z 1242ⁿ n0 2ⁿzⁿ 1 12z 0132ⁿ1 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont ADIÇÃO Se Az n0 an zn é a função geradora ordinária de a0 a1 a2 e Bz n0 bn zn é a FGO de b0 b1 b2 então Az Bz é a FGO de a0 b0 a1 b1 a2 b2 SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1111 n0 zn 11z 1242n n0 2n zn 112z 0132n 1 n2 2n 1 zn 112z 11z Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Funções Geradoras Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então z Az n1 n an zn é a função geradora ordinária de 0 a1 2 a2 3 a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1111 n0 zn 11z 01234n 00136 n choose 2 001m1 n choose m Funções Geradoras Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então zAz n1 n an zn é a função geradora ordinária de 0 a1 2a2 3a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11z 0 1 2 3 4 n n0 n zn z1z2 0 0 1 3 6 n choose 2 n2 n choose 2 zn z21z3 0 0 1 m 1 n choose m nm n choose m zn zm1zm1 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então zAz n1 n an zn é a função geradora ordinária de 0 a1 2a2 3a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11z 0 1 2 3 4 n n0 n zn z1z2 0 0 1 3 6 n choose 2 n2 n choose 2 zn z21z3 0 0 1 m 1 n choose m nm n choose m zn zm1zm1 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont DIFERENCIAÇÃO Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então zAz n1 n an zn é a função geradora ordinária de 0 a1 2a2 3a3 n an SEQUÊNCIA FUNÇÃO GERADORA ORDINÁRIA 1 1 1 1 n0 zn 11z 0 1 2 3 4 n n0 n zn z1z2 0 0 1 3 6 n choose 2 n2 n choose 2 zn z21z3 0 0 1 m 1 n choose m nm n choose m zn zm1zm1 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Integração Se Az n0 anzn é a função geradora ordinária da sequência a0 a1 a2 então 0z Atdt n1 an1n zn é a função geradora ordinária de 0 a12 a33 an1n Sequência Função geradora ordinária 1 1 1 1 n0 zn 11z 0 11 12 13 1n n1 znn ln 1 1z Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Deslocamento à Esquerda Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então Az a0z n0 an1 zn é a função geradora ordinária de a1 a2 a3 a4 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Deslocamento à Esquerda Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então Az a0z n0 an1 zn é a função geradora ordinária de a1 a2 a3 a4 Deslocamento à Direita Se Az n0 an zn é a função geradora ordinária da sequência a0 a1 a2 então z Az n1 an1 zn é a função geradora ordinária de 0 a0 a1 a2 a3 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Soma Parcial Se Az n0 aₙzⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então 11z Az é a função geradora ordinária de a₀ a₀ a₁ a₀ a₁ a₂ Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Soma Parcial Se Az n0 aₙzⁿ é a função geradora ordinária da sequência a₀ a₁ a₂ então 11z Az é a função geradora ordinária de a₀ a₀ a₁ a₀ a₁ a₂ Demonstração 11z Az k0 zᵏ n0 aₙzⁿ k0 n0 aₙ zⁿᵏ Distribuição k0 nk aₙₖ zⁿ Mude n para nk n0 0kn aₙₖ zⁿ Troque a ordem dos somatórios n0 0kn aₖ zⁿ Mude k para nk Funções Geradoras Operações sobre Funções Geradoras Ordinária cont CONVOLUÇÃO Se Az n0 an zn é a FGO a0 a1 a2 e Bz n0 bn zn é a FGO de b0 b1 b2 então Az Bz é a FGO de a0 b0 a0 b1 a1 b0 k0n ak bnk CONVOLUÇÃO Se Az n0 an zn é a FGO a0 a1 a2 e Bz n0 bn zn é a FGO de b0 b1 b2 então Az Bz é a FGO de a0 b0 a0 b1 a1 b0 k0n ak bnk Demonstração Az Bz k0 ak zk n0 bn zn k0 n0 ak bn znk Distribuição k0 nk ak bnk zn Mude n para nk n0 k0n ak bnk zn Troque a ordem dos somatórios Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Sequência Função geradora ordinária 0 1 1 2 3 5 Fn n0 Fnzn 15 11φz 11φz 2 1 3 4 7 11 Ln n1 Lnzn 11φz 11φz 0 2 0 1 1 2 k0n FkLnk n0 k0n FkLnk zn Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Sequência Função geradora ordinária 0 1 1 2 3 5 Fn n0 Fnzn 15 11φz 11φz 2 1 3 4 7 11 Ln n1 Lnzn 11φz 11φz 0 2 0 1 1 2 k0n FkLnk n0 k0n FkLnk zn Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Sequência Função geradora ordinária 0 1 1 2 3 5 Fn n0 Fnzn 15 11φz 11φz 2 1 3 4 7 11 Ln n1 Lnzn 11φz 11φz 0 2 0 1 1 2 k0n FkLnk n0 k0n FkLnk zn 15 11φz 11φz 11φz 11φz 15 11φz2 11φz2 Funções Geradoras Operações sobre Funções Geradoras Ordiniária cont Funções Geradoras Operações sobre Funções Geradoras Ordiniária cont Exemplo Considere a seguinte função geradora ordinária Fz 11z2 Nós temos que Fz 11z 11z Portanto Fz Σ n0 Σ k0n 1 zn Σ n0 n1 zn Funções Geradoras Operações sobre Funções Geradoras Ordiniária cont Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que from 1 k n Hk n 1Hn1 1 Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que from 1 k n Hk n 1Hn1 1 Gz from n 0 from 1 k n 1 Hk Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que from 1 k n Hk n 1Hn1 1 Gz from n 0 from 1 k n Hk Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que 1kn Hk n1Hn1 1 Gz n0 1kn Hk Gz 11z 11z ln 11z Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que 1kn Hk n1Hn1 1 Gz n0 1kn Hk Gz 11z 11z ln 11z Gz 11z2 ln 11z Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Vamos provar que 1kn Hk n1Hn1 1 Gz n0 1kn Hk Gz 11z 11z ln 11z Gz 11z2 ln 11z Agora vamos expandir Gz convoluindo 11z2 com ln 11z Exemplo Vamos provar que 1 k n Hk n 1Hn1 1 Gz n 0 1 k n Hk Gz 11 z 11 z ln 11 z Gz 11 z2 ln 11 z Agora vamos expandir Gz convoluindo 11z2 com ln 11 z zn 11 z2 ln 11 z 1 k n 1k n 1 k Exemplo Vamos provar que 1 k n Hk n 1Hn1 1 Gz n 0 1 k n Hk Gz 11 z 11 z ln 11 z Gz 11 z2 ln 11 z Agora vamos expandir Gz convoluindo 11z2 com ln 11 z zn 11 z2 ln 11 z 1 k n 1k n 1 k n 1Hn n Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo Assuma que an e bn são os números de formas diferentes de selecionar n letras dos multiconjuntos representados pelas palavras ama e sonho respectivamente Dessa forma a função geradora ordinária para as sequências an e bn são Az n0 an zn 1 2z 2z² z³ Gz n0 bn zn 1 5z 7z² 7z³ 4z⁴ z⁵ Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo O conjunto de possibilidades contadas pelas sequências an e bn são completamente disjuntos uma vez que o conjunto de letras das duas palavras é disjunto Portanto o número cn de formas diferentes de selecionar n letras do multiconjunto representado pela palavra amasonho é a soma a0bn a1bn1 a0b0 Logo a função geradora ordinária da sequência cn é Cz AzBz 1 7z 19z2 32z3 37z4 30z5 17z6 6z7 z8 Dessa forma existem por exemplo 19 formas de escolher 2 letras da palavra amasonho Funções Geradoras Operações sobre Funções Geradoras Ordinária cont Exemplo O conjunto de possibilidades contadas pelas sequências an e bn são completamente disjuntos uma vez que o conjunto de letras das duas palavras é disjunto Portanto o número cn de formas diferentes de selecionar n letras do multiconjunto representado pela palavra amasonho é a soma a0bn a1bn1 a0b0 Logo a função geradora ordinária da sequência cn é Cz AzBz 1 7z 19z2 32z3 37z4 30z5 17z6 6z7 z8 Dessa forma existem por exemplo 19 formas de escolher 2 letras da palavra amasonho Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Por znAz nós representamos o coeficiente an de zn na expansão da série de potências de Az Não existe nenhum algoritmo que permita a extração dos coeficientes em todas as situações embora exista a fórmula geral via teorema de Taylor que é raramente útil na prática Para a grande maioria dos casos nós teremos que utilizar um raciocínio baseado em casos já conhecidos combinado com algumas poucas regras Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Por znAz nós representamos o coeficiente an de zn na expansão da série de potências de Az Não existe nenhum algoritmo que permita a extração dos coeficientes em todas as situações embora exista a fórmula geral via teorema de Taylor que é raramente útil na prática Para a grande maioria dos casos nós teremos que utilizar um raciocínio baseado em casos já conhecidos combinado com algumas poucas regras Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Por znAz nós representamos o coeficiente an de zn na expansão da série de potências de Az Não existe nenhum algoritmo que permita a extração dos coeficientes em todas as situações embora exista a fórmula geral via teorema de Taylor que é raramente útil na prática Para a grande maioria dos casos nós teremos que utilizar um raciocínio baseado em casos já conhecidos combinado com algumas poucas regras Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Por znAz nós representamos o coeficiente an de zn na expansão da série de potências de Az Não existe nenhum algoritmo que permita a extração dos coeficientes em todas as situações embora exista a fórmula geral via teorema de Taylor que é raramente útil na prática Para a grande maioria dos casos nós teremos que utilizar um raciocínio baseado em casos já conhecidos combinado com algumas poucas regras Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Por znAz nós representamos o coeficiente an de zn na expansão da série de potências de Az Não existe nenhum algoritmo que permita a extração dos coeficientes em todas as situações embora exista a fórmula geral via teorema de Taylor que é raramente útil na prática Para a grande maioria dos casos nós teremos que utilizar um raciocínio baseado em casos já conhecidos combinado com algumas poucas regras Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Regras para a extração de coeficientes linearidade zn Az Bz znAz znBz zn cAz cznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Regras para a extração de coeficientes linearidade zn Az Bz znAz znBz zn cAz cznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Regras para a extração de coeficientes linearidade zn Az Bz znAz znBz zn cAz cznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Regras para a extração de coeficientes linearidade zn Az Bz znAz znBz zn cAz cznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias multiplicação por constante czn Az 1 c znAz zn Acz cnznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias multiplicação por constante czn Az 1 c znAz zn Acz cnznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias multiplicação por constante czn Az 1 c znAz zn Acz cnznAz Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias multiplicação por uma potência de z multiplicação por uma potência de z znzbAz znbAz b Z convolução convolução zn Az Bz Σ zk Az znk Bz from k0 to n Exemplo Suponha que Az Bz1rz o que é an Exemplo Suponha que Az Bz 1 rz o que é an znAz zn Bz 1 rz sumk0 to n zkBz znk 1 1 rz sumk0 to n bk rnk No text extracted Exemplo Do cálculo nós temos que cos z eiz eiz 2 Suponha que Az cos z Quais são os elementos da sequência A regra da linearidade nós diz que Funções Geradoras Extração de coeficientes de Funções Geradoras Ordinárias Exemplo Do cálculo nós temos que cos z eiz eiz2 Suponha que Az cos z Quais são os elementos da sequência A regra da linearidade nós diz que zn cos z 12zneiz eiz 12zneiz 12zneiz in2n in2n in2n1 1n an 1n2n se n é par 0 se n é ímpar