Programmation Dynamique

EL KAMEL ZAKARIA

Aref Guelmim Oued-Noun

CPGE Lycée BAB SAHRA
zelkamel01@[Link]

Décembre 2024
Suite de Fibonacci

Considérons le calcul des nombres de Fibonacci :


1

si n < 2
Fn = 
Fn−1 + Fn−2 sinon

■ Exemple :

Pour n = 6, les 6 premiers nombres de la suite sont [1, 1, 2, 3, 5, 8] donc le

résultat est 8.
Suite de Fibonacci

■ Solution naïve : :

Une solution simple consiste à implémenter la fonction de manière récursive :

def fibonacci ( n ) :
if n <= 2: return 1
return fibonacci (n -1) + fibonacci (n -2)
Suite de Fibonacci

■ Solution naïve : :
Suite de Fibonacci

■ Meilleure solution ! :

On peut optimiser la solution précédente en évitant les calculs redondants.

def fibonacci (n , cache ) :

if n <= 2:
return 1
if n not in cache :
cache [ n ] = fibonacci (n -1) + fibonacci (n -2)
return cache [ n ]
Suite de Fibonacci

■ Meilleure solution ! :
Suite de Fibonacci

■ Une solution encore meilleure : :

Bien que le calcul récursif de la séquence de Fibonacci soit utile pour des raisons
pédagogiques, il est plus intuitif de la calculer de manière itérative en
commençant par les plus petits nombres, comme le ferait un être humain :

def fibonacci ( n ) :
if n >0:
Fib = [1 , 1]
for i in range (2 , n ) :
Fib . append ( Fib [i -1]+ Fib [i -2])

return Fib [n -1]

return None
Programmation dynamique

■ Défintion :

➠ La programmation dynamique est principalement une optimisation par

rapport à la récursivité simple.
➠ Partout où nous voyons une solution récursive qui a des appels répétés pour
les mêmes entrées, nous pouvons l’optimiser en utilisant la programmation
dynamique.
Programmation dynamique

■ Sous-structure optimale :

Un problème donné a une propriété de sous-structure optimale si une solution

optimale du problème donné peut être obtenue par des solutions optimales de ses
sous-problèmes.
Programmation dynamique

■ Sous-structure optimale : Exemple

Considérons le problème de trouver le chemin le plus court pour voyager entre

deux villes en voiture. Une personne veut conduire de la ville A à la ville C, la
ville B se situe entre les deux villes.
Programmation dynamique

■ Sous-structure optimale : Exemple

❏ En bref, cela signifie que nous pouvons écrire une formule récursive pour une
solution au problème de la recherche du chemin le plus court.
❏ Nous disons que le problème de la recherche de la route la plus courte entre
deux villes démontre la propriété de sous-structure optimale.
Programmation dynamique

■ Utilisation en programmation dynamique :

❏ L’écriture d’une formule récursive ou la définition de la sous-structure

optimale est la première étape vers la programmation dynamique.
❏ La logique de la programmation dynamique vient généralement de la
récursivité. La solution du problème est dérivée de la solution des
sous-problèmes, la solution des sous-problèmes est dérivée de la solution des
sous-sous-problèmes et ainsi de suite.
Programmation dynamique

■ Caractéristiques de la programmation dynamique :

Voici les deux propriétés principales d’un problème suggérant qu’il peut être
résolu à l’aide de la programmation dynamique :

❏ Chevauchement de sous-problèmes.
❏ Sous-structure optimale.
Programmation dynamique

■ Méthode de programmation dynamique :

La programmation dynamique évite de résoudre plusieurs fois le même

sous-problème en réutilisant la solution stockée à ce sous-problème.

❏ Mémoïsation (Top-down)
❏ Tabulation (Bottom-up)
Méthode de programmation dynamique

■ Mémoïsation (Top-down) :

❏ Résoudre le problème principal en trouvant récursivement la solution de ses

