Diviser pour régner et récurrences

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

reconnaître le schéma diviser pour régner dans un algorithme, nommer ses trois temps, et écrire la récurrence $T (n) = a T (n / b) + f (n)$ qui en découle en identifiant $a$ , $b$ et $f$ ;
résoudre une récurrence par l'arbre de récursion, puis valider la solution devinée par une démonstration par récurrence rédigée, et repérer l'erreur classique qui rend une telle récurrence fausse;
énoncer le théorème maître, ses trois cas et ses hypothèses, et le démontrer par l'arbre de récursion;
dire pourquoi le théorème ne couvre pas toutes les récurrences, et reconnaître une récurrence qui tombe dans sa zone aveugle;
analyser la recherche dichotomique, le tri fusion, la multiplication de Karatsuba et le sous-tableau de somme maximale, et retrouver chacun de leurs coûts par le calcul plutôt que par la mémoire;
implémenter ces quatre algorithmes en Python et vérifier votre compte d'opérations en les exécutant.

Le schéma diviser pour régner

Trois verbes

Le chapitre 1 vous a appris à mesurer un algorithme. Celui-ci vous apprend à en fabriquer, et il le fait avec le premier des grands schémas de conception du cours. Son principe tient en trois verbes.

Trois remarques sur cette définition, avant de la voir fonctionner.

Le nombre $a$ de sous-problèmes et le facteur $b$ de réduction sont deux paramètres distincts. L'intuition les confond volontiers, parce que dans les deux premiers exemples du chapitre ils sont égaux: le tri fusion coupe en deux et traite les deux moitiés, donc $a = b = 2$ . Ils se séparent dès le troisième. La recherche dichotomique coupe en deux et ne traite qu'une seule moitié: $a = 1$ , $b = 2$ . La multiplication de Karatsuba coupe en deux et lance trois appels sur des moitiés: $a = 3$ , . Ce sont précisément ces écarts entre et qui font toute la richesse du chapitre, et ils sont la seule chose que le théorème maître regarde.

La taille $n / b$ n'est en général pas un entier. Un tableau de 7 éléments se coupe en 3 et 4, pas en 3,5 et 3,5. Nous écrirons pourtant $T (n / b)$ sans partie entière dans toutes les récurrences, et nous démontrerons les résultats sous l'hypothèse que $n$ est une puissance exacte de $b$ . Cette commodité est légitime — nous disons plus bas pourquoi, et à quelle condition.

Le cas de base doit exister et doit être atteint. Une récurrence sans cas de base ne définit rien, et un algorithme dont les sous-problèmes ne décroissent pas strictement ne termine pas. C'est la première chose à vérifier quand une fonction récursive boucle: la taille passée à l'appel récursif est-elle vraiment plus petite?

De l'algorithme à la récurrence

Écrire la récurrence d'un algorithme récursif est un geste mécanique, et c'est le geste central du chapitre. On lit le corps de la fonction et l'on additionne:

pour chaque appel récursif, un terme $T (taille de l’argument)$ ;
pour tout le reste — le découpage, les boucles, la recombinaison —, sa propre classe de coût, qui devient $f (n)$ .

Sur la fonction suivante, par exemple, qui cherche le maximum d'un tableau en coupant en deux:

def maximum(a, g, d):
    """Maximum de a[g..d], par dichotomie. L'intervalle est inclusif."""
    if g == d:
        return a[g]
    m = (g + d) // 2
    return max(maximum(a, g, m), maximum(a, m + 1, d))

on lit deux appels récursifs sur des moitiés, donc $a = 2$ et $b = 2$ , et un travail de recombinaison réduit à une comparaison, donc $f (n) = Θ (1)$ . La récurrence est $T (n) = 2 T (n /2) + Θ (1)$ . Nous saurons dans quelques pages qu'elle vaut — ce qui était prévisible, puisqu'on ne trouve pas le maximum de nombres sans les regarder tous, mais il est instructif de le retrouver par le calcul plutôt que par le bon sens.

Question 2.1

Remettez dans l'ordre les étapes de l'analyse d'un algorithme récursif, depuis le code jusqu'à la classe de coût.

Glissez les éléments pour les mettre dans le bon ordre

Écrire la récurrence

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

Résoudre la récurrence, par l'arbre de récursion ou par le théorème maître

Évaluer le coût de tout ce qui n'est pas récursif: on obtient

f (n)

Compter les appels récursifs et lire la taille de leur argument: on obtient

a

b

Vérifier la solution sur de petites valeurs, en exécutant le programme

Repérer le cas de base et son coût, qui est

Θ (1)

La recherche dichotomique

L'algorithme et son invariant

Le premier exemple est aussi le plus dépouillé: le problème est celui du chapitre 1 — trouver une valeur dans un tableau —, mais le tableau est maintenant trié, et cette hypothèse change tout.

def dichotomique(a, cible):
    """Indice de cible dans le tableau trie a, ou -1. Compte les comparaisons."""
    gauche, droite = 0, len(a) - 1
    comparaisons = 0
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        comparaisons += 1
        if a[milieu] == cible:
            return milieu, comparaisons
        if a[milieu] < cible:
            gauche

L'opération barométrique est l'examen d'un élément, c'est-à-dire un tour de boucle; le compteur est incrémenté une fois par tour, avant le test. Chaque tour divise par deux, à une unité près, la largeur de l'intervalle $[gauche, droite]$ des indices encore possibles. La correction de l'algorithme repose sur un invariant de boucle qu'il faut savoir énoncer:

Si la cible est présente dans le tableau, alors son indice appartient à $[gauche, droite]$ .

L'invariant est vrai avant le premier tour, puisque l'intervalle est le tableau entier. Il se conserve: si a[milieu] < cible, alors, le tableau étant trié, aucune case d'indice $\leq milieu$ ne peut contenir la cible, et l'on peut poser $gauche = milieu + 1$ sans perdre la cible; le cas symétrique se traite de même. Quand la boucle s'arrête, l'intervalle est vide, donc — par l'invariant — la cible n'est nulle part: renvoyer $- 1$ est correct.

