Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• reconnaître un problème présentant des sous-problèmes répétés et une sous-structure optimale ;

• expliquer pourquoi une récursion naïve peut entraîner un coût exponentiel ;

• transformer une solution récursive en solution mémoïsée, puis en solution tabulée ;

• définir précisément l’état, la relation de transition, les cas de base et l’ordre de calcul ;

• analyser le temps d’exécution et la mémoire d’une solution dynamique ;

• reconstruire une solution optimale à partir d’une table de décisions ;

• appliquer la programmation dynamique à Fibonacci, aux chemins dans une grille, au sac à dos, au chemin de somme minimale et au rendu de monnaie optimal ;

• choisir entre récursion naïve, mémoïsation, tabulation et optimisation mémoire selon le contexte.

Prérequis

• fonctions, procédures et récursivité ;

• tableaux à une et deux dimensions ;

• relations de récurrence simples et analyse asymptotique ;

• méthode diviser pour régner ;

• notions d’optimalité, de minimum, de maximum et de solution réalisable.

Organisation indicative

Introduction générale

De nombreux problèmes algorithmiques semblent difficiles parce qu’une solution récursive explore un grand nombre de possibilités et recalcule plusieurs fois les mêmes résultats. La programmation dynamique transforme cette répétition en avantage : lorsqu’un sous-problème est résolu, son résultat est conservé afin d’être réutilisé.

Cette méthode est particulièrement efficace lorsque le problème possède deux propriétés : des sous-problèmes qui se recouvrent et une sous-structure optimale. Elle permet souvent de remplacer un temps exponentiel par un temps polynomial, au prix d’une mémoire supplémentaire.

15.1 Problèmes à sous-problèmes répétés

15.1.1 Calcul naïf

Une solution naïve applique directement la définition récursive du problème. Elle peut être correcte et très lisible, mais elle ne tient pas compte du fait que plusieurs appels demandent exactement le même résultat.

Exemple introductif — Fibonacci

La suite est définie par F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2) pour n ≥ 2.

15.1.2 Appels identiques

Pour calculer F(5), l’appel F(3) apparaît dans les branches issues de F(4) et de F(3). De même, F(2), F(1) et F(0) sont évalués plusieurs fois. L’arbre des appels contient donc beaucoup de nœuds identiques.

15.1.3 Coût exponentiel

Le nombre d’appels du Fibonacci naïf croît approximativement comme la suite elle-même. Sa complexité est souvent majorée par O(2ⁿ). Une augmentation modeste de n peut donc multiplier fortement le temps d’exécution.

15.1.4 Sous-problèmes recouvrants et sous-structure optimale

Deux propriétés guident l’utilisation de la programmation dynamique :

• Sous-problèmes recouvrants : plusieurs chemins de calcul demandent le même état.

• Sous-structure optimale : une solution optimale du problème peut être obtenue en combinant des solutions optimales de sous-problèmes.

15.1.5 Modéliser un état

Un état est une description compacte d’un sous-problème. Il doit contenir assez d’informations pour déterminer la suite du calcul, sans stocker de détails inutiles.

15.2 Mémoïsation

15.2.1 Approche descendante

La mémoïsation conserve la structure récursive. La fonction commence par le problème complet et descend vers les sous-problèmes nécessaires. Avant tout calcul, elle consulte un cache. Si le résultat existe déjà, il est retourné immédiatement.

15.2.2 Stockage des résultats

Le cache peut être un tableau, une matrice ou un dictionnaire. Le choix dépend de la forme des états.

15.2.3 Réutilisation des valeurs calculées

Avec cette transformation, chaque valeur F(i) est calculée au plus une fois. Le temps devient O(n), tandis que le tableau et la pile récursive utilisent O(n) mémoire.

15.2.4 Valeur sentinelle et état réellement calculé

Il faut distinguer une valeur non calculée d’un résultat valide. Une valeur sentinelle telle que −1 ne convient que si −1 ne peut jamais être une réponse. Sinon, on utilise un tableau booléen Calcule, une valeur spéciale ou la présence de la clé dans un dictionnaire.

15.2.5 Complexité de la mémoïsation

Une estimation pratique est : nombre d’états distincts × coût de traitement d’un état. Si chaque état examine k transitions, le temps est généralement O(nombre d’états × k).

15.2.6 Avantages et limites

15.3 Tabulation

15.3.1 Approche ascendante

La tabulation commence par les cas de base et construit progressivement les états plus grands. Elle remplace les appels récursifs par des boucles et rend explicite l’ordre des dépendances.

15.3.2 Tableau de résultats

15.3.3 Ordre de calcul

Un état ne peut être calculé que lorsque tous les états dont il dépend sont disponibles. L’ordre de parcours constitue donc une partie essentielle de la conception.

15.3.4 Mémoïsation et tabulation : comparaison

15.3.5 Optimisation de la mémoire

Si la transition n’utilise qu’un petit nombre d’états précédents, la table complète n’est pas toujours nécessaire. Pour Fibonacci, deux variables suffisent.

15.4 Exemples détaillés

15.4.1 Fibonacci

