De La Récurrence À La Récursivité Grand Oral

De La Récurrence À La Récursivité Grand Oral

La récursivité

Base récurrente, autodéfinition.

Au début du
xiii-ème siècle, le mathématicien italien Léonard de Pise surnommé Fibonacci, a proposé de décrire l’évolution d’une population de lapins (dont tout le monde sait qu’ils se reproduisent rapidement). L’hypothèse simplificatrice est que chaque mois deux lapins adultes mâle et femelle donnent naissance à 2 lapereaux mâle et femelle et qu’il faut un mois à un lapereau pour devenir adulte et pouvoir procréer. La question est de savoir combien de couples de lapins (ou lapereaux) il y aureola dans le clapier après \(north\) mois ? On suppose que le clapier contient initialement two lapereaux.

À l’étape 0, il y a donc un seul couple de lapereaux. Après un mois, ces lapins sont adultes. Après deux mois ce couple de lapins donne naissance à leur premier couple de lapereaux, il y a donc 2 couples, etc.

Dessinez united nations arbre de profondeur five pour représenter la croissance de la population des lapins après 5 mois, chaque nœud contenant un couple de lapins ou lapereaux. Démontrez ensuite que le nombre de couples de lapins dans le clapier après \(n\) mois est égal à la somme du nombre de couples de lapins des deux mois précédents.

