CPGE MP / PSI · Informatique

Analyse des algorithmes de programmation dynamique

Pr. EL HADIQ Zouhair

Pour Fibonacci, le sac à dos 0/1, la PLSSC et Levenshtein : correction (invariant / récurrence sur les états), terminaison (variant, ordre de remplissage) et complexité (comptage des sous-problèmes).

📘 Cadre : correction totale

Un algorithme est correct (au sens total) s'il vérifie :

\[ \text{Correction totale} \;=\; \text{Correction partielle} \;+\; \text{Terminaison} \]

En programmation dynamique, la correction repose entièrement sur la relation de récurrence entre états. On prouve d'abord que cette récurrence est exacte (elle calcule bien la quantité voulue), puis que l'implémentation (mémoïsation ou tabulation) la remplit dans un ordre valide : chaque case n'est calculée qu'après les cases dont elle dépend.

🔑 Principe de la complexité. La force de la PD se mesure par un argument simple : \[ \text{coût total} \;=\; (\text{nombre d'états distincts}) \times (\text{coût d'un état}). \] Comme chaque état n'est calculé qu'une seule fois (mémorisation), on multiplie le nombre de cases du tableau par le travail fait pour remplir une case. C'est ce qui fait chuter la complexité par rapport à la récursion naïve, qui recalcule un même état un nombre exponentiel de fois.

1. Fibonacci — naïf contre programmation dynamique

📋 Spécification. Entrée : \(n \in \mathbb{N}\). Sortie : \(F_n\), où \(F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2}\).

1.1 — Pourquoi le naïf est exponentiel

Soit \(T(n)\) le nombre d'appels de fib(n) dans la version récursive sans cache. On a \(T(0)=T(1)=1\) et \(T(n)=T(n-1)+T(n-2)+1\). On reconnaît une récurrence « à la Fibonacci » :

T(n) = T(n-1) + T(n-2) + 1  >  F(n)
F(n) ~ φ^n / √5   avec   φ = (1+√5)/2 ≈ 1,618
⇒  T(n) = Θ(φ^n)   (exponentiel)
❌ Le défaut. L'arbre des appels contient un nombre exponentiel de nœuds, alors qu'il n'existe que \(n+1\) valeurs distinctes \(F_0,\dots,F_n\). Le chevauchement des sous-problèmes est massivement gaspillé.

1.2 — Correction de la version mémoïsée / tabulée

🟣 Invariant (tabulation). Dans fib_tab, avant l'itération d'indice \(i\) de la boucle, l'invariant est : \[ I(i):\quad \forall k < i,\ \ f[k] = F_k. \]

Initialisation. Avant \(i=2\), on a posé \(f[0]=0=F_0\) et \(f[1]=1=F_1\) : \(I(2)\) est vrai.

