Changes

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.

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

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 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.

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

À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.

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.

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.

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.

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. 

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

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.

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:

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

com eigenvalues?????autovalor

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

É neste ponto que a diferença com o caso de raizes raízes distintas aparece. O nth enésimo termo da sequenciasequência, quando á há um double eigenvalueautovalor, é dado ṕorpor:

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:

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

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;

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>

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 é

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>

podemos resolver para <math>\ /alpha</math> como se segue.

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'''

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

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”.

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.

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.

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.

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>

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

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:

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)

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.

Primeiro, criamos um conjunto de inteiros postivos positivos menor ou igual do que um mil.

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

(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.

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.

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.

A '''função geradora''' <math> g(x)</math> para uma sequência <math>{\ r_ {{n} \}</math> é a série de potência formal

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

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.

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.