Funcoes Geradoras - Resolvendo Relacoes de Recorrencia

Análise de Algoritmos Berilhes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico 1 Faça a relação válida para todo n 2 Multiplique ambos os lados da recorrência por zn e some sobre n 3 Avalie as somas de modo a determinar uma equação satisfeita pela função geradora ordinária 4 Resolva a equação de modo a encontrar uma fórmula explícita para a função geradora ordinária 5 Expanda a função geradora para encontrar uma fórmula fechada para os coeficientes Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico cont Notação criada por Kenneth E Iverson facilitará sobremaneira as manipulações algébricas Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico cont Notação criada por Kenneth E Iverson facilitará sobremaneira as manipulações algébricas A ideia consiste em colocar uma declaração que é falsa ou verdadeira entre colchetes e afirmar que o resultado é 1 se a declaração é verdadeira e 0 se esta é falsa Por exemplo Resolvendo Relações de Recorrência com Funções Geradoras Algoritmo Básico cont Notação criada por Kenneth E Iverson facilitará sobremaneira as manipulações algébricas A ideia consiste em colocar uma declaração que é falsa ou verdadeira entre colchetes e afirmar que o resultado é 1 se a declaração é verdadeira e 0 se esta é falsa Por exemplo p primo 1 se p é número primo 0 se p não é número primo Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Assuma que a relação de recorrência é an 0 se n0 1 se n1 5 an1 6 an2 se n 2 Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Assuma que a relação de recorrência é an 0 se n0 1 se n1 5 an1 6 an2 se n 2 an 5 an1 6 an2 n1 Passo 1 Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Assuma que a relação de recorrência é an 0 se n0 1 se n1 5 an1 6 an2 se n 2 an 5 an1 6 an2 n1 Passo 1 an zn 5 an1 zn 6 an2 zn n1 zn Passo 2 Exemplo Assuma que a relação de recorrência é an 0 se n 0 1 se n 1 5 an1 6 an2 se n 2 an 5 an1 6 an2 n 1 Passo 1 an zn 5an1 zn 6 an2 zn n 1 zn Passo 2 n0 an zn n0 5 an1 zn n0 6 an2 zn n0 n 1 zn Passo 2 Exemplo Assuma que a relação de recorrência é an 0 se n 0 1 se n 1 5 an1 6 an2 se n 2 an 5 an1 6 an2 n 1 Passo 1 an zn 5an1 zn 6 an2 zn n 1 zn Passo 2 n0 an zn n0 5 an1 zn n0 6 an2 zn n0 n 1 zn Passo 2 Az 5 z Az 6 z2 Az z Passo 3 Exemplo Assuma que a relação de recorrência é an 0 se n 0 1 se n 1 5 an1 6 an2 se n 2 an 5 an1 6 an2 n 1 Passo 1 an zn 5an1 zn 6 an2 zn n 1 zn Passo 2 n0 an zn n0 5 an1 zn n0 6 an2 zn n0 n 1 zn Passo 2 Az 5 z Az 6 z2 Az z Passo 3 Az z 1 5z 6z2 Passo 4 Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Az z 15z6z2 é a razão entre dois polinômios Pz Qz onde Pz z e Qz 1 5z 6z2 Por QRz nós denotamos o polinômio Qz refletido Dessa forma QRz z2 5z 6 As raízes QRz são z 3 e z 2Portanto Qz 1 3z1 2z Az z 1 3z1 2z Az c0 1 3z c1 1 2z Az z 1 3z1 2z c01 2z c11 3z 1 3z1 2z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo c0 c1 0 2c0 3c1 1 Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo c0 c1 0 2c0 3c1 1 Cuja solução é c0 1 e c1 1 Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo c0 c1 0 2c0 3c1 1 Cuja solução é c0 1 e c1 1 Az 113z 112z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo c0 c1 0 2c0 3c1 1 Cuja solução é c0 1 e c1 1 Az 113z 112z zn Az zn113z 112z Resolvendo Relações de Recorrência com Funções Geradoras Exemplos Exemplo c0 c1 0 2c0 3c1 1 Cuja solução é c0 1 e c1 1 Az 113z 112z zn Az zn 113z 112z zn Az zn 113z zn 112z an 3n 2n