Diviser pour régner et programmation dynamique

La récursivité

Une fonction est récursive quand elle s'appelle elle-même sur un problème plus petit. Pour que le calcul s'arrête, il faut deux ingrédients :

def f(n):

    if n == 0:          # cas de base

        return 1

    return n * f(n - 1) # appel récursif sur n - 1

Pourquoi ça marche ? Parce que $n! = n \times (n-1)!$ : on sait calculer $n!$ dès qu'on sait calculer $(n-1)!$, et on finit par arriver à $0! = 1$.

def f(n):

    if n == 0:

        return 1

    return n * f(n - 1)

Recherche dichotomique

La méthode « diviser pour régner » consiste à diviser un problème en sous-problèmes plus petits, les résoudre, puis combiner les résultats. La recherche dichotomique est le cas le plus simple : on ne garde qu'un seul sous-problème, la moitié de la liste.

Elle exige une liste triée. On compare la valeur cherchée à l'élément du milieu : si elle est plus petite, on continue à gauche, sinon à droite.

def dichotomie(L, x):

    g, d = 0, len(L) - 1

    while g <= d:

        m = (g + d) // 2

        if L[m] == x:

            return m

        elif L[m] < x:

            g = m + 1

        else:

            d = m - 1

    return None

Combien d'étapes ? Chaque étape divise la taille par 2. Avec 1 000 éléments : 1 000 → 500 → 250 → … → 1 en une dizaine d'étapes, car $2^{10} = 1\,024 > 1\,000$. En général, pour $n$ éléments il faut environ $\log_2 n$ comparaisons, alors qu'une recherche séquentielle en demande jusqu'à $n$. Ici : 10 contre 1 000. Pour 1 000 000 d'éléments : 20 contre 1 000 000.

Le $\log_2 n$ n'est qu'un outil de comptage : c'est le nombre de fois qu'on peut diviser $n$ par 2 avant d'arriver à 1.

Le tri fusion

Pour trier une liste, on la coupe en deux, on trie chaque moitié (récursivement), puis on fusionne les deux listes triées. Le cas de base est une liste de 0 ou 1 élément, déjà triée.

La fusion de deux listes triées est l'étape clé : on compare les deux premiers éléments restants, on prend le plus petit, et on recommence.

def fusion(g, d):

    i, j, res = 0, 0, []

    while i < len(g) and j < len(d):

        if g[i] <= d[j]:

            res.append(g[i]); i += 1

        else:

            res.append(d[j]); j += 1

    return res + g[i:] + d[j:]

def tri_fusion(L):

    if len(L) <= 1:

        return L

    m = len(L) // 2

    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))

Pourquoi $n \log_2 n$ ?

Prenons $n = 2^k$ éléments. L'arbre des divisions a $k = \log_2 n$ niveaux. À chaque niveau, les fusions parcourent chaque élément une seule fois : environ $n$ comparaisons au plus. Au total : $k \times n = n \log_2 n$ comparaisons.

Pour démontrer ce coût, on note $T(n)$ le nombre de comparaisons dans le pire des cas. Couper en deux, trier chaque moitié, puis fusionner (au plus $n$ comparaisons) donne $T(n) \le 2T(n/2) + n$, avec $T(1) = 0$.

Avec $n = 1\,024$ : $n \log_2 n = 10\,240$ alors que $n^2 = 1\,048\,576$, soit environ 100 fois plus pour un tri quadratique (tri par insertion, par sélection dans le pire des cas).

La programmation dynamique

Parfois, les sous-problèmes se répètent. La suite de Fibonacci le montre :

def fib(n):

    if n < 2:

        return n

    return fib(n - 1) + fib(n - 2)

Dans l'arbre des appels de fib(4), fib(2) est calculé deux fois et fib(1) trois fois : en tout 9 appels. Le nombre d'appels de fib(n) croît à peu près comme $1{,}6^n$, ce qui devient énorme dès $n = 40$.