Le tableau doit être trié, et l'invariant doit être conservé

Deux fautes classiques guettent ici, et la seconde est perfide.

La première est d'appliquer la recherche dichotomique à un tableau non trié. Le programme ne plantera pas: il renverra $- 1$ pour une valeur pourtant présente, silencieusement, une fois sur deux. Un algorithme dont la précondition est violée n'échoue pas forcément, il ment.

La seconde est d'écrire gauche = milieu au lieu de gauche = milieu + 1. L'invariant reste vrai, mais l'intervalle cesse de décroître strictement lorsqu'il ne contient plus que deux éléments, et la boucle tourne indéfiniment. Comme l'exécution d'un <PythonExercise number="2.2"> est interrompue au bout de dix secondes, vous verrez le message plutôt qu'un navigateur figé — mais dans un vrai programme, c'est une boucle infinie. Retenez la règle: la case qui vient d'être comparée est éliminée, donc elle sort de l'intervalle.

Enfin, une remarque de culture générale: l'écriture milieu = (gauche + droite) // 2 est sans danger en Python, dont les entiers n'ont pas de taille bornée, mais elle a produit un débordement arithmétique célèbre dans des implémentations en C et en Java, où l'on écrit gauche + (droite - gauche) // 2. Le modèle RAM du chapitre 1 avec ses mots de $Θ (lo g n)$ bits vous dit d'ailleurs exactement pourquoi la question se pose.

La récurrence et sa solution

La fonction est écrite avec une boucle, mais sa structure est celle de diviser pour régner: on divise en deux, on ne règne que sur une moitié, et il n'y a rien à combiner. D'où $a = 1$ , $b = 2$ , $f (n) = Θ (1)$ , et la récurrence

T (n) = T (n /2) + Θ (1) . (2.2)

On la résout par déroulement, la méthode la plus élémentaire de toutes: on applique la récurrence à elle-même jusqu'au cas de base et l'on compte. En prenant $T (n) = T (n /2) + 1$ et $T (1) = 1$ , avec $n = 2^{k}$ :

T (2^{k}) = T (2^{k - 1}) + 1 = T (2^{k - 2}) + 2 = \dots = T (2^{0}) + k = k + 1.

Comme $k = lo g_{2} n$ , on obtient $T (n) = lo g_{2} n + 1$ , donc $T (n) \in Θ (lo g n)$ . Pour un quelconque, le compte exact du pire des cas est examens — ce que nous avons vérifié en exécutant la récurrence exacte pour toutes les tailles jusqu'à 5000, sans trouver un seul écart.

Ce sont les nombres annoncés au chapitre 1: 10 examens pour mille éléments, 20 pour un million, 30 pour un milliard. Multiplier les données par mille ajoute dix comparaisons.

Exemple 2.1 · La recherche dichotomique sur le tableau témoin trié

Le tableau témoin du cours, trié, est [3, 9, 10, 27, 38, 43, 82]. Faisons afficher, pour quatre cibles, l'indice trouvé et le nombre d'examens.

t = [3, 9, 10, 27, 38, 43, 82]
for cible in [27, 3, 82, 40]:
    print(cible, dichotomique(t, cible))

27 (3, 1)
3 (0, 3)
82 (6, 3)
40 (-1, 3)

Question 2.3

Un annuaire trié contient 2 000 000 d'entrées. Combien d'examens la recherche dichotomique effectue-t-elle au maximum pour y trouver un nom, ou conclure qu'il est absent?

Question 2.4

Écrivez la recherche dichotomique, compteur compris. Le programme de départ renvoie toujours −1 sans rien examiner. Complétez la fonction pour qu'elle renvoie le couple (indice, examens) attendu pour chacune des quatre cibles. Une cible absente doit coûter 3 examens et non 7: c'est ce qui distingue votre fonction d'une recherche séquentielle.

dichotomique.py

Le tri fusion

Fusionner deux moitiés triées

Le deuxième algorithme du chapitre est celui que le chapitre 10 d'Introduction à la programmation vous a seulement annoncé: il y présentait le tri par sélection et le tri par insertion, et renvoyait explicitement à ce cours-ci pour la fusion, qu'il n'a pas détaillée. La voici. Son idée tient en une observation: deux tableaux déjà triés se réunissent en un seul tableau trié en un seul balayage.

def fusion(g, d):
    """Fusionne deux listes deja triees. Renvoie (resultat, comparaisons)."""
    resultat = []
    comparaisons = 0
    i = j = 0
    while i < len(g) and j < len(d):
        comparaisons += 1
        if g[i] <= d[j]:
            resultat.append(g[i])
            i += 1
        else:
            resultat.append(d[j])

Comptons, et disons d'abord ce que nous comptons. L'opération barométrique est la comparaison de deux éléments à l'intérieur de la boucle de fusion; les queues recopiées par les deux extend, une fois l'une des listes épuisée, ne coûtent rien. C'est la convention de tout le cours, celle qui donne les 15 comparaisons du tri par insertion au chapitre 1 et les 13 du tri fusion ci-dessous; une autre convention donnerait un autre nombre pour le même algorithme sur le même tableau.

Chaque tour de la boucle while fait donc une comparaison et place un élément définitivement. Si les deux moitiés comptent $p$ et $q$ éléments, la boucle s'arrête dès que l'une est épuisée, donc après au plus $p + q - 1$ tours: on ne peut pas épuiser les deux en même temps sans avoir placé le dernier élément gratuitement. La fusion de deux moitiés totalisant $n$ éléments coûte donc au plus $n - 1$ comparaisons, et au moins $min (p, q)$ — le cas favorable étant celui où tous les éléments d'une moitié précèdent tous ceux de l'autre.

