Prérequis : récursivité , diviser pour régner
À l’issue de ce chapitre, vous saurez :
La suite de Fibonacci commence par les termes \(F_0 = 0\) et \(F_1 = 1\) ; ensuite, chaque terme est la somme des deux qui le précèdent : \(F_n = F_{n-1} + F_{n-2}\) pour tout entier \(n \geq 2\).
Ses premiers termes sont donc 0, 1, 1, 2, 3, 5, 8, 13, 21 et 34. On numérote les termes à partir de 0 : le terme numéro 7, noté \(F_7\), vaut 13.
Écrire une fonction récursive fibo(n) qui renvoie \(F_n\), puis l’utiliser pour calculer \(F_{10}\), \(F_{20}\), \(F_{30}\) et \(F_{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))
Combien de temps faut-il pour obtenir fibo(40) ? D’où vient cette lenteur ?
Lire le programme suivant et expliquer le rôle du paramètre tableau.
def fibo_memo(n, tableau = None):
"""Renvoie F(n) en gardant en mémoire les termes déjà calculés."""
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))
Lire le programme suivant et expliquer dans quel ordre les cases du tableau sont remplies.
def fibo_dyn(n):
"""Renvoie F(n) en remplissant un tableau du terme 0 au terme n."""
if n == 0:
return 0
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))
Le problème du sac à dos a été rencontré en première. Chaque objet est décrit par un couple (valeur, poids) ; le sac supporte au plus un poids w. Il s’agit de choisir les objets à emporter pour que leur valeur totale soit la plus grande possible, sans dépasser w.
En première, deux méthodes ont été étudiées :
Un glouton ne coûte que le tri des objets, soit \(O(n \log_2 n)\) avec un tri efficace ; en revanche, rien ne garantit que son choix soit le meilleur.
L’idée consiste à traiter les objets un par un, et à se servir des résultats obtenus avec les premiers objets pour trouver le meilleur choix quand on en ajoute un.
Notons (vi, pi) le i-ème objet. Supposons connue, pour chaque capacité de sac p comprise entre 0 et w, la meilleure valeur réalisable avec les i – 1 premiers objets. Pour la capacité p, quand le i-ème objet devient disponible, deux possibilités se présentent :
i-ème objet : la meilleure valeur est celle obtenue avec les i – 1 premiers objets et la capacité p ;i-ème objet, s’il pèse au plus p : il apporte la valeur vi, et il reste la capacité p – pi pour les i – 1 premiers objets.On garde la meilleure des deux. Les résultats se rangent dans un tableau : une ligne par nombre d’objets disponibles (de 0 à n), une colonne par capacité (de 0 à w). Chaque ligne se calcule à partir de la précédente. Changer l’ordre des objets modifie les lignes intermédiaires, mais jamais la dernière.
On prend objets = [(3, 2), (8, 10), (2, 2), (8, 1), (4, 6), (6, 6)], au format (valeur, poids), et un sac de capacité w = 10 kg.
| objets \ poids | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 8 |
| 3 | 0 | 0 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 8 |
| 4 | 0 | 8 | 8 | 11 | 11 | 13 | 13 | 13 | 13 | 13 | 13 |
| 5 | 0 | 8 | 8 | 11 | 11 | 13 | 13 | 13 | 13 | 15 | 15 |
| 6 | 0 | 8 | 8 | 11 | 11 | 13 | 13 | 14 | 14 | 17 | 17 |
La case en bas à droite donne la meilleure valeur : 17. Pour retrouver les objets choisis, on remonte le tableau à partir de la colonne 9, la plus petite capacité où 17 apparaît dans la dernière ligne :
Le meilleur choix est donc formé des objets 1, 4 et 6, pour une valeur de 17 et un poids de 9 kg.
Construire le tableau pour objets = [(4, 3), (7, 4), (5, 2), (9, 5), (3, 1), (6, 3)] et w = 8, puis retrouver les objets choisis.
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 :
Dans les deux activités, la même démarche apparaît : on ramène le problème à des problèmes plus petits, on résout d’abord les plus petits, et l’on conserve leurs résultats pour construire ceux des plus grands. C’est le principe de la programmation dynamique.
La méthode « diviser pour régner » découpe elle aussi un problème en sous-problèmes, mais ceux-ci sont indépendants : le tri fusion trie deux moitiés qui n’ont aucun élément commun, et chaque moitié n’est triée qu’une fois.
Dans la suite de Fibonacci ou le sac à dos, au contraire, les sous-problèmes se répètent : le calcul de \(F_{40}\) demande \(F_{38}\) deux fois, \(F_{37}\) trois fois, et ainsi de suite. Un découpage récursif sans mémoire refait ces calculs ; la programmation dynamique les fait une seule fois et range chaque résultat dans un tableau.
fibo(38) est calculé deux fois, fibo(37) trois fois, etc. La complexité est exponentielle, en O(2n), alors que la version avec mémoïsation ou bottom-up est en O(n).En bio-informatique, on compare deux séquences d’ADN pour savoir à quel point elles se ressemblent. Une mesure possible : le plus petit nombre de modifications qui transforme une chaîne de caractères en l’autre.
Chaque modification compte pour 1 et peut être :
Le plus petit nombre de modifications nécessaires s’appelle la distance d’édition des deux chaînes (ou distance de Levenshtein).
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.
Pour deux chaînes \(A\) et \(B\), on note \(d(i, j)\) la distance d’édition entre le début de \(A\) formé de ses \(i\) premiers caractères et le début de \(B\) formé de ses \(j\) premiers caractères. Ces distances vérifient :
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 fonction donne le bon résultat, mais chaque appel en déclenche trois autres : les mêmes débuts de chaînes sont comparés un très grand nombre de fois, comme les termes de Fibonacci dans fibo.
Si les chaînes ont pour longueurs \(n\) et \(m\), on remplit un tableau de \(n + 1\) lignes et \(m + 1\) colonnes, ligne par ligne : la case de la ligne \(i\) et de la colonne \(j\) reçoit \(d(i, j)\), calculée à partir de trois cases déjà remplies.
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
Chaque case demande un nombre constant d’opérations : le temps de calcul et la place occupée sont en \(O(n \times m)\), alors que la version récursive est exponentielle.
Pour A = "CHAT" et B = "CHATS" :
| C | H | A | T | S | ||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| C | 1 | 0 | 1 | 2 | 3 | 4 |
| H | 2 | 1 | 0 | 1 | 2 | 3 |
| A | 3 | 2 | 1 | 0 | 1 | 2 |
| T | 4 | 3 | 2 | 1 | 0 | 1 |
La case en bas à droite contient la distance cherchée, 1. En remontant depuis cette case vers la case voisine qui a fourni le minimum, on retrouve la suite des modifications.
"BAIN" et "BRIN". Quelle est la distance d’édition ?distance_edition pour qu’elle renvoie non seulement la distance, mais aussi la liste des opérations effectuées (substitution, insertion, suppression ou identité).