MO417 – Atas das Aulas ( Recorrências )

Ata de aula : 2003-03-07

Redator : Guilherme Mundim Torres

Tópicos abordados em sala de aula :

1. Introdução

2. O método da substituição

2.1. Sutilezas

3. O método da árvore de recursão

4. O método mestre

4.1. O teorema mestre

1. Introdução :

Recorrência ( definição ) : É uma equação ou desigualdade que descreve uma função em termos de seu valor em entradas menores.

Serão estudados 3 métodos para se resolver recorrências ( obter limites assintóticos O ou theta sobre a solução ). São eles :

§ Método da substituição

§ Método da árvore de recursão

§ Método mestre

2. O método da substituição :

O nome desse método provem do fato de tentar substituir a resposta inspirada pela resposta indutiva aplicada a valores menores. Sem dúvida é um método bastante poderoso, porém, seu sucesso depende principalmente da percepção do aluno em visualizar a forma da função.

O método da substituição é composto por 2 etapas :

1 ª etapa ) Deve-se pressupor a solução ( “chute” )

2 ª etapa ) Verificação ( através de indução matemática ) do funcionamento da solução proposta na primeira etapa.

Obs : Uma exigência da indução matemática é que a solução deverá satisfazer inclusive as condições limite . Sendo assim, algumas vezes será necessário estender as condições limite de forma que a suposição indutiva funcione mesmo para um n pequeno.

2.1 Sutilezas

Algumas vezes a hipótese indutiva não será forte o bastante para provar o limite detalhado. Nesses casos, uma boa saída é partir da subtração de um termo de mais baixa ordem na suposição inicial. Agindo dessa forma, pode-se provar algo mais forte para um determinado valor supondo algo ainda mais forte para valores menores.

2.2 Troca de variáveis

Esta técnica consiste em tentar efetuar uma troca de variáveis numa recorrência desconhecida com o objetivo de deixar o problema mais parecido com um que já se conheça a solução.

3. O método da árvore de recursão :

Este método simula a execução do algoritmo através da montagem de uma árvore de recursão onde cada nó representa o custo de um único subproblema. Comecamos com apenas a raiz, que representa o problema todo, e sucessivamente expandimos uma folha colocando em seu nó o custo imediato (não-recursivo) e abrindo um filho para cada termo recursivo. Este processo de expnsão termina quando temos apenas folhas que correspondem a casos base. Após fazer o somatório do total de custos de todos os níveis da árvore, chega-se ao modelo desejado para solução da recorrência.

Obs1 : As árvores de recursão são particularmente indicadas para recorrências que descrevem o tempo de execução de um algoritmo de dividir e conquistar.

Obs2 : Outra aplicação do método consiste na geração de uma boa suposição e posterior verificação da mesma através do método de substituição.

4. O método mestre

Este método é utilizado na resolução de recorrências da seguinte forma :

T(n) = aT( n / b ) + f (n)

Onde e b > 1 são constantes e f(n) é uma função assintoticamente positiva.

Recorrências da forma acima descrevem o tempo de execução de um algoritmo que divide um problema de tamanho “ n ” em “ a ” subproblemas, cada um de tamanho “ n / b ” (onde a e b são constantes positivas); “ f(n) ” representa o custo de dividir o problema e combinar os resultados dos subproblemas.

4.1 O teorema mestre (núcleo : n ^log _b ^a )

Sejam e b > 1 constantes, seja f(n) uma função e seja T(n) definida sobre os inteiros não negativos pela recorrência :

T(n) = aT( n / b ) + f (n)

onde n/b é interpretado como piso ( n / b ) ou teto ( n / b ). Pelo método mestre, a solução da recorrência deverá se encaixar em um dos 3 métodos a seguir :

1. Se f(n) = O( n ^log _b ^{a - e} ) para alguma constante e > 0, então T(n) = theta ( n ^log _b ^a ).

2. Se f(n) = theta( n ^log _b ^a ) então T(n) = theta ( n ^log _b ^a lg n ).

3. Se f(n) = Omega( n ^log _b ^{a + e} ) para alguma constante e > 0, e se af( n / b ) cf(n) para alguma constante c<1 e para todo n suficientemente grande, então T(n) = theta ( f(n) ).