Diviser pour régner et programmation dynamique

Récursivité : une fonction qui s'appelle elle-même

Une fonction est récursive quand elle s'appelle elle-même, sur un problème plus petit. Elle contient toujours deux ingrédients :

• un cas de base, traité directement, sans nouvel appel ;

• un appel récursif sur une donnée « plus proche » du cas de base.

def f(n):

    if n == 0:

        return 1          # cas de base

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

Ici f(n) calcule $n!$. Le calcul de f(3) se déroule ainsi : f(3) = 3 * f(2) = 3 * (2 * f(1)) = 3 * (2 * (1 * f(0))) = 3 * 2 * 1 * 1 = 6. Les appels s'empilent jusqu'au cas de base, puis les résultats « remontent ».

def f(n):

    if n == 0:

        return 1

    return n * f(n - 1)

Recherche dichotomique

Diviser pour régner : on découpe un problème en sous-problèmes plus petits, on les résout (souvent récursivement), puis on combine les résultats. Le premier exemple est la recherche dichotomique dans une liste triée.

On garde deux indices g (gauche) et d (droite). On regarde la valeur au milieu m = (g + d) // 2 :

• si t[m] est la valeur cherchée, c'est fini ;

• si t[m] est trop petit, on continue dans la moitié droite (g = m + 1) ;

• sinon, on continue dans la moitié gauche (d = m - 1).

def dichotomie(t, x):

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

    while g <= d:

        m = (g + d) // 2

        if t[m] == x:

            return m

        elif t[m] < x:

            g = m + 1

        else:

            d = m - 1

    return None

Combien d'étapes au pire ? À chaque étape, la taille de la zone de recherche est divisée par 2 environ. Après $k$ étapes, il reste au plus $n / 2^k$ éléments. On s'arrête quand on arrive à 1, soit $2^k \approx n$, donc $k \approx \log_2 n$.

Pour $n = 1\,000$ : comme $2^{10} = 1\,024 > 1\,000$, il suffit d'environ 10 comparaisons, contre 1 000 au pire en séquentiel. Retour au début : dans ton dictionnaire de 1 000 pages, dix coups suffisent.

Le tri fusion

Le tri fusion applique les trois temps de « diviser pour régner » :

1. Diviser : couper la liste en deux moitiés ;

2. Régner : trier chaque moitié (récursivement) ;

3. Combiner : fusionner les deux listes triées en une seule liste triée.

Le cas de base est une liste de 0 ou 1 élément, déjà triée.

La fusion

Pour fusionner deux listes triées, on compare leurs premiers éléments non utilisés et on prend le plus petit.

def fusion(g, d):

    res = []

    i = j = 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(t):

    if len(t) <= 1:

        return t

    m = len(t) // 2

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

Arbre des divisions et coût

Pour $n = 8 = 2^3$, l'arbre a 3 niveaux de division : sa hauteur est $3 = \log_2 8$. Pour $n = 2^k$, la hauteur est $k$.

On remonte ensuite en fusionnant : [3, 7], [1, 5], [2, 8], [4, 6] au premier niveau, puis [1, 3, 5, 7] et [2, 4, 6, 8], puis [1, 2, 3, 4, 5, 6, 7, 8].

À chaque niveau, les fusions traitent en tout $n$ éléments : elles coûtent au plus $n$ comparaisons par niveau. Avec $k = \log_2 n$ niveaux, le coût total est de l'ordre de $n \log_2 n$.

Ordre de grandeur : pour $n = 1\,024 = 2^{10}$, le tri fusion fait au plus $1\,024 \times 10 = 10\,240$ comparaisons, alors que $n^2 = 1\,048\,576$. Le rapport est $1\,048\,576 / 10\,240 = 102{,}4$ : environ 100 fois moins.

Programmation dynamique

Parfois les sous-problèmes se chevauchent : on les recalcule plusieurs fois. La programmation dynamique consiste à calculer chaque sous-problème une seule fois et à garder le résultat.

Exemple : la suite de Fibonacci

def fib(n):

    if n <= 1:

        return n

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

Dans l'arbre des appels de fib(5), fib(3) est calculé 2 fois, fib(2) 3 fois : le nombre d'appels est de 15 pour fib(5) et il double presque à chaque étape (coût exponentiel). On y remédie par la mémoïsation : on stocke les résultats déjà calculés dans un dictionnaire.

def fib_memo(n, memo={}):

    if n <= 1:

        return n

    if n not in memo:

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

    return memo[n]

Chaque valeur de 2 à $n$ n'est calculée qu'une fois : le coût devient linéaire, en $O(n)$.

Exemple : le rendu de monnaie

Un boulanger de Toulouse a des pièces de 1 €, 3 € et 4 €. Comment rendre 6 € avec le moins de pièces possible ?

L'algorithme glouton prend à chaque fois la plus grande pièce possible : $4 + 1 + 1$, soit 3 pièces. Mais $3 + 3$ n'en utilise que 2 : le glouton n'est pas optimal pour ce système de pièces.

La programmation dynamique résout le problème. Soit $T[s]$ le nombre minimal de pièces pour rendre la somme $s$. Alors :

où $p$ décrit les valeurs de pièces.

Exemple : plus longue sous-séquence commune (PLSC)

Une sous-séquence s'obtient en effaçant des caractères sans changer l'ordre des autres. On cherche la plus longue sous-séquence commune à deux chaînes X et Y. On note $L(i, j)$ la longueur de la PLSC des $i$ premiers caractères de X et des $j$ premiers de Y.

Le tableau a $(p+1)(q+1)$ cases, chacune calculée en temps constant : le coût est en $O(p \times q)$. Sans mémoïsation, la récursion recalcule les mêmes sous-problèmes et le coût est exponentiel dans le pire des cas.

Recherche d'un motif : Boyer-Moore-Horspool

Comment trouver le motif ARBRE dans le texte LES ARBRES DE LA RUE ? La recherche naïve place le motif à chaque position du texte et compare caractère par caractère. L'algorithme de Boyer-Moore-Horspool compare le motif de droite à gauche et, en cas d'échec, saute plusieurs positions d'un coup.

On construit d'abord une table de décalage : pour chaque caractère du motif sauf le dernier, la distance entre sa dernière occurrence et la fin du motif. Tout autre caractère décale de la longueur $m$ du motif.

Pour ARBRE ($m = 5$) :

(R apparaît en positions 1 et 3 : on prend la dernière, soit $5 - 1 - 3 = 1$.)

On regarde le caractère du texte aligné avec la dernière lettre du motif : s'il est absent du motif, on avance de $m$ ; sinon on avance de la valeur de la table.

L'essentiel

• Une fonction récursive a un cas de base et un appel récursif qui se rapproche du cas de base ; sinon la récursion est infinie.

• Diviser pour régner : diviser, résoudre les sous-problèmes, combiner. La dichotomie coûte $\log_2 n$ comparaisons sur une liste triée.

• Le tri fusion coûte $O(n \log_2 n)$ : $\log_2 n$ niveaux, au plus $n$ comparaisons par niveau.

• La programmation dynamique stocke les résultats des sous-problèmes qui se chevauchent (mémoïsation ou tableau) : Fibonacci passe d'un coût exponentiel à $O(n)$, la PLSC coûte $O(p \times q)$.

• Le glouton n'est pas toujours optimal (6 € avec 1, 3, 4 € : $4+1+1$ contre $3+3$).

• Boyer-Moore-Horspool compare de droite à gauche et saute grâce à une table de décalage : rapide quand les caractères du texte sont absents du motif, aussi lent que la recherche naïve au pire.