petits sous-problèmes.
❏ Une fois qu’un sous-problème est résolu, il est mis en cache afin que nous
n’ayons pas besoin de le résoudre à nouveau en cas de besoin.
Méthode de programmation dynamique

■ Mémoïsation (Top-down) : Suite de Fibonacci

def fibonacci (n , cache ) :

if n <= 2:
return 1
if n not in cache :
cache [ n ] = fibonacci (n -1) + fibonacci (n -2)
return cache [ n ]
Méthode de programmation dynamique

■ Tabulation (Bottom-up) :

❏ La tabulation est à l’opposé de l’approche Mémoïsation et évite la

récursivité.
❏ Résoudre d’abord tous les sous-problèmes connexes.
❏ Cela se fait généralement en remplissant un tableau à n dimensions. Sur la
base des résultats du tableau, la solution au problème principal/d’origine est
ensuite calculée.
Méthode de programmation dynamique

■ Tabulation (Bottom-up) : Suite de Fibonacci

def fibonacci ( n ) :
if n >0:
Fib = [1 , 1]
for i in range (2 , n ) :
Fib . append ( Fib [i -1]+ Fib [i -2])

return Fib [n -1]

return None
Méthode de programmation dynamique

■ Bottom up vs Top-down :

❏ Si le problème initial nécessite la résolution de tous les sous-problèmes, la

tabulation est généralement plus performante que la mémoïsation par un
facteur constant.
❏ Si seulement certains des sous-problèmes doivent être résolus pour que le
problème initial soit résolu, la mémoïsation est préférable.
Programmation dynamique

■ Etapes de la programmation dynamique :

➠ Caractériser la structure d’une solution optimale.

➠ Définir la valeur de la solution optimale de manière récursive.
➠ Calculer les valeurs de la solution optimale soit de manière descendante
(Top-down) avec mise en cache, soit de manière ascendante (Bottom-up)
dans un tableau.
➠ Construire une solution optimale à partir des valeurs calculées.
Méthode de programmation dynamique

■ Catégories de problèmes résolus par DP :

❏ Problèmes combinatoires : DP est utilisé pour compter ou énumérer le

nombre de façons d’atteindre un objectif.
❏ Problèmes d’optimisation : DP est souvent utilisé pour trouver la solution
optimale (configuration maximale, minimale ou optimale).
❏ Alignement et correspondance de séquences : DP est utilisé pour aligner ou
comparer des séquences.
Méthode de programmation dynamique

■ Catégories de problèmes résolus par DP :

❏ Problèmes de partitionnement : DP est utilisé pour partitionner les données

en groupes significatifs avec des contraintes.
❏ Problèmes de graphes : DP est utilisé pour résoudre des problèmes liés aux
graphes où la récursivité peut être appliquée.
❏ Problèmes de recherche de chemin : DP est souvent utilisé dans les
problèmes de recherche de chemin basés sur une grille.
Nombre de façons d’écrire un nombre

Étant donné un entier n ≥ 0, déterminez le nombre de façons distinctes

d’exprimer n comme une somme de nombres appartenant à l’ensemble {1, 3, 4}.
☛ Exemple :

Pour n=5, la réponse est 6.

5=1+1+1+1+1
=1+1+3
=1+3+1
=3+1+1
=1+4
=4+1
Nombre de façons d’écrire un nombre

■ Caractériser la structure d’une solution optimale :

Soit Fn le nombre de façons d’écrire n comme la somme de 1, 3, 4.

n = x1 + x2 + · · · + xm

❏ Si xm = 1, La somme des autres termes doit être égale à n − 1.

❏ Ainsi, le nombre de sommes qui se terminent par xm = 1 est égal à Fn−1
❏ Prendre en compte les autres cas (xm = 3 , xm = 4)
Nombre de façons d’écrire un nombre

■ Définir la valeur de la solution optimale de manière récursive. :

Soit Fn le nombre de façons d’écrire n comme la somme de 1, 3, 4.

