Fiche à trous · Terminale · NSI

Programmation dynamique — Mémoïsation

Complétez de mémoire, puis vérifiez avec la page de corrigé.

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.

La condition

Règle

Piège

Ajouter une mémoïsation à une fonction récursive quelconque en espérant l'accélérer.

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 ?

Résultat :

Deux façons de procéder

Propriété

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.

Deux problèmes de référence

Propriété

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

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 ?

Corrigé · à détacher

Programmation dynamique — Mémoïsation

1. 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 ?
2. $c h e v a u c h e m e n t d esso u s - p r o b l \overset{e}{ˋ} m es = co n d i t i o n d^{'} e f f i c a c i t \overset{e}{ˊ}$
3. 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.
4. 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.
5. 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.
6. Chevauchement massif d'un côté, nul de l'autre
7. 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.
8. 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.
9. Écrire d'abord la version récursive naïve, et identifier ce qui caractérise un sous-problème.
10. Vérifier le chevauchement : les mêmes paramètres reviennent-ils dans plusieurs branches ?
11. Si oui, ajouter une mémoïsation : consulter la table avant de calculer, y écrire après.
12. Estimer le gain : nombre de sous-problèmes distincts multiplié par le coût de chacun.
13. Si la profondeur de récursion est un risque, passer à la tabulation en déterminant l'ordre de remplissage.