Annonce 1

2nde Générale SNT

Annonce 2

1ère Générale NSI

Annonce 3

Term. Générale NSI

Annonce 4

Terminale STI2D SIN

 

1. Récursivités simples

Dans cette partie nous allons donc traiter le cas des algorithmes récursifs, et voir comment le calcul de leur complexité se déduit d'une étude de suite.

 Position du problème

Dans un algorithme itératif, le décompte du nombre d'opérations élémentaires se fait en additionnant le nombre d'opérations de chaque itération. C'est pourquoi dans le chapitre précédent nous avons souvent utilisé des calculs de sommes pour arriver à nos fins.

La complexité d’un algorithme récursif traitant des données d'une certaine taille va quand à elle naturellement dépendre de la complexité du même algorithme avec des données de taille inférieure. Cette complexité va donc être une suite définie par récurrence.

Définition

Soit kk élément de Nℕ∗, et (un)nN(un)n∈ℕ une suite réelle.

On dit que la suite (un)nN(un)n∈ℕ est une suite définie par une récurrence d'ordre kk s'il existe une fonction ff définie sur Rkℝk et à valeur dans R telle que

un=f(un1,un2,...,unk)un=f(un−1,un−2,...,un−k)

Dans la suite de cette partie on se limitera au cas des suites arithmético-géométriques et des suites récurrentes linéaires d’ordre 22. Cela sera déjà bien suffisant pour calculer la complexité de nombreux algorithmes récursifs.

 Suites arithmético-géométriques

Commençons par une définition, sans doute déjà connue du lecteur.

Définition

Une suite réelle (un)nN(un)n∈ℕ est dite arithmético-géométrique s'il existe deux réels aa et bb tels que

nN,un=aun1+b∀n∈ℕ*, un=aun−1+b

On prend l'habitude de distinguer deux cas particuliers, celui des suites arithmétiques et celui des suites géométriques.

Définition

Avec les notations de la définition précédente :

  • Si a=1a=1, on dit que la suite (un)nN(un)n∈ℕ est une suite arithmétique de raison bb.

  • Si b=0b=0, on dit que la suite (un)nN(un)n∈ℕ est une suite géométrique de raison aa.

Le résultat suivant nous donne l'expression explicite du terme général d'une suite arithmético-géométrique.

Propriété

Soit (un)nN(un)n∈ℕ une suite arithmético-géométrique associée aux réels aa et bb.

Si a=1a=1, alors

nN,un=u0+nb∀n∈ℕ,  un=u0+nb

Si a1a≠1, et si l'on pose l=b1al=b1-a, alors

nN,un=(u0l)an+l∀n∈ℕ,  un=(u0−l)an+l
[Note]

On admettra ce résultat, ce n’est pas l’objet de ce cours. Ce n’est ceci-dit pas bien méchant à démontrer.

Nous utiliserons peu cette expression exacte, mais plutôt l'approximation suivante qui nous renseigne sur l'ordre de grandeur du terme général d'une suite arithmético-géométrique.

Propriété

Soit (un)nN(un)n∈ℕ une suite arithmético-géométrique associée aux réels aa et bb.

On suppose que aabb et u0u0 sont positifs.

Si a=1a=1un=Θ(n)un=Θ(n).

Si a>1a>1un=Θ(an)un=Θ(an).

[Note]

La restriction que aabb et u0u0 soient positifs n'est absolument pas génante car ça sera toujours le cas dans notre contexte de calculs de complexité.

Voyons maintenant sur des exemples comment appliquer ce qui précède. Le premier concerne la très fameuse fonction factorielle.

Example 1.1. Complexité de la fonction factorielle récursive

Rappelons tout d'abord que n!=1×2×3×...×nn!=1×2×3×...×n et que cette fonction vérifie la relation de récurrence n!=n×(n1)!n!=n×(n-1)!.

L'implémentation en Python de cette fonction est :

def factorielleRecursive(n):
    if n == 0:
        return 1
    else:
        return n*factorielleRecursive(n-1)

Cette fonction n'est composée que d'une structure conditionelle.

Si n>0n>0, une opération élémentaire (une comparaison) est effectuée lors du test, et une autre (un produit) lors de l'appel récursif. On a donc dans ce cas T(n)=T(n1)+2T(n)=T(n-1)+2.

Si n=0n=0, seule la comparaison a lieu donc T(0)=1T(0)=1.

La complexité TT est donc une suite arithmético-géométrique associée aux constantes a=1a=1 et b=2b=2.

