Lycée > Terminale > NSI > Programmer de manière dynamique

Programmer de manière dynamique

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Comprendre la notion de programmation dynamique.
Programmer de manière dynamique.

Points clés

La programmation dynamique consiste à diviser le problème à résoudre en sous-problèmes et à stocker les résultats de ces sous-problèmes afin de reconstruire la solution du problème initial.
En programmation dynamique, le stockage des résultats intermédiaires permet d’optimiser la résolution du problème. Cette démarche s’appelle la mémoïsation.

Pour bien comprendre

Utiliser la récursivité en Python.
Résoudre un problème avec un algorithme glouton.
Utiliser la méthode « diviser pour régner ».

1. La programmation dynamique

a. Principe

La programmation dynamique consiste à diviser le problème à résoudre en plusieurs sous-problèmes dépendants. On combine les solutions de ces sous-problèmes pour obtenir une solution globale au problème initial.
La programmation dynamique est un principe algorithmique qui permet d’optimiser la résolution des problèmes.

En pratique, il s’agit de stocker les résultats des sous-problèmes au fur et à mesure pour éviter d’avoir à les résoudre plusieurs fois et les réutiliser facilement. Ce principe de stockage s’appelle la mémoïsation.

L’un des avantages de la programmation dynamique sur la méthode « diviser pour régner » vient de la mémoïsation. Chaque sous-problème n’est traité qu’une seule fois avec la programmation dynamique. Ce n’est pas forcément le cas avec la méthode « diviser pour régner ».

b. Exemple - Suite de Fibonacci

La suite de Fibonacci est la suite de nombres entiers :

1 – 1 – 2 – 3 – 5 – 8 – ...

En pratique, on obtient un élément de la suite en additionnant les deux termes précédents.

Par exemple, après 5 et 8, on obtient le nombre 13 car 5 + 8 = 13.

Programmation récursive

Cette suite peut naturellement être programmée récursivement. Par exemple, la fonction suivante fibo_rec(n) implémente le calcul du (n+1)-ème terme de la suite de Fibonacci avec la récursivité.

Python	Explication
def fibo_rec(n):	On définit la fonction fibo_rec.
if n < 2	Si n = 0 ou n = 1, alors
return 1	on retourne 1.
else:	Sinon
return fibo(n–1) + fibo(n–2)	on retourne la somme des deux termes précédents fibo(n).

Cette fonction est algorithmiquement correcte. En pratique, elle est cependant peu efficace puisque plusieurs valeurs de la suite sont calculées plusieurs fois.

Voici l’appel de cette fonction sur Python Tutor pour n = 10.

L’exécution de ce programme se fait en 710 étapes, ce qui est beaucoup.

Programmation dynamique

Pour optimiser le calcul des termes de la suite de Fibonacci, on peut utiliser la programmation dynamique.

On écrit pour cela la fonction suivante fibo_dyn(n), qui stocke au fur et à mesure les termes de la suite dans le tableau suite.

Python	Explication
def fibo_dyn(n):	On définit la fonction fibo_dyn
suite = [1]*(n+1)	On crée un tableau suite de taille n+1 qui ne contient que des 1.
for i in range(2, n+1):	Pour i qui va de 2 à n,
suite[i] = suite[i–1] + suite[i–2]	On affecte au (i+1)-ème élément du tableau suite la somme des deux termes précédents (i et i–1).
return suite[n]	on retourne le dernier élément du tableau suite.

Voici l’appel de cette fonction sur Python Tutor pour n = 10.

L’exécution de ce programme se fait en 25 étapes. L’approche dynamique avec mémoïsation optimise le calcul des termes de la suite de Fibonacci.

2. Programmer de manière dynamique - Le rendu de monnaie dynamique

a. Principe

Le problème du rendu de monnaie consiste, à partir d’un système monétaire, à rendre la monnaie sur une somme donnée avec le moins de pièces et de billets possible.

L’approche gloutonne de ce problème (vue en première) consiste à choisir à chaque étape la pièce ou le billet de plus grande valeur qui ne dépasse pas la somme restant à rendre. Cette méthode n’est pas optimale puisque l’on n’est pas certain d’avoir le moins de pièces et de billets possibles.

Exemple
Si on considère le système monétaire [1, 7, 8] et la somme 21 à rendre, l’approche gloutonne donnerait le rendu suivant avec 7 pièces/billets : 8 – 8 – 1 – 1 – 1 – 1 – 1.
Ce n’est pas une solution optimale puisque l’on pourrait rendre cette somme avec 7 – 7 – 7.

b. Premier rendu avec optimisation - Obtenir le nombre de pièces/billets nécessaires

Une première optimisation consiste à tout d’abord s'intéresser uniquement au nombre de pièces/billets pour le rendu.

Cette démarche est récursive :

Si la somme à rendre vaut 0, alors il faut 0 pièce/billet pour rendre la monnaie.
Si la somme à rendre est strictement supérieure à 0, alors le nombre de pièces pour le rendu optimal de cette somme est le minimum, pour chaque pièce/billet p du système monétaire, de la somme de 1 (qui correspond à la pièce/billet prise) et du nombre de pièces pour le rendu optimal de somme – p.

