Partie 4 : Programmation dynamique¶
Programme officiel (B.O.)¶
B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Programmation dynamique. | Utiliser la programmation dynamique pour écrire un algorithme. | Les exemples de l'alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée. |
1. Le problème des sous-problèmes chevauchants¶
1.1 Retour sur Fibonacci récursif¶
Pour calculer fib(5), on observe une explosion des appels :
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ │ ├── fib(1)
│ │ │ └── fib(0)
│ │ └── fib(1)
│ └── fib(2)
│ ├── fib(1)
│ └── fib(0)
└── fib(3)
├── fib(2)
│ ├── fib(1)
│ └── fib(0)
└── fib(1)
fib(2) est calculé 3 fois, fib(3) est calculé 2 fois. Le nombre total d'appels croît exponentiellement : O(2ⁿ).
1.2 L'idée de la programmation dynamique¶
La programmation dynamique résout ce problème en mémorisant les résultats déjà calculés pour ne pas les recalculer. Deux approches existent :
| Approche | Principe | Direction |
|---|---|---|
| Descendante (mémoïsation) | Récursion + stockage des résultats | Du problème vers les cas de base |
| Ascendante (tabulation) | Remplissage d'un tableau de bas en haut | Des cas de base vers le problème |
2. Fibonacci optimisé¶
2.1 Approche descendante (mémoïsation)¶
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
2.2 Approche ascendante (tabulation)¶
def fib_tab(n):
if n <= 1:
return n
tab = [0] * (n + 1)
tab[1] = 1
for i in range(2, n + 1):
tab[i] = tab[i - 1] + tab[i - 2]
return tab[n]
2.3 Comparaison des complexités¶
| Version | Temps | Mémoire |
|---|---|---|
| Récursive naïve | O(2ⁿ) | O(n) (pile) |
| Mémoïsation | O(n) | O(n) (dictionnaire) |
| Tabulation | O(n) | O(n) (tableau) |
3. Le rendu de monnaie¶
3.1 Le problème¶
On dispose d'un système de pièces (par exemple {1, 2, 5, 10}) et on veut rendre une somme donnée avec le minimum de pièces.
En première, on a vu l'algorithme glouton (prendre la plus grande pièce possible). Mais le glouton ne donne pas toujours la solution optimale (exemple : pièces {1, 3, 4}, somme 6 → glouton donne 4+1+1 = 3 pièces, optimal = 3+3 = 2 pièces).
3.2 Solution par programmation dynamique¶
On construit un tableau nb_pieces[s] = nombre minimal de pièces pour rendre la somme s.
Relation de récurrence :
def rendu_monnaie(pieces, somme):
nb_pieces = [float('inf')] * (somme + 1)
nb_pieces[0] = 0
for s in range(1, somme + 1):
for p in pieces:
if p <= s and nb_pieces[s - p] + 1 < nb_pieces[s]:
nb_pieces[s] = nb_pieces[s - p] + 1
return nb_pieces[somme]
3.3 Retrouver la décomposition¶
Pour connaître les pièces utilisées, on mémorise les choix :
def rendu_monnaie_detail(pieces, somme):
nb_pieces = [float('inf')] * (somme + 1)
nb_pieces[0] = 0
dernier_choix = [0] * (somme + 1)
for s in range(1, somme + 1):
for p in pieces:
if p <= s and nb_pieces[s - p] + 1 < nb_pieces[s]:
nb_pieces[s] = nb_pieces[s - p] + 1
dernier_choix[s] = p
# Reconstruction de la solution
resultat = []
s = somme
while s > 0:
resultat.append(dernier_choix[s])
s -= dernier_choix[s]
return resultat
4. Alignement de séquences¶
4.1 Le problème¶
En bioinformatique, on compare des séquences d'ADN ou de protéines en cherchant le meilleur alignement : faire correspondre les caractères de deux séquences en insérant éventuellement des « trous » (gaps, notés -).
Exemple : aligner ACTG et ACG :
4.2 Distance d'édition¶
La distance d'édition (ou distance de Levenshtein) entre deux chaînes est le nombre minimal d'opérations élémentaires pour transformer l'une en l'autre :
- Insertion d'un caractère ;
- Suppression d'un caractère ;
- Substitution d'un caractère par un autre.
4.3 Solution par programmation dynamique¶
On construit un tableau d[i][j] = distance d'édition entre les i premiers caractères de la chaîne 1 et les j premiers caractères de la chaîne 2.
def distance_edition(s1, s2):
n, m = len(s1), len(s2)
d = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
d[i][0] = i
for j in range(m + 1):
d[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
cout = 0 if s1[i-1] == s2[j-1] else 1
d[i][j] = min(
d[i-1][j] + 1, # suppression
d[i][j-1] + 1, # insertion
d[i-1][j-1] + cout # substitution (ou correspondance)
)
return d[n][m]
>>> distance_edition("ACTG", "ACG")
1 # une suppression (le T)
>>> distance_edition("chat", "chien")
3 # a→i, t→e, +n
4.4 Complexité¶
- Temps : O(n × m) où n et m sont les longueurs des chaînes ;
- Mémoire : O(n × m) pour le tableau (peut être réduit à O(min(n, m)) si on n'a besoin que de la distance).
5. Quand utiliser la programmation dynamique ?¶
| Condition | Description |
|---|---|
| Sous-structure optimale | La solution optimale contient les solutions optimales des sous-problèmes |
| Chevauchement | Les mêmes sous-problèmes sont résolus plusieurs fois |
Diviser pour régner vs programmation dynamique
- Diviser pour régner : sous-problèmes indépendants (tri fusion, rotation d'image)
- Programmation dynamique : sous-problèmes chevauchants (Fibonacci, rendu de monnaie)
À retenir¶
| Concept | Description |
|---|---|
| Programmation dynamique | Mémoriser les résultats pour éviter les recalculs |
| Mémoïsation | Approche descendante (récursion + cache) |
| Tabulation | Approche ascendante (remplissage d'un tableau) |
| Rendu de monnaie | Nombre minimal de pièces, optimal contrairement au glouton |
| Distance d'édition | Nombre minimal d'opérations pour transformer une chaîne en une autre |
| Sous-problèmes chevauchants | Condition nécessaire pour que la prog. dynamique soit utile |