Preuve de correction par récurrence d'un algorithme de programmation dynamique

Bonjour,

Dans la leçon précédente, vous avez brillamment transformé la relation de récurrence du problème du sac à dos en un algorithme de tabulation efficace, allant même jusqu'à en optimiser la complexité spatiale. Pour un concours comme l'Agrégation, cette maîtrise de l'implémentation est nécessaire, mais non suffisante. L'étape qui distingue une compréhension superficielle d'une maîtrise profonde est la capacité à prouver formellement que votre algorithme est correct.

Aujourd'hui, nous nous consacrons entièrement à cette compétence. L'objectif est d'apprendre à rédiger une preuve de correction pour un algorithme de programmation dynamique. Nous établirons une méthode structurée, puis nous l'appliquerons à un exemple canonique, en utilisant un raisonnement par récurrence sur la structure des sous-problèmes. C'est une compétence fondamentale, attendue à l'oral comme à l'écrit du concours.

1. Le Fondement de la Preuve : Sous-structure Optimale

Avant de plonger dans la rédaction d'une preuve, rappelons le principe qui sous-tend toute la programmation dynamique : la sous-structure optimale. Un problème présente une sous-structure optimale si une solution optimale au problème peut être construite à partir de solutions optimales à ses sous-problèmes.

La preuve de correction d'un algorithme de programmation dynamique consiste essentiellement à démontrer formellement que cette propriété est bien respectée par la relation de récurrence que nous avons établie. Les outils pour ce faire sont les techniques de démonstration mathématique que vous connaissez, notamment la preuve par l'absurde (ou par contradiction) et la preuve par récurrence (ou induction).

La vidéo suivante introduit de manière conceptuelle la preuve de cette propriété, d'abord par contradiction puis par induction, sur deux exemples classiques.

Principle of Optimality - Dynamic Programming

Cette vidéo de CSBreakdown, intitulée 'Principle of Optimality', illustre comment prouver formellement la propriété de sous-structure optimale. C'est le cœur logique de nos futures preuves de correction.

Regardez deux segments : De 05:06 à 06:54 : La preuve par contradiction pour le problème du plus court chemin. Observez l'argument "cut-and-paste" : on suppose qu'il existe un meilleur chemin pour un sous-problème et on montre que cela contredit l'optimalité de la solution globale. De 06:54 à 09:10 : La preuve par induction pour la suite de Fibonacci. C'est le modèle que nous allons le plus utiliser : on établit un cas de base, on pose une hypothèse de récurrence pour k < n, et on l'utilise pour prouver la propriété pour k+1.

2. Une Méthodologie pour la Preuve de Correction

Une preuve de correction pour un algorithme de programmation dynamique est un exercice de rigueur qui suit une structure bien définie. Le document suivant, une guide de l'Université de Stanford, décompose cette structure en cinq étapes claires.

[PDF] Guide to Dynamic Programming

Ce guide, intitulé 'Guide to Dynamic Programming', formalise la structure d'une preuve de correction. Nous allons adopter cette méthodologie.

Lisez attentivement la section 'Dynamic Programming Proofs' (première page). Concentrez-vous sur les cinq points listés qui décrivent le plan d'une preuve de correction. Nous allons les traduire et les utiliser comme notre feuille de route.

Voici la traduction et notre plan de bataille pour toute preuve de correction :

Définir les sous-problèmes : Définir précisément ce que la quantité $O P T (k)$ ou $O P T (i, j)$ représente.
Écrire une récurrence : Donner l'équation de récurrence qui lie $O P T$ à ses sous-problèmes, sans oublier les cas de base.
Prouver que la récurrence est correcte : C'est l'étape la plus cruciale. On y démontre que la relation de récurrence calcule bien la valeur optimale définie à l'étape 1.
Prouver que l'algorithme évalue la récurrence : Montrer que le code (souvent itératif) remplit la table de programmation dynamique dans un ordre qui respecte les dépendances de la récurrence, et que chaque cellule de la table correspond bien à la valeur de $O P T$ . C'est ici que la preuve par récurrence sur les sous-problèmes intervient de manière centrale.
Prouver que l'algorithme est correct : Conclure en montrant que la valeur retournée par l'algorithme (par ex. la dernière case de la table) correspond bien à la solution du problème initial.

3. Application : Preuve de l'Algorithme pour le Rendu de Monnaie