Fn = Fn−1 + Fn−3 + Fn−4

les cas de base :

➥ Fn = 0, pour n < 0,
➥ F0 = 1
➥ F1 = 1
➥ F2 = 1
Nombre de façons d’écrire un nombre

■ Solution récursive :

def nbFacons ( n ) :
if n < 0:
return 0
elif n < 3:
return 1
else :
return nbFacons (n -1) + nbFacons (n -3) + nbFacons (n -4)
Nombre de façons d’écrire un nombre

■ Solution récursive :
Nombre de façons d’écrire un nombre

■ Solution Top-down :

def nbFacons (n , cache ) :

if n < 0:
return 0
elif n < 3:
return 1
else :
if n not in cache :
cache [ n ] = nbFacons (n -1 , cache ) + nbFacons (n -3 , cache )
+ nbFacons (n -4 , cache )
return cache [ n ]
Nombre de façons d’écrire un nombre

■ Solution Bottom-up :

def nbFacons ( n ) :
if n >=0:
F = [1 , 1 , 1]
for i in range (3 , n +1) :
F . append ( F [i -1]+ F [i -3]+ F [i -4])

return F [ n ]
return None
Appariement d’amis

Etant donné N étudiants dans un atelier, chacun peut travailler seul ou peut être
jumelé avec un autre étudiant. Chacun peut être jumelé qu’une fois. Découvrez le
nombre total de façons de séparer les étudiants dans cet atelier.
■ Exemple :

Pour n=4 étudiants, il peut y avoir 10 façons de séparer les étudiants.

Appariement d’amis

■ Exemple :
Appariement d’amis

■ Formule récursive :


1,

si 0 ≤ i < 2
nbFacons(i) = 
nbFacons(i − 1) + (i − 1) · nbFacons(i − 2), sinon
Problème de carrelage

Soit un sol de taille n x m et des carreaux de taille 1 x m. Le problème est de

compter le nombre de façons de carreler le sol donné en utilisant des carreaux de
taille 1 x m. ■ Exemple :
Problème de carrelage

■ Formule récursive :






 1, si n < m

NB(n) = 2, si n = m



NB(n − 1) + NB(n − m), sinon


Plus longue sous-chaîne commune

Étant donné deux chaînes de caractères (séquences) X et Y, trouver la plus

longue sous-séquence commune (LCS) et afficher sa longueur.
❏ Une sous-séquence est une séquence qui apparaît dans le même ordre relatif,
mais pas nécessairement contiguë.
☛ Exemple :
Plus longue sous-chaîne commune

■ Caractériser la structure d’une solution optimale :

Soit LCSi,j la longueur du LCS de X1...i et Y1...j

❏ Si Xi = Yj , ils contribuent tous les deux au LCS, donc
LCSi,j = 1 + LCSi−1,j−1
❏ Sinon, Xi ou Yi ne contribuent pas au LCS, donc un peut être supprimé :
LCSi,j = max (LCSi−1,j , LCSi,j−1 )
Les cas de base :
❏ LCSi,0 = LCS0,j = 0
Plus longue sous-chaîne commune

■ Solution récursive :

def lcs (X , Y , i , j ) :
if i == 0 or j == 0:
return 0
elif X [i -1] == Y [j -1]:
return 1 + lcs (X , Y , i -1 , j -1)
else :
return max ( lcs (X , Y , i , j -1) , lcs (X , Y , i -1 , j ) )
Plus longue sous-chaîne commune

■ Solution récursive :
Plus longue sous-chaîne commune

■ Solution Top-down :

def lcs (X , Y , m , n , cache ) :

if ( m == 0 or n == 0) :
return 0
if (m , n ) in cache :
return cache [( m , n ) ]
if X [ m - 1] == Y [ n - 1]:
cache [( m , n ) ] = 1 + lcs (X , Y , m - 1 , n - 1 , cache )
return cache [( m , n ) ]
cache [( m , n ) ] = max ( lcs (X , Y , m , n - 1 , cache ) ,
lcs (X , Y , m - 1 , n , cache ) )
return cache [( m , n ) ]
Plus longue sous-chaîne commune

