Programme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte
Sous-problèmes chevauchants. Mémoïsation (top-down) vs tabulation (bottom-up). Exemples : Fibonacci, problème du sac à dos, plus longue sous-séquence commune.
La règle d'or
La programmation dynamique n'apporte quelque chose que si les sous-problèmes se chevauchent : sans recouvrement, il n'y a rien à mémoriser.
L'erreur que tout le monde fait
Ajouter une mémoïsation à une fonction récursive quelconque en espérant l'accélérer.
Mémoriser n'a d'effet que si le même sous-problème est demandé plusieurs fois : sur un découpage où chaque appel porte sur des données distinctes, le dictionnaire se remplit sans jamais servir et ne fait qu'occuper de la mémoire. La mémoïsation exige de plus que la fonction rende toujours le même résultat pour les mêmes arguments.
Dessiner l'arbre des appels sur un petit exemple : si un même nœud y apparaît plusieurs fois, la mémoïsation gagne.
Mémoriser les résultats intermédiaires d'une fonction récursive peut la rendre des millions de fois plus rapide — ou n'avoir strictement aucun effet, sinon celui d'occuper de la mémoire. Tout dépend d'une seule propriété du problème, et il faut la vérifier avant d'écrire une ligne.
1La condition
Règle
La programmation dynamique n'apporte quelque chose que si les sous-problèmes se chevauchent, c'est-à-dire si les mêmes calculs sont demandés plusieurs fois. Sans recouvrement, il n'y a rien à mémoriser : chaque résultat stocké ne sert qu'une fois, et l'on paie la mémoire sans rien gagner. La vérification est donc préalable : les appels récursifs portent-ils sur des entrées déjà rencontrées ?
Ajouter une mémoïsation à une fonction récursive quelconque en espérant l'accélérer.
Pourquoi — Sur un problème sans recouvrement — un tri fusion, une dichotomie —, chaque sous-problème est distinct : la table se remplit d'entrées consultées zéro fois. On ajoute alors le coût du stockage et celui de la consultation, sans supprimer le moindre calcul. Le programme devient plus lent et consomme davantage. La mémoïsation n'est pas une optimisation générale.
Le réflexe — Avant de mémoriser, vérifier que les mêmes entrées reviennent.
Exemple
Pourquoi la mémoïsation transforme-t-elle le calcul récursif de Fibonacci, et pas celui du tri fusion ?
Pour Fibonacci, calculer le terme n demande le terme n−1 et le terme n−2, et chacun redemande les précédents : le terme n−2 est recalculé un nombre exponentiel de fois. Le recouvrement est massif.
Pour le tri fusion, chaque appel porte sur une portion différente du tableau : aucune portion n'est triée deux fois. Le recouvrement est nul.
La mémoïsation fait donc chuter Fibonacci d'un coût exponentiel à un coût linéaire, et n'apporte rien au tri fusion.
Chevauchement massif d'un côté, nul de l'autre
2Deux façons de procéder
Propriété
La mémoïsation est l'approche descendante : on garde la fonction récursive et on lui ajoute un dictionnaire qui mémorise les résultats déjà calculés. Elle ne calcule que les sous-problèmes effectivement nécessaires. La tabulation est l'approche ascendante : on remplit un tableau des plus petits cas vers les plus grands, sans récursion. Elle évite la pile d'appels et son risque de saturation, mais calcule parfois des cases dont on n'avait pas besoin.
Le choix entre les deux n'est pas qu'une question de goût. La mémoïsation se code en modifiant très peu la fonction récursive d'origine, ce qui limite les erreurs d'écriture. La tabulation demande de trouver le bon ordre de remplissage — chaque case ne doit dépendre que de cases déjà remplies —, ce qui est parfois le vrai travail du problème.
3Deux problèmes de référence
Propriété
Le problème du sac à dos : choisir parmi des objets ayant chacun un poids et une valeur, de façon à maximiser la valeur totale sans dépasser une capacité. Les sous-problèmes — « la meilleure valeur avec les i premiers objets et une capacité c » — se chevauchent massivement, d'où l'efficacité de la programmation dynamique. La plus longue sous-séquence commune à deux chaînes relève du même schéma, et sert à comparer des textes ou des séquences biologiques.
Ces deux problèmes partagent la structure qui rend le paradigme applicable : une solution optimale se compose de solutions optimales de sous-problèmes. Cette propriété n'est pas automatique — elle se vérifie, et c'est elle, avec le chevauchement, qui autorise le procédé. Un problème où un choix localement optimal interdit le meilleur choix global ne s'y prête pas.
Transformer une récursion en solution par programmation dynamique
Écrire d'abord la version récursive naïve, et identifier ce qui caractérise un sous-problème.
Vérifier le chevauchement : les mêmes paramètres reviennent-ils dans plusieurs branches ?
Si oui, ajouter une mémoïsation : consulter la table avant de calculer, y écrire après.Sans chevauchement, s'arrêter là : la mémoïsation coûterait sans rien rapporter.
Estimer le gain : nombre de sous-problèmes distincts multiplié par le coût de chacun.
Si la profondeur de récursion est un risque, passer à la tabulation en déterminant l'ordre de remplissage.
▢Ai-je vérifié que les sous-problèmes se chevauchent ?
▢Ai-je identifié ce qui caractérise un sous-problème — quels paramètres ?
▢Ma table est-elle consultée avant le calcul et écrite après ?
▢Ai-je mesuré le nombre de sous-problèmes distincts pour estimer le gain ?
▢Si je tabule, chaque case ne dépend-elle que de cases déjà remplies ?
▢Ai-je vérifié qu'une solution optimale se compose de sous-solutions optimales ?
L'essentiel en 11 points
·La programmation dynamique exige le chevauchement des sous-problèmes.
·Sans recouvrement, il n'y a rien à mémoriser : on paie sans gagner.
·Ajouter une mémoïsation à un tri fusion le rend plus lent.
·Mémoïsation : descendante, récursion + table, ne calcule que le nécessaire.
·Tabulation : ascendante, tableau rempli des petits cas vers les grands.
·La tabulation évite la pile d'appels mais exige le bon ordre de remplissage.
a.Quelle condition rend la programmation dynamique utile ?
b.Différencier mémoïsation et tabulation.
c.Quel risque la tabulation évite-t-elle ?
d.Énoncer le problème du sac à dos.
e.Quelle seconde propriété le problème doit-il vérifier ?
›Voir le corrigéMasquer le corrigé
a. Le chevauchement des sous-problèmes : les mêmes calculs doivent être demandés plusieurs fois.
b. La mémoïsation est descendante — on garde la récursion et on mémorise. La tabulation est ascendante — on remplit un tableau des petits cas vers les grands.
c. La saturation de la pile d'appels, puisqu'elle n'emploie pas de récursion.
d. Choisir parmi des objets ayant un poids et une valeur, de façon à maximiser la valeur sans dépasser une capacité.
e. Qu'une solution optimale se compose de solutions optimales de sous-problèmes.
2
Un développeur ajoute une mémoïsation à une fonction de tri fusion. Analyser.
Analyser
a.Les sous-problèmes d'un tri fusion se chevauchent-ils ?
b.Que contient alors la table de mémoïsation ?
c.Le programme devient-il plus rapide ?
d.Quel est le coût ajouté ?
e.Quelle vérification aurait évité ce travail ?
›Voir le corrigéMasquer le corrigé
a. Non. Chaque appel porte sur une portion différente du tableau : aucune portion n'est triée deux fois.
b. Des entrées consultées zéro fois : chaque résultat stocké ne sera jamais redemandé.
c. Non : il devient plus lent. Aucun calcul n'est supprimé, et deux opérations sont ajoutées à chaque appel.
d. Le stockage de la table, sa consultation avant chaque calcul et son écriture après. On paie donc la mémoire et le temps.
e. Vérifier, sur la version récursive naïve, si les mêmes paramètres reviennent dans plusieurs branches. La réponse était non, et la mémoïsation était donc exclue d'emblée.
3
Le calcul récursif naïf de Fibonacci recalcule massivement les mêmes valeurs.
Raisonner
a.Pourquoi le terme n−2 est-il recalculé de nombreuses fois ?
b.Combien de sous-problèmes distincts existe-t-il pour calculer le terme n ?
c.Quelle complexité obtient-on avec mémoïsation ?
d.Pourquoi ce gain est-il si spectaculaire ?
›Voir le corrigéMasquer le corrigé
a. Parce que le terme n demande n−1 et n−2, et que n−1 redemande n−2 : la branche se duplique à chaque niveau, et le nombre d'appels croît de façon exponentielle.
b. n au plus : un par valeur de 0 à n. Le nombre d'appels naïfs est exponentiel, mais le nombre de calculs distincts est linéaire.
c. O(n) : chaque sous-problème n'est calculé qu'une fois, les autres appels étant des consultations.
d. Parce qu'on passe d'un nombre exponentiel d'appels à un nombre linéaire de calculs. L'écart entre les deux croît si vite qu'il rend utilisable, en une fraction de seconde, un calcul qui demandait auparavant des durées inatteignables.
4
Mémoïsation ou tabulation. Raisonner sur le choix.
Argumenter
a.Quel avantage la mémoïsation a-t-elle sur le nombre de calculs ?
b.Quel avantage la tabulation a-t-elle sur la mémoire d'exécution ?
c.Quelle difficulté propre la tabulation introduit-elle ?
d.Pourquoi le sac à dos se prête-t-il au paradigme ?
e.Quel type de problème ne s'y prête pas ?
›Voir le corrigéMasquer le corrigé
a. Elle ne calcule que les sous-problèmes effectivement nécessaires, là où la tabulation peut remplir des cases dont on n'avait pas besoin.
b. Elle n'emploie pas de récursion, donc n'empile aucun appel : elle évite la saturation de la pile d'appels sur les grandes entrées.
c. Il faut trouver le bon ordre de remplissage : chaque case ne doit dépendre que de cases déjà remplies. C'est parfois le vrai travail du problème.
d. Parce que ses sous-problèmes — la meilleure valeur avec les i premiers objets et une capacité c — se chevauchent massivement, et qu'une solution optimale s'y compose de sous-solutions optimales.
e. Un problème où un choix localement optimal interdit le meilleur choix global : la seconde propriété tombe, et décomposer en sous-problèmes optimaux ne reconstruit plus l'optimum. La propriété se vérifie, elle n'est pas automatique.
Ce qui rapporte des points, ce qui en coûte
Énoncer la condition de chevauchement5 ptsPerdu si : Traiter la mémoïsation comme une optimisation générale
Montrer qu'une mémoïsation inutile coûte4 ptsPerdu si : Conclure qu'elle est au pire neutre
Distinguer mémoïsation et tabulation4 ptsPerdu si : Les présenter comme équivalentes
Estimer le gain par le nombre de sous-problèmes distincts4 ptsPerdu si : Annoncer un gain sans le mesurer
Vérifier la sous-structure optimale3 ptsPerdu si : La supposer acquise
4
La méthode
Transformer une récursion en solution par programmation dynamique
1
Écrire d'abord la récurrence naïve, sans se soucier de son coût.
2
Vérifier le recouvrement des sous-problèmes sur l'arbre des appels.
3
Choisir la clé qui identifie un sous-problème et stocker chaque résultat une fois calculé.
4
Décider du sens de résolution : depuis le problème initial, ou depuis les plus petits cas.
Remplir un tableau des petits cas vers les grands évite toute pile d'appels.
5
Évaluer le coût final, qui vaut le nombre de sous-problèmes distincts multiplié par le travail de chacun.
5
Se tester
Touches 1 à 4
NSITerminale
Question 1
Quel est le résultat de l'exécution de ce code Python ?
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Programmation dynamique — Mémoïsation : c'est en quelle classe ?+
Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
Que faut-il savoir sur Programmation dynamique — Mémoïsation ?+
Sous-problèmes chevauchants. Mémoïsation (top-down) vs tabulation (bottom-up). Exemples : Fibonacci, problème du sac à dos, plus longue sous-séquence commune. Les notions à maîtriser sont : programmation dynamique, mémoïsation, tabulation, sac à dos, Fibonacci, sous-séquence.
Où télécharger la fiche PDF de Programmation dynamique — Mémoïsation ?+
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 6 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Le corrigé de Programmation dynamique — Mémoïsation est-il fourni ?+
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Programmation dynamique — Mémoïsation peut-il tomber au Baccalauréat ?+
Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Faut-il un compte pour s'entraîner sur Programmation dynamique — Mémoïsation ?+
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.