La programmation dynamique consiste à calculer chaque sous-problème une seule fois et à mémoriser le résultat. Deux façons :

• La mémoïsation (de haut en bas) : on garde les résultats déjà calculés dans un dictionnaire.

• La méthode ascendante (de bas en haut) : on remplit un tableau en partant des cas les plus petits.

def fib_memo(n, memo=None):

    if memo is None:

        memo = {}

    if n < 2:

        return n

    if n not in memo:

        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    return memo[n]

Chaque valeur de $0$ à $n$ est calculée une fois : le coût est proportionnel à $n$.

Attention : on crée le dictionnaire dans la fonction (memo=None) car une valeur par défaut mutable (memo={}) serait partagée entre tous les appels.

Le rendu de monnaie

Rendre 8 € avec des pièces de 1 €, 4 € et 6 € en un minimum de pièces. L'algorithme glouton prend toujours la plus grande pièce possible : $6 + 1 + 1$, soit 3 pièces. Or $4 + 4$ n'en utilise que 2 : le glouton n'est pas toujours optimal.

La programmation dynamique, elle, trouve toujours l'optimum. Soit $T[s]$ le nombre minimal de pièces pour rendre $s$ euros. Pour chaque pièce $p \le s$, on peut rendre $p$ puis $s - p$ :

La plus longue sous-séquence commune (PLSC)

Une sous-séquence garde l'ordre des lettres mais pas forcément leur contiguïté. Soit $L(i, j)$ la longueur de la PLSC des $i$ premiers caractères de X et des $j$ premiers de Y :

• $L(i, j) = 0$ si $i = 0$ ou $j = 0$ ;

• $L(i, j) = L(i-1, j-1) + 1$ si $X_i = Y_j$ ;

• $L(i, j) = \max\big(L(i-1, j),\, L(i, j-1)\big)$ sinon.

Sans mémoïsation, la récursion refait les mêmes calculs et le coût est exponentiel ; avec le tableau, il est en $p \times q$.

Recherche d'un motif : Boyer-Moore-Horspool

Pour chercher un motif $M$ de longueur $m$ dans un texte $T$, la méthode naïve décale le motif d'une case à la fois. L'algorithme de Boyer-Moore-Horspool compare de droite à gauche et peut sauter plusieurs positions d'un coup.

Table de décalage : pour chaque caractère $c$ du motif sauf le dernier, le décalage est la distance entre sa dernière occurrence et la fin du motif. Pour tout autre caractère, le décalage est $m$.

Règle : on aligne le motif sur le texte, on compare de droite à gauche. S'il y a échec, on décale le motif selon la table, en regardant la lettre du texte alignée avec la dernière lettre du motif.

L'algorithme est le plus efficace quand le texte contient beaucoup de lettres absentes du motif : on saute alors de $m$ cases à chaque échec. Il se comporte comme la recherche naïve quand les décalages valent presque toujours 1.

L'essentiel

• Récursivité : un cas de base et un appel sur un problème plus petit ; sans cas de base atteint, RecursionError.

• Diviser pour régner : diviser, résoudre, combiner. La dichotomie (liste triée) coûte environ $\log_2 n$ comparaisons.

• Tri fusion : on coupe en deux, on trie, on fusionne ; $\log_2 n$ niveaux avec environ $n$ comparaisons par niveau, soit un coût en $n \log_2 n$ (contre $n^2$).

• Programmation dynamique : quand les sous-problèmes se répètent, on mémorise (dictionnaire) ou on remplit un tableau. Le glouton n'est pas toujours optimal.

• Boyer-Moore-Horspool : comparaison de droite à gauche et décalages donnés par une table, avec de grands sauts quand le texte contient peu de lettres du motif.

Retour au début : dans un dictionnaire de 100 000 entrées, la dichotomie demande $\log_2 100\,000 \approx 17$ ouvertures au maximum, car $2^{17} = 131\,072$.