Terminale · Numérique et sciences informatiques

Comprendre la notion de sous-problème en programmation dynamique

Identifier, pour un problème d'optimisation ou de dénombrement, les sous-problèmes qui le composent, établir la relation qui les relie et vérifier qu'ils se recouvrent et que l'optimalité se transmet.

Aperçu gratuit
Illustration de la fiche « Comprendre la notion de sous-problème en programmation dynamique »

Les points essentiels

  • Un sous-problème est une version plus petite du même problème, définie par un ou plusieurs paramètres (taille, indice, capacité restante). Exemple : F(k) pour calculer F(n), avec k < n.
  • Résoudre un problème par programmation dynamique revient à écrire une relation de récurrence exprimant la solution d'un problème en fonction de solutions de sous-problèmes plus petits, plus un ou plusieurs cas de base.

Les mots à connaître

Sous-problème
Instance plus petite du même problème, caractérisée par des paramètres (indice, taille, capacité restante...), dont la solution sert à construire celle du problème initial.
Recouvrement de sous-problèmes
Situation où un même sous-problème est demandé plusieurs fois au cours de la résolution récursive. C'est la condition qui rend la mémorisation rentable.

Un exemple pour comprendre

Suite de Fibonacci : F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Identifier les sous-problèmes de F(5), montrer le recouvrement en comptant les appels de la version récursive naïve, puis donner le nombre de sous-problèmes distincts.

Le sous-problème est F(k), paramétré par l'entier k avec 0 ≤ k ≤ 5. Appels de la version naïve, en notant C(n) le nombre d'appels pour F(n) : C(0)=C(1)=1 et C(n)=1+C(n-1)+C(n-2). Donc C(2)=1+1+1=3, C(3)=1+3+1=5, C(4)=1+5+3=9, C(5)=1+9+5=15. L'appel F(5) fait ainsi 15 appels au total. Recouvrement : F(3) est calculé 2 fois, F(2) 3 fois, F(1) 5 fois, F(0) 3 fois. Pourtant il n'existe que 6 sous-problèmes distincts : F(0), F(1), F(2), F(3), F(4), F(5). Avec mémoïsation, chaque F(k) avec k ≥ 2 est calculé une seule fois par une addition, soit 4 additions pour F(5). Le coût devient linéaire en n au lieu d'exponentiel.

Première page de l’Essentiel : Comprendre la notion de sous-problème en programmation dynamique
Ketty