NSI · Terminale · Algorithmique
Programmation dynamique
Ne jamais calculer deux fois la même chose.
En bref
La programmation dynamique s’applique aux problèmes dont les sous-problèmes se recouvrent : les mêmes calculs y reviennent un grand nombre de fois.
La programmation dynamique s’applique aux problèmes dont les sous-problèmes se recouvrent : les mêmes calculs y reviennent un grand nombre de fois. L’idée est de les mémoriser.
Les deux conditions
| Condition | Ce qu’elle signifie |
|---|---|
| Sous-structure optimale | La solution optimale se construit à partir des solutions optimales des sous-problèmes |
| Chevauchement des sous-problèmes | Les mêmes sous-problèmes réapparaissent |
Si la première seule est vérifiée, diviser pour régner suffit. C’est la seconde qui justifie la programmation dynamique.
Les deux façons de faire
| Descendante (mémoïsation) | Ascendante (tabulation) | |
|---|---|---|
| L’écriture | On garde la récursivité naturelle | On remplit un tableau, sans récursivité |
| Le mécanisme | Ranger chaque résultat dans un dictionnaire avant de le renvoyer | Aller des plus petits sous-problèmes vers les plus grands |
| L’avantage | Le code change à peine | Plus rapide, aucun risque de dépassement de pile |
| La contrainte | La pile reste limitée | Il faut déterminer soi-même le bon ordre de remplissage |
L’exemple de Fibonacci
| Version | Coût | Appels pour le 30ᵉ terme |
|---|---|---|
| Naïve | Exponentiel | plus d’un million |
| Avec mémoïsation | Linéaire | trente |
Le même algorithme, plus un dictionnaire, change de classe de complexité. C’est l’illustration la plus nette du chapitre.
Le rendu de monnaie
Rendre une somme avec le moins de pièces possible.
| Méthode | Son résultat |
|---|---|
| L’algorithme glouton | Optimal avec le système européen, mais il échoue ailleurs |
| La programmation dynamique | Toujours l’optimum |
Avec des pièces de 1, 3 et 4, rendre 6 : le glouton donne 4 + 1 + 1 (trois pièces) au lieu de 3 + 3 (deux).
La méthode dynamique calcule le nombre minimal de pièces pour chaque somme de 0 jusqu’à la somme visée, en réutilisant les résultats précédents.
Deux autres problèmes classiques
Le sac à dos — choisir des objets de valeurs et de poids donnés sans dépasser une capacité — et l’alignement de séquences en bio-informatique se traitent de la même façon, par un tableau à deux dimensions.
Le compromis
On échange de la mémoire contre du temps. Un tableau de taille n coûte de la place, mais évite un nombre exponentiel de recalculs.
Le signal à repérer : dans l’arbre des appels récursifs, le même argument revient plusieurs fois. Dès qu’on le voit, un dictionnaire suffit.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quelles sont les deux conditions d’application de la programmation dynamique ?
2.Qu’est-ce que la mémoïsation ?
3.Quelle est l’approche ascendante de la programmation dynamique ?
4.Quel est le coût de Fibonacci calculé avec mémoïsation ?
5.L’algorithme glouton donne toujours l’optimum pour le rendu de monnaie.
6.Que troque-t-on en programmation dynamique ?
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Prog. dynamique » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
