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 comporte toujours deux parties :

• un cas de base : un cas assez simple pour répondre directement, sans nouvel appel ;

• un appel récursif : on se ramène à un problème plus petit, qui se rapproche du cas de base.

def somme(n):

    if n == 0:          # cas de base

        return 0

    return n + somme(n - 1)   # appel récursif

Chaque appel attend le résultat du suivant : les appels s'empilent, puis les résultats remontent.

def f(n):

    if n == 0:

        return 1

    return n * f(n - 1)

Diviser pour régner et recherche dichotomique

Diviser pour régner est une méthode en trois temps :

1. diviser le problème en sous-problèmes plus petits, de même nature ;

2. régner : résoudre chaque sous-problème (souvent par récursivité) ;

3. combiner les résultats pour obtenir la solution.

Le cas le plus simple : la recherche dichotomique dans une liste triée. On compare la valeur cherchée à l'élément du milieu. Selon le résultat, on garde la moitié gauche ou la moitié droite, et on recommence.

def dichotomie(t, x):

    debut, fin = 0, len(t) - 1

    while debut <= fin:

        milieu = (debut + fin) // 2

        if t[milieu] == x:

            return milieu

        elif t[milieu] < x:

            debut = milieu + 1

        else:

            fin = milieu - 1

    return None

Pourquoi c'est efficace ? À chaque étape, le nombre d'éléments restants est divisé par 2. Avec $n$ éléments, il faut environ $\log_2 n$ étapes (le nombre de fois qu'on peut diviser $n$ par 2 avant d'arriver à 1). Pour 1 000 éléments : $2^{10} = 1\,024 > 1\,000$, donc au plus 10 comparaisons environ, contre 1 000 pour une recherche séquentielle dans le pire des cas.

Le tri fusion

Le tri fusion applique diviser pour régner au tri d'une liste :

1. diviser la liste en deux moitiés ;

2. trier chaque moitié (par récursivité) ;

3. 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 : elle est déjà triée.

L'étape clé est la fusion de deux listes déjà triées : on compare les deux premiers éléments restants et on prend le plus petit.

def fusion(a, b):

    i, j = 0, 0

    res = []

    while i < len(a) and j < len(b):

        if a[i] <= b[j]:

            res.append(a[i])

            i += 1

        else:

            res.append(b[j])

            j += 1

    return res + a[i:] + b[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:]))

Le coût en n log₂ n

Pourquoi le tri fusion est-il plus rapide que les tris simples ? Comptons les comparaisons, pour $n = 2^k$ éléments.

• L'arbre des divisions a $k = \log_2 n$ niveaux (on divise par 2 jusqu'à obtenir des listes à 1 élément).

• À chaque niveau, les fusions parcourent au total les $n$ éléments : au plus $n$ comparaisons par niveau.

• Total : environ $n \times \log_2 n$ comparaisons.

Pour $n = 1\,000$ : $n^2 = 1\,000\,000$ alors que $n \log_2 n \approx 9\,970$ (environ $10\,000$). Ici $\log_2$ n'est qu'un outil de comptage : le nombre de fois qu'on peut couper en deux.

Programmation dynamique : ne pas recalculer

Parfois, diviser un problème donne des sous-problèmes qui se recoupent : on recalcule plusieurs fois la même chose. La programmation dynamique consiste à calculer chaque sous-problème une seule fois et à conserver son résultat.

Un exemple : Fibonacci

La suite de Fibonacci vérifie $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$. La version récursive naïve :

def fib(n):

    if n <= 1:

        return n

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

Voici l'arbre des appels pour fib(4) :

fib(2) est calculé deux fois (cadres orange). Pour de grands $n$, le nombre d'appels croît de façon exponentielle : fib(40) devient déjà très lent.

Mémoïsation

La mémoïsation consiste à ranger chaque résultat dans un dictionnaire et à le réutiliser :

def fib_memo(n, memo=None):

    if memo is None:

        memo = {}

    if n in memo:

        return memo[n]

    if n <= 1:

        memo[n] = n

    else:

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

    return memo[n]

