La version récursive naïve de Fibonacci recalcule sans cesse les mêmes valeurs. La programmation dynamique évite ce gaspillage : on résout chaque sous-problème une seule fois et on mémorise son résultat. Cette idée simple transforme des algorithmes exponentiels en algorithmes rapides, et permet de résoudre des problèmes d’optimisation comme le rendu de monnaie ou l’alignement de séquences d’ADN.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Reconnaître un problème dont les sous-problèmes se chevauchent
- Mémoïser une fonction récursive avec un dictionnaire
- Écrire une version ascendante (itérative) qui remplit un tableau
- Résoudre le rendu de monnaie et comprendre le principe de l’alignement de séquences
1. Le principe
Comme pour diviser pour régner, on exprime la solution d’un problème à partir de solutions de sous-problèmes. Mais ici, les sous-problèmes se chevauchent : le même sous-problème apparaît de nombreuses fois. fib(5) appelle fib(3) deux fois, fib(2) trois fois…
- Mémoïsation (approche descendante) : on garde la fonction récursive, mais on stocke chaque résultat calculé dans un dictionnaire ; avant de calculer, on regarde s’il est déjà connu.
- Approche ascendante : on calcule les sous-problèmes du plus petit au plus grand en remplissant un tableau, sans récursivité.
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n < 2:
r = n
else:
r = fib(n - 1) + fib(n - 2)
memo[n] = r
return r
def fib_asc(n):
f = [0, 1]
for k in range(2, n + 1):
f.append(f[k - 1] + f[k - 2])
return f[n]2. Le rendu de monnaie
On veut rendre une somme avec le moins de pièces possible, chaque valeur de pièce étant disponible en quantité illimitée. L’algorithme glouton (prendre à chaque fois la plus grande pièce possible) est optimal pour le système de l’euro, mais pas pour tous les systèmes.
Pièces 1, 3 et 4 ; somme 6
- Glouton : 4, puis 1, puis 1 : 3 pièces.
- Optimal : 3 + 3 : 2 pièces.
Le glouton n’est pas toujours optimal : il faut une méthode qui envisage tous les choix.
nb(0) = 0 et nb(v) = 1 + min( nb(v − p) ) pour les pièces p ≤ v
def rendu(pieces, somme):
"""nb[v] = nombre minimal de pièces pour rendre v."""
nb = [0] + [float("inf")] * somme
for v in range(1, somme + 1):
for p in pieces:
if p <= v and nb[v - p] + 1 < nb[v]:
nb[v] = nb[v - p] + 1
return nb[somme]| v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| nb(v) | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
3. Alignement de séquences
En biologie, on compare des séquences d’ADN ; un correcteur orthographique compare des mots. Une mesure classique est la distance d’édition : le nombre minimal d’opérations (insertion, suppression ou remplacement d’une lettre) pour passer d’un mot à l’autre.
D(i, j) = min( D(i − 1, j) + 1 ; D(i, j − 1) + 1 ; D(i − 1, j − 1) + c )
De CHAT à CHIEN
- On garde C et H.
- On remplace A par I, T par E, puis on insère N.
Distance d’édition : 3. Le tableau D, de taille (5 × 6), se remplit ligne par ligne.
À retenir
- Programmation dynamique : sous-problèmes qui se chevauchent, chacun résolu une seule fois.
- Mémoïsation : récursivité + dictionnaire des résultats déjà calculés.
- Approche ascendante : remplir un tableau du plus petit au plus grand sous-problème.
- Rendu de monnaie : nb(v) = 1 + min nb(v − p) ; le glouton n’est pas toujours optimal.
- Distance d’édition : tableau D(i, j) rempli à partir des cases voisines.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.