Técnicas Avançadas de Contagem

Neste capítulo vamos descrever como usar Maple para trabalhar com três temas importantes na contagem: relações de recorrência, inclusão-exclusão e funções geradoras. Começamos por descrever como Maple pode ser usado para resolver relações de recorrência, incluindo a relação de recorrência para a sequência de números de Fibonacci. Em seguida, mostramos como resolver o enigma da Torre de Hanói e encontramos o número de movimentos necessários para n discos. Descrevemos como Maple pode ser utilizada para resolver as relações lineares homogêneas de recorrência com coeficientes constantes, bem como as relações de recorrência não-homogêneas relacionadas. Depois de descrever como resolver estes tipos especiais de relações de recorrência com Maple, vamos mostrar como usar a resolução geral de recorrência Mapple. Nós ilustramos o uso dessa resolução geral demonstrando como usa-la para resolver divide and conquer relações de recorrência. Depois de estudar relações de recorrência, vamos mostrar como usar bordo para ajudar a resolver problemas usando o princípio da inclusão e exclusão. Ao fim, discutimos como Maple pode ser usado para trabalhar com funções geradoras, um tema abordado no Apêndice 3 no texto.

1. Relações de recorrência

Uma relação de recorrência descreve uma relação que um membro de uma sequência {${a_{n}}$} de valores tem de outro membro da seqüência que o precedem. Por exemplo, a famosa seqüência de Fibonacci {$F_{n}$} satisfaz a relação de recorrência

$F_{(n)}=F_{(n-1)}+F_{(n-2)}$

Juntamente com as condições iniciais $F_{1}=1$ e $F_{2}=1$, esta relação é suficiente para definir toda a seqüência $F_{n}$

Em geral, podemos pensar em uma relação de recorrência como uma relação do formulário

$r_{n}=f(r_{n-1},r_{n-2},\ldots ,r_{n-k})$,

em que cada termo $r_{n}$ da sequência depende de um número k dos termos que o precedem na seqüência. Por exemplo, para a sequência de Fibonacci, a função F é $f(x,y)=y+x$.

Para entender como podemos trabalhar com relações de recorrência em Maple, temos de parar por um momento e perceber que uma sequência $r_{n}$ de valores (números, matrizes, círculos, funções, etc.) é apenas uma função cujo domínio passa a ser o conjunto de inteiros (geralmente positivos). Se queremos levar este ponto de vista (e nós queremos!), então o $r$ enésimo termo $r_{n}$ de uma sequência de {$r_{n}$} seria convencionalmente escrito como $r_{(}n)$, e gostaríamos de referir à função r. Desta forma, podemos pensar na seqüência {$r_{n}$} como uma forma de representar uma função $r$ cujo domínio é o conjunto de números inteiros positivos, e cujo valor no número $n$ é apenas $r_{n}=r(n)$. Isto apenas equivale a uma mudança na notação; não há nada mais do que isso.

Uma vez que esta alteração na notação for feita, então é fácil ver como representar uma relação de recorrência como um procedimento Maple tendo argumentos inteiros.

No capítulo 3 descobrimos como representar de forma eficiente a seqüência de Fibonacci pelo procedimento:

Fibonacci := proc(n::posint) option remember;
if   n = 1  or n = 2 then RETURN( 1 ); fi;
Fibonacci2(n-1) + Fibonacci2(n-2);

Lembre-se que a primeira linha deste procedimento instrui a Maple de lembrar que quaisquer sejam os valores do processo já foram calculado na sessão atual.

Às vezes, apesar de nossos melhores esforços, uma aplicação recursiva de um algoritmo pode ser muito caro, simplesmente devido à sua própria natureza. A aplicação recursiva pode ser evitado se podemos encontrar uma fórmula explícita para o termo geral da recorrência. O processo de encontrar uma fórmula explícita é referido como resolver a recorrência. Na próxima seção, veremos como usar Maple para fazer isso por certos tipos de relações de recorrência.

1.1 Torre de Hanoi

O famoso enigma conhecido como Torre de Hanoi é discutido no texto, onde a relação de recorrência:

$H_{n}=2H_{n-1}+1,H_{1}=1$

é derivada, em que $H_{n}$ indica o número de movimentos necessários para resolver o enigma para n discos. Como discutido no texto, este tem a solução $H_{n}=2^{n}-1$

