Programmation dynamique

Activité 1 : la suite de Fibonacci

Récursivité

La célèbre suite de Fibonacci est définie par \(F_0 = 0\), \(F_1 = 1\) et pour tout entier naturel \(n \geq 2\), \(F_n = F_{n-1} + F_{n-2}\).

Il s’agit de la suite de nombres \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34\ldots\)

Chaque nombre s’obtient en ajoutant les deux précédents. Le premier terme de cette liste est dit terme de rang ou d’indice \(0\), le suivant terme de rang \(1\), … Ainsi, le terme de rang \(7\) est égal à \(13\). On le note \(F_7\).

Écrire une fonction récursive fibo(n) renvoyant le nombre d’indice n de la suite de Fibonacci, le premier de la liste ayant pour indice \(0\). Utiliser votre fonction pour calculer les termes d’indice \(10, 20, 30, 40…\).

def fibo(n):
    if n == 0 or n == 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

print(fibo(7))
print(fibo(40))

Quel est le problème avec cette implémentation ?

Programmation dynamique

Approche récursive par mémoïsation (top-down)

Lire et commenter le programme suivant.

def fibo_memo(n, tableau = None):
    """Calcule le terme d'indice n de la suite de Fibonacci."""
    if tableau is None:
        tableau = [None] * (n + 1)
    if tableau[n]:
        return tableau[n]
    if n == 0 or n == 1:
        return n
    tableau[n] = fibo_memo(n - 1, tableau) + fibo_memo(n - 2, tableau)
    return tableau[n]

print(fibo_memo(710))

Approche de bas en haut (bottom-up)

Lire et commenter le programme suivant.

def fibo_dyn(n):
    """Calcule le terme d'indice n de la suite de Fibonacci."""
    tableau = [0] * (n + 1)
    tableau[1] = 1 # deuxième terme de la suite de Fibonacci
    for i in range(2, n + 1):
        tableau[i] = tableau[i - 1] + tableau[i - 2]
    return tableau[n]

print(fibo_dyn(40))
print(fibo_dyn(710))

Activité 2 : le sac à dos

On rappelle le problème du sac à dos déjà vu en Première : on dispose de n objets assimilables à des couples (valeur, poids) et d’un sac à dos qui peut porter un poids maximum w. L’objectif est de maximiser la valeur des objets contenus dans le sac.

Résolution à l’aide d’un algorithme glouton

Nous avons vu deux stratégies en Première :

• force brute : tester toutes les combinaisons possibles, envisageable avec 20 objets par exemple, mais pas avec 60 objets ;
• algorithmes gloutons :
  • glouton 1 : on prend d’abord les objets de valeurs maximales ;
  • glouton 2 : on prend d’abord les objets maximisant le rapport valeur/poids.

Les algorithmes gloutons sont très rapides, en \(O(n log_2(n))\) si on trie les objets suivant le critère choisi avec un bon algorithme de tri, mais ne garantissent pas d’obtenir la meilleure solution.

Résolution par programmation dynamique

On peut construire une solution optimale du problème à i objets à partir d’une résolution du problème à i – 1 objets.

Supposons qu’on a résolu le problème à i – 1 objets pour un poids maximal p allant de 0 à w. On rajoute un i-ème objet (vi, pi). Alors, une solution optimale du problème à i objets avec un poids maximal de p est :

• soit une solution optimale du problème à i – 1 objets avec le poids maximal p ;
• soit une solution optimale du problème à i – 1 objets avec le poids maximal p – pi à laquelle on ajoute le i-ème objet.

On résout donc successivement les problèmes à 1 objet, 2 objets, 3 objets, … pour les poids allant de 0 à w. On présente les solutions dans un tableau. Le contenu du tableau dépend de l’ordre des objets mais pas la dernière ligne.

Exemple

Résolution du problème du sac à dos avec la liste objets = [(3, 2), (8, 10), (2, 2), (8, 1), (4, 6), (6, 6)] et le poids maximal w = 10 kg. Les objets sont au format (valeur, poids).

La valeur maximale est 17, atteinte avec un poids de 9 kg. Puisque cette valeur n’est pas atteinte avec 5 objets, on a pris l’objet n°6, qui pèse 6 kg, donc il reste 9 – 6 = 3 kg pour 5 objets. Pour 5 objets, la valeur maximale atteinte avec 3 kg est égale à 11, c’est la même avec 4 objets. On n’a donc pas pris l’objet n°5, mais on a pris l’objet n°4 qui pèse 1 kg, donc il reste 2 kg pour 3 objets, ce qui permet une valeur égale à 3, déjà atteinte avec l’objet n°1.

On obtient donc la valeur optimale de 17 avec les objets 1, 4, 6.

