Recorrencia

1450 palavras 6 páginas
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ão apresentados 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) e

Relacionados

  • Recorrência
    1562 palavras | 7 páginas
  • Recorrencia
    1260 palavras | 6 páginas
  • Recorrencias
    1913 palavras | 8 páginas
  • recorrencia
    954 palavras | 4 páginas
  • recorrencias
    8050 palavras | 33 páginas
  • Indução e recorrências
    909 palavras | 4 páginas
  • exame de recorrencia
    410 palavras | 2 páginas
  • HERANÇA COMPLEXA risco de recorrencia.
    1530 palavras | 7 páginas
  • Classes De Recorrencia E Partição De Um Conjunto
    1311 palavras | 6 páginas
  • Relatório: Quedas de árvores no Distrito Federal (Recorrência)
    627 palavras | 3 páginas