Mais tarde, veremos como usar Maple para obter esse resultado de forma simples.

Além de resolver para o número de movimentos necessários para resolver o enigma das Torres de Hanói para para n discos, podemos ilustrar a solução escrevendo um programa em Maple para calcular os movimentos necessários para resolver o dito problema, e descrevendo-os para nós. Nós vamos escrever um pequeno programa em Maple que consiste em três procedimentos: o principal programa de Hanói, a rotina utilitária PrintMove, e o mecanismo recursivo do programa TransferDisk, que faz a maioria do trabalho.

A parte mais fácil de escrever é a função PrintMove, que apenas mostra para nós a mudança para fazer em um determinado passo.

  PrintMove: = proc (src :: string, dest :: string)
  printf (`Mova disco de peg% s para peg% s`, src, dest);
  end:
  

Aqui, nós apenas chamamos o comando printf da biblioteca do Maple, que pode ser usado para saída formatada. A função printf tem uma sintaxe de chamada complexa; consulte a ajuda online para obter detalhes e informações adicionais. (Nota: Se você estiver familiarizado com a função printf em C, então você vai achar que a versão do Maple do printf é bem semelhante. Neste caso, os símbolos %s acima são substituídos pelos valores de string do segundo e terceiro argumentos, respectivamente.)

Em seguida, o procedimento recursivo TransferDisk faz a maior parte do trabalho para nós. Esta função modela a ideia de transferir um disco de um Peg para outro. Mas, porque é recursivo, precisamos fornecer a ele, como um argumento, o número total de discos a serem tratados em cada chamada.

 TransferDisk := proc(src::string, via::string, 
 dest::string, ndisks::posint)
     if ndisks = 1 then
         PrintMove(src, dest);
     else
         TransferDisk(src, via, dest, ndisks -1);
         PrintMove(src, dest);
         TransferDisk(via, dest, src, ndisks -1);
     fi;
 end:

Finalmente, empacotamos em uma procedure de alto nível, Hanoi, proporcionando assim uma interface para o mecanismo recursivo.

 Hanoi := proc(ndisks::posint)
   if ndisks < 1 then
       printf(`What's wrong with this picture?`);
   else
       TransferDisk(`A`, `B`, `C`, ndisks);
   fi;
 end:

Nosso programa Hanoi consegue exibir uma solução específica para o Enigma das Torres de Hanoi para qualquer número ndisk de discos.

 Hanoi(2);
 Hanoi(3);

Tente experimentar com diferentes valores ndisk para ter uma noção do quão grande o problema se torna mesmo para valores moderadamente grandes de ndisks.

2. Resolução de recorrências com Maple

Agora que sabemos como implementar relações de recorrência em Maple, e temos trabalhado com eles um pouco, vamos ver como usar Maple para resolver certos tipos de relações de recorrência.

Maple tem um poderoso solucionador de recorrência, rsolver, que discutiremos mais tarde. A sua utilização, no entanto, pode obscurecer algumas das ideias importantes que estão envolvidas. Portanto, devemos primeiro usar algumas das instalações mais rudimentares do Maple para resolver certos tipos de relações de recorrência, um passo de cada vez.

Dada uma seqüência definida recursivamente ${r_{n}}$, o que nós gostaríamos é encontrar algum tipo de fórmula, envolvendo apenas o índice n (e, talvez, outras constantes fixas e funções conhecidas) que não dependem do conhecimento da valor de $r_{k}$, por qualquer índice k.

Para começar, vamos considerar relações de recorrência que são lineares, homogêneas, e que têm coeficientes constantes; ou seja, eles têm a forma

$r_{n}=a_{1}r_{n-1}+a_{2}r_{n-2}+\cdots +a_{k}r_{n-k}$

onde $a_{1},a_{2},\ldots ,a_{k}$ são constantes reais e $a_{k}$ é diferente de zero. Lembre-se que o inteiro k é chamado de grau da relação de recorrrência. Para ter uma núnica solução, pelo menos o k inicial deve sere especificado.

O método geral para resolver tal relação de recorrência envolve encontrar as raízes de seu polinômio característico.

$x^{k}-a_{1}x^{k-1}-a_{2}x^{k-2}-\cdots -a_{k-1}x-a_{k}$