■ Solution Bottom-up :
Plus longue sous-chaîne commune

■ Solution Bottom-up :
Plus longue sous-chaîne commune

■ Solution Bottom-up :

def lcs ( X , Y , m , n ) :
L = [[ None ]*( n +1) for i in range ( m +1) ]
for i in range ( m +1) :
for j in range ( n +1) :
if i == 0 or j == 0 :
L [ i ][ j ] = 0
elif X [i -1] == Y [j -1]:
L [ i ][ j ] = L [i -1][ j -1]+1
else :
L [ i ][ j ] = max ( L [i -1][ j ] , L [ i ][ j -1])

return L [ m ][ n ]
Distance d’édition (Levenshtein)

Étant donné deux chaînes de caractères X (Taille m) et Y (Taille n) et les

opérations ci-dessous qui peuvent être effectuées sur X .
➥ Insérer
➥ Retirer
➥ Remplacer
Toutes les opérations ci-dessus ont un coût égal.

Trouvez le nombre minimum de modifications (opérations) requises pour

convertir X en Y .
Distance d’édition (Levenshtein)

☛ Exemple :
Distance d’édition (Levenshtein)

☛ Exemple :
Distance d’édition (Levenshtein)

☛ Etudes de cas :
Distance d’édition (Levenshtein)

☛ Etudes de cas :
Distance d’édition (Levenshtein)

☛ Etudes de cas : Insérer

Distance d’édition (Levenshtein)

☛ Etudes de cas : Remplacer

Distance d’édition (Levenshtein)

☛ Etudes de cas : Retirer

Distance d’édition (Levenshtein)

■ Caractériser la structure d’une solution optimale :

Soit Di,j la distance minimale pour convertir X1...i en Y1...j


Di−1,j−1 ,

si X [i] = Y [j]
Di,j =
1 + min(Di−1,j−1 , Di−1,j , Di,j−1 ),

sinon

Avec Di,0 = i, et D0,j = j

Distance d’édition (Levenshtein)

■ Solution récursive :