Exemple
Dans le système monétaire [1, 2, 3], on étudie la pièce/billet 2 pour une somme à rendre qui vaut 7. On a ici utilisé 1 pièce de 2, le nombre de pièces/billets à rendre vaut donc 1 + les autres pièces qui permettront de rendre 7 – 2 = 5.

En Python, cela donne la fonction nb_rendu(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.

Python	Explication
def nb_rendu(pieces, somme):	On définit la fonction nb_rendu.
if somme == 0: return 0	Si la somme est nulle, il faut 0 pièce/billet pour le rendu.
else:	Sinon,
nb_pieces = somme	on affecte somme à la variable nb_pieces (pire cas où le rendu ne se fait qu’avec des pièces de 1. S’il faut par exemple rendre 7, on aura nb_pieces = 7, ce qui signifie qu’il faut 7 pièces/billets de 1.)
for p in pieces:	Pour chaque pièce p dans le système monétaire pieces,
if p <= somme:	si p est inférieur à la somme qui est à rendre,
n = 1 + nb_rendu(pieces, somme–p)	on affecte à n (nombre intermédiaire de pièces) la somme de 1 et du rendu pour une somme de somme–p. (on a utilisé 1 pièce/billet, il ne reste donc plus qu’à rendre somme–p.)
nb_pieces = min(nb_pieces, n)	on affecte à la variable nb_pieces le minimum de n et de nb_pieces (pire cas où on ne rend que des pièces de 1). Ce minimum correspond au minimum de pièces recherchées.
return nb_pieces	Enfin, on retourne nb_pieces.

Exemple
Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 7.

L’exécution de ce programme renvoie 2. Ainsi il faut deux pièces pour rendre la monnaie sur une somme de 7. Néanmoins cela se fait en 662 étapes, ce qui est beaucoup, d’autant que le rendu se fait facilement avec 2 et 5.

c. Rendu de monnaie dynamique

Obtenir le nombre de pièces/billets nécessaires

Pour optimiser la fonction précédente, on peut stocker les rendus des sommes intermédiaires dans un tableau rendu.

En Python, cela donne la fonction nb_rendu_dyn(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.

Python	Explication
def nb_rendu_dyn(pieces, somme):	On définit la fonction.
rendu = [0]*(somme + 1)	On crée un tableau rendu de taille somme+1 qui ne contient que des 0. (On stocke le rendu d'un montant égale à 0 jusqu'à somme. Il y a donc somme+1 montants.)
for s in range(1, somme + 1):	Pour s allant de 1 à somme,
rendu[s] = s	on affecte s au (s+1)-ème élément du tableau rendu.
for p in pieces:	Pour chaque pièce p dans le système monétaire pièces,
if p <= s:	si la pièce/billet p est inférieure à la somme à rendre,
rendu[s] = min(rendu[s], 1 + rendu[s – p])	on affecte au (s+1)-ème élément du tableau rendu le minimum de rendu[s] et de 1 + rendu[s–p]. (on prend 1 pièce et on étudie le rendu sur le reste.)
return rendu[somme]	on retourne le dernier élément du tableau rendu (pour s qui vaut somme).

Exemple
Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 7.

On obtient le même résultat qu’avec la fonction précédente (il faut 2 pièces/billets pour rendre la somme 7), mais l’exécution de ce programme se fait en moins d’étapes (88 étapes).

Obtenir la liste des pièces/billets nécessaires

Il reste ensuite à finaliser cette fonction pour obtenir la liste des pièces/billets nécessaires pour faire le rendu optimal.

En Python, on crée la fonction rendu_dyn(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.

Cette fonction renvoie le tableau des pièces/billets utilisés pour le rendu.

Dans cette fonction, on stockera :

le nombre de pièces/billets des rendus intermédiaires dans le tableau rendu ;
et la liste des pièces/billets nécessaires à ces rendus dans le tableau solution.

Python	Explication
def rendu_dyn(pieces, somme):	On définit la fonction.
rendu = [0](somme + 1) solution = [[]](somme + 1)	On crée un tableau rendu de taille somme+1 qui ne contient que des 0. On crée également un tableau solution de taille somme+1 qui ne contient que des tableaux vides []. Ce tableau contiendra les pièces/billets nécessaires pour chaque rendu intermédiaire.
for s in range(1, somme + 1):	Pour s allant de 1 à somme,
rendu[s] = s solution[s] = [1]*s	on affecte s au (s+1)-ème élément du tableau rendu et [1]*s au (s+1)-ème élément du tableau solution.
for p in pieces:	Pour chaque pièce p dans le système monétaire pieces,
if p <= s:	si la pièce/billet p est inférieure à la somme à rendre,
if 1 + rendu[s–p] < rendu[s]:	si 1+rendu[s-p] est inférieur à rendu[s], alors
rendu[s] = 1 + rendu[s–p] solution[s] = solution[s–p]+[p]	On affecte 1+rendu[s–p] au (s+1)-ème élément du tableau rendu et on affecte solution[s–p]+[p] au (s+1)-ème élément du tableau solution. (si on prend la pièce p, on ajoute 1 à rendu et [p] aux pièces rendues)
return solution[somme]	on retourne le dernier élément du tableau rendu (pour s qui vaut somme)