Quando este polinômio tem raízes distintas, todas as soluções são combinações lineares das enésimas (palavra para número ordinal) potências dessas raízes. Quando não são raízes repetidas, a situação é um pouco mais complicado, como veremos.

Para começar, vamos considerar uma relação de recorrência linear homogênea com coeficientes constantes de grau dois:

$r_{n}=2r_{n-1}+3r_{n-2}$

sujeitos às condições iniciais

$r_{1}=4$ and $r_{2}=2$

Então sua equação caracerística é:

$x^{2}-2x-3$

Para resolver a relação de recorrência, temos de resolver para as raízes dessa equação. Usar Maple faz disso algomuito fácil; nós usamos a função solve em Maple para fazer isso.

 solve (x ^ 2-2 * x - 3 = 0, x);

A sintaxe diz à função que queremos os valores da variável x que satisfazem a equação quadrática.

$x^{2}-2*x-3=0.$

Agora que o Maple aponta que as soluções são $x=3$ e $x=-1$, podemos escrever a forma de a solução para a recorrência como

$r_{n}=\alpha 3^{n}+\beta (-1)^{n}$

onde \alpha e \beta são constantes que ainda temos de determinar. Podemos usar Maple para determinar as constantes \alpha e \beta. Uma vez que as condições iniciais são $r_{1}=4er_{2}=2$, sabemos que a nossa relação de recorrência deve satisfazer as seguintes duas equações.

$3\alpha -\beta =4$ $3^{2}\alpha +\beta =2$

2.1. Uma relação de recorrência linear homogênea com coeficientes constantes

Agora vamos generalizar o que temos feito e escrever um procedimento em Maple para resolver uma relação de recorrência geral homogênea com coeficientes constantes, de grau 2, considerando que as raízes do polinômio característico da relação de recorrência são distintos. Vamos escrever um procedimento RecSol2 que resolve a recorrência

$r_{n}=ar_{n-1}+br_{n-2}$

sujeito às condições iniciais

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{1} = u \hspace{3em}\mbox{and}\hspace{3em} r_{2} = v }

e, em seguida, retorna um procedimento que pode ser utilizado para calcular termos da sequência. Por enquanto, suponha que o polinômio característico $x^{2}-ax-b$ tem duas raízes distintas. Então, tudo o que o nosso procedimento precisa fazer é repetir os passos que fizemos manualmente no nosso exemplo anterior.

 RecSol2 := proc(a, b, u, v) 
   local evals, S, alpha, beta, ans , n;

Resolve-se a equação característica

 evals := solve(x^2 - a * x - b = 0, x);

Depois, resolve-se o sistema de equações lineares

   S := solve(alpha * evals[1] + beta * evals[2] = u,
       alpha * evals[1]^2 + beta * evals[2]^2 = v,
       alpha,beta);
   ans := subs(S,alpha*evals[1]^n + beta*evals[2]^n);
   RETURN( unapply( ans , n ) );
end:

Paraobservar como funciona, iremos tentar alguns casos de teste. Paraconstruir uma função para calcular a sequencia Fibonacci chamamos nosso novo procedimento:

 f := RecSol2(1,1,1,1,5);

O procedimento resultante ode ser usado para calcular o termo geral da sequencia Fibonacci.

 f(n);

Da mesma forma, os primeiros cinco números Fibonacci podem ser calculados da seguinte forma:

 seq(simplify(f(n)), n = 1..10);

Agora apresentamos uma resolução que pode lidar com o caso de raízes repetidas.

Antes de olharmos para a nova versão do RecSol2, vamos olhar para um exemplo envolvendo uma relação de recorrência com um valor double próprio (raiz de seu polinômio característico). A relação de recorrência

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_} {n = 4 r_ {N-1} - 4 r_ {N-2} }

tem a equação característica

 char_eqn := x^2 - 4 * x + 4 = 0;

com eigenvalues?????

 evals := [solve(char_eqn, x)];

No geral, para testar um eigenvalue repetido, que é o caso para este exemplo, apenas testamos se

 evalb(evals[1] = evals[2]);

(Nota: Nós não requeremos o uso de EVALB em uma instrução condicional já que expressões são automaticamente avaliados como booleans.) Se chamarmos a raiz dupla (2 neste caso) $\ lambda$, então a relação de recorrência tem a solução explícita

