Changes

Técnicas Avançadas de Contagem (view source)

Revision as of 10:07, 30 November 2015

5,718 bytes added , 10:07, 30 November 2015

no edit summary

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

'''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 <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???? 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 <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 a n = 3? A figura mostrada aqui é representativa da situação.

'''Figure''': file = ch05 / 3lines.eps

Neste caso, o número <math>R_ {3}</math> das regiões é 7, de modo que a estimativa inicial que<math> R_ {n}</math> é <math>n ^ {2}</math> não pode ser certa. Para encontrar <math>r_ {4}</math>, temos de acrescentar uma quarta linha para o diagrama. Isto sugere tentar calcular <math>r_ {4}</math> em termos de <math>r_ {3}</math>, para que possamos pensar em <math>\ {r_ {n} \} </math>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, <math>R_ {4} = r_ {3} + 3</math>. Argumentos semelhantes para uma configuração geral de linhas revelam que <math>R_ {n}</math> satisfaz a relação de recorrência

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

rSolve (

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

R (1) = 2,

r (n));

simplify(%);

Deeh

31

edits