Open main menu

Changes

no edit summary
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 Começaremos 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 mostraremos como resolver o enigma da Torre de Hanói Hanoi e encontramos o número de movimentos necessários para n discos. Descrevemos Descreveremos 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 MappleMaple. Nós ilustramos o uso dessa resolução geral demonstrando como usausá-la para resolver divide and conquer relações de recorrênciacom o método “Divide and Conquer”. Depois de estudar relações de recorrência, vamos mostrar como usar bordo Maple para ajudar a resolver problemas usando o princípio da inclusão e exclusão. Ao fim, discutimos discutiremos 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 {<math>{a_n}</math>} de valores tem de outro membro da seqüência sequência que o precedem. Por exemplo, a famosa seqüência sequência de Fibonacci {<math>F_n</math>} satisfaz a relação de recorrência
<math>F_{(n)} = F_{(n-1)} + F_{(n-2)}</math>
Juntamente com as condições iniciais <math>F_1 = 1 </math> e <math>F_2 = 1 </math>, esta relação é suficiente para definir toda a seqüência sequência <math>F_n</math>
Em geral, podemos pensar em uma relação de recorrência como uma relação do formulário
<math>r_{n} = f(r_{n-1}, r_{n-2}, \ldots , r_{n-k})</math>,
em que cada termo <math>r_{n}</math> 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 é <math>f(x, y) = y + x</math>.
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 <math>r_{n}</math> 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 <math>r</math> enésimo termo <math>r_{n}</math> de uma sequência de {<math>r_{n}</math>} seria convencionalmente escrito como <math>r_(n)</math>, e gostaríamos de referir à função r. Desta forma, podemos pensar na seqüência sequência {<math>r_ {n}</math>} como uma forma de representar uma função <math>r</math> cujo domínio é o conjunto de números inteiros positivos, e cujo valor no número <math>n</math> é apenas <math>r_{n} = r(n)</math>. 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 sequência de Fibonacci pelo procedimento:
<pre>Fibonacci := proc(n::posint) option remember;
if n = 1 or n = 2 then RETURN( 1 ); fi;
Fibonacci2(n-1) + Fibonacci2(n-2);</pre>
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.
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 Hanoi 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-que, posteriormente, os para nósdescreverá. Nós vamos escrever um pequeno programa em Maple que consiste em três procedimentos: o principal programa de '''HanóiHanoi''', a rotina utilitária '''PrintMove''', e o mecanismo recursivo do programa '''TransferDisk''', que faz a maioria do trabalho.
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 pino para outro. Mas, porque é uma vez sendo recursivo, precisamos fornecer a ele, como um argumento, o número total de discos a serem tratados em cada chamada.
Finalmente, empacotamos em uma procedure compilamos como um procedimento de alto nível, '''Hanoi''', proporcionando assim uma interface para o mecanismo recursivo.
Hanoi := proc(ndisks::posint)
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 mecanismo 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 sequência definida recursivamente <math> {r_ {n}} </math>, 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 <math>r_{k}</math>, 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
<math> r_{n} = a_{1}r_{n-1} + a_{2}r_{n-2} + \cdots + a_{k}r_{n-k} </math>
onde <math> a_{1}, a_{2}, \ldots , a_{k} </math> são constantes reais e <math> a_{k} </math> é diferente de zero. Lembre-se que o inteiro k é chamado de grau da relação de recorrrência. Para ter uma núnica ú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.
<math> r_{1} = 4 </math> and <math> r_{2} = 2 </math>
Então sua equação caracerística característica é:
<math> x^{2} - 2x - 3 </math>
Para resolver a relação de recorrência, temos de resolver para as raízes dessa equação. Usar Maple faz disso algomuito algo muito fácil; nós usamos a função solve em Maple para fazer isso.
solve (x ^ 2-2 * x - 3 = 0, x);
Paraobservar Para observar como funciona, iremos tentar alguns casos de teste. Paraconstruir De modo a construir uma função para calcular a sequencia Fibonacci , chamamos nosso novo procedimento:
f := RecSol2(1,1,1,1,5);
O procedimento resultante ode pode ser usado para calcular o termo geral da sequencia Fibonacci.
f(n);
char_eqn := x^2 - 4 * x + 4 = 0;
com eigenvalues?????autovalor
evals := [solve(char_eqn, x)];
No geral, para testar um eigenvalue autovalor repetido, que é o caso para este exemplo, apenas testamos se
evalb(evals[1] = evals[2]);
rsols := solve(S, alpha, beta);
É neste ponto que a diferença com o caso de raizes raízes distintas aparece. O nth enésimo termo da sequenciasequência, quando á um double eigenvalueautovalor, é dado ṕorpor:
subs(rsols , alpha * evals[1]^n + n * beta * evals[1]^n );
end:
Esta versão da nossa resolução testa primeiro raizes raízes repetidas, e então faz o calculo cálculo apropriado baseado no resultado. É chamado da mesma forma que o RecSol2:
g := RecSolver2(4,-3,1,2);
Isto dá os dez primeiros termos da sequência definida pela relação de recorrência <math> r_{n} = 4r_ {N-1} - 3 * r_ {N-2} </math>, com condições iniciais <math> r_{1} = 1 e R_ {2} = 2 </math>.
Para resolver a recorrência <maaathmath> r_{n} = {N -r_-1} - r_ {N-2}</math>, com condições iniciais <math> r_{1} = 1 e R_ {2} = 2 </math>, usamos A solução e os primeiros 100 termos desta sequência são
h := RecSolver2(-1,-1,1,2);
'''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 estendidas 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 <math>\ /alpha_ {n}, \ /alpha_ {n-1}, \ ldots, \ /alpha_ {nk} e c_ {n} </math> são constantes. A única nova problemática é que, aqui, o <math>c_ {n}</math> não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada <math>c_ {n}</math> é 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 <math>\ c_ {{n} \} </math> pela seqüência sequência zero:
<math>\ /alpha_ {n} r_ {n} + \ /alpha_ {n-1} r_ {n-1} + \ cdots + \ /alpha_ {nk} {r_ nk} = 0 </math>
Então, nós já sabemos como fazer o segundo passo.
Se temos um valor inicial para <math>r_ {0}</math>, então nós temos uma solução completa.
Agora vamos resolver a Torre de HanóiHanoi
<math>{H_} {n = 2H_ {N-1} + 1</math>
o que dá o número de movimentos necessários para resolver o enigma da Torres de Hanói Hanoi com n discos. Lembre-se que <math>H_ {1} = 1.</math> A relação de recorrência homogênea associada é
<math>h_ {n} = 2 h_ {n - 1}</math>
<math>h_ {n} = \ alpha 2 ^ {n - 1}</math>
para alguma constante <math>\ /alfa </math>. (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 <math>H_ N} = {-1</math>, para todo n, então todas as soluções para a H são da forma
<math>H_ {n} = \ /alpha 2 ^ {n} - 1</math>
Usando a condição inicial
<math>H_ {1} = 1</math>
podemos resolver para <math>\ /alpha</math> como se segue.
solve (alfa * 2 ^ 1 - 1 = 1, alfa);
Assim, a solução para as Torres de Hanói Hanoi é <math>H_ {n} = 2 ^ {n-1} - 1</math>.
'''2.3. Resolvedor de Resolvendo 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 (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 <math>(\ /sqrt {-1})</math>.
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???? “Divide and Conquer” 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, é ele simplesmente retorna unevaluated“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 <math> r_{n}</math>, então temos <math>r_ {1} = 2</math> e <math>r_ {2} = 4</math>. Até agora, ele está começando a se parecer com <math>r_ {n} = n ^ {2}</math>. Mas não vamos ter pressa. O que acontece quando a situação se torna semeslhante semelhante semelhante a n = 3? A figura mostrada aqui é representativa da situação.
'''2.4. Relações de dividir e conquistar'''
Um bom exemplo de relações de dividir e conquistar “Divide and Conquer” é 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)
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 passo com uma lista de amostras para pesquisa.
a := [3,5,7,12,34,546,5324,5346753];
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 "Divide and conquer Conquer" são geradas. Em geral, uma relação de recorrência do tipo dividir e conquistar tem a forma
<math> {r_} {n = a r_ {n / K} + b </math>
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.
'''3. Inclusão – Exclusão'''
Nós vamos começar a ver, nesta seção, a segunda das duas principais técnicas de contagem abrangida no Capítulo 5 desse texto – o O princípio de inclusão e exclusão. Vamos ver como usar Maple para resolver problemas com essa técnica. No cerne do princípio de inclusão e exclusão está a fórmula
<math> | A \cup B | = | A | + | B | - | A \cap B | </math>
A := 2, 3, 5;
Perceba que a idéia ideia do Maple de um conjunto corresponde precisamente a uma notação matemática. Assim, não existe uma ordem implícita entre os membros de um conjunto, nem existe qualquer noção de multiplicidade para membros do conjunto. Para problemas que requerem este tipo de informação adicional, outras estruturas de dados, como listas e arranjos, devem ser usadas. Podemos ver isso em Maple com os exemplos a seguir:
A := `Alice`, `Bob`, `Eve`;
evalb(A = C);
O procedimento evalbMaple evalf avalia uma expressão booleana, e retorna verdadeiro ou falso, de acordo com a veracidade da falsidade da expressão. Então, Maple considera os três conjuntos A, B e C como o mesmo conjunto. O primeiro exemplo mostra que a ordem em que são listados os membros de um conjunto é irrelevante, enquanto o segundo mostra que, apesar de listar a string ‘Eve’ duas vezes, Maple só a vê uma vez. (Experimento com estes exemplos usando listas, que são delimitadas com colchetes em vez de chaves, para ver a diferença entre conjuntos e listas in Maple).
Para determinar o tamnho tamanho de um conjunto (o número de objetos dentro dele) in Maple, usamos o procedimento Maple nops (pense nisso como n operandos)
A := `Alice`, `Bob`, `Eve`;
que, claro, que é!
Como outro exemplo, considere um problema de determinar o número de inteiros positivos menor ou igual a 1000 que não são divisíveis por 2 ou 111 ao mesmo tempo. Primeiro, nós geraremos um conjunto de inteiros positicos positivos menor ou igual a 1000.
hundred := seq(i, i = 1..1000):
O mesmo princípio pode ser usado para exemplos maiores. Aqui, descrevemos o que precisa ser feito para determinar o número de inteiros positivos menor que 10.000 que são indivisíveis pelos primos 2, 3, 5 e 7. Para fazer isso, vamos usar o princípio da inclusão e exclusão para contar esses inteiros menor que 10000, que são divisíveis por, ao menos, um destes quatro números primos, e depois subtraí-los de 10000.
Primeiro, criamos um conjunto de inteiros postivos positivos menor ou igual do que um mil.
th := seq(i, i=1..10^3):
Agora, os inteiros menores que 10000 que são divisiveis divisíveis por um dos 2, 3, 5 e 7 são os da união dos conjuntos
th2 := th intersect seq(2*i, i=1..1000):
th7 := th intersect seq(7*i, i=1..1000):
(Note que não temos que permitir o índice i para alcançar 10000 em cada um destes, mas é mais simples deste modo, uma vez que irá descartar os valores desnecessários por tomar a interseção).)  A seguir, criamos conjunto de inteiros que são divisíveis por estes quatro primos em pares.
th_2_3 := th intersect seq(2*3*i, i=1..1000):
th_3_5_7 := th intersect seq(3*5*7*i, i=1..1000):
Finalmente, contamos os numeros números menores que 10000 que sao são divisíveis por todos os quarto quatro número 2, 3, 5 e 7.
th_2_3_5_7 := th intersect seq(2*3*5*7*i, i=1..1000):
Agora, para calcular os números inteiros menores que 10000 que são divisíveis por pelo menos um dos 2, 3, 5 e 7, nós calculamos como se segue.
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 , em seguida, cada objeto do conjunto original está representado nesta expansão do produto dos dois polinômios por um monômio como <math> x ^ 5</math>. Várias combinações diferentes pode levar a um <math> x ^ 5</math>. O coeficiente de <math> x ^ 5</math> 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''' <math> g(x)</math> para uma sequência <math>{\ r_ {{n} \}</math> é a série de potência formal
<math>\ 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 </math>
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 sequência de equações que definem o coeficiente geral. As equações especificam uma maneira de calcular o coeficiente kth em <math> \ sum_ {k = 0} ^ {\ infty} a_ {k} x ^ {k}</math>. Por exemplo, a função exponencial formal, o que tem de representação de série de potência
<math>\ exp (s) = \ sum_ {n = 0} ^ {\ infty} \ frac {s ^ {n}} {n!}</math>
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 sequência de seus coeficientes. Maple fornece uma maneira de acessar um coeficiente arbitrário em uma série de potências formalformais. Isto é feito como se segue. Para Maple, cada série de potências formal formais é, na verdade, um procedimento, que leva argumentos inteiros. O valor retornado por uma série de potências formalformais, quando dado um inteiro n como argumento é o coeficiente de <math> x ^ {n}</math> . Assim, por exemplo, o quinto número de Fibonacci pode ser produzido chamando a série de potência formal potências formais f acima com '5' como argumento.
f (5);
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 sequência de Fibonacci, podemos usar '''tpsform''', como se segue.
tpsform (F, X, 9);
1

edit