$r_{n}=\alpha \lambda ^{n}+n\beta \lambda ^{n}$

para todos os positivos inteiros n, e para algumas constantes $\alpha$ and $\beta$. Assumir as condições iniciais de $r_{1}=1andr_{2}=4$, o conjunto S de equações a resolver é:

 S := alpha * evals[1] + beta * evals[2] = 1,
       alpha * evals[1]^2 + 2* beta * evals[2]^2 = 4;

Como antes, para obter as soluções, digitamos:

 rsols := solve(S, alpha, beta);

É neste ponto que a diferença com o caso de raizes distintas aparece. O nth termo da sequencia, quando á um double eigenvalue, é dado ṕor:

 subs(rsols , alpha * evals[1]^n + n * beta * evals[1]^n );

Os passos feitos neste exemplo são bem gerais Um procedimento geral para resolver uma recorrência de dois termos da forma r(n) = a r(n-1) + b r(n-2), com os valors iniciais values r(1) = u and r(2) = v é:

 RecSolver2 := proc(a,b,u,v)
   local ans, evals, S, alpha, beta, rsols, n;

resolve a equação característica

 evals := solve(x^2 - a * x - b = 0, x);

resolve o sistema de equações lineares

   S := alpha * evals[1] + beta * evals[2] = u,
       alpha * evals[1]^2 + beta * evals[2]^2 = v;
   rsols := solve(S, alpha, beta);
   if evals[1] = evals[2] then # repeated roots
     ans := subs(rsols,alpha*evals[1]^n + beta*n*evals[1]^n);
   else
     ans := subs(rsols,alpha*evals[1]^n + beta*evals[2]^n );
   fi;
   RETURN( unapply(ans , n ) );
 end:

Esta versão da nossa resolução testa primeiro raizes repetidas, e então faz o calculo apropriado baseado no resultado. É chamado da mesma forma que o RecSol2:

 g := RecSolver2(4,-3,1,2);
 i :='i': seq(simplify(g(i)), i=1..10);

Isto dá os dez primeiros termos da sequência definida pela relação de recorrência $r_{n}=4r_{N-1}-3*r_{N-2}$, com condições iniciais $r_{1}=1eR_{2}=2$.

Para resolver a recorrência <maaath> r_{n} = {N -r_-1} - r_ {N-2}</math>, com condições iniciais $r_{1}=1eR_{2}=2$, usamos A solução e os primeiros 100 termos desta sequência são

 h := RecSolver2(-1,-1,1,2);
 i := 'i': seq(simplify(h(i)),i=1..10);

Perceba que o padrão que aparece se substituirmos as condições iniciais $r_{1}=1andr_{2}=2$ com constantes simbólicas.

 k := RecSolver2(-1, -1, lambda, mu);
 i := 'i': seq(simplify(k(i)),i=1..10);

2.2. Relações de recorrência heterogêneas

Nós temos, até agora, discutido relações de recorrência lineares homogêneas com coeficientes constantes. No entanto, as técnicas utilizadas para resolvê-los podem ser extendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma

math>\ alpha_ {n} r_ {n} + \ alpha_ {n-1} r_ {n-1} + \ cdots + \ alpha_ {nk} {r_ nk} = c_ {n} </math>

onde $\ alpha_{n},\ alpha_{n-1},\ ldots,\ alpha_{nk}ec_{n}$ são constantes. A única nova problemática é que, aqui, o Failed to parse (syntax error): {\displaystyle c_ {n}<math> não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada <math>c_ {n}} é zero é homogênea, por isso as relações homogêneas são apenas um caso especial deste tipo mais geral. Para resolver a recorrência mais geral, precisamos fazer duas coisas:

1) Encontrar uma solução específica para a recorrência heterogênea

2) Resolver a recorrência homogênea correspondente.

A recorrência homogênea correspondente é apenas a obtida substituindo a sequência Failed to parse (syntax error): {\displaystyle \ c_ {{n} \} } pela seqüência zero:

$\ alpha_{n}r_{n}+\ alpha_{n-1}r_{n-1}+\ cdots+\ alpha_{nk}{r_{n}k}=0$