Conservation. Si \(I(i)\) est vrai, alors \(f[i-1]=F_{i-1}\) et \(f[i-2]=F_{i-2}\) sont déjà corrects (car \(i-1

Sortie. À la fin, \(i=n+1\) donc \(I(n+1)\) donne \(f[n]=F_n\). \(\blacksquare\)

🟢 Terminaison. La boucle for i in range(2, n+1) a un nombre d'itérations fixé \(n-1\) ; le variant \(V=(n+1)-i \in \mathbb{N}\) décroît strictement de 1 à chaque tour et l'ensemble \((\mathbb{N},<)\) est bien fondé. Pour la version mémoïsée, la mesure \(\mu = n\) décroît strictement à chaque appel récursif (on appelle \(n-1\) et \(n-2\)) et atteint le cas de base \(n<2\).
🔵 Complexité. \(n+1\) états, chacun calculé en \(O(1)\) : \[ T(n) = (n+1)\times O(1) = O(n) \quad\text{en temps},\qquad O(n)\ \text{en espace}. \] On passe de \(O(\varphi^n)\) à \(O(n)\) : c'est exactement « réduire la complexité temporelle ».

2. Sac à dos 0/1

📋 Spécification. Entrée : poids \((p_i)\), valeurs \((v_i)\) pour \(1\le i\le n\), capacité \(C\). Sortie : valeur totale maximale d'un sous-ensemble d'objets de poids total \(\le C\).

État : \(M(i,c)\) = valeur maximale en n'utilisant que les \(i\) premiers objets sous capacité \(c\). Récurrence :

\[ M(i,c)=\begin{cases} 0 & i=0\\[2pt] M(i-1,c) & p_i>c\\[2pt] \max\big(M(i-1,c),\ v_i+M(i-1,c-p_i)\big) & p_i\le c \end{cases} \]

🟣 Correction de la récurrence. On raisonne par récurrence sur \(i\) (nombre d'objets considérés).

Base \(i=0\) : sans aucun objet, la seule valeur atteignable est \(0\), donc \(M(0,c)=0\).

Hérédité : supposons \(M(i-1,\cdot)\) correct. Pour le \(i\)-ème objet, une solution optimale soit ne le contient pas (valeur \(M(i-1,c)\)), soit le contient — possible seulement si \(p_i\le c\) — auquel cas il reste une capacité \(c-p_i\) à remplir optimalement avec les \(i-1\) premiers objets (sous-structure optimale), d'où \(v_i+M(i-1,c-p_i)\). Le maximum des deux cas couvre toutes les solutions : \(M(i,c)\) est optimal. \(\blacksquare\)

🟢 Terminaison. Deux boucles for bornées (\(i\) de \(1\) à \(n\), \(c\) de \(0\) à \(C\)) : variant \(V=(n-i)\,(C+1)+(C-c)\in\mathbb{N}\) strictement décroissant. Ordre de remplissage valide : \(M(i,c)\) ne dépend que de la ligne \(i-1\), déjà entièrement calculée — la dépendance va du petit \(i\) vers le grand, donc la tabulation est cohérente.
🔵 Complexité. Tableau \((n+1)\times(C+1)\), chaque case en \(O(1)\) : \[ T = O(n\,C),\qquad \text{espace } O(n\,C). \]
⚠️ Pseudo-polynomial. \(O(nC)\) dépend de la valeur \(C\), pas seulement du nombre d'objets \(n\). En codant \(C\) en binaire, sa taille est \(\log_2 C\) bits : la complexité est exponentielle en la taille de l'entrée. C'est pourquoi le sac à dos 0/1 reste un problème \(\mathsf{NP}\text{-difficile}\), même si la PD le résout efficacement pour des \(C\) modérés.

3. Plus longue sous-séquence commune

📋 Spécification. Entrée : deux chaînes \(X\) (longueur \(n\)) et \(Y\) (longueur \(m\)). Sortie : longueur de la plus longue sous-séquence commune.

État \(L(i,j)\) = longueur de la PLSSC des préfixes \(X_{1..i}\) et \(Y_{1..j}\) :

\[ L(i,j)=\begin{cases} 0 & i=0 \text{ ou } j=0\\[2pt] L(i-1,j-1)+1 & X_i=Y_j\\[2pt] \max\big(L(i-1,j),\,L(i,j-1)\big) & X_i\neq Y_j \end{cases} \]

🟣 Correction. Récurrence sur \(i+j\).

Cas \(X_i=Y_j\) : il existe une PLSSC optimale qui apparie ces deux derniers caractères (sinon on pourrait l'allonger), donc \(L(i,j)=L(i-1,j-1)+1\).

Cas \(X_i\neq Y_j\) : les deux derniers caractères ne peuvent pas être appariés ensemble ; une PLSSC optimale ignore soit \(X_i\), soit \(Y_j\). On garde le meilleur des deux : \(\max(L(i-1,j),L(i,j-1))\). \(\blacksquare\)

🟢 Terminaison. Deux boucles bornées (\(n\times m\) itérations). \(L(i,j)\) ne dépend que de cases d'indices \((i',j')\) avec \(i'+j' < i+j\), toutes calculées avant : ordre de remplissage par lignes croissantes valide.
🔵 Complexité. \[ T=O(n\,m),\qquad \text{espace } O(n\,m). \] À comparer à l'approche naïve qui testerait les \(2^n\) sous-séquences de \(X\) : \(O(2^n m)\).

4. Distance de Levenshtein

📋 Spécification. Entrée : chaînes \(X\) (\(n\)) et \(Y\) (\(m\)). Sortie : nombre minimal d'insertions, suppressions et substitutions transformant \(X\) en \(Y\).

État \(D(i,j)\) = distance entre \(X_{1..i}\) et \(Y_{1..j}\) :

\[ D(i,j)=\begin{cases} i & j=0\\ j & i=0\\ D(i-1,j-1) & X_i=Y_j\\ 1+\min\big(D(i-1,j),\,D(i,j-1),\,D(i-1,j-1)\big) & X_i\neq Y_j \end{cases} \]

🟣 Correction. Récurrence sur \(i+j\). Les cas de base correspondent à « tout supprimer » (\(j=0\)) ou « tout insérer » (\(i=0\)). Pour le cas général, la dernière opération de la transformation optimale est forcément l'une des trois : supprimer \(X_i\) (\(D(i-1,j)+1\)), insérer \(Y_j\) (\(D(i,j-1)+1\)), ou substituer/laisser (\(D(i-1,j-1)+[X_i\neq Y_j]\)). Le minimum sur ces trois choix donne l'optimum. \(\blacksquare\)
🟢 Terminaison. Boucles bornées \(n\times m\) ; chaque \(D(i,j)\) dépend de cases déjà remplies (indices strictement inférieurs en somme). Aucun risque de boucle infinie.
🔵 Complexité. \[ T=O(n\,m),\qquad \text{espace } O(n\,m)\ \text{(réductible à } O(\min(n,m))\text{ en ne gardant que deux lignes).} \]

5. Synthèse

ProblèmeÉtatNb d'étatsCoût / étatComplexité
Fibonacci\(F(n)\)\(n+1\)\(O(1)\)\(O(n)\) vs \(O(\varphi^n)\)
Sac à dos 0/1\(M(i,c)\)\((n{+}1)(C{+}1)\)\(O(1)\)\(O(nC)\)
PLSSC\(L(i,j)\)\((n{+}1)(m{+}1)\)\(O(1)\)\(O(nm)\)
Levenshtein\(D(i,j)\)\((n{+}1)(m{+}1)\)\(O(1)\)\(O(nm)\)
✅ À retenir.

CPGE MP/PSI — Informatique · Analyse : programmation dynamique · Conforme au programme officiel 2023