Comment utiliser le théorème Master pour décrire la récursivité?

Question

Récemment j'ai étudié la récursivité; comment l'écrire, l'analyser, etc. J'ai pensé pendant un moment que la récurrence et la récursion étaient la même chose, mais quelques problèmes sur les devoirs et les quiz récents m'ont fait penser qu'il y a de légères différences, que la «récurrence» est le moyen de décrire un programme ou une fonction récursive. Cela a été très grec jusqu'à récemment, quand je me suis rendu compte qu'il y avait quelque chose appelé le «maître théorème» utilisé pour écrire la «récurrence» pour les problèmes ou les programmes. J'ai lu la page wikipedia, mais, comme d'habitude, les choses sont écrites de telle façon que je ne comprends pas vraiment de quoi il s'agit. J'apprends beaucoup mieux avec des exemples.

Alors, quelques questions: Disons que vous donne cette récurrence:

r (n) = 2 * r (n-2) + r (n-1);
r (1) = r (2) = 1

Est-ce, en fait, sous la forme du théorème de maître? Si oui, en mots, que dit-il? Si vous deviez essayer d'écrire un petit programme ou un arbre de récursion basé sur cette récurrence, à quoi cela ressemblerait-il? Devrais-je simplement essayer de substituer des nombres, de voir un modèle, puis écrire un pseudocode qui pourrait créer récursivement ce modèle, ou, puisque cela peut être sous la forme du théorème principal, y a-t-il une approche mathématique plus directe? Maintenant, disons qu'on vous a demandé de trouver la récurrence, T (n), pour le nombre d'ajouts effectués par le programme créé à partir de la récurrence précédente. Je peux voir que le cas de base serait probablement T (1) = T (2) = 0, mais je ne sais pas où aller à partir de là. Fondamentalement, je demande comment passer d'une récurrence donnée au code, et le contraire. Comme cela ressemble au théorème du maître, je me demande s'il y a une façon simple et mathématique de s'y prendre. EDIT: Bon, j'ai regardé à travers certaines de mes missions passées pour trouver un autre exemple d'où l'on me demande, 'pour trouver la récurrence', qui est la partie de cette question que j'ai le problème de poste avec.

Récurrence qui décrit le mieux façon dont le nombre d'opérations d'addition dans le fragment de programme suivant (lorsqu'il est appelé avec l == 1 et r == n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

Answer 1

Il y a quelques années, Mohamad Akra et Louay Bazzi ont prouvé un résultat qui généralise la méthode Master - c'est presque toujours mieux. Vous devriez vraiment pas utiliser le théorème de maître plus ...

Voir, par exemple, cet article intitulée: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

Fondamentalement, obtenir votre récurrence pour ressembler à l'équation 1 dans le papier, choisissez les coefficients de, et intégrer l'expression dans le théorème 1.

Answer 2

Votre méthode, écrite en code en utilisant une fonction récursive, ressemblerait à ceci:

function r(int n) 
{ 
    if (n == 2) return 1; 
    if (n == 1) return 1; 
    return 2 * r(n-2) + r(n-1); // I guess we're assuming n > 2 
} 

Je ne suis pas su Qu'est-ce que la "récurrence" est, mais une fonction récursive est simplement celle qui s'appelle elle-même.

fonctions récursives ont besoin d'une clause d'évasion (certains cas non récurrent - par exemple, « si n == 1 retour 1 ») pour éviter une erreur de débordement de pile (à savoir, La fonction est appelée tant que l'interprète court de mémoire ou d'autres ressources)

Answer 3

Un programme simple qui mettrait en œuvre qui ressemblerait à ceci:

public int r(int input) { 
    if (input == 1 || input == 2) { 
     return 1; 
    } else { 
     return 2 * r(input - 2) + r(input -1) 
    } 
} 

Vous devez également vous assurer que l'entrée ne va pas provoquer une récursion infinie, par exemple, si l'entrée au début était inférieure à 1. Si ce n'est pas un cas valide, renvoyer une erreur, si elle est valide, puis retourner la valeur appropriée.

Answer 4

« Je ne suis pas sûr de ce que « récurrence » est soit »

la définition d'une « relation de récurrence » est une séquence de nombres « dont le domaine est une série infinie des entiers et dont la gamme est un ensemble de nombres réels. " Avec la condition supplémentaire que la fonction décrivant cette séquence "définit un membre de la séquence en fonction d'une précédente". Et, l'objectif derrière les résoudre, je pense, est de passer d'une définition récursive à une définition qui ne l'est pas. Dites si vous aviez T (0) = 2 et T (n) = 2 + T (n-1) pour tout n> 0, il faudrait passer de l'expression "T (n) = 2 + T (n -1) "à un comme" 2n + 2 ".

sources: 1) "Mathématiques discrètes avec la théorie des graphes - deuxième édition", par Edgar G. Goodair et Michael M. Parmenter 2) "Computer algorithmes C++," par Ellis Horowitz, Sartaj Sahni, et Sanguthevar Rajasekaran.