D'après les résultats précédents, on a alors T(n)=1+2nT(n)=1+2n et surtout T(n)=Θ(n)T(n)=Θ(n). Cet algorithme est donc de complexité linéaire.

[Note]

A noter que l'algorithme itératif calculant cette factorielle a la même complexité. Le voici en effet en Python :

def factorielleIterative(n):
    resultat = 1
    for i in range(2,n+1):
        resultat *= i
    return resultat

On a une structure for qui réalise n1n-1 itérations, chacune comportant le même nombre fixe d'opérations élémentaires. C'est pourquoi là aussi T(n)=Θ(n)T(n)=Θ(n).

L'exemple suivant est le fameux problème des tours de Hanoï, imaginé par le mathématicien français Edouard Lucas (1842-1891).

[Note]

Ce problème a été recontré dans les séances d'exercices du cours 1ADS mais nous allons le redétailler.

Example 1.2. Problème des tours de Hanoï

Le but est de déplacer nn disques de diamètres différents, d’une tour initiale (celle de gauche) à une tour finale (celle de droite) en passant par une tour intermédiaire (celle du milieu).

Initialement, tous les disques sont empilés sur la tour initiale, du plus grand au plus petit.

Les règles de déplacement sont les suivantes :

  • On ne peut bouger qu’un seul disque à la fois.

  • On ne peut déplacer un disque que vers une tour vide, ou sur un disque plus grand.

Etudions "à la main" le cas n=3n=3.

Voici la position initiale :

Effectuons ces trois premiers mouvements :

On a donc réussi à bouger les deux plus petits disques vers la tour intermédiaire en passant par la tour finale.

Bougeons maintenant le plus grand :

Il ne reste plus qu'à effectuer ces trois derniers mouvements qui ressemblent évidemment fortement aux trois premiers :

Et le problème est résolu pour trois disques.

Essayons maintenant de reproduire dans le cas général ce que l'on vient de faire dans ce cas très particulier. On arrive vite à la conclusion que la résolution du problème pour toute valeur de nn est récursive :

  • On déplace n1n-1 disques de la tour initiale à la tour intermédiaire en passant par la tour finale.

  • On déplace le plus grand disque de la tour initiale vers la tour finale.

  • On déplace n1n-1 disques de la tour intermédiaire à la tour finale en passant par la tour initiale.

Le cas de base étant le déplacement d'un seul disque.

En Python cela donne cette implémentation :

def hanoi(de,vers,via,n):
    if n==1:
        print(de," vers ",vers)
    else:
        hanoi(de,via,vers,n-1)
        print(de," vers ",vers)
        hanoi(via,vers,de,n-1)


hanoi("1","3","2",3)

Sans surprises, pour trois disques on retrouve bien les mouvements précédemment mis en images :

1  vers  3
1  vers  2
3  vers  2
1  vers  3
2  vers  1
2  vers  3
1  vers  3

Venons-en maintenant au calcul de la complexité de cette procédure qui n'est composée que d'une structure conditionnelle.

Si n>1n>1, une opération élémentaire (une comparaison) est effectuée lors du test, une autre lors de l'affichage, et on a deux appels récursifs. On a ainsi T(n)=2T(n1)+2T(n)=2T(n-1)+2.

Si n=1n=1, seule la comparaison a lieu donc T(1)=1T(1)=1.

La complexité TT est donc une suite arithmético-géométrique associée aux constantes a=2a=2 et b=2b=2.

D’après le résultat précédent, on a alors T(n)=Θ(2n)T(n)=Θ(2n). Cet algorithme est donc de complexité exponentielle.

 Suites récurrentes linéaires

Cette sous-partie n'est pas conceptuellement très difficile, mais elle demande de la vigilance car certains résultats sont assez techniques.

On distinguera le cas des suites homogènes des suites non homogènes, et l'on verra qu'en pratique ce sont ces dernières qui nous intéresserons le plus.

 Suites homogènes

Commençons naturellement par une définition du concept.

Définition

Une suite réelle (un)nN(un)n∈ℕ est une suite récurrente linéaire homogène d'ordre deux s'il existe deux réels aa et bb tels que

n2,un=aun1+bun2∀n≥2,  un=aun−1+bun−2

Pour étudier une telle suite, on doit tout d'abord lui associer un polynôme dit caractéristique.

Définition

Soit (un)nN(un)n∈ℕ une suite récurrente linéaire homogène d'ordre deux associée aux réels aa et bb.