Deux détails du code ne sont pas décoratifs. Le test g[i] <= d[j], avec un large, prend l'élément de gauche en cas d'égalité: c'est ce qui rend le tri fusion stable, c'est-à-dire qu'il préserve l'ordre relatif de deux éléments égaux. Écrire < à la place casserait cette propriété sans changer d'un iota le nombre de comparaisons. Et les deux extend finaux ne coûtent aucune comparaison: ce sont des recopies, et elles s'ajoutent au coût en accès mémoire, pas en comparaisons.

Le tri

Le tri lui-même n'est plus que trois lignes:

def tri_fusion(a):
    """Trie une copie de a. Renvoie (liste triee, comparaisons)."""
    if len(a) <= 1:
        return list(a), 0
    m = len(a) // 2
    gauche, cg = tri_fusion(a[:m])
    droite, cd = tri_fusion(a[m:])
    fusionne, cf = fusion(gauche, droite)
    return fusionne, cg + cd + cf

Deux appels récursifs sur des moitiés, donc $a = 2$ et $b = 2$ ; une fusion linéaire, donc $f (n) = Θ (n)$ . La récurrence du tri fusion est

T (n) = 2 T (n /2) + Θ (n) . (2.3)

C'est la récurrence la plus importante de tout le cours, et c'est elle que la figure 2.1 dissèque.

Exemple 2.2 · Le tri fusion du tableau témoin, fusion par fusion

Traçons les six fusions que subit a = [38, 27, 43, 3, 9, 82, 10]. Le découpage prend $m = ⌊ n /2 ⌋$ , donc la moitié gauche compte 3 éléments et la droite 4 — le découpage n'est pas équilibré, et il n'a pas à l'être.

a = [38, 27, 43, 3, 9, 82, 10]
trie, total = tri_fusion(a)
print(trie, total)

[3, 9, 10, 27, 38, 43, 82] 13

En instrumentant chaque fusion pour qu'elle s'affiche, on obtient le détail suivant, dans l'ordre où les fusions ont lieu:

Une précision honnête, pour ne pas vendre plus que ce que l'algorithme donne. Sur les $5040$ permutations de sept éléments, le tri fusion fait au minimum 9 comparaisons, au maximum 14, et 12,73 en moyenne — nous l'avons obtenu en énumérant les $7!$ permutations et en comptant, exactement comme l'exemple 1.3 du chapitre 1 le faisait pour le tri par insertion. Les 13 comparaisons du tableau témoin sont donc légèrement au-dessus de la moyenne. Le tri fusion se distingue moins par sa moyenne que par l'étroitesse de sa fourchette: de 9 à 14, alors que le tri par insertion va de 6 à 21 sur les mêmes entrées. C'est un tri prévisible, et le chapitre 3 dira que cette prévisibilité se paie en mémoire.

L'arbre de récursion

Il est temps de dessiner ce que la récurrence (2.3) raconte.

L'arbre se lit en deux temps, et la lecture est toujours la même, quelle que soit la récurrence.

Combien coûte un niveau? Au niveau $i$ , il y a $2^{i}$ sous-problèmes, chacun de taille $n / 2^{i}$ , et chacun paie sa fusion, soit $Θ (n / 2^{i})$ . Le niveau entier coûte donc $2^{i} \times n / 2^{i} = n$ . Les facteurs se compensent exactement, et c'est cette compensation qui est le contenu de la figure: le niveau 0 est un bloc de largeur , le niveau 1 deux blocs de largeur , le niveau 2 quatre blocs de largeur , et la somme des largeurs ne bouge pas.

Combien y a-t-il de niveaux? La taille est divisée par 2 à chaque descente; partant de $n$ , on atteint 1 après $lo g_{2} n$ divisions. Il y a donc $lo g_{2} n + 1$ niveaux, numérotés de 0 à $lo g_{2} n$ .

Le total s'ensuit:

T (n) = niveaux (lo g_{2} n + 1) \times par niveau n = n lo g_{2} n + n \in Θ (n lo g n) . (2.4)

Le contrôle numérique est immédiat: pour la récurrence exacte $T (n) = 2 T (n /2) + n$ avec $T (1) = 1$ , le programme donne $T (8) = 32$ , et la formule $8 lo g_{2} 8 + 8 = 24 + 8 = 32$ ; , et . La formule ne se contente pas d'être de la bonne classe, elle est exacte sur les puissances de deux.

Question 2.5

Dans l'arbre de récursion du tri fusion, pourquoi le coût d'un niveau ne dépend-il pas du niveau?

Question 2.6

Écrivez la fusion, le seul endroit où le tri fusion travaille. Le programme de départ fournit le découpage récursif, mais sa fonction fusion se contente de recoller les deux moitiés bout à bout: elle ne trie rien et ne compte rien. Remplacez-la par la vraie fusion, qui compare les deux têtes, déplace la plus petite et compte une comparaison par tour. Le programme doit alors afficher le tableau témoin trié, puis le nombre de comparaisons du cours.

tri_fusion.py

Résoudre une récurrence

Trois méthodes, dans l'ordre où l'on s'en sert.

L'arbre de récursion

La première, vous venez de la voir à l'œuvre: dessiner l'arbre, calculer le coût d'un niveau, compter les niveaux, sommer. C'est la méthode à privilégier parce qu'elle est constructive, qu'elle montre où le temps passe, et qu'elle démontre le théorème maître plutôt que de l'invoquer.

Sa forme générale, pour $T (n) = a T (n / b) + f (n)$ avec $n = b^{k}$ :

au niveau $i$ , il y a $a^{i}$ sous-problèmes de taille $n / b^{i}$ , donc un coût de niveau $a^{i} f (n / b^{i})$ ;
l'arbre a $k = lo g_{b} n$ niveaux internes, plus le niveau des feuilles;

La dernière égalité mérite qu'on s'y arrête, parce qu'elle est le cœur du chapitre et qu'elle surprend souvent:

a^{l o g_{b} n} = (b^{l o g_{b} a})^{l o g_{b} n} = b^{l o g_{b} a \cdot l o g_{b} n} = (b^{l o g_{b} n})^{l o g_{b} a} = n^{l o g_{b} a} . (2.5)

On échange les rôles de $a$ et de $n$ dans l'exposant, ce qui est licite parce que les deux s'écrivent comme des puissances de $b$ . Le nombre de feuilles de l'arbre est donc $n^{l o g_{b} a}$ , et cet exposant $lo g_{b} a$ est autour duquel tout le théorème maître s'organise.

Le total s'écrit alors

T (n) = feuilles Θ (n^{l o g_{b} a}) + niveaux internes i = 0 \sum k - 1 a^{i} f (\frac{n}{b ^{i}}) . (2.6)

Toute la question devient: laquelle des deux parties l'emporte? Et pour la somme, tout dépend de la vitesse à laquelle ses termes croissent ou décroissent. Quand $f (n) = n^{c}$ , le terme de rang $i$ vaut $a^{i} (n / b^{i})^{c} = n^{c} (a / b^{c})^{i}$ : c'est une . Une géométrique de raison plus grande que 1 est dominée par son dernier terme, une géométrique de raison plus petite par son premier, et une géométrique de raison 1 est une somme de termes égaux. Trois comportements: ce sont les trois cas du théorème maître, et il n'y en a pas d'autre.

La substitution: deviner, puis démontrer

La deuxième méthode consiste à deviner la réponse — par l'arbre, par analogie, par expérience — et à la démontrer par récurrence. Elle est indispensable pour les récurrences que l'arbre ne rend pas évidentes, et elle est la seule qui produise une démonstration en bonne et due forme.

Le changement de variable

La troisième méthode est un artifice, mais il rend de grands services: quand la récurrence ne porte pas sur $n / b$ , on change de variable pour qu'elle y porte. L'exemple canonique est

T (n) = 2 T (n) + lo g_{2} n .

Posons $n = 2^{u}$ , c'est-à-dire $u = lo g_{2} n$ , et $S (u) = T (2^{u})$ . Alors , donc , et la récurrence devient — la récurrence du tri fusion, dont nous connaissons la solution . En revenant à : .

Retenez le mécanisme plus que l'exemple: une récurrence sur les tailles devient, après passage au logarithme, une récurrence sur les profondeurs, et c'est souvent là qu'elle se laisse résoudre.

Le théorème maître

L'énoncé

Nous avons maintenant tout ce qu'il faut pour énoncer le résultat qui donne son nom au chapitre et pour le démontrer.

Démonstration. On travaille sur $n = b^{k}$ , de sorte que toutes les tailles rencontrées, $n / b^{i} = b^{k - i}$ , soient entières. Déroulons la récurrence dans son arbre.

La structure de l'arbre. La racine est un problème de taille $n$ et paie $f (n)$ . Elle a $a$ enfants de taille $n / b$ , qui paient chacun $f (n / b)$ . Par récurrence immédiate sur $i$ , le niveau $i$ compte $a^{i}$ nœuds, chacun de taille $n / b^{i}$ , et coûte donc . La taille atteint 1 au niveau , où les nœuds sont des feuilles de coût ; il y en a par la relation (2.5). En sommant tous les niveaux:

T (n) = Θ (n^{L}) + g (n), g (n) = i = 0 \sum k - 1 a^{i} f (\frac{n}{b ^{i}}) . (2.7)

Le premier terme est le coût des feuilles, le second celui des niveaux internes. Toute la démonstration consiste à majorer $g$ dans chacun des trois cas.

Cas 1. Par hypothèse il existe $γ > 0$ et $ε > 0$ tels que $f (m) \leq γ m^{L - ε}$ pour $m$ assez grand. Alors

a^{i} f (\frac{n}{b ^{i}}) \leq γ a^{i} (\frac{n}{b ^{i}})^{L - ε} = γ n^{L - ε} \frac{a ^{i}}{b ^{i (L - ε)}} .

Or $b^{L} = b^{l o g_{b} a} = a$ , donc $b^{i (L - ε)} = a^{i} / b^{i ε}$ et le quotient vaut . La somme est donc géométrique de raison :

g (n) \leq γ n^{L - ε} i = 0 \sum k - 1 (b^{ε})^{i} = γ n^{L - ε} \frac{b ^{ε k} - 1}{b ^{ε} - 1} .

Comme $b^{ε k} = (b^{k})^{ε} = n^{ε}$ , il vient $g (n) \leq \frac{γ}{b ^{ε} - 1} n^{L}$ , c'est-à-dire . En reportant dans (2.7), ; et la minoration est gratuite, puisque le seul terme des feuilles donne déjà . D'où .

Cas 2. Par hypothèse il existe $γ_{1}, γ_{2} > 0$ tels que $γ_{1} m^{L} \leq f (m) \leq γ_{2} m^{L}$ pour assez grand. Le terme de rang vérifie alors

a^{i} f (\frac{n}{b ^{i}}) \leq γ_{2} a^{i} (\frac{n}{b ^{i}})^{L} = γ_{2} n^{L} \frac{a ^{i}}{b ^{i L}} = γ_{2} n^{L},

puisque $b^{i L} = a^{i}$ . Le même calcul avec $γ_{1}$ donne la minoration. Chaque niveau coûte donc $Θ (n^{L})$ , la raison géométrique vaut exactement 1, et il n'y a plus qu'à compter les niveaux: $g (n) = Θ (k n^{L}) = Θ (n^{L} lo g_{b} n)$ . Le changement de base du logarithme étant un facteur constant, , et ce terme absorbe les des feuilles. D'où .

Cas 3. C'est ici que sert la condition de régularité $a f (n / b) \leq κ f (n)$ , avec $κ < 1$ . En l'itérant $i$ fois, on obtient $a^{i} f (n / b^{i}) \leq κ^{i} f (n)$ pour tout et tout assez grand. D'où une géométrique de raison , dont on majore la somme par sa somme infinie:

g (n) \leq f (n) i = 0 \sum k - 1 κ^{i} \leq \frac{f ( n )}{1 - κ} \in O (f (n)) .

Dans l'autre sens, le terme de rang $i = 0$ vaut $f (n)$ , donc $g (n) \geq f (n)$ et $g (n) \in Θ (f (n))$ . Reste à voir que les feuilles ne pèsent rien: de $f (n) \in Ω (n^{L + ε})$ on tire . En reportant dans (2.7), .

Trois remarques sur ce qui vient d'être fait.

La démonstration est une seule idée, appliquée trois fois. Les termes $a^{i} f (n / b^{i})$ forment une suite géométrique — exactement, quand $f$ est une puissance; à un encadrement près, dans le cas général. Une géométrique décroissante est dominée par son premier terme, une croissante par son dernier, une de raison 1 par le nombre de ses termes. Les trois cas du théorème sont ces trois comportements, et rien d'autre. Si vous ne devez retenir qu'une chose du chapitre, retenez celle-ci: le théorème maître est une somme de série géométrique.

L'hypothèse $n = b^{k}$ a été utilisée. Pour un $n$ quelconque, les sous-problèmes ont les tailles $⌊ n / b ⌋$ et $⌈ n / b ⌉$ , l'arbre n'est plus parfaitement régulier et la démonstration demande un travail technique supplémentaire — encadrer $T$ entre deux récurrences exactes, l'une sur $⌊ n / b ⌋$ et l'autre sur $⌈ n / b ⌉$ . Ce travail ne change aucune conclusion et nous l' ici, parce qu'il n'apprend rien sur les algorithmes et beaucoup sur les parties entières; il est mené en détail dans CLRS, chapitre 4. Nous l'admettons sous une hypothèse qu'il faut nommer: doit être , au sens où elle ne saute pas brutalement entre deux entiers voisins — ce qui est le cas de toutes les fonctions rencontrées dans ce cours.

La condition de régularité du cas 3 n'est pas une formalité. Elle dit que le travail de découpage et de recombinaison décroît géométriquement quand on descend dans l'arbre. Elle est automatiquement vérifiée pour une puissance $f (n) = n^{c}$ avec $c > L$ , puisque $a (n / b)^{c} = (a / b^{c}) n^{c}$ et que exactement quand . Elle peut échouer pour des plus exotiques, et l'exercice 2.5 en construit une.

La zone aveugle

L'explorateur ci-dessous vous fait manipuler les trois paramètres et regarder la série géométrique se former. C'est la partie de la démonstration qu'un dessin fait comprendre mieux qu'un calcul.

Explorateur 2.1 · L’arbre de récursion d’une récurrence réglable

La récurrence explorée est T(n) = a T(n/b) + nᶜ. Les trois curseurs règlent le nombre a de sous-problèmes, le facteur b de réduction de la taille, et l’exposant c du travail de découpage et de recombinaison. Regardez la colonne de droite: elle montre ce que coûte chaque niveau de l’arbre, relativement au premier. Toute la démonstration du théorème maître tient dans la raison de cette suite géométrique, r = a divisé par b puissance c — au-dessus de 1 les feuilles gagnent, en dessous la racine gagne, et à 1 exactement les niveaux se valent et il faut les compter, d’où le facteur log n. Cherchez des réglages différents qui donnent la même raison: le cas ne change pas, alors que a et b ont changé.

Sous-problèmes a2

Facteur de réduction b2

Exposant c de f(n) = n^c1

Exposant critique L = log_b a

Exposant c de f

Raison r = a / b^c

Cas du théorème maître

cas 2

Ce qui domine le total

tous les niveaux

Résultat

Θ(n log n)

Le théorème au travail

Question 2.7

Que donne le théorème maître sur la récurrence $T (n) = 4 T (n /2) + n^{2}$ ?

La multiplication de Karatsuba

Le problème: multiplier deux grands entiers

Jusqu'ici nous avons compté des comparaisons entre éléments d'un tableau. Ce paragraphe change d'unité, et le chapitre 1 nous y avait préparés: dès que les nombres manipulés ne tiennent plus dans un mot machine, une multiplication n'est plus une opération élémentaire, et il faut compter des opérations sur les chiffres.

Le problème: multiplier deux entiers de $n$ chiffres. La méthode apprise à l'école — multiplier chaque chiffre du premier par chaque chiffre du second, puis additionner les lignes décalées — fait $n^{2}$ multiplications de chiffres et autant d'additions: elle est en $Θ (n^{2})$ . Pendant des siècles, on a cru que c'était optimal; Kolmogorov le conjecturait encore publiquement en 1960, et c'est en cherchant à le démontrer qu'un de ses étudiants, Anatolii Karatsuba, a trouvé le contraire en une semaine.

Le découpage naïf, qui ne gagne rien

Coupons chaque facteur en deux moitiés de $n /2$ chiffres. En base 10 et avec $n$ pair, posons $p = 1 0^{n /2}$ , puis

x = a p + b, y = c p + d,

où $a$ , $b$ , $c$ , $d$ ont $n /2$ chiffres. Le produit se développe:

x y = a c p^{2} + (a d + b c) p + b d . (2.8)

L'opération barométrique est ici la multiplication de deux chiffres. On voit quatre produits de nombres à $n /2$ chiffres — $a c$ , $a d$ , $b c$ , $b d$ — plus des décalages et des additions, qui coûtent $Θ (n)$ . La récurrence est donc $T (n) = 4 T (n /2) + Θ (n)$ , avec et : , donc . On a écrit un algorithme récursif compliqué pour retrouver exactement le coût de la méthode de l'école. C'est un résultat négatif instructif:

L'identité de Karatsuba

L'observation est d'une simplicité désarmante. La relation (2.8) n'a pas besoin de $a d$ et de $b c$ séparément: elle n'a besoin que de leur somme. Or