Appliquons cette méthode rigoureuse au problème du Rendu de Monnaie (Coin Change), un autre classique de la programmation dynamique. L'objectif est de rendre une somme $x$ en utilisant un nombre minimal de pièces, à partir d'un système de pièces donné ${c_{1}, c_{2}, \dots, c_{n}}$ .

Nous allons nous appuyer sur le document suivant, qui offre des exercices corrigés de niveau Agrégation.

[PDF] Diplôme Inter-Universitaire (DIU) “Enseigner l'informatique au lycée”

Ce document, 'ExosAvecCorrection' de Nicolas Nisse, contient une analyse complète du problème du rendu de monnaie. Nous allons utiliser les exercices 72 et 73 pour construire notre preuve.

Pour l'instant, survolez simplement les exercices 72 et 73 pour vous familiariser avec le problème, la formule de récurrence et l'algorithme proposé (Algorithm 60). Nous allons les disséquer étape par étape.

Étape 1 & 2 : Définition du sous-problème et de la récurrence

Sous-problème : Soit $O P T (x)$ le nombre minimum de pièces nécessaires pour rendre la monnaie pour une valeur $x$ .
Récurrence : Pour $x > 0$ , la dernière pièce ajoutée pour atteindre $x$ doit être l'une des pièces $c_{i}$ disponibles. Si cette pièce est $c_{i}$ , alors les pièces restantes doivent former une solution optimale pour la valeur $x - c_{i}$ . On choisit donc la pièce $c_{i}$ qui minimise le total. Cela nous donne : $O P T (x) = 1 + i ∣ c_{i} \leq x min {O P T (x - c_{i})}$ Le cas de base est $O P T (0) = 0$ .

Étape 3 : Preuve de la correction de la récurrence

C'est le cœur de la preuve. Nous devons montrer que la formule ci-dessus est correcte. L'Exercice 72 du document de N. Nisse le fait de manière très formelle par une double inégalité.

Veuillez étudier attentivement la réponse à l'Exercice 72.

La preuve se déroule en deux temps :

$O P T (x) \geq 1 + min {\dots}$ : On part d'une solution optimale pour $x$ . Elle contient au moins une pièce, disons $c_{j}$ . En retirant cette pièce, on obtient une solution (pas forcément optimale) pour $x - c_{j}$ , dont la taille est $O P T (x) - 1$ . Par définition, la taille de cette solution est supérieure ou égale à la taille de la solution optimale pour $x - c_{j}$ , soit $O P T (x - c_{j})$ . On a donc $O P T (x) - 1 \geq O P T (x - c_{j})$ . Comme cela est vrai pour un certain $j$ , c'est forcément vrai pour le $j$ qui minimise l'expression. On en déduit l'inégalité.
$O P T (x) \leq 1 + min {\dots}$ : On part d'une solution optimale pour un sous-problème bien choisi. Soit $j$ l'indice tel que $O P T (x - c_{j})$ est minimal. On prend une solution optimale pour $x - c_{j}$ (de taille $O P T (x - c_{j})$ ) et on y ajoute la pièce $c_{j}$ . On obtient une solution valide (pas forcément optimale) pour $x$ , de taille $1 + O P T (x - c_{j})$ . Par définition, la taille de la solution optimale pour $x$ , $O P T (x)$ , est inférieure ou égale à la taille de n'importe quelle solution valide. On en déduit l'inégalité.

Ces deux inégalités prouvent l'égalité et donc la correction de la relation de récurrence.

Étape 4 : Preuve que l'algorithme évalue la récurrence

C'est ici que nous utilisons une preuve par récurrence sur les sous-problèmes. L'algorithme itératif renduMonnaieProgDyn (Algorithm 60) calcule les valeurs de $O P T (i)$ pour $i$ allant de 1 à $x$ et les stocke dans un tableau res. Nous allons prouver par récurrence sur $i$ que res[i] contient bien la valeur de $O P T (i)$ .

Fonctionnement de la preuve (Mathematical Induction) — Cette image illustre le principe d'une preuve par récurrence (induction). On prouve un cas de base (P(0)), puis on montre que si la propriété est vraie pour k (hypothèse de récurrence), elle l'est aussi pour k+1. C'est exactement ce que nous faisons pour prouver que notre algorithme remplit correctement la table des sous-problèmes.

Propriété à prouver : Soit $P (i)$ la proposition : "Après la fin de l'itération $i$ de la boucle principale (externe), on a res[k] = OPT(k) pour tout $0 \leq k \leq i$ ".