Answer 5

Zachary:

Disons que vous donne cette récurrence :

r (n) = 2 * r (n-2) + r (n-1); r (1) = r (2) = 1

Est-ce, en fait, sous la forme du théorème maître ? Si oui, en mots, qu'est-ce que cela veut dire?

Je pense que ce que votre relation de récurrence dit est que pour la fonction de « r » avec « n » comme paramètre (représentant le nombre total de données ensembles en cours de saisie), tout ce que vous obtenez au nième la position de l'ensemble de données est la sortie de la n-1e position plus deux fois quel que soit le résultat de la n-2 e position, sans travail non récursif. Lorsque vous essayez de résoudre une relation de récurrence, vous essayez de l'exprimer d'une manière qui n'implique pas de récursivité.

Cependant, je ne pense pas que ce soit dans la forme correcte pour la méthode du théorème maître. Votre affirmation est une «relation de récurrence linéaire de second ordre avec des coefficients constants». Apparemment, d'après mon ancien manuel Discrete Math, c'est la forme que vous devez avoir pour résoudre la relation de récurrence.

est ici la forme qu'ils donnent:

r(n) = a*r(n-1) + b*r(n-2) + f(n) 

pour 'a' et 'b' sont des constantes et f (n) est une fonction de n. Dans votre énoncé, a = 1, b = 2 et f (n) = 0. Chaque fois que f (n) est égal à zéro, la relation de récurrence est connue comme «homogène». Donc, votre expression est homogène.

Je ne pense pas que vous puissiez résoudre une relation de récurrence homogène en utilisant la méthode maître Theoerm parce que f (n) = 0. Aucun des cas pour le théorème de la méthode maître ne le permet car n-to-the-power- de-tout ne peut pas égaler zéro. Je peux me tromper, parce que je ne suis pas vraiment un expert en la matière mais je ne pense pas qu'il soit possible de résoudre une relation de récurrence homogène en utilisant la méthode principale.

I qui que la façon de résoudre une relation de récurrence homogène est de passer par 5 étapes:

1) forment l'équation caractéristique, ce qui est de la forme:

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0 

Si vous « ai seulement eu 2 cas récursifs dans votre relation de récurrence homogène alors vous ne devez changer votre équation dans l'équation où quadratique

x^2 - a*x - b = 0 

C'est bec ause une relation de récurrence de la forme de

r(n) = a*r(n-1) + b*r(n-2) 

peut être réécrite comme

r(n) - a*r(n-1) - b*r(n-2) = 0 

2) Une fois que votre relation de récurrence est réécrite comme une équation caractéristique, trouver ensuite les racines (x [1] et x [2]) de l'équation caractéristique.

3) Avec vos racines, votre solution sera désormais l'une des deux formes:

if x[1]!=x[2] 
    c[1]*x[1]^n + c[2]*x[2]^n 
else 
    c[1]*x[1]^n + n*c[2]*x[2]^n 

lorsque n> 2. 4) Avec la nouvelle forme de votre solution récursive, vous utilisez les conditions initiales (r (1) et r (2)) pour trouver c [1] et c [2]

Voulez-vous profiter de votre exemple est ici ce que nous obtenons:

1) r (n) = 1 * r (n-1) + 2 * r (n-2) => x^2 - x - 2 = 0

2) Résolution pour x

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1) 

    x[1] = ((-1 + 3)/2) = 1 
    x[2] = ((-1 - 3)/2) = -2 

3) Depuis x [1]! = x [2], votre soluti sur a la forme:

c[1](x[1])^n + c[2](x[2])^n 

4) Maintenant, utilisez vos conditions initiales pour trouver les deux constantes c [1] et c [2]:

c[1](1)^1 + c[2](-2)^1 = 1 
c[1](1)^2 + c[2](-2)^2 = 1 

Honnêtement, je ne suis pas sûr de ce que vos constantes sont dans cette situation, je me suis arrêté à ce point. Je suppose que vous auriez à brancher des nombres jusqu'à ce que vous ayez une valeur pour c [1] et c [2] qui satisferait ces deux expressions.Ou alors effectuer la réduction de la rangée sur une matrice C, où C est égal à:

[ 1 1 | 1 ] 
[ 1 2 | 1 ] 

Zachary:

Récurrence qui décrit le mieux manière le nombre d'opérations d'addition dans le fragment de programme suivant (lorsqu'elle est appelée avec l == r == 1 et n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

ici s » les valeurs de complexité de temps pour votre code donné pour quand r> l:

int example(A, int l, int r) {  => T(r) = 0 
    if (l == r)    => T(r) = 1 
    return 2;    => T(r) = 1 
    return (A[l] + example(A, l+1, r); => T(r) = 1 + T(r-(l+1)) 
} 

Total:      T(r) = 3 + T(r-(l+1)) 

Sinon, lorsque r == l alors T (r) = 2, parce que le instruction if et le retour à la fois besoin d'une étape par exécution.