Fibonacci illustre clairement les sous-problèmes répétés, mais ne constitue pas toujours le meilleur exemple d’optimisation réelle. Il permet néanmoins de comparer les trois approches.

15.4.2 Nombre de chemins dans une grille

On considère une grille de n lignes et m colonnes. Depuis la case supérieure gauche, on peut uniquement se déplacer vers la droite ou vers le bas. Le nombre de chemins vers (i, j) est la somme des chemins vers la case située au-dessus et vers celle située à gauche.

État : dp[i][j] représente le nombre de chemins permettant d’atteindre la case (i, j).

Transition : dp[i][j] = dp[i − 1][j] + dp[i][j − 1].

Cas de base : la première ligne et la première colonne contiennent une seule possibilité, en l’absence d’obstacle.

Pour une grille 3 × 4, le résultat est 10. La complexité est O(nm) en temps et O(nm) en mémoire. Une seule ligne suffit si l’on ne reconstruit pas les chemins.

Variante avec obstacles

Une case bloquée reçoit 0 chemin. Les autres cases conservent la même transition. La valeur de la case initiale vaut 1 uniquement si elle est accessible.

15.4.3 Problème du sac à dos simplifié

On dispose de n objets. L’objet i possède un poids poids[i] et une valeur valeur[i]. Le sac a une capacité C. Chaque objet peut être choisi au plus une fois. L’objectif est de maximiser la valeur totale sans dépasser C.

État : dp[i][c] est la valeur maximale obtenue avec les i premiers objets et une capacité c.

Transition : si poids[i] > c, l’objet ne peut pas être pris. Sinon, on choisit le meilleur résultat entre ne pas le prendre et le prendre.

Pour C = 5, la meilleure valeur est 7, obtenue avec A et B. Le temps et la mémoire de la version 2D sont O(nC).

Reconstruction des objets choisis

15.4.4 Chemin de somme minimale

Dans ce chapitre, « somme minimale » désigne le problème suivant : chaque case d’une grille possède un coût. On cherche un chemin de la case supérieure gauche à la case inférieure droite, avec des déplacements vers la droite ou vers le bas, minimisant la somme des coûts visités.

État : dp[i][j] représente le coût minimal pour atteindre (i, j).

Transition : dp[i][j] = cout[i][j] + min(dp[i − 1][j], dp[i][j − 1]).

Le coût minimal est 7. Pour reconstruire le chemin, on remonte depuis la destination vers le voisin ayant fourni le minimum.

15.4.5 Rendu de monnaie optimal

On connaît des valeurs de pièces et une somme S. On cherche le nombre minimal de pièces nécessaire pour former exactement S. Contrairement à une stratégie gloutonne, la programmation dynamique garantit l’optimalité pour tout système de pièces.

État : dp[s] est le nombre minimal de pièces pour former la somme s.

Cas de base : dp[0] = 0. Les autres valeurs sont initialisées à +∞.

Transition : dp[s] = min(dp[s], 1 + dp[s − piece]) pour chaque pièce utilisable.

Pour S = 6, la réponse optimale est 2, avec 3 + 3. Une stratégie gloutonne prenant 4 puis deux pièces de 1 utiliserait 3 pièces.

Reconstruction des pièces

Méthode générale de conception

Une solution dynamique fiable peut être conçue selon une démarche en sept étapes.

1. Définir précisément le problème, les entrées, les contraintes et la valeur recherchée.

2. Identifier les sous-problèmes et choisir un état minimal mais suffisant.

3. Écrire la relation de transition entre un état et des états plus simples.

4. Définir tous les cas de base et les valeurs impossibles.

5. Choisir mémoïsation ou tabulation, puis déterminer l’ordre de calcul.

6. Analyser le nombre d’états, le coût des transitions et la mémoire.

7. Prévoir la reconstruction de la solution si le résultat attendu ne se limite pas à sa valeur.

Preuve de correction

La correction d’un algorithme dynamique repose généralement sur une induction selon l’ordre de calcul :

• Cas de base : les plus petits états possèdent la bonne valeur.

• Hypothèse : les états dont dépend l’état courant sont corrects.

• Étape : la transition examine tous les choix admissibles et sélectionne la combinaison correcte ou optimale.

• Conclusion : tous les états, notamment l’état final, sont corrects.

Erreurs fréquentes

Applications guidées

Travaux dirigés

Les exercices suivants sont conçus pour travailler la modélisation avant l’écriture du code. Pour chaque problème, préciser l’état, la transition, les cas de base, l’ordre de calcul et la complexité.

TD 1 — Reconnaissance des sous-problèmes

Pour Fibonacci(6), dessiner l’arbre des appels naïfs et identifier les appels répétés. Estimer le nombre d’états distincts.

TD 2 — Comparaison mémoïsation / tabulation

Présenter les avantages et limites des deux approches pour une grille contenant de nombreux obstacles et dont seule une petite partie est accessible.

TD 3 — Escalier

Une personne peut monter une ou deux marches. Déterminer le nombre de façons d’atteindre la marche n.

TD 4 — Chemins avec obstacles

Calculer le nombre de chemins dans une grille 4 × 5 contenant des cases interdites.