Exercice

Même exercice avec objets = [(5, 3), (9, 2), (10, 5), (6, 4), (7, 1), (9, 3)] et w = 10.

Programmation en Python

Résoudre le problème du sac à dos dans le cas où objets = [["A", 6, 5], ["B", 3, 2], ["C", 3, 2], ["D", 3, 2], ["E", 1, 1]] (format (nom de l'objet, valeur, poids)) et w = 6 :

1. À l’aide d’un algorithme glouton (programme en Python de la version glouton1).
2. Par programmation dynamique (programme en Python).

Programmation dynamique

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires et en suivant une règle d’optimalité.

La méthode de programmation dynamique, comme la méthode « diviser pour régner », résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes « diviser pour régner » partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial.

Mais la méthode « diviser pour régner » est inefficace si on doit résoudre plusieurs fois le même sous-problème. En programmation dynamique, on se rappelle des sous-problèmes que l’on a résolus et de leurs solutions.

Activité 3 : alignement de séquences

L’alignement de séquences est un problème classique en bio-informatique : il s’agit de mesurer la ressemblance entre deux chaînes de caractères (par exemple, deux séquences ADN) en calculant le nombre minimal d’opérations pour transformer l’une en l’autre.

Les trois opérations autorisées sont :

• substitution : remplacer un caractère par un autre (coût 1) ;
• insertion : insérer un caractère dans la première chaîne (coût 1) ;
• suppression : supprimer un caractère de la première chaîne (coût 1).

Ce nombre minimal d’opérations s’appelle la distance d’édition (ou distance de Levenshtein).

Exemple

Pour transformer "CHAT" en "CHATS", il suffit d’une insertion (ajouter le S). La distance est donc 1.

Pour transformer "NICHE" en "CHIEN", la distance est 4 : supprimer N, supprimer I, insérer I après CH, insérer N.

Approche récursive naïve

Notons \(d(i, j)\) la distance d’édition entre les \(i\) premiers caractères de la chaîne \(A\) et les \(j\) premiers caractères de la chaîne \(B\). On a la relation de récurrence suivante :

• si \(i = 0\) : \(d(0, j) = j\) (il faut \(j\) insertions) ;
• si \(j = 0\) : \(d(i, 0) = i\) (il faut \(i\) suppressions) ;
• sinon : \(d(i, j) = \min\begin{cases} d(i-1, j) + 1 & \text{(suppression)} \\ d(i, j-1) + 1 & \text{(insertion)} \\ d(i-1, j-1) + c & \text{(substitution si } c=1 \text{, ou rien si } c=0 \text{)} \end{cases}\)

où \(c = 0\) si \(A[i-1] = B[j-1]\), et \(c = 1\) sinon.

def distance_recursive(a, b):
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)
    cout = 0 if a[-1] == b[-1] else 1
    return min(
        distance_recursive(a[:-1], b) + 1,
        distance_recursive(a, b[:-1]) + 1,
        distance_recursive(a[:-1], b[:-1]) + cout
    )

print(distance_recursive("CHAT", "CHATS"))
print(distance_recursive("NICHE", "CHIEN"))

1
4

Cette approche est correcte mais extrêmement lente : comme pour Fibonacci, on recalcule de nombreuses fois les mêmes sous-problèmes.

Résolution par programmation dynamique

On construit un tableau de taille \((n+1) \times (m+1)\) où \(n\) et \(m\) sont les longueurs des deux chaînes. La case \((i, j)\) contient \(d(i, j)\).

def distance_edition(a, b):
    n, m = len(a), len(b)
    t = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        t[i][0] = i
    for j in range(m + 1):
        t[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cout = 0 if a[i - 1] == b[j - 1] else 1
            t[i][j] = min(
                t[i - 1][j] + 1,
                t[i][j - 1] + 1,
                t[i - 1][j - 1] + cout
            )
    return t[n][m]

print(distance_edition("CHAT", "CHATS"))
print(distance_edition("NICHE", "CHIEN"))
print(distance_edition("ALGORITHME", "ALTRUISME"))

1
4
5

La complexité est en \(O(n \times m)\) en temps et en espace, ce qui est bien plus efficace que l’approche récursive naïve.

Visualisation du tableau

Pour A = "CHAT" et B = "CHATS" :

La valeur en bas à droite (1) donne la distance d’édition. On peut remonter le chemin optimal depuis cette case pour retrouver les opérations effectuées.

Exercice

1. Construire à la main le tableau pour les chaînes "BAIN" et "BRIN". Quelle est la distance d’édition ?
2. Modifier la fonction distance_edition pour qu’elle renvoie non seulement la distance, mais aussi la liste des opérations effectuées (substitution, insertion, suppression ou identité).