Le polynôme caractéristique de la suite (un)nN(un)n∈ℕ est par définition le polynôme x2axbx2-ax-b.

L'équation caractéristique de la suite (un)nN(un)n∈ℕ est alors l'équation x2axb=0x2-ax-b=0.

Le terme général d'une suite récurrente linéaire homogène d'ordre deux va alors s'exprimer en fonction des racines de son polynôme caractéristique.

[Note]

On ne fera pas l'insulte au lecteur de lui rappeler comment l'on calcule les racines d'un polynôme du second degré.

Propriété

Soit (un)nN(un)n∈ℕ une suite récurrente linéaire homogène d'ordre deux et soit ΔΔ le discriminant de son équation caractéristique.

Si Δ>0Δ>0, en notant x1x1 et x2x2 les deux racines réelles distinctes du polynôme caractéristique, on a

λ,μR,nN,un=λxn1+μxn2∃λ,μ∈ℝ, ∀n∈ℕ, un=λx1n+μx2n

Si Δ=0Δ=0, en notant xx la racine réelle double du polynôme caractéristique, on a

λ,μR,nN,un=(λn+μ)xn∃λ,μ∈ℝ, ∀n∈ℕ, un=(λn+μ)xn

Dans les deux cas, les constantes λλ et μμ se déterminent à l’aide de la valeur des deux premiers termes de la suite. On a alors un système linéaire de deux équations à deux inconnues à résoudre.

[Note]

On ne traitera pas le cas où Δ<0Δ<0 car on ne le rencontrera pas lors de nos calculs de complexités.

En un mot, on peut alors montrer que les suites sont alors exprimables à l’aide des fonctions cosinus et sinus. Ou au choix de l’exponentielle complexe.

Appliquons ce resultat sur un exemple célèbre, la suite due au mathématicien italien Leonardo Fibonacci (1175-1250).

Example 1.3. Suite de Fibonacci

La suite de Fibonnaci est la suite récurrente linéaire homogène d'ordre deux définie par