Chaque valeur $F_0, \dots, F_n$ n'est calculée qu'une fois : le coût devient linéaire, en $O(n)$, au prix d'un peu de mémoire. On peut aussi remplir un tableau de bas en haut (approche « ascendante »).

Le rendu de monnaie

Rendre 10 € avec des pièces de 1 €, 5 € et 6 €, avec le moins de pièces possible.

• Algorithme glouton : on prend toujours la plus grande pièce possible. Ici 6 + 1 + 1 + 1 + 1 : 5 pièces.

• Optimal : 5 + 5, soit 2 pièces.

Le glouton ne donne donc pas toujours l'optimum. La programmation dynamique, si. On note $T[s]$ le nombre minimal de pièces pour rendre la somme $s$. Pour chaque pièce $p \le s$, on peut rendre $p$ puis la somme $s - p$ :

Par exemple $T[8] = 1 + \min(T[7], T[3], T[2]) = 1 + \min(2, 3, 2) = 3$ et $T[10] = 1 + \min(T[9], T[5], T[4]) = 1 + \min(4, 1, 4) = 2$.

def rendu(pieces, somme):

    T = [0] + [None] * somme

    for s in range(1, somme + 1):

        T[s] = 1 + min(T[s - p] for p in pieces if p <= s)

    return T[somme]

Le coût est de l'ordre de $\text{somme} \times \text{nombre de pièces}$.

Plus longue sous-séquence commune

Une sous-séquence d'une chaîne s'obtient en effaçant des caractères, sans changer l'ordre des autres (ils ne sont pas forcément consécutifs). Par exemple « AC » est une sous-séquence de « AGC ». La PLSC de deux chaînes est la plus longue sous-séquence qu'elles ont en commun. On s'en sert pour comparer deux textes, ou deux séquences d'ADN (alignement de séquences).

On note $L(i, j)$ la longueur de la PLSC des $i$ premiers caractères de X et des $j$ premiers de Y.

Pourquoi ? Si les derniers caractères sont égaux, on peut les ajouter à une PLSC des préfixes précédents. Sinon, l'un des deux ne sert pas : on teste les deux possibilités et on garde la meilleure.

Coût. Le tableau a $(p+1) \times (q+1)$ cases, chacune calculée en temps constant : le coût est en $O(p \cdot q)$. La récursivité sans mémoïsation recalcule les mêmes $L(i, j)$ de nombreuses fois et peut demander un nombre d'appels exponentiel.

Recherche d'un motif : Boyer-Moore-Horspool

Chercher le motif « RUE » dans un texte : la méthode naïve teste chaque position, en comparant le motif caractère par caractère depuis la gauche. L'algorithme de Boyer-Moore (ici sa version simplifiée de Horspool) accélère la recherche en sautant des positions, grâce à une table calculée à l'avance. Il compare le motif de droite à gauche.

Table de décalage. Pour un motif $M$ de longueur $m$ et un caractère $c$ :

• si $c$ apparaît dans $M$ en dehors du dernier caractère, le décalage est la distance de sa dernière occurrence à la fin du motif, soit $m - 1 - (\text{indice de cette occurrence})$ ;

• sinon, le décalage est $m$.

Pour $M$ = « RUE » ($m = 3$) : R (indice 0) donne $3 - 1 - 0 = 2$ ; U (indice 1) donne $3 - 1 - 1 = 1$ ; tout autre caractère donne 3.

def table_decalage(motif):

    m = len(motif)

    table = {}

    for i in range(m - 1):

        table[motif[i]] = m - 1 - i

    return table

def horspool(texte, motif):

    m = len(motif)

    table = table_decalage(motif)

    pos = 0

    while pos <= len(texte) - m:

        k = m - 1

        while k >= 0 and texte[pos + k] == motif[k]:

            k -= 1

        if k < 0:

            return pos

        pos += table.get(texte[pos + m - 1], m)

    return None

Après un échec, on décale selon le caractère du texte situé sous le dernier caractère du motif.

Retour au début : avec la dichotomie, 1 000 livres demandent au plus 10 comparaisons ($2^{10} = 1\,024$). Pour les trier, le tri fusion coupe la pile en deux à chaque étape et fusionne, soit environ $n \log_2 n$ opérations au lieu de $n^2$.

L'essentiel