(a + b) (c + d) = a c + a d + b c + b d,

donc

a d + b c = (a + b) (c + d) - a c - b d . (2.9)

Le membre de droite ne fait intervenir que trois produits: $a c$ , $b d$ et $(a + b) (c + d)$ . Les deux premiers sont de toute façon nécessaires dans (2.8). On est donc passé de quatre multiplications récursives à trois, au prix de deux soustractions supplémentaires — qui coûtent $Θ (n)$ et disparaissent dans le $f$ .

Le coût

Trois appels récursifs sur des moitiés, et un travail d'addition, de soustraction et de décalage en $Θ (n)$ :

T (n) = 3 T (n /2) + Θ (n) . (2.10)

L'exposant critique vaut $L = lo g_{2} 3 \approx 1, 585$ , et $f (n) = n = n^{1}$ avec $1 < 1, 585$ : avec, par exemple, . Donc

T (n) \in Θ (n^{l o g_{2} 3}) \approx Θ (n^{1, 585}) .

Le gain se voit sur le compte exact des multiplications de chiffres. Pour $n = 2^{k}$ , la méthode de l'école en fait $n^{2} = 4^{k}$ et Karatsuba $3^{k} = n^{l o g_{2} 3}$ :

$n$ chiffres	École: $n^{2}$	Karatsuba: $3^{l o g_{2} n}$	Rapport
16	256	81	3,2
64	4096	729	5,6
256	65 536	6561	10,0
1024	1 048 576	59 049	17,8

Les quatre lignes ont été obtenues en exécutant les deux algorithmes et en comptant les multiplications de chiffres, jamais à la main. Le rapport croît comme $n^{2 - l o g_{2} 3} = n^{0, 415}$ : il n'explose pas, il monte lentement, et c'est pourquoi Karatsuba ne devient rentable qu'à partir de quelques centaines de chiffres — en dessous, les additions et les décalages supplémentaires mangent le gain, et les bibliothèques de grands entiers basculent sur la méthode scolaire sous un seuil qu'elles règlent empiriquement.

L'arbre de récursion rend le compte encore plus concret. Pour $n = 1024$ , le niveau $i$ coûte $3^{i} \times (1024/ 2^{i})$ , donc la somme des niveaux internes vaut

i = 0 \sum 9 3^{i} \frac{1024}{2 ^{i}} = 1024 i = 0 \sum 9 (\frac{3}{2})^{i} = 2 \cdot 3^{10} - 2 \cdot 1024 = 116050,

à quoi s'ajoutent les $3^{10} = 59049$ feuilles, soit $175099$ au total. Regardez la répartition: le niveau 0 coûte 1024 et le niveau 9 en coûte $39366$ , presque quarante fois plus. Le travail est en bas de l'arbre, et c'est la définition même du cas 1.

