31
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 20:47, 24 November 2015
, 20:47, 24 November 2015no edit summary
Em geral, podemos pensar em uma relação de recorrência como uma relação do formulário
r_} {n = f (N-R_ {1}, {N-R_ 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 {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);
end:
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.