En mathématiques, la suite de Fibonacci \((F_n)_{n\in{\mathbf Northward}}\) est une suite d’entiers naturels dont le terme courant est égal à la somme des deux termes précédents, les deux premiers termes de la suite étant \(F_0=0\) et \(F_1=one\). On peut exprimer cette définition à fifty’aide de la récurrence : \begin{equation}\label{eq:fibo} {\color{#DDA}F_n}= \begin{cases} i&\text{si}\ n\in\{0,1\},\\ F_{northward-one}+F_{due north-2}&\text{sinon.} \terminate{cases} \end{equation} La définition récurrente (\ref{eq:fibo}) ne permet pas de calculer la valeur \(F_n\) directement, c’est-à-dire en effec­tuant un nombre d’opérations
indépendants
de l’entier \(northward\). Nous verrons en exercice comment obtenir une formule directe. Mais pour le moment, il faut calculer tous les termes qui précèdent. On déduit facilement united nations algorithme itératif pour calculer le \(due north\)-ème terme \(F_n\), il suffit de conserver en mémoire à chaque étape les deux termes précédents, les additionner (instruction #16) puis les mettre à jour (instructions 17 et 18 en faisant attention à l’ordre des copies), cascade la prochaine étape :

Fibonacci(n):entier données    due north: entier variables    F,10,y,i: entiers DEBUT    SI n < 2 ALORS       RENVOYER 1    SINON       x ← 1       y ← i       i ← 2       TQ i ≤ due north FAIRE          F ← x + y          x ← y          y ← F       FTQ           RENVOYER F    FSI  FIN
    

De la même manière que l’on peut définir une suite ou une
fonction récurrente
en mathématiques, on peut définir un algorithme récursif en informatique. Le parallèle est parfaitement adapté puisqu’une fonction récursive due south’adapte en général immédiatement en son équivalent algorithmique récursif.

L’algorithme précédent s’écrit récursivement :

Fibonacci(northward):entier données    n: entier DEBUT    SI n < 2 ALORS       RENVOYER 1    SINON       RENVOYER Fibonacci(due north-one) + Fibonacci(n-two)    FSI  FIN
    

L’algorithme est ici uniquement constitué par les deux blocs de l’instruction conditionnelle
SI / ALORS / SINON. Le premier bloc (instruction #6) constitue ce que l’on appelle la base récurrente qui correspond à la situation que fifty’algorithme sait traiter sans faire appel à lui-même. C’est l’homoloque informatique de l’initialisation dans un raisonnement par récurrence en mathématiques. La seconde appelée autodéfinition concerne la partie de l’algorithme qui fait référence à lui même, ici un unique appel récursif (instruction #8). C’est l’homoloque informatique de fifty’hérédité dans un raisonnement par récurrence en mathématiques.

50’idée sous-jacente, tout comme pour une récurrence, est que le ou les appels récursifs se font sur des instances
plus petites
du ou des paramètres de 50’algorithme, ici \(n-ane\) et \(n-2\) au lieu de \(n\). Comme l’algorithme sait traiter le cas de base of operations, la suite des appels récursifs sur des instances de plus en plus petites aboutira inexorablement à un appel sur la ou les instances de la base récurrente ce qui achèvera le processus. Retenons donc les deux concepts clefs d’un algorithme récursif : la
base récurrente
et fifty’autodéfinition.

La plupart des langages de programmation modernes autorisent les définitions récursives des fonctions et même la récursivité croisée, où une fonction \(A\) fait appel à une fonction \(B\) qui appelle \(A\). Cette liberté d’écriture offerte au programmeur tranquillity sur 50’beingness d’une pile. À chaque appel de la fonction, un bloc d’activation contenant les paramètres d’appel de la fonction, ses variables locales et sa valeur de retour est
empilé. La fonction travaille toujours avec les variables du bloc d’activation au sommet de la pile. Si elle est appelée à nouveau récursivement, united nations nouveau bloc d’activation est empilé et la fonction travaillera avec les variables de ce nouveau bloc et ainsi de suite jusqu’à ce que sa valeur de retour soit instanciée et qu’elle termine son exécution, moment où le bloc d’activation est
dépilé.

Ainsi, pour 50’algorithme récursif Fibonacci, 50’algorithme opère sur une nouvelle variable \(northward\) et une nouvelle valeur de retour placées au sommet d’une pile à chaque nouvel appel. La figure ci-dessous contient l’arbre des appels récursifs de l’algorithme Fibonacci cascade la valeur \(n=iv\). La valeur de retour de fifty’algorithme est l’étiquette des branches.



Arbre des appels de l’algorithme Fibonacci pour \(due north=4\). Les étiquettes des arcs sont les valeurs de retour. Les feuilles en gris correspondent à la base récurrente.

La table suivante décrit l’état de la pile au fur et à mesure des appels récursif de fifty’algorithme Fibonacci pour les valeurs \(north\) inférieures ou égales à 5 (afin de limiter la taille de l’affichage). Saisissez la valeur \(n:=\). Dans la pile, le bloc d’activation contient la valeur \(n\) et la valeur de retour

ret

de fifty’algorithme (matérialisée par united nations point tant qu’elle north’a pas été instanciée).



Évolution de la pile lors de l’exécution de 50’algo­ri­thme Fibonacci pour \(due north=\).

La possibilité d’écrire des algorithmes récursifs donne une souplesse considérable et parfois décisive. Il peut être très délicat d’écrire une méthode itérative pour résoudre united nations problème machine sa nature est récursive. Ce qui distingue fondamentalement une méthode itérative d’une méthode récursive, c’est la nécessité ou non de conserver une trace de chaque calcul à toutes les étapes de la méthode, autrement dit la nécessité de disposer d’une pile ou not. Ainsi le calcul du \(due north\)-ème terme de la suite de Fibonacci
due north’est pas
un problème de nature récursive. En effet, seuls deux termes nécessitent d’être conservés à chaque étape pour pouvoir calculer le prochain, il est donc artificiel et dispandieux de conserver
toutes
les valeurs \(F_i\) pour \(i < northward\). L’algorithme itératif Fibonacci initialement proposé est à privilégier.

Popular:   Comment Faire Un Oral De Brevet Sur Son Stage

Il est également important de noter que dans la version récursive, outre l’empilement superflu d’une quantité non négligeable d’informations, certains calculs sont effectués plusieurs fois inutilement comme le montre 50’arbre des appels récursifs dans la figure i avec les deux nœuds \(F(2)\) qui par construction sont la racine du même sous-arbre. C’est un écueil majeur et très commun lorsqu’on écrit des algorithmes récursifs.

Évaluez la complexité en temps et en mémoire des deux algorithmes qui calculent le \(north\)-ème terme \(F_n\) de la suite de Fibonacci et comparez.

On rappelle la définition de la fonction factorielle \({\mathbf North}\rightarrow{\mathbf N}\) définie par \[northward!=n(northward-1)(n-2)\ldots two\times one\] Écrivez un algorithme récursif pour calculer cette fonction. Tracez la pile d’exécution pour \(n=4\). La fonction factorielle est-elle une fonction de nature récursive ? Écrivez un algorithme itératif pour calculer cette fonction. Évaluez la complexité en temps et en mémoire des deux algorithmes et comparez.

Soient \(p\) et \(northward\) deux entiers tels que \(0\leq p\leq n\). La formule du triangle de Pascal : \begin{equation} \binom{north}{p}= \brainstorm{cases} 1&\text{si}\ p=0\ \text{ou}\ p=due north,\\ \binom{north-1}{p}+\binom{n-1}{p-1}&\text{sinon}. \stop{cases} \end{equation} fournit une définition récursive du coefficient binomial \(\binom{n}{p}\). Écrivez united nations algorithme récursif
Binomial
cascade le calculer. Tracez la pile d’exécution pour \(northward=iii\) et \(p=2\). La fonction binomiale est-elle une fonction de nature récursive ? Écrivez un algorithme itératif pour calculer cette fonction. Évaluez la complexité en temps et en mémoire des deux algorithmes et comparez.

(Formule de Binet). La suite de Fibonacci est une suite récurrente linéaire d’ordre 2, c’est-à-dire une suite à valeurs dans un corps commutatif, ici \({\mathbf R}\), telle que le terme courant est une combinaison linéaire des deux termes précédents. En notant \(U_n\) le vecteur \((F_n,F_{n+1})\) de \({\mathbf R}^2\), calculez la matrice \(2\times 2\) notée \(A\) telle que \(U_{n+1}=AU_n\). En déduire que \(U_{n-one}=A^{n-1}U_0\). Diagonalisez la matrice \(A\) et en déduire une formule pour calculer directement \(F_n\).

Les tours de Hanoï.

Si ni le calcul de la suite de Fibonacci, ni le calcul de la factorielle d’un entier ne sont des problèmes de nature récursive, malgré ce que suggèrent leurs définitions récurrentes, quel type de problème jus­ti­fie une écriture récursive ?

Présentation du problème.

Nous allons aborder un problème très classique en informatique qui a le mérite d’illustrer la puissance de l’écriture récursive en fournissant une solution simple et particulièrement élégante. La résolution de ce problème demanderait des efforts beaucoup plus conséquents s’il fallait se limiter à une écriture itérative classique pour calquer la méthode manuelle. Sans une analyse plus approfondie, il faudrait ni plus ni moins recréer une pile calquant ce que fait la pile d’exécution dans la version récursive.

Nous verrons en exercice plus loin qu’il est malgré tout possible de se passer d’une pile avec une solution itérative. Cela north’a rien d’étonnant, le mécanisme de résolution de ce casse-tête se trouve assez facilement après quelques tâtonnements et il est manifeste qu’united nations joueur n’a pas besoin de conserver en mémoire l’intégralité des manipulations effectuées pour déterminer quel est le mouvement suivant, ce jeu ne s’adresse pas à des
mutants.



Le problème des tours de Hanoï avec \(due north=8\) disques.

Le problème des
tours de Hanoï, imaginé par fifty’arithméticien français Edouard Lucas à la fin du
xix-ème siècle, consiste à déplacer les disques d’une pile de \(n\) disques de diamètres décroissants de leur tour d’origine vers une autre bout en southward’aidant d’une troisième tour auxiliaire. Il faut respecter les deux conditions suivantes :

  1. On ne peut empiler qu’un seul disque à la fois ;
  2. On ne peut empiler un disque que sur united nations disque de diamètre
    supérieur
    (ou sur une bout vide).

Ce jeu est devenu united nations casse-tête populaire qui se vend dans la plupart des boutiques de jeux. La photograph ci-dessus est celle de mon exemplaire personnel qui contient 8 disques.

Dans la suite les tours seront numérotées de one à three de la gauche vers la droite et nous coderons \(10\rightarrow y\) le déplacement du disque au sommet de la pile de la tour \(x\) vers le sommet de la pile de la tour \(y\). Bien entendu ce déplacement est supposé respecter la règle two. Par convention la pile est initialement placée sur la première tour et il faut la déplacer vers la troisième bout.

Le problème est trivial pour \(northward=1\), une solution évidente est \(1\rightarrow three\). Cascade \(north=two\) c’est à peine plus compliqué, la suite des déplacements \(one\rightarrow 2,\ 1\rightarrow 3,\ two\rightarrow 3\) constitue une solution. Pour \(north=3\) cela demande un peu plus de réflexion : \[1\rightarrow 3,\ 1\rightarrow ii,\ 3\rightarrow ii,\ 1\rightarrow three,\ two\rightarrow i,\ 2\rightarrow 3,\ 1\rightarrow 3.\] Notons déjà qu’il existe plusieurs solutions pour une instance de taille \(north\) et qu’il est naturel de due south’interroger sur l’optimalité des solutions en termes de nombre de déplacements à réaliser. Il est aisé de prouver que les solutions fournies cascade \(n=one\) et \(n=ii\) ci-dessus sont optimales. Nous étudierons cette question dans l’étude de la complexité de 50’algorithme qui résout ce problème.

Algorithme de résolution du problème.

Analysons le problème. Notons \(A\), \(B\) et \(C\) les trois tours. Cascade déplacer \(n\) disques de la bout \(A\) à la tour \(C\), il faut déplacer \(n-ane\) disques de la tour \(A\) à la tour \(B\) puis déplacer le dernier disque de la tour \(A\) à la tour \(C\) et finalement déplacer les \(n-ane\) disques de la tour \(B\) à la bout \(C\). Autrement dit si l’opération
Déplacer(northward,A,C)
signifie déplacer \(north\) disques de la tour \(A\) vers la tour \(C\), alors elle peut se décomposer en trois opérations plus simples :

  1. Déplacer(n-1,A,B) ;
  2. Déplacer(one,A,C) ;
  3. Déplacer(north-1,B,C).

On vient de décrire la partie autodéfinition de l’algorithme récursif Déplacer. Mais cascade que fifty’algorithme soit complet, il faut que les appels récursifs s’arrêtent, il faut alors déterminer les valeurs des paramètres pour lesquels on sait annotate traiter le problème directement sans s’appuyer sur la récursion. La base récurrente est ici très uncomplicated, s’il ne reste qu’un disque, il suffit de le déplacer de sa tour d’origine vers la bout d’arrivée. L’algorithme complet southward’écrit donc :

Popular:   Le Plus Grand Multiple De 36 Inférieur À 100

Déplacer(northward,X,Y) DONNEES     north,X,L: entiers DEBUT    SI (n = 1)       Afficher(X, "→", Y)    SINON       Déplacer(n-one, X, 6-X-Y)       Afficher(10, "→", Y)       Déplacer(north-1, vi-Ten-Y, Y)    FSI FIN
    

Les paramètres \(Ten\) et \(Y\) de l’algorithme désignent respectivement la tour d’origine et la tour de destination des \(n\) disques.

Démontrez que si les tours sont numérotées de 1 à iii et que si \(X\) et \(Y\) désignent le numéro de deux tours distinctes alors la troisième tour a nécessairement pour numéro \(6-X-Y\).

Fifty’animation suivante montre l’état des trois tours lors de la résolution du problème par l’algorithme Déplacer pour un nombre de disque \(northward\) tel que \(1\leq due north\leq xvi\). Saisissez sa valeur \(n:=\).



Solution optimale au problème des tours de Hanoï pour \(n=\)

Programmez fifty’algorithme Déplacer et comptez empiriquement le nombre d’appels récursifs réalisés. Tracez la courbe du nombre d’appels en fonction du nombre de disques \(north\) avec
Gnuplot.

Complexité de fifty’algorithme et optimalité.

Calculons la complexité de cet algorithme. Le coût de la base of operations récurrente est constant en \(\Theta(1)\) et le traitement réalisé dans le corps de l’algorithme, hormis les appels récursifs, a un coût abiding \(\Theta(1)\). Il y a exactement deux appels récursifs. La fonction de complexité \(T\) est donc donnée par l’équation suivante : \begin{equation}\label{eqhan} T(northward)=\begin{cases} \Theta(one)&\text{si}\ north =1,\\ 2T(n-1)+\Theta(one)&\text{sinon}. \end{cases} \finish{equation} En substituant successivement les \(T(thou)\) par leurs valeurs dans l’expression (\ref{eqhan}), on arrive à \begin{marshal*} T(due north)&=2^nT(1)+\Theta(1)\sum_{i=0}^{northward-1}2^i\\ &=two^n\Theta(1)+\Theta(1)(2^n-1)\\ &=\Theta(2^north). \end{align*}

En vous inspirant du calcul de la fonction de complexité de l’algorithme Déplacer, montrez que le nombre de mouvements de disques effectués si la pile initiale contient \(north\) disques est exactement \(2^n-1.\)

Cascade déplacer \(n\) disques, l’algorithme Déplacer réalise \(2^north-ane\) mouvements. C’est le nombre minimal de mouvements et c’est l’unique façon d’obtenir ce minimum.

La première partie de l’énoncé a été traitée dans l’exercice précédent. On montre la deuxième partie par récurrence sur le prédicat \(P(north)\) suivant :



Fifty’algorithme Déplacer réalise
la
suite optimale de mouvements cascade déplacer \(due north\) disques d’une bout à une autre.


C’est évident cascade \(due north=i\). On numérote les \(n+i\) disques sur la première tour de \(1\) à \(n+1\) dans l’ordre croissant de leurs diamètres. Pour les déplacer vers la troisième bout, compte tenu des règles imposées, il faut nécessairement qu’à une certaine étape le disque \(north+1\) en bas de la pile soit déplacé de la tour 1 vers la tour 3. Ceci n’est possible que si la pile des \(n\) disques au-dessus est placée sur la tour ii. Ainsi pour déplacer optimalement les \(due north+ane\) disques de la tour \(1\) vers la tour \(three\), il faut déplacer optimalement la pile des \(n\) disques au sommet de la tour \(ane\) vers la tour \(2\) au préalable pour pouvoir déplacer le disque \(north+1\) de la tour 1 vers la tour three et enfin déplacer optimalement la pile des \(n\) disques de la tour \(ii\) vers la tour \(3\). L’hypothèse de récurrence permet de conclure.

Calculez la complexité en espace de fifty’algorithme Déplacer.

On numérote les trois tours 0, one et 2 de la gauche vers la droite. Soit \(n\) le nombre de disques sur la tour #0. On considère les deux opérations suivantes :

  1. Déplacer le plus petit disque de sa tour \(ten\) vers la tour \(x+ane\pmod 3\) si \(n\) est pair, vers la tour \(x-1\pmod 3\) si \(north\) est impair ;
  2. Déplacer united nations autre disque (un seul des deux autres disques peut en effet être déplacé).

Pour les four instances \(n=ane, 2, 3\) et \(4\), répétez ces deux règles jusqu’à ce que la tour #0 soit vide. Que constatez-vous ? Écrivez un algorithme itératif
Décaler
qui répète ces déplacements jusqu’à ce que la tour #0 soit vide (en fonction de \(due north\)). Démontrez par récurrence que cette méthode est optimale. Calculez la complexité en temps et en espace de cet algorithme ? Comparez ces complexités avec celles de l’algorithme récursif Déplacer. Quel est l’algorithme le plus efficace ?

On rappelle que le poids de Hamming \(w(k)\) d’un entier \(k\) est le nombre de chiffres non-nuls dans son écriture binaire. Ainsi \(w(13)=three\) auto \(13=1101_2\). Écrivez united nations algorithme récursif
Poids
qui calcule le poids d’un entier \(k\) passé en paramètre en montrant préalablement que \begin{equation} w(k)=\begin{cases} w(t),&\text{si}\ thou=2t\\ w(t)+1,&\text{si}\ thou=2t+1.\\ \cease{cases} \end{equation} Calculez la complexité de cet algorithme en ne tenant compte que du nombre de tests réalisés. À l’aide de l’algorithme
Poids
écrivez un algorithme
Peser
qui construit une table de \(W\) telle que \(W[i]=west(i)\). Quelle est la complexité de cet algorithme ? Montrez que fifty’on peut écrire un algorithme qui réalise la même opération en \(\Theta(due north)\) avec un facteur caché de \(\frac{1}{2}\).

Écrivez united nations algorithme récursif pour calculer le \(n\)-ème terme de la suite de Syracuse. Comparez le avec l’algorithme itératif.

On appelle dérécursivation tout procédé qui consiste à transformer un algorithme récursif en un algorithme équivalent mais qui ne contient aucun appel récursif (algorithme que 50’on qualifie communément d’itératif). On dit qu’united nations algorithme est récursif concluding s’il ne contient qu’un appel récursif et qu’il s’agit de la dernière education.

Expliquez comment dérécursiver un algorithme récursif terminal avec une boucle. Plus généralement expliquez annotate dérécursiver un algorithme récursif quelconque à l’aide d’une pile auxiliaire globale.

Les chapitres suivants consacrés à la résolution de trois problèmes classiques, le problème des reines, le problème du cavalier et le problème du le problème du Sudoku sont des exemples où la connaissance de l’historique est un élément clef cascade élaborer une stratégie.

Complexité des algorithmes du type
diviser pour régner

Diviser pour régner

Le principe algorithmique dit diviser pour régner consiste à :

  1. diviser
    50’instance d’un problème en sous-instances,
  2. traiter
    indépendamment ces sous-instances,
  3. combiner
    les différents résultats obtenus pour construire une solution au problème initial.

Les algorithmes qui southward’appuient sur ce principe sont souvent récursifs et opèrent sur des instances de plus en plus petites jusqu’à ce que la taille de fifty’instance à traiter rende la résolution du problème unproblematic voire triviale. La
recherche dichotomique
fait partie des premiers algorithmes étudiés de ce type. Notons que 50’algorithme d’addition étudié en classe primaire peut également être classé dans cette catégorie bien qu’il soit itératif. Les nombres sont segmentés en chiffres sur lesquels l’opération d’add-on est élémentaire puisqu’elle consiste à effectuer une simple recherche en table, la pro­pa­ga­tion de la retenue éventuelle combine les additions des sous-instances pour obtenir le ré­sul­tat.

Popular:   Pot De Fer Contre Pot De Terre

Ce principe algorithmique southward’est avéré très efficace pour obtenir de meilleures fonctions de complexité qu’avec une approche globale, d’où sa popularité. Nous le retrouverons dans d’autres algorithmes fondamentaux dans les prochains chapitres comme fifty’algorithme du TriFusion et du TriRapide mais également dans 50’algorithme de recherche par Dichotomie ou encore la multiplication rapide avec l’algorithme de Ka­rat­su­ba ou la transformée de Fourier discrète.

Complexité

La suite des instructions qui définissent un algorithme récursif sont constituées d’un certain nombre d’appels récursifs, que 50’on notera \(a\), sur des entrées \(y_i\) dont la taille est une fraction de la taille \(n:=\#x\) de fifty’entrée initiale \(x\), disons \(n/b\). Les opérations réalisées par fifty’algorithme en dehors de ces \(a\) appels récursifs,
pré-traitement
(incluant le partitionnement de \(x\)) et
post-traitement, a un coût noté \(f(northward)\). La construction d’un algorithme récursif est synthétisée de la manière suivante :

Générique-Récursif(ten,n) DONNEES    10: paramètre    n: entier // taille de ten VARIABLES    i: entier    y: liste DEBUT    SI (n > constante) ALORS
      Pré-traitement
      i ← 1       TQ i ≤ a FAIRE
      Générique-Récursif(yi,northward/b)          i ← i + one       FTQ
      Mail service-traitement
      FSI FIN
    

Pour résumer, on a les variables suivantes :

  • \(northward\) est la taille de l’instance du problème à traiter ;
  • \(a\) est le nombre d’appels récursifs ;
  • \(due north/b\) est la taille (constante) des \(a\) sous-instances ;
  • \(f(north)\) est le coût des instructions hors appels récursifs.

Dans le cas où \(north=1\), le coût de traitement est supposé constant, donc en \(\Theta(one)\). Si 50’on note \(T(n)\) la complexité de cet algorithme, on obtient directement la formule récurrente \brainstorm{equation} T(n)=\brainstorm{cases} \Theta(one),&\text{si}\ n=ane,\\ aT(\frac{north}{b})+f(northward),&\text{sinon.} \cease{cases} \cease{equation} Nous allons estimer cette fonction \(T(due north)\) et pour simplifier les calculs, nous supposerons tout d’abord que \(n\) est une puissance de \(b\), disons \(n=b^k\). Si nous développons l’expression de \(T(n)\), nous obtenons \begin{align*} T(northward)&=a\large(aT(n/b^two)+f(n/b)\big)+f(due north)\\ T(due north)&=a\Large(a\big(aT(n/b^3)+f(north/b^2)\big)+f(n/b)\Big)+f(n)\ldots\\ T(n)&=a^k\Theta(i)+\sum_{i=0}^{thou-1}a^if(due north/b^i). \end{align*} Et si l’on exprime ce résultat en fonction de \(n\), en remarquant que \(a^{\log_bn}=(b^{\log_ba})^{\log_bn}\) soit \(a^{\log_bn}=n^{\log_ba}\) en permutant les exposants, on arrive à \begin{equation}\label{eqrecTn} T(n)=\Theta(northward^{\log_ba})+{\color{yellow}\sum_{i=0}^{\log_bn-1}a^if(n/b^i)}. \end{equation}

Pour obtenir ce résultat, on aurait également pu utiliser fifty’arbre de récursion associé à l’exécution de l’algorithme. La profondeur de cet arbre est évidemment \(\log_bn-ane\). Pour poursuivre ce calcul, il devient nécessaire de faire des hypothèses sur la nature de la fonction \(f\). Il apparaît clairement que le résultat, sans même le connaître, dépend essentiellement du comportement de \(f(north)\) par rapport à la fonction \(due north\mapsto due north^{\log_ba}\). Cascade la suite nous allons noter \(\color{xanthous}S\) la somme de l’équation (\ref{eqrecTn}).

Nous allons étudier trois situations :

Cas 1.
\(f(northward)=O(northward^{\log_ba-\epsilon})\), avec \(\epsilon>0\). La somme \(S\) est donc majorée : \brainstorm{marshal*} Southward&\leq\sum_{i=0}^{\log_bn-one}a^i\left(\frac{n}{b^i}\right)^{\log_ba-\epsilon}\\ &=n^{\log_ba-\epsilon}\sum_{i=0}^{\log_bn-1}\left(\frac{ab^\epsilon}{b^{\log_ba}}\right)^i\\ &=north^{\log_ba-\epsilon}\sum_{i=0}^{\log_bn-1}b^{i\epsilon} \cease{align*} En sommant la série géométrique on aboutit à \begin{marshal*} Due south&\leq n^{\log_ba-\epsilon}\left(\frac{b^{\epsilon\log_bn}-1}{b^\epsilon-ane}\right)\\ &=n^{\log_ba-\epsilon}\left(\frac{n^\epsilon-ane}{b^\epsilon-one}\right)\\ &=\frac{1}{b^\epsilon-one}\left(due north^{\log_ba}-n^{\log_ba-\epsilon}\right) \end{align*} Comme \(1/(b^\epsilon-1)\) est une constante, on peut conclure en disant que la somme \(S\) est majorée par une constante fois \(n^{\log_ba}\) et par conséquent déterminer la classe de la fonction de complexité : \(T(north)=O(n^{\log_ba})\).

Cas ii.
\(f(due north)=\Theta(n^{\log_ba})\). Si on remplace dans la somme \(S\), la fonction \(f\) par \(n\mapsto northward^{\log_ba}\), on obtient une quantité \(Due south’\) qui permet de borner \(South\). Il est en effet aisé de déduire de l’appartenance de \(f\) à la classe \(\Theta\) qu’il existe deux constantes positives \(\alpha\) et \(\beta\) telles que \(\alpha S’\leq S \leq \beta S’\). Cascade éviter d’allourdir inutilement les calculs, on se contente donc d’évaluer la quantité \(S’\). On a \begin{align*} S’&=\sum_{i=0}^{\log_bn-1}a^i\left(\frac{due north}{b^i}\right)^{\log_ba}\\ &=n^{\log_ba}\sum_{i=0}^{\log_bn-i}\left(\frac{a}{b^{\log_ba}}\right)^{i}\\ &=n^{\log_ba}\sum_{i=0}^{\log_bn-1}1\\ &=n^{\log_ba}\log_bn. \cease{marshal*} En réinjectant ce résultat dans les deux inégalités issues de (\ref{eqrecTn}), on conclut avec

\[T(north)=\Theta(due north^{\log_ba}\log_bn).\]

Cas 3.
Il existe \(c<1\) tel que pour tout \(n\geq b\), \(af(n/b)\leq cf(n)\). C’est le cas où le coût de la récursivité est plus faible que celui du calcul intra algorithme. Dans un premier temps, l’expression de la somme \(S\) nous permet immédiatement d’affirmer que \(Southward=\Omega(f(n))\). Introduisons l’hypothèse dans l’expression de \(Due south\) : \[\leq\sum_{i=0}^{\log_bn-1}c^if(due north)=f(n)\sum_{i=0}^{\log_bn-1}c^i.\] La somme de la série géométrique vaut \((i-c^{\log_bn})/(1-c)\) et comme \(c<1\) cette somme est inférieure à \(1/(1-c)\) et par conséquent \(S=O(f(n))\). Cascade montrer que \(T(northward)=\Theta(f(n))\), il reste united nations petit travail qui fait l’objet de l’exercice suivant.

Montrez que due south’il existe une constante \(c < 1\) telle que \(af(n/b) < cf(n)\) pour \(n\) suffisamment grand, alors il existe une constante \(\epsilon > 0\) telle que \(f(n)=\Omega(n^{\log_ba+\epsilon})\). Concluez alors le cas 3 en montrant que \(T(north)=\Theta(f(n))\).

Il nous reste maintenant à généraliser ces trois résultats dans le cas où \(n\) n’est pas une puissance entière de la base \(b\). Nous allons étudier brièvement le cas où l’appel se fait sur \(\lceil north/b\rceil\), fifty’autre cas étant similaire. À chaque appel récursif, fifty’argument \(n\) passe à \(\lceil n/b\rceil\), puis \(\lceil\lceil n/b\rceil/b\rceil\) et \(\lceil\lceil\lceil n/b\rceil/b\rceil/b\rceil\) et ainsi de suite… Il faut donc déterminer au bout de combien d’appels le paramètre est strictement inférieur à \(b\).

En posant \(n_i=n\) si \(i=0\) et \(n_i=\lceil n_{i-ane}/b\rceil\) sinon, on montre que \(n_i=\lceil n/b^i\rceil\). D’autre office, comme \(\log_bn<\lfloor\log_bn\rfloor+1\) on a \(n < b.b^{\lfloor\log_bn\rfloor}\) d’où \(n/b^{\lfloor\log_bn\rfloor} < b\) et finalement \(\lceil n/b^{\lfloor\log_bn\rfloor}\rceil < b\) machine \(n/b^{\lfloor\log_bn\rfloor}=\lceil northward/b^{\lfloor\log_bn\rfloor}\rceil\). Le nombre d’appels récursifs hormis le premier appel est donc égal à \(\lfloor\log_bn\rfloor.\) Il suffit donc de remplacer \(\log_bn\) par \(\lfloor\log_bn\rfloor\) dans la sommation de l’équation (\ref{eqrecTn}). Nous laissons au lecteur le soin de refaire les calculs avec cette nouvelle borne.

Soient \(a\geq ane\) et \(b > 1\) deux constantes, et \(f:{\mathbf North}\rightarrow {\mathbf N}\). Soit \(T:{\mathbf North}\rightarrow {\mathbf Northward}\) une fonction définie par la récurrence suivante : \begin{equation} T(n)=\begin{cases} \Theta(1)&\text{si}\ due north=1,\\ aT(n/b)+f(n) &\text{sinon}. \finish{cases} \end{equation} où \(n/b\) désigne soit l’entier \(\lfloor northward/b\rfloor\) soit l’entier \(\lceil north/b\rceil\). Alors la fonction de complexité \(T\) peut être bornée asymptotiquement de la façon suivante :

  1. Si \(f(north)=O(north^{\log_ba-\epsilon})\) pour une certaine constante \(\epsilon>0\), alors \(T(n)=\Theta(n^{\log_ba})\) ;
  2. Si \(f(north)=\Theta(n^{\log_ba})\), alors \(T(northward)=\Theta(n^{\log_ba}\log_bn)\) ;
  3. Si \(f(n)=\Omega(north^{\log_ba+\epsilon})\) pour une certaine constante \(\epsilon>0\) et south’il existe \(c<1\) telle que \(af(north/b)\leq cf(north)\) pour \(n\) suffisamment grand, alors \(T(n)=\Theta(f(n))\).

Ce résultat général de complexité est connu sous le nom de
Master Theorem
dans la littérature anglo-saxonne. Il ne traite pas tous les types de récurrences que l’on peut rencontrer en algorithmique. Le théorème d’Akra-Bazzi, établi en 1998 généralise ce théorème.

De La Récurrence À La Récursivité Grand Oral

Source: http://zanotti.univ-tln.fr/ALGO/III/Recursivite.html

Ce site utilise des cookies pour améliorer la convivialité. Vous acceptez en utilisant le site Web plus loin.

Politique de confidentialité des cookies