Então, nós já sabemos como fazer o segundo passo.

O primeiro passo é mais difícil, mas com a ajuda do Maple, ele manejável.

 rSolve (R (0) = 0, r (n) = 3 * r (n-1) + 3 ^ N, r (n));
 normal (%, expanded);

Isso nos diz que $r_{n}=n3^{n}$ é uma solução para a relação de recorrência $r_{n}=3r_{n-1}+3^{n}$. Agora, todas as soluções são obtidos por adição de uma solução para este conjunto de soluções da recorrência homogênea correspondente.

 rSolve (r (n) = 3 * r (n-1), r (n));
 % + * 3 N ^ N;

Se temos um valor inicial para $r_{0}$, então nós temos uma solução completa.

Agora vamos resolver a Torre de Hanói

Failed to parse (syntax error): {\displaystyle H_} {n = 2H_ {N-1} + 1}

o que dá o número de movimentos necessários para resolver o enigma da Torres de Hanói com n discos. Lembre-se que $H_{1}=1.$ A relação de recorrência homogênea associada é

$h_{n}=2h_{n-1}$

com polinômio característico

$x-2$

A única raiz disso é 2, portanto, todas as soluções da relação de recorrência homogênea têm a forma

$h_{n}=\ alpha2^{n-1}$

para alguma constante $\ alfa$. (A potência de 2 é N-1, em vez de N, porque a recorrência começa no 1 em vez de 0.) Soluções para a H são obtidos a partir das soluções para h por adição de uma solução particular para H. Agora, H tem a solução constante $H_{N}}={-1$, para todo n, então todas as soluções para a H são da forma

$H_{n}=\ alpha2^{n}-1$

Usando a condição inicial

$H_{1}=1$

podemos resolver para $\ alpha$ como se segue.

 solve (alfa * 2 ^ 1 - 1 = 1, alfa);

Assim, a solução para as Torres de Hanói é $H_{n}=2^{n-1}-1$.

2.3. Resolvedor de recorrências em Maple

Agora que vimos como é possível usar Maple para implementar um algoritmo para resolver relações de recorrência simples, é hora de introduzir próprios utilitários do Maple para trabalhar com relações de recorrência. Já vimos o comando Maple solve para trabalhar com equações e sistemas de equações polinomiais. Da mesma forma, há um comando rSolve em Maple, que é especialmente projetado para lidar com relações de recorrência. É uma versão sofisticada de nosso procedimento RecSol2, que pode lidar com relações de recorrência de grau arbitrário, e pode lidar com raízes repetidas, bem como relações de recorrência não-lineares. Para usar rSolve, você precisa dizer a ele qual é a relação de recorrência, e algumas condições iniciais. Você também deve especificar o nome da função recursiva para resolver. Por exemplo, para resolver a recorrência Fibonacci, você pode digitar

 rSolve (f (n) = f (n-1) + f (n-2), F (0) = 0, f (1) = 1, f (n));
 normal (%, expanded);

Não é realmente necessário especificar as condições iniciais para uma relação de recorrência. Se eles não estiverem presentes, o Maple ainda vai resolver a equação, inserindo constantes simbólicas (aqui, G (0) e g (1)) em lugar das constantes numéricas, como o exemplo a seguir ilustra.

 rSolve (g (n) = 2 * g (n-1) - 6 * g (n-2), g (n));

Vemos, nesta fórmula, que Maple utiliza o símbolo I para denotar a unidade imaginária $(\ sqrt{-1})$.

A função rSolve pode lidar com vários tipos de diferenças de relações de recorrência. Em Maple V, Release 4, esta lista inclui:

1. relações de recorrência lineares com coeficientes constantes

2. sistemas de relações de recorrência lineares com coeficientes constantes

3. dividir e conquistar???? relações de recorrência com coeficientes constantes

4. muitas relações de recorrência lineares de primeira ordem

5. algumas relações de recorrência não-lineares de primeira ordem

As capacidades do rSolve, como outras funções do Maple, estão constantemente a serem melhoradas e ampliadas. Se você tiver uma versão posterior do Maple você pode achar que a sua versão do rSolve tem capacidades para além das enumeradas acima. No entanto, rSolve não é um algo mágico para resolver todos os problemas; você pode facilmente encontrar relações de recorrência que o rSolve é incapaz de resolver. Quando rSolve é incapaz de resolver uma relação de recorrência, é simplesmente retorna unevaluated.

Muitas vezes é o caso que um problema, tal como apresentado, não dá qualquer indicação de que uma solução pode ser encontrada usando recorrências. Vamos ver como podemos usar Maple para resolver um problema real; isto é, um que não esteja explicitamente expresso como um que exige a utilização de recorrência para a sua solução. Em quantas regiões é o plano dividido por 10000 linhas, assumindo que nenhuma das duas linhas são paralelas, e nenhuma das três são coincidentes? Tal situação pode ocorrer, numa tentativa de modelar fissuras no fundo do oceano, ou em qualquer outra parte da superfície da terra.

Para começar, podemos tentar descobrir a resposta para um número menor de linhas. Assim, para generalizar o problema, poderemos perguntar o número de regiões produzidas por n linhas, onde n é um número inteiro positivo. É bastante óbvio que uma única linha (que corresponde ao caso em que n = 1) divide o plano em 2 regiões. Duas linhas, se não forem paralelas, pode ser facilmente vistas para dividir um plano em 4 regiões. (Duas linhas paralelas distintas produzem apenas três regiões.) Se chamarmos o número de regiões produzidas por n linhas, duas das quais são paralelas, e três das quais são coincidentes $r_{n}$, então temos $r_{1}=2$ e $r_{2}=4$. Até agora, ele está começando a se parecer com $r_{n}=n^{2}$. Mas não vamos ter pressa. O que acontece quando a situação se torna semeslhante semelhante a n = 3? A figura mostrada aqui é representativa da situação.

Figure: file = ch05 / 3lines.eps

Neste caso, o número $R_{3}$ das regiões é 7, de modo que a estimativa inicial que$R_{n}$ é $n^{2}$ não pode ser certa. Para encontrar $r_{4}$, temos de acrescentar uma quarta linha para o diagrama. Isto sugere tentar calcular $r_{4}$ em termos de $r_{3}$, para que possamos pensar em Failed to parse (syntax error): {\displaystyle \ {r_ {n} \} } como uma relação de recorrência. A figura mostra que a situação parece quando uma quarta linha é adicionada a três linhas existentes.

Figure: file = ch05 / 4lines.eps

A partir dos pressupostos que nem duas das linhas podem ser paralelas e que nenhuma das três passam através de um único ponto, segue-se que a nova linha deve interceptar cada uma das três linhas existentes em exatamente um ponto. Isto significa que a nova linha passa através de exatamente três das regiões formadas pelas três linhas originais. Cada região que é atravessada é dividida em duas zonas, de modo que o número total de novas regiões adicionados através da adição da quarta linha é 3. Assim, $R_{4}=r_{3}+3$. Argumentos semelhantes para uma configuração geral de linhas revelam que $R_{n}$ satisfaz a relação de recorrência

$R_{n}=N-R_{1}+(n-1)$

Além disso, já calculamos a condição inicial $r_{1}=2$. Este é o suficiente para resolver esta recorrência.

 rSolve (
   r (n) = r (n-1) + (n-1),

   R (1) = 2,

 r (n));
 simplify(%);

2.4. Relações de dividir e conquistar

Um bom exemplo de relações de dividir e conquistar é a fornecida pelo algoritmo de busca binária. Aqui, vamos considerar uma aplicação prática deste algoritmo em uma implementação de uma busca binária em uma lista ordenada de números inteiros. O algoritmo procura por chave no IList.

 BinSearch := proc(ilist::list(integer), key::integer)
   local mid, lo, hi;
   hi := nops(ilist);
   lo := 0;
   while hi - lo > 1 do
     mid := floor((lo + hi) / 2);
       if key <= ilist[mid] then hi := mid;
     else lo := mid; fi;
   od;
   if ilist[hi] = key then RETURN(hi);
   else RETURN(false); fi;
 end:

A variável IList é a lista de números inteiros para a busca, e o parâmetro key é o número inteiro para procurar. A posição na lista é retornada se ele for encontrado, e o valor false é retornado em caso contrário. Para testar Binsearch, usamos o seguinte aço com uma lista de amostras para pesquisa.

 a := [3,5,7,12,34,546,5324,5346753];
 for i in a do
   if a[BinSearch(a, i)] <> i then
     print(`Socks for President in '96!`);
   fi;
 od;

Infelizmente para Socks, o nosso programa funcionou muito bem.

Vamos agora fazer a análise do algoritmo para ver como relações de recorrência divide and conquer são geradas. Em geral, uma relação de recorrência do tipo dividir e conquistar tem a forma

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_} {n = a r_ {n / K} + b }