un=0si n=01si n=1un1+un2si n2un={0si n=01si n=1un−1+un−2si n≥2

L'équation caractéristique de cette suite est x2x1=0x2-x-1=0. Son discriminant ΔΔ est égal à 55. Le polynôme caractéristique possède donc deux racines distinctes x1=1+52x1=1+52 et x2=152x2=1-52.

D'après le résultat précédent

λ,μR,nN,un=λ(1+52)n+μ(152)n∃λ,μ∈ℝ, ∀n∈ℕ, un=λ(1+52)n+μ(1−52)n

On détermine alors λλ et μμ en se servant de la valeur des deux premiers termes u0u0 et u1u1.

On a en effet d'une part u0=0u0=0 et u1=1u1=1 d'après la définition de la suite, et d'autre part d'après l'expression du terme général

u0=λ+μu1=λ(1+52)+μ(152){u0=λ+μu1=λ(1+52)+μ(1−52)

On doit donc résoudre le système

0=λ+μ1=λ(1+52)+μ(152){0=λ+μ1=λ(1+52)+μ(1−52)

On trouve λ=15λ=15 et μ=15μ=-15. Finalement, on obtient

nN,un=15(1+52)n15(152)n∀n∈ℕ, un=15(1+52)n−15(1−52)n

Rappelons maintenant un résultat classique sur les limites, qui nous permettra ensuite d'obtenir l'ordre de grandeur d'une suite récurrente linéaire.

Propriété

Soit xx élément de R.

On a

  • Si x>1x>1limnxn=+limn→∞xn=+∞.

  • Si 1<x<1-1<x<1limnxn=0limn→∞xn=0.

  • Si x1x≤-1xnxn n'a pas de limite quand n+n→+∞.

Le prochain résultat sera celui qui in fine nous servira lors de nos calculs de complexité.

Propriété

Soit (un)nN(un)n∈ℕ une suite récurrente linéaire homogène d'ordre deux et soit ΔΔ le discriminant de son équation caractéristique.

On suppose que Δ>0Δ>0 et l'on note x1x1 et x2x2 les deux racines réelles distinctes du polynôme caractéristique.

Si x1>1x1>1, et si |x1|>|x2||x1|>|x2|, alors un=Θ(xn1)un=Θ(x1n).

Cette propriété signifie moralement que sous certaines conditions xn1x1n impose le comportement asymptotique de la suite. Appliquons la à la suite de Fibonacci.

Example 1.4. Ordre de grandeur de la suite de Fibonacci

Pour la suite de Fibonacci, on a montré que Δ=5Δ=5x1=1+52x1=1+52 et x2=152x2=1-52. Les hypothèses de la propriété précédente sont donc vérifiées. Ainsi un=Θ((1+52)n)un=Θ((1+52)n).

 Suites non homogènes

La différence avec une suite homogène réside dans la présence d'un terme supplémentaire dans l'équation de récurrence.

Définition

Une suite réelle (vn)nN(vn)n∈ℕ est une suite récurrente linéaire non homogène d'ordre deux s'il existe deux réels aa et bb et une fonction ff de N dans R, tels que

n2,vn=avn1+bvn2+f(n)∀n≥2, vn=avn−1+bvn−2+f(n)

On pourrait donner des résultats très précis sur le terme général d'une telle suite, mais nous nous contenterons de la propriété suivante qui en donne son ordre de grandeur. En un mot, pour étudier une suite non homogène il convient d'étudier la suite homogène associée, i.e. la suite obtenue en "supprimant" la fonction ff dans l'équation de récurrence.

Propriété

Soit (vn)nN(vn)n∈ℕ une suite récurrente linéaire non homogène d'ordre deux associée aux réels aa et bb et à la fonction ff.

On considère (un)nN(un)n∈ℕ la suite récurrente linéaire homogène d'ordre deux associée aux réels aa et bb. Soit ΔΔ le discriminant de son équation caractéristique. On suppose que Δ>0Δ>0 et l'on note x1x1 et x2x2 les deux racines réelles distinctes du polynôme. caractéristique.

Si x1>1x1>1, si |x1|>|x2||x1|>|x2|, et si ff est une fonction polynomiale alors vn=Θ(xn1)vn=Θ(x1n).

Moralement cela signifie que si elle est polynomiale, la fonction ff n’influe pas sur le comportement de la suite, et que l'ordre de grandeur de la suite non homogène est alors celui de la suite homogène.

Terminons cette partie par un exemple, avec l'implémentation de la suite de Fibonacci et le calcul de sa complexité.

Example 1.5. Complexité de la fonction récursive calculant le terme général de la suite de Fibonacci

Voici une fonction récursive calculant le nième terme de la suite de Finonacci :

def fibonacci(n):
    if n<2:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Si n>2n>2, une opération élémentaire (une comparaison) est effectuée lors du test et une autre (une addition) entre les deux appels récursifs. On a ainsi T(n)=T(n1)+T(n2)+2T(n)=T(n-1)+T(n-2)+2.

Si n=0n=0 ou n=1n=1, seule la comparaison a lieu donc T(0)=T(1)=1T(0)=T(1)=1.

Dans cet exemple la complexité est donc une suite récurrente linéaire non homogène d'ordre deux.

La suite homogène associée est

un=1si n=01si n=1un1+un2si n2un={1si n=01si n=1un−1+un−2si n≥2

Cette dernière suite est quasiment celle de Fibonacci, seul le premier terme diffère. La relation de récurrence est en tout cas la même que pour la suite de Fibonacci donc (avec les notations précédentes) Δ=5Δ=5x1=1+52x1=1+52 et x2=152x2=1-52.

D'autre part, la fonction ff de la relation de récurrence non linéaire est constante égale à 22 donc en particulier polynomiale.

Toute les hypothèses de la propriété précédente sont vérifiées, ainsi T(n)=Θ((1+52)n)T(n)=Θ((1+52)n). La complexité de cet algorithme est donc exponentielle.

 Algorithmes de type "diviser pour régner"

Après les récursivités relativement simples de la partie précédente, nous allons maintenant nous confronter à celles inhérentes à l'utilisation d'une technique de type "diviser pour régner".

Soyons honnête, ce qui va suivre est délicat et demandera de gros efforts au lecteur.

 Position du problème

Commençons par rappeler les trois étapes du paradigme "diviser pour régner" :

  1. Diviser : on divise les données initiales en plusieurs sous-parties.

  2. Régner : on résout récursivement chacun des sous-problèmes associés (ou on les résout directement si leur taille est assez petite).

  3. Combiner : on combine les différents résultats obtenus pour obtenir une solution au problème initial.

Avec ce paradigme, la complexité d’un algorithme traitant des données de taille nn va naturellement dépendre de la complexité du même algorithme avec des données de taille n/bn/b, où bb est le facteur avec lequel on divise le problème en sous-problèmes.

Il va falloir de plus tenir compte de la complexité de l’étape de combinaison des résultats des sous-problèmes.

Avant le cas général, nous allons commencer par étudier un exemple, celui du tri fusion.

 L’exemple du tri fusion

Le tri fusion consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée.

[Note]

Nous renvoyons le lecteur à ce chapitre du cours 1ADS pour la description des principaux algorithmes de tri, y compris celui-ci.

Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :

  1. Diviser la liste en deux sous-listes de même taille (à un élément près) en la "coupant" par la moitié.

  2. Trier récursivement chacune de ces deux sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.

  3. Fusionner les deux sous-listes triées en une seule.

Example 1.6. Déroulement du tri fusion sur un exemple

On considère la liste suivante de sept entiers :

On la scinde en deux sous-listes en la coupant par la moitié :

Sous-listes que l’on scinde à leur tour :

Sous-listes que l’on scinde à leur tour :

Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées :

De nouveau une étape de fusionnnement :

Une dernière fusion :

On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé :

En voici son implémentation en Python :

def fusion(l,first,middle,last):
    i,j = first,middle+1
    pro = []
    while (i<=middle) and (j<=last):
        if l[i]<=l[j]:
            pro.append(l[i])
            i+=1
        else:
            pro.append(l[j])
            j+=1
    while i<=middle:
        pro.append(l[i])
        i+=1
    while j<=last:
        pro.append(l[j])
        j+=1
    for k in range(last-first+1):
        l[first+k] = pro[k]

def triFusionRec(l,first,last):
    if first<last:
        triFusionRec(l,first,(first+last)//2)
        triFusionRec(l,((first+last)//2)+1,last)
        fusion(l,first,(first+last)//2,last)

def triFusion(l):
    triFusionRec(l,0,len(l)-1)
[Note]

Bien prendre le temps d'appréhender le fonctionnement de cet algorithme.

Voici maintenant le résultat établissant la complexité du tri fusion. Vu la nature même de celui-ci, le lecteur comprendra facilement qu'il n'y a pas de meilleur ou pire des cas.

Théorème

La complexité du tri fusion est T(n)=Θ(nlog2(n))T(n)=Θ(nlog2(n)).

Il s'agit de la meilleure complexité que puisse avoir un algorithme de tri.

L'idée pour démontrer ce résultat est de construire l'arbre des appels récursifs, d'évaluer le coût de chaque sommet, puis d'en faire la somme.

Démonstration

Commençons par remarquer que la procédure de fusion est de complexité linéaire. Plus précisément, pour fusionner deux tableaux de taille n/2n/2, on a une complexité en Θ(n)Θ(n). Dans l’algorithme précédent nn étant la différence entre "last" et "first" et donc n/2n/2 la différence entre "middle" et "first" ou "last" et "middle". Cela provient du fait que l'on traite une et une seule fois chaque élément des deux listes à fusionner, et que ce traitement est de complexité constante.

Dans la suite de cette preuve on va supposer que nn est une puissance de 22, cela nous permettra d'avoir des subdivisions qui "tombent juste".

A chaque appel récursif, on subdivise un problème de taille nn en 22 sous-problèmes de taille n/2n/2, les 22 sous-listes que l'on va trier récursivement. A un niveau jj on aura donc 2j2j sous-problèmes. Chacun de ces sous-problèmes sera de taille n/2jn/2j, et aura ainsi un coût de l'ordre de n/2jn/2j (rappelons que la procédure de fusion est de complexité linéaire).

Le coût d'un niveau jj est donc 2j×(n2j)=n2j×(n2j)=n. C'est en effet le nombre de sous-problèmes du niveau jj multiplié par le coût de chacun d'eux.

Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question :

On a supposé que nn était une puissance de 22, donc nn est de la forme n=2hn=2h où hh est la hauteur de l'arbre. C'est pourquoi h=log2(n)h=log2(n). Egalité que l'on a utilisée dans la figure précédente.

Le nombre de niveaux est alors égal à h+1h+1 (ne pas oublier le niveau initial), i.e. log2(n)+1log2(n)+1. On a de plus déjà constaté que le coût de chaque niveau était égal à nn.

Le coût total est alors égal à la somme des coûts de tous les niveaux, i.e. n×(log2(n)+1)n×(log2(n)+1). Q.E.D.

[Note]

Dans la preuve précédente, on a supposé que nn était une puissance de 22, ce qui a facilité notre étude de l'arbre. Si ce n'est pas le cas, il faut alors l'encadrer entre deux puissances de 22, puis effectuer le raisonnement précédent sur ces deux puissances. On arrive alors relativement facilement au résultat.

Nous ne rentrerons pas dans ces détails car ils n'apportent rien en terme de compréhension profonde.

 Le Master Theorem (version simplifiée)

Dans cette sous-partie nous n'allons plus nous limiter au cas du tri fusion, mais nous allons présenter et démontrer un résultat applicable à la majorité des algorithmes de type diviser pour régner.

Nous allons donc nous intéresser à des algorithmes de la forme :

def divideAndConquer(n):
    if n ==1:
        end of processing
    else:
        divideAndConquer(n//b)
        divideAndConquer(n//b)
        ... a times
        divideAndConquer(n//b)
        work of cost f(n) for dividing the problem
            and merging the solutions to
            the subproblems

Un problème de taille nn est ainsi divisé en aa sous-problèmes de taille n/bn/b, avec un coût f(n)f(n) pour combiner les résultats de ces sous-problèmes.

[Note]

Il est donc implicitement supposé que chaque sous-problème a la même taille. Dans le cas contraire le Master Theorem ne peut s'appliquer.

Master Theorem

Soient a1a≥1b>1b>1, et TT une fonction vérifiant

T(n)=aT(nb)+f(n)T(n)=aT(nb)+f(n)

Les différents paramètres s'interprètent comme suit :

  • nn est la taille du problème.

  • aa est le nombre de sous-problèmes.

  • n/bn/b est le taille de chaque sous-problèmes.

  • f(n)f(n) est le coût de la subdivision et de la combinaison des solutions des sous-problèmes.

On suppose de plus que f(n)=Θ(nd)f(n)=Θ(nd).

Alors

T(n)=⎪ ⎪⎪ ⎪Θ(nd)si logb(a)<dΘ(ndlog(n))si logb(a)=dΘ(nlogb(a))si logb(a)>dT(n)={Θ(nd)si logb(a)<dΘ(ndlog(n))si logb(a)=dΘ(nlogb(a))si logb(a)>d

On a également la formulation équivalente suivante

T(n)=⎪ ⎪⎪ ⎪Θ(nd)si a<bdΘ(ndlog(n))si a=bdΘ(nlogb(a))si a>bdT(n)={Θ(nd)si a<bdΘ(ndlog(n))si a=bdΘ(nlogb(a))si a>bd
[Note]

Il n’est pas nécessaire de préciser la base du logarithme dans le deuxième cas, puisque rappelons le toutes les fonctions logarithmes diffèrent juste d’une constante multiplicative.

Comme lors de la démonstration de la complexité du tri fusion, nous allons étudier l'arbre des appels récursifs en faisant la somme des coûts de chaque sommet. Certains arguments seront donc similaires à ceux utilisés dans la sous-partie précédente.

Nous aurons également besoin du petit lemme suivant :

Lemme

Soit qRq∈ℝ.

Si q<1q<1, on a

rj=0qj11q∑j=0rqj≤11-q

Si q>1q>1, on a

rj=0qjqr(1+1q1)∑j=0rqj≤qr(1+1q-1)

Démonstration du lemme

On sait (voir paragraphe 1.4 du chapitre, 1) que si q1q≠1, on a

rj=0qj=1qr+11q=qr+11q1∑j=0rqj=1-qr+11-q=qr+1-1q-1

Si q<1q<1, on se sert de la première égalité et du fait que 1qr+1<11-qr+1<1. Le résultat en découle immédiatement.

Si q>1q>1, on utilise cette fois la seconde égalité et le fait que qr+11<qr+1qr+1-1<qr+1. On obtient alors

rj=0qjqr+1q1∑j=0rqj≤qr+1q-1

Il ne reste plus qu'à factoriser par qrqr et à changer la forme de la fraction.

Démonstration du Master Theorem

Dans la suite de cette preuve on va supposer que nn est une puissance de bb, cela nous permettra d'avoir des subdivisions qui "tombent juste".

A chaque appel récursif, on subdivise un problème de taille nn en aa sous-problèmes de taille n/bn/b. A un niveau jj on aura donc ajaj sous-problèmes. Chacun de ces sous-problèmes sera de taille n/bjn/bj, et aura ainsi un coût de l'ordre de (n/bj)d(n/bj)d (rappelons que la complexité de la procédure de combinaison est en Θ(nd)Θ(nd)).

Le coût d'un niveau jj est donc aj×(nbj)daj×(nbj)d. C'est en effet le nombre de sous-problèmes du niveau jj multiplié par le coût de chacun d'eux.

Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question :

On a supposé que nn était une puissance de bb, donc nn est de la forme n=bhn=bh où hh est la hauteur de l'arbre. C'est pourquoi h=logb(n)h=logb(n). Egalité que l'on a utilisée dans la figure précédente.

Contrairement au tri fusion, chaque niveau n'a pas le même coût, et l'on ne peut donc avoir le coût total en multipliant le nombre de niveaux par le coût de chacun d'eux.

Pour estimer T(n)T(n) on doit ainsi calculer la somme

logb(n)j=0aj×(nbj)d∑j=0logb(n)aj×(nbj)d

On peut factoriser par ndnd dans cette somme puisque ce terme ne dépend pas de l'indice jj de sommation. On obtient alors l'égalité

logb(n)j=0aj×(nbj)d=ndlogb(n)j=0(abd)j∑j=0logb(n)aj×(nbj)d=nd∑j=0logb(n)(abd)j

On reconnaît la somme des premiers termes d'une suite géométrique de raison q=abdq=abd. La valeur de cette quantité va donc déterminer celle de la complexité totale. Plus précisément, on devra distinguer les cas où abdabd est plus petit, plus grand ou égal à 11.

Cas où a=bda=bd :

On a alors abd=1abd=1, et l'on est ramené à une somme de termes constants

ndlogb(n)j=0(abd)j=ndlogb(n)j=01=nd×(logb(n)+1)nd∑j=0logb(n)(abd)j=nd∑j=0logb(n)1=nd×(logb(n)+1)

D'où

T(n)=Θ(ndlog(n))T(n)=Θ(ndlog(n))

Cas où a<bda<bd :

On utilise la première inégalité du lemme pour obtenir

ndlogb(n)j=0(abd)jnd11abdnd∑j=0logb(n)(abd)j≤nd11−abd

D'où

T(n)=Θ(nd)T(n)=Θ(nd)

Cas où a>bda>bd :

On utilise cette fois la seconde inégalité du lemme. Il vient

ndlogb(n)j=0(abd)jnd(abd)logb(n)(1+1abd1)nd∑j=0logb(n)(abd)j≤nd(abd)logb(n)(1+1abd−1)

Quelques changements d'expressions dues aux règles opératoires usuelles sur les puissances conduisent à

ndbdlogb(n)=ndbdlogb(n)=nd(blogb(n))dndbdlogb(n)=ndb−dlogb(n)=nd(blogb(n))−d

Or l'on sait que les fonctions logarithmes et exponentielles de base bb sont réciproques l'une de l'autre. Cela implique en particulier que blogb(n)=nblogb(n)=n

On a alors

nd(blogb(n))d=ndnd=1nd(blogb(n))−d=ndn−d=1

Cela prouve que

ndlogb(n)j=0(abd)jalogb(n)(1+1abd1)nd∑j=0logb(n)(abd)j≤alogb(n)(1+1abd−1)

Et donc

T(n)=Θ(alogb(n))T(n)=Θ(alogb(n))

Il ne reste plus qu'à constater que alogb(n)=nlogb(a)alogb(n)=nlogb(a). Cela est vrai car les logarithmes dans la base bb de chacun de ces deux termes sont égaux à logb(a)×logb(n)logb(a)×logb(n).

[Note]

Si nn n'est pas une puissance de bb il faut procéder par encadrement. Comme pour le tri fusion nous ne rentrerons pas dans ces détails.

Example 1.7. Retour sur le tri fusion

Le tri fusion rentre bien sûr dans le cadre du Master Theorem.

A chaque appel récursif, on y subdivise un problème de taille nn en 22 sous-problèmes de taille n/2n/2. On a donc a=2a=2 et b=2b=2.

De plus la procédure de fusion est de complexité linéaire donc d=1d=1.

On est ainsi dans le cas où a=bda=bd. La complexité est alors T(n)=Θ(ndlog(n))T(n)=Θ(ndlog(n))i.e. T(n)=Θ(nlog(n))T(n)=Θ(nlog(n)).

On retrouve bien le résultat démontré sur ce cas particulier au début de cette partie.

Pour terminer cette sous-partie, on propose au lecteur un petit exercice corrigé afin qu'il s'interroge sur les conditions d'application du Master Theorem.

Exercice corrigé

 

Expliquer dans chacun des cas suivants pourquoi le Master Theorem ne s'applique pas :

  1. T(n)=2nT(n2)+n3T(n)=2nT(n2)+n3.

  2. T(n)=T(n2)+T(n4)+n2T(n)=T(n2)+T(n4)+n2.

  3. T(n)=12T(n2)+nT(n)=12T(n2)+n.

[Note]

Si l'on se retrouve dans une situation où le Master Theorem ne s'applique pas, il faut considérer l'arbre des appels récursifs et l'analyser en détail. Un peu comme dans la preuve du théorème, mais en prenant bien sûr en compte les facteurs qui ont fait qu'il ne s'appliquait pas.

 Interprétation des trois cas du Master Theorem

Livrons nous maintenant à une petite interprétation de chacun des cas du Master Theorem afin de mieux en comprendre leur essence.

Rappelons que le coût d'un niveau jj est proportionnel à aj×(nbj)daj×(nbj)d, quantité que l'on peut mettre sous la forme nd×(abd)jnd×(abd)j.

La constante aa peut être vue comme la vitesse de prolifération des sous-problèmes, et le terme bdbd comme la vitesse de diminition du coût de traitement par sous-problème.

Le fait que l'une de ces vitesses prenne le pas sur l'autre ou au contraire qu'elles se compensent expliquera la complexité finale.

Voici les trois situations possibles :

  1. Cas où a<bda<bd : le coût d’un niveau est une fonction décroissante de jj. Moralement la complexité sera essentiellement celle de l’appel initial donc en ndnd.

  2. Cas où a=bda=bd : le coût d’un niveau est une fonction constante de jj et vaut ndnd. La complexité sera alors égale à ndnd multiplié par le nombre de niveau qui est logb(n)logb(n).

  3. Cas où a>bda>bd : le coût d’un niveau est une fonction croissante de jj. Moralement la complexité sera essentiellement celle due aux appels finaux. Elle sera donc de l’ordre du nombre de feuilles de l’arbre des appels récursifs, i.e. nlogb(a)nlogb(a).

 Le Master Theorem (cas général)

Les notations et leur signification seront les mêmes que dans la version dite simple, mais les hypothèses seront moins restrictives, en particulier celles portant sur la complexité de la procédure de subdivision et combinaison.

Nous présentons cette version du théorème par soucis de complétude, mais en général la précédente suffit. D'ailleurs nous n'en ferons pas de démonstration, les "nouveaux" arguments étant essentiellement mathématiques.

Master Theorem

Soient a1a≥1b>1b>1, et TT une fonction vérifiant

T(n)=aT(nb)+f(n)T(n)=aT(nb)+f(n)

Les différents paramètres s'interprètent comme suit :

  • nn est la taille du problème.

  • aa est le nombre de sous-problèmes.

  • n/bn/b est le taille de chaque sous-problèmes.

  • f(n)f(n) est le coût de la subdivision et de la combinaison des solutions des sous-problèmes.

Alors

T(n)=⎪ ⎪ ⎪ ⎪⎪ ⎪ ⎪ ⎪Θ(f(n))si f(n)=Ω(nd) avec logb(a)<d et si a×f(nb)c×f(n) avec c<1Θ(nlogb(a)log(n))si f(n)=Θ(nd) avec logb(a)=dΘ(nlogb(a))si f(n)=O(nd) avec logb(a)>dT(n)={Θ(f(n))si f(n)=Ω(nd) avec logb(a)<d et si a×f(nb)≤c×f(n) avec c<1Θ(nlogb(a)log(n))si f(n)=Θ(nd) avec logb(a)=dΘ(nlogb(a))si f(n)=O(nd) avec logb(a)>d
[Note]

On trouve ce théorème sous cette forme générale dans l'excellent livre de Thomas H. Cormen (1956-), Charles E. Leiserson (1953-), Ronald L. Rivest (1947-) et Clifford Stein (1965-), "Introduction to algorithms".

Ne pas se fier au titre, ce livre est bien plus qu'une introduction, c'est une référence.

 
A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels


Logo Lycée Paul Sérusier

J'enseigne au
Lycée Paul SERUSIER
Avenue de Waldkappel
29270 CARHAIX PLOUGUER
Tél : 02 98 99 29 29
Site : www.lycee-serusier.fr

footer2

Richard GAUTHIER
Professeur de Physique Appliquée
Certification ISN
Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

www.carhaix2020.bzh