PROGRAMMATION
DYNAMIQUE
INTRODUCTION
La suite de Fibonacci est la suite d’entier définie
récursivement par :
0
1
∀ 2
# Python
def Fib(n) :
if n <= 1 :
return n
else :
return Fib(n-1) + Fib(n-2)
20XX PRESENTATION TITLE 2
INTRODUCTION
Calcule de Fibonacci de 6 :
Problème : Calcul répétitives de plusieurs valeurs. Complexité : O 2
20XX PRESENTATION TITLE 3
INTRODUCTION
Remarque :
• Les sous problèmes se chevauchent. (les uns dépend des autres)
• Si on optimise le calcul d’un terme de la suite de Fibonacci cela
conduira à l’optimisation du calcul des autres
20XX PRESENTATION TITLE 4
DEFINITION : PROGRAMMATION DYNAMIQUE
La programmation dynamique (PD) est une technique
algorithmique pour résoudre un problème d’optimisation
en le décomposant en sous-problèmes plus simples et en
utilisant le fait que la solution optimale au problème global
dépend de la solution optimale à ses sous-problèmes.
20XX PRESENTATION TITLE 5
PD : CARACTÉRISTIQUES
Les 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 : La programmation dynamique
est principalement utilisée lorsque des solutions des mêmes sous-problèmes
sont nécessaires à plusieurs reprises.
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.
20XX PRESENTATION TITLE 6
PD METHIODE 1 : 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.
20XX PRESENTATION TITLE 7
PD : APPROCHE TOP DOWN(MÉMOÏSATION)
memo = {}
def fibonacci (n):
if n < 2:
return n
if n not in memo :
memo [n] = fibonacci (n -1) + fibonacci (n -2)
return memo [n]
Chaque valeur calculée de la suite est mémoïser dans un
dictionnaire. Complexité O(n)
20XX PRESENTATION TITLE 8
PD METHIODE 2 : 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 (liste) à n
dimensions. Sur la base des résultats du tableau, la solution au
problème principal/d’origine est ensuite calculée.
20XX PRESENTATION TITLE 9
PD METHIODE 2 : TABULATION (BOTTOM-UP)
def fibonacci (n):
Fib = [0, 1]
for i in range (2,n+1):
Fib. append (Fib[i -1]+ Fib[i -2])
return Fib [ n]
Etant donnée les valeurs Fibonacci de 0 et 1, on calcule celle
de 2 puis 3,… jusqu’à n. Complexité O(n)
20XX PRESENTATION TITLE 10
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N
Trouver le nombre de façons d'atteindre l'escalier
numéro n en utilisant des pas de 1, 2 ou 3
Pour n = 3, la réponse est 4.
3=1+1+1 (1)
=1+2 (2)
=2+1 (3)
=3 (4)
20XX PRESENTATION TITLE 11
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N
Etant donné le système de S = {1, 2, 3} et un nombre n
à écrire.
1. Ecrire l’équation de récurrence qui donne le nombre
de façons d’écrire un nombre n dans le système S.
.... si n = 0
F(n) = .... si n < ...
.... sinon.
2. Ecrire la fonction naïve récursive F(n) permettant de
renvoyer le nombre de façons d’écrire n dans S = {1,
20XX
2, 3}. PRESENTATION TITLE 12
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N
1 si n = 0
F(n) = 1 si n < 3
F(n-1) + F(n-2) + F(n-3) sinon.
20XX PRESENTATION TITLE 13
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N
# Solution Naive
def F(n):
if n == 0 :
return 1
elif n <= 2 :
return n
return F(n -1) + F(n - 2) + F(n - 3)
20XX PRESENTATION TITLE 14
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N (TOP DOWN)
3- Ecrire une fonction récursive F_Top_down(n) qui
renvoie le nombre de façons d’écrire n dans le système S.
20XX PRESENTATION TITLE 15
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N (TOP DOWN)
cache = {}
def F_Top_down (n) :
if n == 0 :
return 1
elif n <= 2 :
return n
elif n not in cache :
cache [n] = F_Top_down(n -1) + F_Top_down(n - 2) +
F_Top_down(n - 3)
return cache [n]
20XX PRESENTATION TITLE 16
PD : NOMBRE DE FAÇONS D'ATTEINDRE
L'ESCALIER NUMÉRO N (BOTTOM UP)
4- Ecrire une fonction itérative F_Bottom_Up(n) qui
renvoie le nombre de façons d’écrire n dans le système S.
20XX PRESENTATION TITLE 17
PD : NOMBRE DE FAÇON POUR ÉCRIRE UN
NOMBRE (BOTTOM UP)
def F_Bottom_Up (n):
memoire = [1, 1, 2]
for i in range (3, n +1):
memoire.append( memoire [i - 1] + memoire [i - 2] +
memoire [i - 3] )
return memoire [n]
20XX PRESENTATION TITLE 18
PD : PROBLEME DU SAC À DOS (0/1)
Étant donné plusieurs objets possédant chacun un poids (pi) et
une valeur (vi) et étant donné un poids maximum pour le sac (P),
quels objets faut-il mettre dans le sac de manière à maximiser la
valeur totale sans dépasser le poids maximal autorisé pour le
sac?
max ∑ ∗! ) sous contrainte ∑ ∗" #
Avec ∈ %0,1' : 1 si l’objet est dans le sac, 0 sinon
20XX PRESENTATION TITLE 19
PD : PROBLEME DU SAC À DOS (0/1)
Objet Objet Objet Objet
Poids max du sac :
1 2 3 4
P=8
vi 1 2 5 7
Pi 2 3 4 5
Liste des objets
Le nombre des combinaisons possible est X1 x2 x3 x4
2( . Un algorithme qui va tester toutes 0 0 0 0
1 0 0 0
ces combinaisons prendra un temps 2( 0 1 0 0
exponentiel en fonction du nombre …
d’objets ( Pour n objets 2 ). d’où 1 1 1 1
l’intérêt d’utiliser la programmation Liste des possibilités
dynamique
20XX PRESENTATION TITLE 20
PD : PROBLEME DU SAC À DOS (0/1)
Soit ) * Le profit gagné pour remplir le poids j (+ # ) en considérant les
éléments de 0 à i.
o Si " > j, Ignorer cet article, alors, donc ) * = ) ,*
o Sinon, on a le choix de :
• Prendre l’article i, donc ) * = ! + ) ,* ,-
• Ignorer l’article i, donc ) * = ) ,*
./0 = max {1/ + ./ 2,0 3/ , ./ 2,0 }
20XX PRESENTATION TITLE 21
PD : PROBLEME DU SAC À DOS (0/1)
Poids
0 1 2 3 4 5 6 7 8
vi pi
0 0 0 0 0 0 0 0 0 0
Obj 1 1 2
1 0
Obj2 2 3
Objets
2 0
Obj3 5 4
3 0
Obj4 7 5
4 0
Le calcule de la valeur pour une
ligne i de la matrice exige la ./0 = max {1/ + ./ , ./ }
2,0 3/ 2,0
prise en compte de tout les
objets précédents (0 à i-1)
20XX PRESENTATION TITLE 22
PD : PROBLEME DU SAC À DOS (0/1)
Poids
0 1 2 3 4 5 6 7 8
vi pi
0 0 0 0 0 0 0 0 0 0
Obj 1 1 2
1 0 0 1 1 1 1 1 1 1
Obj2 2 3
Objets
2 0 0 1 2 2 3 3 3 3
Obj3 5 4
3 0 0 1 2 5 5 6 7 7
Obj4 7 5
4 0 0 1 2 5 7 7 8 9
Le calcule de la valeur pour une
ligne i de la matrice exige la ./0 = max {1/ + ./ , ./ }
2,0 3/ 2,0
prise en compte de tout les
objets précédents (0 à i-1)
20XX PRESENTATION TITLE 23
PD : ETAPES
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.
20XX PRESENTATION TITLE 24