TD 5 — Sac à dos

Résoudre le sac à dos pour des objets (poids, valeur) : (2, 6), (2, 10), (3, 12), capacité 5.

TD 6 — Somme minimale

Calculer le coût minimal dans une grille 3 × 4 et reconstruire un chemin optimal.

TD 7 — Monnaie

Pour les pièces {1, 3, 4} et S = 6, comparer le choix glouton à la solution dynamique.

TD 8 — Optimisation mémoire

Transformer une table 2D de chemins en une solution utilisant une seule ligne.

TD 9 — Sous-ensemble de somme

Déterminer si un sous-ensemble de {3, 5, 7, 10} peut former la somme 15.

TD 10 — Conception libre

Proposer un état dynamique pour minimiser le coût d’une suite de décisions sur n étapes, avec deux choix possibles à chaque étape et un coût de changement.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

F(6) produit notamment plusieurs occurrences de F(4), F(3), F(2), F(1) et F(0). Les états distincts sont seulement F(0) à F(6), soit 7 états. L’arbre naïf contient beaucoup plus de nœuds, ce qui justifie le cache.

Correction du TD 2

La mémoïsation est intéressante si les obstacles rendent une grande partie de la grille inaccessible : seuls les états visités sont calculés. La tabulation reste souvent plus simple et évite la pile, mais elle parcourt potentiellement toutes les cases.

Correction du TD 3 — Escalier

État : dp[i] est le nombre de façons d’atteindre la marche i. Transition : dp[i] = dp[i − 1] + dp[i − 2]. Bases : dp[0] = 1 et dp[1] = 1. Temps O(n), mémoire O(n), réductible à O(1).

Correction du TD 4 — Grille avec obstacles

Initialiser la case de départ à 1 si elle est libre. Chaque obstacle reçoit 0. Pour une case libre, additionner le haut et la gauche. Le résultat dépend de la disposition exacte des obstacles. La complexité est O(nm).

Correction du TD 5 — Sac à dos

Objets : A(2,6), B(2,10), C(3,12), capacité 5. Les choix possibles montrent que B + C pèse 5 et vaut 22. A + C vaut 18 et A + B vaut 16. La valeur optimale est donc 22.

Correction du TD 6 — Somme minimale

Construire la première ligne et la première colonne par cumul, puis appliquer la transition coût + minimum(haut, gauche). Pour reconstruire, partir de la destination et remonter vers le voisin de plus faible coût cumulé jusqu’à la source.

Correction du TD 7 — Monnaie

Le glouton choisit 4, puis 1, puis 1 : trois pièces. La programmation dynamique trouve 3 + 3 : deux pièces. Ce contre-exemple montre que le choix local du plus grand montant n’est pas toujours optimal.

Correction du TD 8 — Une seule ligne

Correction du TD 9 — Sous-ensemble de somme

État booléen dp[s] : une somme s est-elle réalisable ? Initialiser dp[0] = Vrai. Pour chaque valeur x, parcourir s en ordre décroissant et poser dp[s] = dp[s] OU dp[s − x]. Pour 15, la réponse est Vrai grâce à 5 + 10 ou 3 + 5 + 7.

Correction du TD 10 — Coût de changement

Un état possible est dp[i][c], coût minimal après les i premières étapes lorsque le choix courant est c ∈ {0,1}. La transition ajoute le coût de l’étape et éventuellement une pénalité si le choix diffère de celui de l’étape précédente. Il existe O(n) états et O(1) transitions par état.

Travail pratique — Laboratoire de programmation dynamique

Objectif

Implémenter et comparer les approches naïve, mémoïsée, tabulée et optimisée. Le TP doit mettre en évidence le lien entre théorie, mesures expérimentales et reconstruction des solutions.

Travail demandé

1. Implémenter Fibonacci dans les quatre versions et compter les appels ou itérations.

2. Implémenter le nombre de chemins dans une grille, avec puis sans obstacles.

3. Implémenter le sac à dos 0/1 et reconstruire la liste des objets choisis.

4. Implémenter le chemin de somme minimale et afficher un chemin optimal.

5. Implémenter le rendu de monnaie optimal et afficher les pièces utilisées.

6. Mesurer le temps, la mémoire approximative et le nombre d’états calculés.

7. Rédiger une conclusion expliquant les différences entre mémoïsation et tabulation.

Architecture suggérée

Jeux d’essai minimaux

Grille d’évaluation

Synthèse du chapitre

Glossaire

Auto-évaluation

Pour chaque compétence, indiquer : acquis, en cours d’acquisition ou à revoir.

Conclusion

La programmation dynamique fournit une méthode générale pour remplacer des recalculs coûteux par une organisation méthodique des sous-problèmes. La mémoïsation conserve la logique récursive et calcule à la demande ; la tabulation explicite l’ordre de calcul et facilite souvent l’optimisation mémoire. Dans les deux cas, la qualité de la solution dépend d’abord de la définition de l’état, de la transition et des cas de base.

Les chapitres suivants pourront approfondir cette méthode à travers des problèmes classiques plus complexes, la reconstruction d’optima et l’optimisation de l’espace mémoire.