para algumas constantes a, K e b. Agora, a rotina Maple rSolve não tem absolutamente nenhuma dificuldade para lidar com até mesmo o tipo mais geral de relação dividir e conquistar.

 rSolve (r (n) = a * r (n / k) + b, r (n));

Se sabemos que, dado $r_{1}=4$, então podemos calcular

 Subs (R (1) = 4,%);

Cada chamada para o algoritmo de busca binária produz listas a = 2, e cada um é metade do tamanho da lista original (k = 2). Portanto, o multiplicador e o período, no caso de um algoritmo de busca binária são ambos iguais a 2 e, portanto, obtemos

 Subs (a = 2, k = 2,%);

Finalmente, se sabemos que b = 2, podemos calcular

 Subs (b = 2,%);
 simplify(%);

4. Funções geradoras

Funções geradoras são ferramentas poderosas para modelar conjuntos de objetos e suas construções. Por exemplo, se um conjunto de objetos é construído a partir de dois outros através da realização de um produto cartesiano de dois conjuntos subjacentes, em seguida, a função geradora para o novo conjunto é muitas vezes apenas o produto das funções geradoras pelos dois conjuntos subjacentes. Assim, saber como um conjunto é construído pode nos ajudar a construir a sua função geradora.

Se você pensar nas funções geradoras como polinômios. Em seguida, cada objeto do conjunto original está representado nesta expansão do produto dos dois polinômios por um monômio como $x^{5}$. Várias combinações diferentes pode levar a um $x^{5}$. O coeficiente de $x^{5}$ na função geradora expandido indica o número de tais objetos no novo conjunto.