Veuillez maintenant lire la section "Validité" de l'Algorithm 60 (Exercice 73). Elle esquisse cette preuve. Détaillons-la :

Cas de base (Initialisation) : Avant la boucle, res[0] est initialisé à 0, ce qui correspond bien à $O P T (0)$ . La propriété $P (0)$ est donc vraie.
Hypothèse de récurrence : Supposons que $P (i - 1)$ est vraie. C'est-à-dire, pour tout $k < i$ , res[k] contient la valeur correcte de $O P T (k)$ .
Étape de récurrence (Preuve pour $i$ ) : À l'itération $i$ , l'algorithme calcule res[i] avec la ligne de code :
res[i] = min(res[i - c[j]] + 1, res[i])
Cette ligne est exécutée pour tous les j tels que i - c[j] >= 0. Quand la boucle interne sur j se termine, res[i] contient la valeur : $1 + j ∣ c_{j} \leq i min {res [i - c_{j}]}$ Par notre hypothèse de récurrence, comme $i - c_{j} < i$ , nous savons que res[i - c_j] = OPT(i - c_j). En substituant, on obtient : $res [i] = 1 + j ∣ c_{j} \leq i min {O P T (i - c_{j})}$ D'après l'étape 3, nous savons que le second terme est exactement la définition de $O P T (i)$ . Donc, res[i] = OPT(i).
De plus, les valeurs res[k] pour $k < i$ ne sont pas modifiées. La propriété $P (i)$ est donc vraie.

Par le principe de récurrence, la propriété est vraie pour tout $i$ de 0 à $x$ .

Étape 5 : Preuve de la correction finale de l'algorithme

L'algorithme termine et retourne res[x]. D'après la preuve de l'étape 4, nous avons démontré que res[x] = OPT(x). L'algorithme renvoie donc bien le nombre minimum de pièces, ce qui achève la preuve de correction.

4. Synthèse

La structure de la programmation dynamique, où la solution d'un problème dépend de celles de sous-problèmes "plus petits", se prête naturellement à la preuve par récurrence. On peut visualiser l'ensemble des sous-problèmes et leurs dépendances comme un graphe orienté acyclique (DAG). L'algorithme de tabulation parcourt ce graphe dans un ordre topologique, et la preuve de correction par récurrence montre qu'à chaque étape, le chemin calculé est bien optimal.

Dynamic Programming Graph Representation for Knapsack Problem — Cette image représente un graphe de sous-problèmes pour un problème de programmation dynamique. Chaque nœud est un sous-problème. L'algorithme de tabulation consiste à calculer la valeur de chaque nœud en se basant sur les valeurs de ses prédécesseurs. Notre preuve par récurrence formalise l'idée que si les valeurs des prédécesseurs sont optimales (hypothèse de récurrence), alors la valeur calculée pour le nœud courant est aussi optimale.

La méthode en 5 étapes que nous avons appliquée au Rendu de Monnaie est un schéma général que vous pouvez appliquer à d'autres problèmes, y compris le problème du sac à dos que nous avons traité précédemment.

Conclusion

Aujourd'hui, vous avez ajouté une compétence cruciale à votre arsenal : la capacité de prouver formellement la correction d'un algorithme de programmation dynamique.

Points clés à retenir :

Une preuve de correction pour un algorithme de PD suit une structure en 5 étapes : définition des sous-problèmes, écriture de la récurrence, preuve de la récurrence, preuve de l'évaluation par l'algorithme, et preuve du résultat final.
Le cœur de la preuve est de justifier la relation de récurrence, souvent par un argument de type "couper-coller" (cut-and-paste) formalisé par une double inégalité ou une preuve par l'absurde.
La preuve que l'algorithme de tabulation calcule correctement la récurrence se fait par récurrence sur l'indice des sous-problèmes (par exemple, la taille du problème ou le nombre d'objets considérés).

Cette leçon conclut notre module sur la programmation dynamique. Vous avez appris à identifier les problèmes qui s'y prêtent, à formuler des relations de récurrence, à les implémenter (mémoïsation, tabulation) et, enfin, à prouver leur correction.

Dans notre prochaine leçon, nous aborderons un nouveau domaine fondamental de l'informatique théorique, essentiel pour l'Agrégation : les automates finis et les langages réguliers. Nous quitterons le monde de l'optimisation pour celui de la reconnaissance de motifs.

Recommended resources