La programmation dynamique

Pr. EL HADIQ Zouhair

CPGE MP/PSI — Informatique · Calculer chaque sous-problème une seule fois

1 / 12

Le problème de la récursivité naïveMOTIVATION

La suite de Fibonacci : $F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2}$.

def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)
Catastrophe. Le même sous-problème est recalculé des milliers de fois. Complexité exponentielle $O(\varphi^n)$ avec $\varphi\approx 1{,}618$. Pourtant il n'y a que $n+1$ valeurs distinctes !
2 / 12

L'idée centralePRINCIPE

« Ne jamais recalculer deux fois la même chose. » On mémorise le résultat de chaque sous-problème, et on le réutilise.

Pour Fibonacci, la complexité tombe de $O(\varphi^n)$ à $O(n)$.

Intérêt (programme officiel). La programmation dynamique sert à réduire la complexité temporelle de certains problèmes — souvent d'exponentielle à polynomiale.
3 / 12

Les deux ingrédientsCONDITIONS

1. Sous-structure optimale. La solution optimale se construit à partir des solutions optimales des sous-problèmes $\Rightarrow$ on peut écrire une formule de récurrence.
2. Chevauchement des sous-problèmes. Les mêmes sous-problèmes reviennent plusieurs fois $\Rightarrow$ la mémorisation est rentable.
PD vs diviser-pour-régner. Les deux découpent ; mais en « diviser pour régner » les sous-problèmes sont disjoints. La PD n'a d'intérêt qu'avec le chevauchement.
4 / 12

Lien avec les algorithmes gloutonsCOMPARAISON

GloutonProgrammation dynamique
Un seul choix, jamais remis en causeExamine tous les choix, garde le meilleur
RapidePlus coûteuse
Optimal parfoisToujours optimal
La PD résout exactement les problèmes où le glouton échoue — comme le sac à dos 0/1.
5 / 12

Top-Down : la mémoïsationAPPROCHE 1

Garder la récursion naturelle + un cache.

def fib_memo(n, memo={}): if n < 2: return n if n in memo: return memo[n] # réutilise memo[n] = fib_memo(n-1) + fib_memo(n-2) return memo[n]
= récursion + cache. On ne calcule que les sous-problèmes utiles. Attention à la profondeur de pile.
6 / 12

Bottom-Up : la tabulationAPPROCHE 2

Partir des plus petits sous-problèmes, remplir un tableau par des boucles.

def fib_tab(n): if n < 2: return n f = [0]*(n+1); f[1] = 1 for i in range(2, n+1): f[i] = f[i-1] + f[i-2] return f[n]
= boucles + tableau. Pas de récursion (pas de limite de pile) ; calcule tous les sous-problèmes ; il faut le bon ordre de remplissage.
7 / 12

Méthode généraleRECETTE

Le cœur du travail = trouver la récurrence :

  1. définir l'état (que désigne le sous-problème ?) ;
  2. écrire les cas de base ;
  3. exprimer un sous-problème en fonction de plus petits ;
  4. repérer la réponse finale.
Ensuite, au choix : mémoïsation (Top-Down) ou tabulation (Bottom-Up). Même résultat, même complexité.
8 / 12

Le sac à dos 0/1EXEMPLE

$n$ objets $(p_i,v_i)$, capacité $C$, objet pris en entier ou pas. $M(i,c)$ = valeur max avec les $i$ premiers objets et capacité $c$.

$$M(i,c)=\max\big(M(i{-}1,c),\ v_i+M(i{-}1,c{-}p_i)\big)$$ (si $p_i\le c$ ; sinon $M(i,c)=M(i{-}1,c)$).

Ne pas prendre vs prendre l'objet $i$. Complexité $O(nC)$ (pseudo-polynomiale).

Pour A(60,10), B(100,20), C(120,30), $C=50$ : la PD donne 220 (B+C), le glouton donnait 160.
9 / 12

Plus longue sous-séquence communeEXEMPLE

$L(i,j)$ = longueur de la PLSSC des $i$ premiers caractères de $X$ et $j$ premiers de $Y$.

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

Pour ABCBDAB et BDCAB : PLSSC = BCAB, longueur 4. Complexité $O(nm)$.

Utilisé par diff, Git, la bio-informatique.

10 / 12

Distance de LevenshteinEXEMPLE

Nombre minimal d'insertions / suppressions / substitutions pour transformer $X$ en $Y$. $D(i,j)$ sur les préfixes.

Si $X_i=Y_j$ : $D(i,j)=D(i{-}1,j{-}1)$. Sinon : $$D(i,j)=1+\min\big(D(i{-}1,j),\,D(i,j{-}1),\,D(i{-}1,j{-}1)\big)$$

= suppression, insertion, substitution. Complexité $O(nm)$. Base des correcteurs orthographiques.

11 / 12

À retenirBILAN

12 / 12