Recorrencia

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1450 palavras )
  • Download(s) : 0
  • Publicado : 3 de dezembro de 2011
Ler documento completo
Amostra do texto
EQUAÇÕES DE RECORRÊNCIA
Héctor Soza Pollman - Universidade Católica do Norte - Antofagasta, Chile

( Nível Avançado

Frenqüentemente em teoria da Computação (ver exemplo [2]), ao analisar o tempo de execução de um algoritmo (ou o espaço ocupado na memória pelos dados), obtemos uma (ou mais) equações discretas, chamadas de Equações de Recorrência, cuja incógnita é uma função inteira f(n),que geralmente é uma função do tamanho n do problema (por exemplo: a quantidade de dados a ordenar se é um algoritmo de ordenamento). Esta equação resulta ser uma relação entre f(n) e seus valores prévios, como são f(n – 1), f(n / 2), ou outro. Além disso se conhecemos o algoritmo analisado com detalhe, podemos estabelecer um valor de bordo num ponto dado (como f(0) por exemplo). Neste artigo sãoapresentados alguns dos métodos desenvolvidos para resolver este tipo de equações, as quais aparecem em ordem de dificuldade.

Os tipos de equações de recorrência a serem consideradas são as seguintes, em que a incógnita é a sucessão [pic]com [pic]

1. EQUAÇÃO LINEAR DE PRIMEIRA ORDEM COM COEFICIENTES DE VALOR INTEIRO 1.

O tipo mais simples de equação de recorrência de primeira ordem é:[pic] , [pic]
em que [pic] e a sucessão [pic] são dados do problema. Sua resolução faz uso da propriedade telescópica da soma obtendo:
[pic] [pic]
Exemplo: Para a equação: [pic] com [pic] obtemos [pic]

2. EQUAÇÃO LINEAR DE PRIMEIRA ORDEM COM COEFICIENTES CONSTANTES.

A equação linear de primeira ordem com coeficientes constantes é:
[pic] [pic]
em que [pic] e as sucessões numéricas [pic],[pic] e [pic] são dados do problema (as sucessões [pic]e [pic]não devem ser nulas). Para resolver esta equação ela deve ser multiplicada pelo fator [pic] (chamado fator somante):
[pic]
Impõe-se a condição:
[pic] (1)
com o qual obtemos:
[pic]

Observa-se que a equação anterior se reduz a uma de primeiro tipo, e que sua solução é:
[pic]

O fator somante é obtido a partir da condição (1) econsiderando que [pic]
[pic]

EXEMPLO: AS TORRES DE HANOI.
Dadas três varetas e n discos de distintos tamanhos colocados na primeira vareta em ordem de tamanho (do menor ao maior), mover estes n discos desde a vareta inicial até a terceira usando a segunda como auxiliar, sem colocar um disco de tamanho maior sobre um de tamanho menor (para maiores explicações ver [4]). Se [pic]é a quantidade demovimentos para levar os n discos da primeira a terceira vareta, podemos provar, ao analisar como são distribuídos os movimentos, que, se [pic]é a quantidade de movimentos para mover os n discos desde a primeira à terceira vareta (com [pic]então:
[pic]
com [pic] De fato, dada uma solução do problema de Hanoi com n – 1 discos em [pic] movimentos, podemos mover os n – 1 primeiros discos para asegunda vareta, depois mover o último disco para a terceira vareta e por fim mover os [pic] primeiros discos para a terceira vareta, gastando [pic]movimentos. Neste caso temos que o fator somante resulta ser: [pic] Logo, a solução da equação das torres de Hanoi é:
[pic]
Observamos, por exemplo, que para n = 3 devem ser realizados 7 movimentos. Deixamos como exercício para o leitor provar que éimpossível resolver este problema usando uma quantidade menor de movimentos.

3. EQUAÇÕES HOMOGÊNEAS DE PRIMEIRA ORDEM COM COEFICIENTES CONSTANTES.

Considere a equação:
[pic] (2)
em que [pic] são sucessões independentes de n, e os valores de [pic] são conhecidos para i = 0, ..., k – 1 (correspondem aos valores de bordo). Supondo que a equação (2) admite uma solução do tipo: [pic] em que [pic]é um parâmetro inteiro, e substituindo em (2) temos:
[pic]
Se [pic]então obtemos a equação característica associada a equação (2):
[pic]
Vamos mostrar que se esta equação tem as raízes complexas [pic] com multiplicidades [pic], respectivamente, então as soluções de (2) são exatamente as seqüências [pic] da forma [pic]
onde [pic] são polinômios com grau [pic] [pic](em particular, se [pic] é...
tracking img