def karatsuba(x, y, n):
    """Produit de deux entiers d'au plus n chiffres, n puissance de 2."""
    if n == 1:
        return x * y
    demi = n // 2
    p = 10 ** demi
    a, b = divmod(x, p)
    c, d = divmod(y, p)
    ac = karatsuba(a, c, demi)
    bd = karatsuba(b, d, demi)
    milieu = karatsuba(a +

Une subtilité de cette implémentation mérite d'être signalée: $a + b$ et $c + d$ peuvent avoir $n /2 + 1$ chiffres, alors que l'appel récursif est fait avec demi. Ce n'est pas une faute, parce que le paramètre n ne sert qu'à choisir où couper: divmod et la reconstruction restent exacts quel que soit le nombre de chiffres effectif. Dans une implémentation qui travaillerait sur des tableaux de chiffres de longueur fixe, en revanche, ce chiffre de retenue devrait être traité à part — et c'est là que la plupart des implémentations de Karatsuba se trompent la première fois.

Question 2.8

Combien de multiplications de chiffres l'algorithme de Karatsuba effectue-t-il pour multiplier deux entiers de 256 chiffres, en descendant la récursion jusqu'au chiffre isolé?

Question 2.9

Implémentez le cœur de Karatsuba: les trois appels récursifs et la recombinaison. Le programme de départ découpe correctement les deux facteurs mais renvoie 0. Complétez-le pour qu'il affiche le produit, puis le nombre de multiplications de chiffres effectuées. Un découpage à quatre produits donnerait 16 et 64 au lieu de 9 et 27: le compteur est ce qui distingue Karatsuba du découpage naïf.

karatsuba.py

Le sous-tableau de somme maximale

Le problème

Dernier exemple du chapitre, et le plus surprenant, parce que le découpage n'y est pas évident.

Le problème. Étant donné un tableau a de $n$ nombres, éventuellement négatifs, trouver la plus grande somme d'un segment non vide a[i:j]. C'est une question qui se pose telle quelle en traitement du signal, en bio-informatique et en analyse de séries financières — «quelle période d'achat-vente aurait été la plus profitable?» —, et sa version naïve est facile: essayer tous les segments, en calculant chaque somme au fur et à mesure, coûte $Θ (n^{2})$ additions.

Nous utiliserons dans toute cette section le tableau

b = [38, - 27, 43, - 3, 9, - 82, 10],

qui est le tableau témoin du cours avec un signe alterné. Il est propre à ce chapitre et n'engage aucun autre.

Le découpage, et le segment qu'on oublie

Coupons a en deux moitiés au milieu $m$ . Un segment optimal ne peut être que de trois sortes:

entièrement dans la moitié gauche — un appel récursif le trouve;
entièrement dans la moitié droite — l'autre appel récursif le trouve;
à cheval sur la frontière, c'est-à-dire contenant à la fois $m$ et $m + 1$ .

Le troisième cas est celui qu'on oublie, et c'est celui qui fait tout l'intérêt de l'exercice. Il se traite directement, et en temps linéaire: un segment à cheval est la réunion d'un suffixe de la moitié gauche se terminant en $m$ et d'un préfixe de la moitié droite commençant en $m + 1$ ; ces deux morceaux sont indépendants, donc il suffit de trouver le meilleur suffixe et le meilleur préfixe, par deux balayages.

def maximum_croisant(a, g, m, d):
    """Meilleure somme d'un segment contenant a la fois m et m+1."""
    somme, meilleure_gauche = 0, None
    for i in range(m, g - 1, -1):          # suffixes finissant en m
        somme += a[i]
        if meilleure_gauche is None or somme > meilleure_gauche:
            meilleure_gauche = somme
    somme, meilleure_droite = 0, None
    for

def maximum_segment(a, g, d):
    """Somme maximale d'un segment non vide de a[g..d], inclusif."""
    if g == d:
        return a[g]
    m = (g + d) // 2
    return max(maximum_segment(a, g, m),
               maximum_segment(a, m + 1, d),
               maximum_croisant(a, g, m, d))

Deux appels récursifs sur des moitiés, un balayage linéaire pour le segment à cheval: $a = 2$ , $b = 2$ , $f (n) = Θ (n)$ . C'est la récurrence du tri fusion, relation (2.3), et la conclusion est la même:

T (n) = 2 T (n /2) + Θ (n) \in Θ (n lo g n) .

De $Θ (n^{2})$ à $Θ (n lo g n)$ pour un problème qui n'avait aucune raison apparente de se découper: c'est un des plus jolis résultats de la méthode.

Exemple 2.6 · Le sous-tableau de somme maximale, trace complète

Traçons maximum_segment sur $b = [38, - 27, 43, - 3, 9, - 82, 10]$ . L'appel initial porte sur $[0, 6]$ et coupe en $m = 3$ .

Appel	Moitié gauche	Moitié droite	À cheval	Retour

Un algorithme linéaire existe, et il n'est pas récursif

Honnêteté oblige: le sous-tableau de somme maximale se résout en $Θ (n)$ par un simple balayage — l'algorithme de Kadane, qui maintient la meilleure somme d'un segment se terminant à la position courante. Diviser pour régner ne donne donc pas ici le meilleur algorithme connu.

Pourquoi l'enseigner alors? Parce qu'il montre comment on passe de $Θ (n^{2})$ à $Θ (n lo g n)$ sans avoir eu l'idée géniale, par application mécanique d'un schéma. C'est la vertu d'un schéma de conception: il donne un bon algorithme à qui n'a pas trouvé le meilleur. Et l'idée du segment à cheval, elle, se généralise à des problèmes où aucun balayage linéaire n'existe — la paire de points la plus proche dans le plan, par exemple, se résout en $Θ (n lo g n)$ exactement de cette manière, avec une bande centrale à la place de la frontière.

Question 2.10

Écrivez le découpage du sous-tableau de somme maximale. La fonction maximum_croisant vous est donnée, entièrement écrite: c'est elle qui traite le segment à cheval. Il vous reste à écrire le corps récursif, qui coupe en deux, se rappelle sur chaque moitié et prend le meilleur des trois candidats. Le programme doit afficher la somme maximale, puis le nombre d'appels récursifs effectués.

somme_maximale.py

Strassen, la même idée un étage plus haut

Le procédé de Karatsuba — découper, puis trouver une identité qui économise un appel récursif — n'est pas propre à la multiplication d'entiers. À la fin des années 1960, Volker Strassen l'a appliqué au produit de deux matrices $n \times n$ , et la démonstration est du même esprit.

Le produit matriciel classique coûte $Θ (n^{3})$ multiplications scalaires: trois boucles imbriquées. En coupant chaque matrice en quatre blocs $\frac{n}{2} \times \frac{n}{2}$ , le produit par blocs s'écrit avec produits de blocs et quatre additions, d'où ; l'exposant critique vaut , on est dans le cas 1, et l'on retrouve — le même résultat négatif que le découpage naïf de la relation (2.8).

Strassen exhibe alors sept produits de blocs, combinaisons linéaires soigneusement choisies des blocs de départ, dont on retire les quatre blocs du résultat par additions et soustractions. La récurrence devient

T (n) = 7 T (n /2) + Θ (n^{2}),

et le théorème maître conclut: $L = lo g_{2} 7 \approx 2, 807$ , l'exposant de $f$ vaut 2, donc cas 1 et $T (n) \in Θ (n^{l o g_{2} 7}) \approx Θ (n^{2, 807})$ . Pour , cela fait multiplications scalaires contre : environ .

Trois honnêtetés pour finir, parce qu'un résultat célèbre mérite d'être présenté avec ses limites.

Le gain d'exposant est petit et le seuil de rentabilité est élevé. Les quatorze additions de matrices de Strassen ont une constante bien plus lourde que les quatre du découpage naïf, et les implémentations qui l'utilisent basculent sur le produit classique en dessous d'une taille de bloc de l'ordre de la centaine.
La stabilité numérique se dégrade. Sur des nombres à virgule flottante, les soustractions de Strassen amplifient les erreurs d'arrondi davantage que le produit classique. Dans une bibliothèque de calcul scientifique, ce n'est pas un détail.
Ce n'est pas le meilleur exposant connu. Depuis 1969, une longue suite de travaux a fait descendre l'exposant du produit matriciel; les meilleurs résultats actuels sont en dessous de $2, 372$ , mais ce sont des algorithmes dits galactiques: leurs constantes cachées sont si grandes qu'aucun d'eux n'est utilisé en pratique. La borne inférieure évidente est $Ω (n^{2})$ — il faut au moins lire les données — et l'écart entre $2$ et $2, 37$ est l'un des grands problèmes ouverts de la discipline.

Synthèse

Un algorithme diviser pour régner divise en $a$ sous-problèmes de taille $n / b$ , règne récursivement, et combine en $f (n)$ ; son coût obéit à $T (n) = a T (n / b) + f (n)$ . Écrire cette récurrence est un geste mécanique: on compte les appels récursifs pour $a$ , on lit la taille de leur argument pour $b$ , et l'on évalue tout le reste pour . Ne sautez jamais cette étape: , et sont trois algorithmes récursifs et trois classes différentes.

Série d'exercices du chapitre 2Exercice 1 sur 5

Question 2.11

Un algorithme divise une instance de taille $n$ en trois sous-instances de taille $n /3$ , et recombine en temps linéaire. Quelle est sa récurrence, et que vaut son coût?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 2.1 · Lire une récurrence dans du code

Pour chacun des trois fragments, écrivez la récurrence vérifiée par le nombre d'appels à travail(), puis donnez la classe $Θ$ correspondante en appliquant le théorème maître. On suppose travail() en $Θ (1)$ et $n$ puissance de 2.

# fragment A
def fa(n):
    if n <= 1:
        return
    travail()
    fa(n // 2)

# fragment B

Exercice 2.2 · Trois récurrences, trois cas

Résolvez les récurrences suivantes par le théorème maître, en indiquant à chaque fois $a$ , $b$ , $f$ , l'exposant critique $lo g_{b} a$ , le cas retenu et la vérification de ses hypothèses.

$T (n) = 9 T (n /3) + n$

Exercice 2.3 · Compter les comparaisons du tri fusion

Écrivez la récurrence exacte du nombre de comparaisons du tri fusion dans le pire des cas, pour un $n$ quelconque, en tenant compte du découpage $⌊ n /2 ⌋$ et $⌈ n /2 ⌉$ .
Calculez $C (1)$ à $C (8)$ .
Le tableau témoin du cours coûte 13 comparaisons. Comparez à $C (7)$ et commentez.

Solution

Exercice 2.4 · Le découpage déséquilibré

On considère un algorithme qui, sur une instance de taille $n$ , se rappelle sur une sous-instance de taille $n /3$ et sur une sous-instance de taille $2 n /3$ , avec une recombinaison en $Θ (n)$ :

T (n) = T (n /3) + T (2 n /3) + Θ (n) .

Exercice 2.5 · Une récurrence que le théorème maître ne sait pas résoudre

Cet exercice demande une démonstration complète.

On considère la récurrence, définie pour $n = 2^{k}$ avec $k \geq 1$ ,

T (n) = 2 T (n /2) + \frac{n}{lo g _{2} n}, T (2) = 1.

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 2.3 pour le tri fusion, chapitre 4 en entier pour les récurrences, le théorème maître et sa démonstration complète avec les parties entières, section 4.2 pour Strassen.
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour le vocabulaire: «diviser pour régner», «théorème général», «méthode de substitution».
Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 5, qui présente le schéma diviser pour régner par les problèmes plutôt que par les récurrences, avec le comptage des inversions et la paire de points la plus proche.
Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 2, une présentation courte et très claire de Karatsuba, avec l'arbre de récursion dessiné et la transformée de Fourier rapide comme suite.
Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 2.2 pour le tri fusion, ses variantes descendante et ascendante, et la question du seuil de bascule vers un tri quadratique sur les petits fragments.
Knuth, The Art of Computer Programming, vol. 3, Addison-Wesley — section 5.2.4 pour l'analyse fine du nombre de comparaisons de la fusion, si vous voulez le compte exact plutôt que la classe.

Cible	Intervalle	Milieu	Valeur lue	Décision
27	[0, 6]	3	27	trouvée, 1 examen
3	[0, 6]	3	27	27 est trop grand, aller à gauche
3	[0, 2]	1	9	9 est trop grand, aller à gauche
3	[0, 0]	0	3	trouvée, 3 examens
40	[0, 6]	3	27	27 est trop petit, aller à droite
40	[4, 6]	5	43	43 est trop grand, aller à gauche
40	[4, 4]	4	38	38 est trop petit, intervalle vide: absente

Objectifs du chapitre

Le schéma diviser pour régner

Trois verbes

De l'algorithme à la récurrence

La recherche dichotomique

L'algorithme et son invariant

La récurrence et sa solution

Le tri fusion

Fusionner deux moitiés triées

Le tri

L'arbre de récursion

Résoudre une récurrence

L'arbre de récursion

La substitution: deviner, puis démontrer

Le changement de variable

Le théorème maître

L'énoncé

La zone aveugle

Le théorème au travail

La multiplication de Karatsuba

Le problème: multiplier deux grands entiers

Le découpage naïf, qui ne gagne rien

L'identité de Karatsuba

Le coût

Le sous-tableau de somme maximale

Le problème

Le découpage, et le segment qu'on oublie

Strassen, la même idée un étage plus haut

Synthèse

Exercices

Références

Lire la récurrence

Compter les feuilles

Comparer les deux exposants

Comparer à un concurrent

Profondeur	Moitié gauche	Moitié droite	Résultat	Comparaisons
2	27	43	27, 43	1
1	38	27, 43	27, 38, 43	2
2	3	9	3, 9	1
2	82	10	10, 82	1
1	3, 9	10, 82	3, 9, 10, 82	2
0	27, 38, 43	3, 9, 10, 82	3, 9, 10, 27, 38, 43, 82	6
total				13

Recherche dichotomique	1	2	$Θ (1)$	0	2	$Θ (lo g n)$
Tri fusion	2	2	$Θ (n)$	1	2	$Θ (n lo g n)$
Maximum par dichotomie	2	2	$Θ (1)$	1	1	$Θ (n)$
Karatsuba	3	2	$Θ (n)$	1,585	1	$Θ (n^{1, 585})$
Strassen	7	2	$Θ (n^{2})$	2,807	1	$Θ (n^{2, 807})$
Découpage coûteux	2	2	$Θ (n^{2})$	1	3	$Θ (n^{2})$

[0, 1]	38	−27	11	38
[2, 3]	43	−3	40	43
[0, 3]	38	43	54	54
[4, 5]	9	−82	−73	9
[4, 6]	9	10	−63	10
[0, 6]	54	10	60	60