Os coeficientes da função geradora expandida forma uma sequência de números - o número de objetos em seu conjunto de cada tamanho. Assim, muitas vezes nos referimos a uma função geradora como a função geradora para a sequência --- seus coeficientes. Em particular, tais sequências também podem ser descritas por relações de recorrência. Aqui, vamos discutir como usar as funções geradoras para nos ajudar a resolver essas relações de recorrência.

A função geradora $g(x)$ para uma sequência Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_ {{n} \}} é a série de potência formal

$\ sum_{k=0}^{\ infty}r_{k}x^{k}=r_{0}+r_{1}x+r_{2}x^{2}+r_{3}x^{3}+\ cdots+r_{n}x^{n}+\ cdots$

Ele é chamado formal, porque não estamos mesmo interessados em avaliá-lo como uma função de x. Todo o nosso foco está em encontrar fórmulas para seus coeficientes. Em particular, isto significa que não há problemas de convergência a serem investigados.

Maple fornece extensas habilidades para a manipulação de séries de potências formais (ou seja, as funções geradoras). Pertencem ao pacote powseries do Maple, de modo que parar acessa-las, você deve carregar este pacote.

 with (powseries);

A primeira coisa que precisamos fazer é aprender a criar uma série de potência. Para isso, o Maple fornece a função powcreate. Ela toma como argumentos uma seqüência de equações que definem o coeficiente geral. As equações especificam uma maneira de calcular o coeficiente kth em $\ sum_{k=0}^{\ infty}a_{k}x^{k}$. Por exemplo, a função exponencial formal, o que tem de representação de série de potência

$\ exp(s)=\ sum_{n=0}^{\ infty}\ frac{s^{n}}{n!}$

pode ser criado em Maple emitindo a chamada

 powcreate (e (n) = 1 / N!);

O que torna isto especialmente útil para trabalhar com relações de recorrência é que o coeficiente geral não precisa ser especificado na forma fechada (como foi acima). Você pode especificar uma relação de recorrência satisfeita com os coeficientes, em conjunto com suficientemente muitas condições iniciais para garantir uma solução única para a recorrência.

Vamos ver um exemplo disso. Para criar a função geradora para a sequência de Fibonacci, a qual é definida pela relação de recorrência