def Distance (X , Y , m , n ) :
if m == 0:
return n
if n == 0:
return m
if X [m -1] == Y [n -1]:
return Distance (X , Y , m -1 , n -1)
return 1 + min ( Distance (X , Y , m , n -1) , # Inserer
Distance (X , Y , m -1 , n ) , # Retirer
Distance (X , Y , m -1 , n -1) # Remplacer
Distance d’édition (Levenshtein)

■ Solution récursive :
Distance d’édition (Levenshtein)

■ Solution Top-down :

def Distance (X , Y , m , n , cache ) :

if ( n == 0) : return m
if ( m == 0) : return n
if cache [ m ][ n ] != -1 : return cache [ m ][ n ]
if ( X [ m - 1] == Y [ n - 1]) :
cache [ m ][ n ] = Distance (X , Y , m - 1 , n - 1 , cache )
else :
if cache [ m - 1][ n ] == -1:
cache [ m - 1][ n ] = Distance (X , Y , m - 1 , n , cache )
if cache [ m ][ n - 1] == -1:
cache [ m ][ n - 1] = Distance (X , Y , m , n - 1 , cache )
if cache [ m - 1][ n - 1] == -1:
cache [ m - 1][ n - 1] = Distance (X , Y , m - 1 , n - 1 , cache )
cache [ m ][ n ] = 1 + min ( cache [ m - 1][ n ] , cache [ m ][ n - 1] ,
cache [ m - 1][ n - 1])
return cache [ m ][ n ]
Distance d’édition (Levenshtein)

■ Solution Bottom-up :
Distance d’édition (Levenshtein)

■ Solution Bottom-up :
Distance d’édition (Levenshtein)

■ Solution Bottom-up :

def Distance (X , Y , n , m ) :
D = [[0 for x in range ( m + 1) ] for x in range ( n + 1) ]
for i in range ( n + 1) :
for j in range ( m + 1) :
if i == 0: D [ i ][ j ] = j
elif j == 0: D [ i ][ j ] = i
elif X [i -1] == Y [j -1]:
D [ i ][ j ] = D [i -1][ j -1]
else :
D [ i ][ j ] = 1 + min ( D [ i ][ j -1] , # Inserer
D [i -1][ j ] , # Retirer
D [i -1][ j -1]) # Remplacer
return D [ n ][ m ]
Problème de sac à dos

On considère :
❏ n objets, chacun caractérisé par :
➠ Un poids pi (entier positif),
➠ Un profit vi (entier positif),
❏ Un sac à dos avec une capacité maximale de poids W .

L’objectif est de sélectionner un sous-ensemble des objets pour maximiser la

valeur totale (profit) placée dans le sac, tout en respectant la contrainte de poids.
Problème de sac à dos

■ Exemple :
Problème de sac à dos

■ Etudes de cas :
Problème de sac à dos

■ Etudes de cas :
Problème de sac à dos

☛ Méthode exhaustive :
Problème de sac à dos

☛ Méthode exhaustive :
Problème de sac à dos

■ Variables de décision :

Définir une variable binaire xi pour chaque objet i


1,

si l’objet i est inclus dans le sac dos
xi = 
0, sinon

Maximiser la valeur totale des objets sélectionnés :

n
X
Maximiser Z = vi xi
i=1
Problème de sac à dos

■ Caractériser la structure d’une solution optimale :

Soit Zi,j Le profit gagné pour remplir le poids j en considérant les articles 0 . . . i :

➥ Si pi > j, Ignorer cet article, alors, donc Zi,j = Zi−1,j

➥ Sinon, on a le choix de :
➠ Prendre l’article i, donc Zi,j = vi + Zi−1,j−pi
➠ Ignorer l’article i, donc Zi,j = Zi−1,j

Zi,j = max (vi + Zi−1,j−pi , Zi−1,j )

Les cas de base : Zi,0 = Z0,j = 0
Problème de sac à dos

☛ Solution récursive :

def sac_rec ( articles , W , n ) :

if n == 0 or W == 0:
return 0

if articles [ n - 1][0] > W :

return sac_rec ( articles , W , n - 1)

include = articles [ n - 1][1] +

sac_rec ( articles , W - articles [ n - 1][0] , n - 1)
exclude = sac_rec ( articles , W , n - 1)
return max ( include , exclude )
Problème de sac à dos

☛ Solution Top-down :

def sac_top ( articles , W , n , cache ) :

if n == 0 or W == 0:
return 0

if (n , W ) in cache :
return cache [( n , W ) ]

if articles [ n - 1][0] > W :

cache [( n , W ) ]= sac_rec ( articles , W , n - 1)
return cache [( n , W ) ]

include = articles [ n - 1][1] +

sac_rec ( articles , W - articles [ n - 1][0] , n - 1)
exclude = sac_rec ( articles , W , n - 1)
cache [( n , W ) ]= max ( include , exclude )
return cache [( n , W ) ]
Problème de sac à dos

☛ Solution Bottom-up :
Problème de sac à dos

☛ Solution Bottom-up :
Problème de sac à dos

☛ Solution Bottom-up :

def sac_bottom ( articles , W , n ) :

n = len ( articles )
dp = [[0 for _ in range ( W + 1) ] for _ in range ( n + 1) ]
for i in range (1 , n + 1) :
for w in range (1 , W + 1) :
if articles [ i - 1][0] <= w :
dp [ i ][ w ] = max (
articles [ i - 1][1] + dp [ i - 1][ w - articles [ i - 1][0]] ,
dp [ i - 1][ w ]
)
else :
dp [ i ][ w ] = dp [ i - 1][ w ]

return dp [ n ][ W ]