$F_{n}=F_{n-1}+F_{N-2}\ hspace{3EX}\ mbox{e}\ hspace{3EX}F(0)=1,F(1)=1$

podemos entrar

 powcreate (f (n) = f (n - 1) + f (n - 2), F (0) = 1, F (1) = 1);

Agora, a única informação interessante em uma função geradora é a seqüência de seus coeficientes. Maple fornece uma maneira de acessar um coeficiente arbitrário em uma série de potências formal. Isto é feito como se segue. Para Maple, cada série de potências formal é, na verdade, um procedimento, que leva argumentos inteiros. O valor retornado por uma série de potências formal, quando dado um inteiro n como argumento é o coeficiente de $x^{n}$ . Assim, por exemplo, o quinto número de Fibonacci pode ser produzido chamando a série de potência formal f acima com '5' como argumento.

 f (5);

De fato, o coeficiente geral pode ser obtido fazendo passar o argumento especial _k

 F (_K);

Para exibir uma função geradora, é melhor usar a função tpsform do Maple. Esse procedimento converte uma série de potências formal sobre uma série de potência truncada de grau especificado. Por exemplo, para exibir os dez primeiros termos da função geradora para a nossa seqüência de Fibonacci, podemos usar tpsform, como se segue.

 tpsform (F, X, 9);

Funções geradoras são mais do que apenas uma forma conveniente para representar sequências numéricas e seus conjuntos de objetos associados. Eles são uma ferramenta poderosa para a solução de relações de recorrência, bem como outros tipos de problemas de contagem. Este poder deriva de nossa capacidade de manipulá-los, mais ou menos, como séries de potência comuns de Cálculo e de interpretar essas manipulações em termos de sua ação sobre os conjuntos.

Assim como é feito em Cálculo com a série de potência comum, funções geradoras podem ser adicionadas, multiplicadas, multiplicadas por escalares e polinômios, compostas, avaliadas e mesmo diferenciadas e integradas. É importante reconhecer que estamos falando aqui de diferenciação formal e integração --- não há limites para se preocupar.

É ainda mais importante, associar estas operações algébricas com operações combinatórias que você pode realizar no conjunto de objetos implicitamente representadas pela função geradora. Por exemplo, considerando a união de dois conjuntos disjuntos de objetos corresponde a adição de suas funções geradoras. Cada uma das operações são muitas vezes melhor pensadas em termos do seu efeito sobre os monômios que representam os objetos individuais do conjunto subjacente de objetos. Por exemplo, se um único objeto feito de de cinco sub-objetos é representado por $x^{5}$, então existem exatamente 5 maneiras de escolher uma dessas sub-objetos para remoção. O conjunto de objetos produzidos através disso de todas as maneiras possíveis seriam representados por $5x^{4}$. Assim, em um sentido muito real, esta operação combinatória de dividir um único objeto desta forma corresponde à operação conhecida de diferenciação em sua função geradora.

Todas as operações mais comuns que você pode realizar em séries de potência comum têm interpretações combinatórias úteis e podem ser realizadas em nossas séries de potência formal. Em cada caso, pode especificar o que tal efeito terá sobre o coeficiente da série. Maple fornece habilidades para a realização de todas estas manipulações, e muito mais.

Estas habilidades são melhor demonstradas pelo trabalhar através de um exemplo. Usaremos Maple para resolver a recorrência Fibonacci com funções geradoras.

Se multiplicarmos ambos os lados da recorrência Fibonacci

$F_{n}=F_{n-1}+F_{N-2}$ por $x^{n}$, obtemos

$F_{n}x^{n}=f_{n-1}x^{n}+f_{n-2}x^{n}$

Agora soma de n = 1 rende

$\ sum_{n=1}^{\ infty}f_{n}x^{n}=\ sum_{n=1}^{\ infty}f_{n-1}x^{n}+\ sum_{n=1}^{\ infty}{f_{n}-2}x^{n}$

O lado esquerdo desta equação difere da função geradora apenas o primeiro termo (em que n = 0), e as somas no lado direito podem ser fatoradas, assim que obtemos

$g(x)-1=XG(x)+x^{2}g(x)$

Agora, resolver esta equação para g (x) produz

$g(x)=\ frac{-1}{x^{2}+x-1}$