Aller au contenu

% TD : Rendu de Monnaie &
Introduction à la Programmation Dynamique % Rodrigo SCHWENCKE, http://lyceeperier.fr

Avant-Propos :

  • Auteur: Rodrigo SCHWENCKE, Lycée PÉRIER
  • Thème (Bloc 5): Algorithmique Avancée
  • Référence du B.O., page 12: Contenus -> Programmation Dynamique. Plus précisément, commentaires -> les exemples de l'alignement de séquences ou de rendu de monnaie peuvent être présentés.
  • Licence :
  • Durée: 2 heures (et plus si affinités)
  • TD en Salle Informatique
  • Logiciels requis: un IDE (mon choix : OSS) + Python3. Matplotlib et Numpy sont utilisés pour le Tracé de Courbes.
  • Présupposés pédagogiques : Récursivité, Diviser pour Régner, Heuristique Gloutonne
  • Scénario Pédagogique proposé: Travail par groupe de 3 élèves

Introduction

  • Le but de ce TD est de présenter un nouveau paradigme de programmation autre que ceux de l'Heuristique Gloutonne, et que Diviser pour Régner, présupposés tous deux connus, et dont nous montrerons les limites.
  • Cette nouvelle méthode s'appellera la Programmation Dynamique.
  • Nous la mettrons en application sur un grand problème classique : le problème du Rendu de Monnaie:
  • On se donne un certain montant, à titre d'exemple considérons le montant de \(33\) centimes, sur lequel on souhaite rendre la monnaie, c'est à dire décomposer en somme de pièces de plus petite valeur.
  • Dans un premier temps, la question du Rendu de Monnaie, est de proposer un algorithme capable de déterminer le nombre minimal de pièces pour rendre la monnaie sur le montant choisi. Autrement dit, Combien de pièces au minimum faut-il, en rendant la monnaie sur \(33c\)? On dira que ce nombre minimal de pièces est la valeur de la solution au problème du rendu de monnaie.
  • Dans un deuxième temps, une amélioration qui semblera légitime et nécessaire, sera alors de déterminer également quelle est la répartition de pièces qui correspond à ce nombre minimal, précédemment trouvé. Mais à priori il s'agit d'une deuxième question qui se traite APRÈS, comme souvent en optimisation algorithmique. On dira que cette répartition de pièces est la solution au problème du rendu de monnaie.

Systèmes de pièces{.newpage}⚓︎

Le Système de Pièces Européen est \(S=(1,2,5,10,20,50,100,200)\) (en centimes).

Système de Pièces Europe

Notations :

  • Par la suite, le système \(S\) sera implémenté en Python dans un tuple.
  • \(S[i]\) désignera la \(i\)-ème pièce du système de pièces \(S\), avec \(0 \leq i \leq n\)
  • Ex : Dans le système Européen, \(S[0]=1\), \(S[1]=2\), \(S[2]=5\), \(S[3]=10\),etc...

Remarques :

  • Rien n'empêche d'imaginer que les billets de 5€, 10€, etc.. puissent être considérés comme des pièces (virtuelles) de 500 centimes, 1000 centimes, etc.. si besoin était.
  • PAS tous les pays n'ont le même système de pièces:
    e.g. pour les USA, \(S=(1,5,10,25,50,100)\)
  • Rien n'empêche d'imaginer des pays imaginaires, avec d'autres systèmes de pièces imaginaires

Approche Heuristique Gloutonne⚓︎

Pour rendre la monnaie sur un certain montant \(X\), dans le système de pièces \(S\) envisagé, une première méthode simple et intuitive,

Principe de l'Algorithme Glouton :
1. Choisir la plus grosse pièce de \(S\), parmi celles qui sont possibles:
\(\forall 0 \leq i \leq n\), on a: \(S[i] \leq X\)
2. Déduire cette pièce de la somme
3. tant que la somme n'est pas nulle, recommencer l'étape 1

Remarquons que cette méthode correspond bien à une Heuristique Gloutonne, car elle se résume à commencer par choisir systématiquement la plus grosse pièce possible.

Exemple:
Dans le système de pièces Européen :

  • le nombre minimal de pièces à rendre, pour la monnaie sur \(X=33\) centimes est mini = 4 pièces. \(mini=4\) est la valeur de la solution au problème du rendu de monnaie.
  • la solution au problème du rendu de monnaie, i.e. la répartition précise des pièces à rendre est : \(X= 33 c = 1 \times 20c + 1 \times 10c + 1 \times 2c + 1 \times 1c\)
  • Cette méthode à heuristique gloutonne semble bien fonctionner, du moins dans le système Européen. On montre en effet, que dans le système de pièces Européen, cette valeur de la solution est Optimale, i.e. qu'elle donne toujours le nombre minimal de pièces à rendre: il n'existe pas de meilleure valeur de la solution. On dit que le système de pièces Européen est canonique.
  • Mais qu'en serait-il si l'on était dans un autre système de pièces?

Exercice 1: Pays Imaginaire de Groland (Débranché)[ ]{.newpage}
Dans le pays imaginaire de Groland, disons qu'il existe des pièces imaginaires de \(13c\) en plus de celles du système de pièces Européen, donc le système de pièces de Groland est \(S=(1,2,5,10,13,20,50,100,200)\).

  1. Quel est le nombre minimal de pièces à rendre sur \(39c\) dans le système de pièces de Groland?
  2. Quel serait alors le détail des pièces à rendre?
  3. Expliquer pourquoi l'algorithme précédent à heuristique gloutonne n'est PAS optimal dans le système de pièces de Groland

Exercice 2:
On se donne un système de pièces (e.g. Européen, ou Groland) noté S:tuple , et un montant \(X:int\) dont on doit rendre la monnaie.

  1. Dans le langage de programmation Python, Proposer un algorithme glouton récursif contenant une fonction minPieces(S:tuple,X:int)->int qui renvoie le nombre minimal de pièces à rendre sur un montant \(X\) (en centimes, donc entier) choisi à l'avance. Cette fonction renvoie donc la valeur de la solution
  2. Dans le langage de programmation Python, Proposer un algorithme glouton itératif contenant une fonction minPieces(S:tuple,X:int)->int qui renvoie le nombre minimal de pièces à rendre sur un montant \(X\) (en centimes, donc entier) choisi à l'avance. Cette fonction renvoie donc la valeur de la solution
  3. Combien de temps mettent ces algorithmes pour rendre la monnaie sur \(33c\)?
  4. Modifier l'algorithme glouton récursif, pour qu'il renvoie également la solution du problème du rendu de monnaie, c'est à dire la répartition des pièces sur un montant \(X\) choisi à l'avance
  5. Modifier l'algorithme glouton itératif, pour qu'il renvoie également la solution du problème du rendu de monnaie, c'est à dire la répartition des pièces sur un montant \(X\) choisi à l'avance
  6. En utilisant les librairies matplotlib et numpy, modifier l'algorithme précédent (récursif, et/ou itératif) pour qu'il construise la courbe représentant la fonction Y(X:int)->float qui, à chaque montant entier \(X\) sur l'axe des abscisses dont on veut rendre la monnaie , associe sur l'axe des ordonnées la durée Y(X) , mise pour calculer le nombre minimal de pièces à rendre (pour le montant X). On veillera à prendre des valeurs de \(0 \leq X \leq 5000\)

Rappel de syntaxe Matplotlib + Numpy élémentaire: 

import numpy as np
import matplotlib.pyplot as plt

x = np.array([1, 3, 4, 6])
y = np.array([2, 3, 5, 3])
plt.plot(x, y, marker="+",markersize=7,markeredgecolor="r")

plt.show() # affiche la figure suivante a l'ecran

Ce code produit la courbe ci-contre, passant par les points \(A(1,2)\), \(B(3,3)\), \(C(4,5)\), \(D(6,3)\) :

  1. Conjecturer la Complexité de cet algorithme glouton (récursif et/ou itératif) de rendu de monnaie

Compléter le Résumé de l'Algorithme Glouton pour le Rendu de Monnaie:

  • Que peut-on dire de l'algorithme de rendu de monnaie à heuristique gloutonne en ce qui concerne :
  • Sa difficulté de réalisation? _____________________________________________
  • Sa Complexité ? ________________________________________________________

  • Son Optimalité? ________________________________________________________

  • Comment pourrait-on garantir qu'un algorithme renvoie la valeur de la solution Optimale dans le cas général, avec une bonne Complexité?
    C'est le but principal de tout ce qui suit.

Approche Récursive naïve/par force brute de type Diviser pour Régner{.newpage}⚓︎

Principe de l'algorithme :

  • On part du montant souhaité \(X\), dans le système de pièces choisi \(S\) (e.g. Groland), dont on veut rendre la monnaie
  • On répète récursivement les étapes suivantes:
  • Pour chacune des pièces \(x\) possibles (\(1 \leq x \leq X\)) du système (e.g. Groland), on simule un rendu de monnaie incluant cette pièce-là pour commencer. Et on ajoute +1 au nombre minimal mini de pièces à rendre, puisqu'on simule avoir déjà pris cette pièce \(x\) dans la simulation.
  • on calcule ensuite récursivement le nombre minimal de pièces pour le nouveau montant \(X-x\)
  • On conservera ensuite finalement, le nombre minimal parmi TOUTES les simulations/sous-problèmes engendrés par les situations précédentes
  • Résumé du raisonnement en une seule Formule de Récurrence :
\[ (*) \,\,\, minPieces(montant) = min \,\,\, de \left\{ \begin{array}{ll} \ 1+minPieces(montant-1) \\ \ 1+minPieces(montant-2) \\ \ 1+minPieces(montant-5) \\ \ 1+minPieces(montant-10) \\ \ 1+minPieces(montant-13) \\ \ 1+minPieces(montant-20) \\ \ 1+minPieces(montant-50) \\ \end{array} \right. \]

Exercice 3:
1. Justifier qu'il s'agit d'un algorithme récursif de type diviser pour régner, par force brute
2. Proposer une fonction minPieces(S:tuple,X:int)->int qui renvoie la quantité minimale de pièces dans le système S, pour rendre la monnaie sur un montant X (en centimes, donc un nombre entier). On pourra utiliser la Formule de Récurrence \((*)\)
3. En utilisant les librairies matplotlib et numpy, modifier l'algorithme précédent pour qu'il construise la courbe représentant la fonction Y(X:int)->float qui, à chaque montant entier \(X\) sur l'axe des abscisses dont on veut rendre la monnaie , associe sur l'axe des ordonnées la durée Y(X) , mise pour calculer le nombre minimal de pièces à rendre (pour le montant X). On veillera à prendre des valeurs de \(0 \leq X \leq 35\)
4. Que peut-on en dire des sous-problèmes du problème initial? sont-ils indépendants? ou pas? On pourra par exemple tracer l'arbre des appels récursifs pour le système \(S\) de Groland et la somme \(X=6\). 5. Est-ce bien ce à quoi on s'attendait pour un algorithme de type Diviser pour Régner?
6. Combien d'appels récursifs pour calculer le nombre minimal de pièces pour rendre la monnaie sur \(33c\)?
7. Complexité : Que pouvez vous dire ou intuiter de la Complexité de cet algorithme?
8. Optimalité : Que pouvez vous dire ou intuiter de l'Optimalité de cet algorithme?
9. Résumer ce que vous pouvez dire ou penser de l'algorithme précédent de type Diviser pour Régner Récursif, en ce qui concerne ses sous-problèmes, sa complexité en temps (resp. en mémoire), son optimalité.

Paradigme de la Programmation Dynamique :

La méthode de Programmation Dynamique consiste à :

  • prévenir/empêcher le RE-calcul des mêmes valeurs/des mêmes sous-problèmes, qui sont redondants et coûteux (en temps et en mémoire)
  • Pour permettre cela, l'idée principale de la Programmation Dynamique consiste à stocker quelque part les valeurs des sous-problèmes déjà calculés. Ainsi lorsque l'on aura besoin de nouveau de cette valeur /résultat de ce sous-problème:
  • on vérifie si on l'a déjà calculée, ou pas
  • Si on l'a déjà calculée, Alors on renvoie la valeur SANS NOUVEAU RE-CALCUL
  • Sinon, on CALCULE une première fois la valeur demandée, ET on la stocke parmi les valeurs déjà calculées (afin d'empêcher son RE-calcul futur)
  • En pratique, la Programmation Dynamique peut prendre deux formes:
  • Une forme Récursive appelé souvent Top Down
  • Une forme Itérative appelé souvent Bottom Up

Approche Dynamique Top Down⚓︎

On va adopter une technique de mémoïsation (terminologie officielle), encore appelée mémoire cache, ou plus simplement cache (terminologie usuelle).

Principe de la Programmation Dynamique Récursive Top Down

  • On se donne un système de pièces noté \(S\) (e.g. Groland), stocké dans un tuple
  • On se donne un montant \(X\) dont il faut rendre la monnaie
  • Au lieu de recalculer plusieurs fois les valeurs des solutions des mêmes sous-problèmes, pour chacun des montants \(x\) compris entre \(0\) et \(X\), nous allons mémoriser le nombre minimal de pièces à rendre sur \(x\) dans une mémoire \(cache\), implémentée en une liste unidimensionnelle Python:
  • On peut convenir que \(cache[0] = 0\)
  • On initialise la liste \(cache\) ainsi: \(cache[x]=0\) pour tout \(0 \leq x \leq X\)
  • et, pour tout \(0 \leq x \leq X\), l'entier stocké dans \(cache[x]\) représente :
    • le nombre minimal de pièces à rendre sur \(x\) lorsqu'on l'aura calculé
    • ou bien \(0\) s'il n'a jamais encore été calculé
  • Notez que le principe ici est de commencer à calculer les valeurs du \(cache\) pour \(X\), la valeur la plus grande (=> Top), et de calculer/descendre récursivement vers des sous-problèmes plus petits (=> Down), jusqu'à déterminer la valeur du \(cache\) pour \(0\). D'où le nom Top Down. On pourra encore utiliser la Formule de Récurrence \((*)\)
  • La valeur de la Solution au problème initial étant alors \(cache[X]\) (\(X\) majuscule...attention)

Algorithme Dynamique Récursif Top Down[ ]{.newpage}
On s'inspire directement de l'algorithme récursif Diviser pour Régner précédent du 3°) , donc on pourra encore utiliser la Formule de Récurrence \((*)\), à la seule différence que, pour chaque montant \(x\) entre \(0\) et \(X\), on commence par vérifier AVANT DE CALCULER le nombre minimal de pièces à rendre sur \(x\), qu'on ne l'a PAS DÉJÀ CALCULÉ et stocké dans le \(cache\):

  • Si \(x\) est déjà dans le \(cache\), c'est à dire que \(cache[x]\) ne vaut pas \(0\), Alors on renvoie cette valeur déjà stockée dans le cache, SANS LA RECALCULER
  • Sinon, si \(x\) n'est pas dans le \(cache\) (i.e. \(cache[x]\) est nul, i.e. n'a jamais été calculé), Alors:
  • On calcule récursivement \(minPieces\), le nombre minimal de pièces à rendre sur \(x\), comme dans l'algorithme précédent. On pourra encore utiliser la Formule de Récurrence \((*)\)
  • ET on stocke \(x\) dans le \(cache\): C'est à dire que \(cache[x] = minPieces\)

  • Notez également que l'algorithme est récursif, et que le \(cache\) doit être connu de toutes les fonctions appelées récursivement, donc cette variable DOIT être passée en paramètre de la fonction récursive minPieces(S:tuple,X:int,cache:list)->int

  • Exemple de résultats pour \(X=11c\) dans le Système Groland:

\(x\) 0 1 2 3 4 5 6 7 8 9 10 11
\(cache[x]\) 0 1 1 2 2 1 2 2 3 3 1 2

Exercice 4:

  1. Proposer un algorithme qui utilise la programmation dynamique récursive Top Down, contenant une liste cache à initialiser correctement et une fonction minPieces(X:int,S:tuple,cache:list)->int qui renvoie le nombre minimal de pièces à rendre sur un montant \(X\) dans un système de pièces \(S\) (Europe ou Groland). On pourra encore utiliser la Formule de Récurrence \((*)\)
  2. En utilisant les librairies matplotlib et numpy, modifier l'algorithme précédent pour qu'il construise la courbe représentant la fonction Y(X:int)->float qui, à chaque montant entier \(X\) sur l'axe des abscisses (dont on veut rendre la monnaie), associe sur l'axe des ordonnées la durée Y(X) , mise pour calculer le nombre minimal de pièces à rendre (pour le montant X). On veillera à prendre des valeurs de \(0 \leq X \leq 35\)
  3. Complexité : Que pouvez-vous dire ou intuiter sur la Complexité de cet algorithme?
  4. Que peut-on dire des sous-problèmes? sont-ils indépendants, ou pas? On pourra par exemple, tracer l'arbre d'appels récursifs pour \(X=6\)
  5. Optimalité : Que pouvez-vous dire ou intuiter sur l'Optimalité de cet algorithme?

Exercice 5: Sucre Syntaxique & Décorateurs en Python[ ]{.newpage}
(Avertissement : Difficulté 🚀🚀, Vous pouvez sereinement passer à la partie suivante s'il est trop difficile)
Un décorateur est une fonction qui modifie le comportement d'autres fonctions.

Exemple de Syntaxe: 

def monDecorateur(func):
    def wrapper(*args):
        # *args sont les arguments de la fonction 'func'
        # Actions qui modifient la fonction 'func'
        if args[0]%2 == 1:
            return func(args[0]*2,args[1])
        else:
            return func(*args)
    return wrapper

@monDecorateur
def somme(a,b):
  print("a+b=",a+b)

somme(1,6)

  1. Faites tourner ce code pour somme(1,6) puis somme(2,6), somme(3,6), somme (4,6)
  2. Que fait ce code? Testez-le!!
  3. Proposer un algorithme qui utilise la programmation dynamique Top Down, contenant un décorateur avecCache(func:function)->function à définir préalablement, et une fonction minPieces(X:int,S:tuple,cache:list)->int qui renvoie le nombre minimal de pièces à rendre sur un montant \(X\) dans un système de pièces \(S\) (Europe ou Groland). On pourra encore utiliser la Formule de Récurrence \((*)\)

Remarque :
Si vous rencontrez une erreur "RecursionError: maximum recursion depth exceeded in comparison", c'est que la pile d'appels récursifs de Python a été dépassée. Vous pouvez résoudre ce problème en ajoutant/adaptant ce snippet de code en haut de votre script:

import sys
sys.setrecursionlimit(5000)

Approche Dynamique Bottom Up{.newpage}⚓︎

On va de nouveau adopter une méthode de mémoire cache, comme dans le cas Top Down.

Principe de la Programmation Dynamique Itérative Bottom Up

  • On se donne un système de pièces noté \(S\) (e.g. Groland), stocké dans un tuple
  • On se donne un montant \(X\) dont il faut rendre la monnaie
  • Au lieu de recalculer plusieurs fois les valeurs des solutions des mêmes sous-problèmes, pour chacun des montants \(x\) compris entre \(0\) et \(X\), nous allons mémoriser le nombre minimal de pièces à rendre sur \(x\) dans une mémoire \(cache\), implémentée en une liste unidimensionnelle Python:
  • On peut convenir que \(cache[0] = 0\)
  • On initialise la liste \(cache\) ainsi: \(cache[x]=0\) pour tout \(0 \leq x \leq X\)
  • et, pour tout \(0 \leq x \leq X\), l'entier stocké dans \(cache[x]\) représente :
    • le nombre minimal de pièces à rendre sur \(x\) lorsqu'on l'aura calculé
    • ou bien \(0\) s'il n'a jamais encore été calculé
  • Notez que le principe ici est de commencer à calculer les valeurs du \(cache\) pour \(0\), la valeur la plus petite (=> Bottom), et de calculer/remonter itérativement vers des sous-problèmes plus grands (=> Up), jusqu'à déterminer la valeur du \(cache\) pour \(X\). D'où le nom Bottom Up.
  • On pourra néanmoins, encore utiliser la Formule de Récurrence \((*)\)
  • La valeur de la solution au problème initial étant alors \(cache[X]\) (\(X\) majuscule...attention)

Algorithme Dynamique Itératif Bottom Up
On s'inspire de certaines parties de l'algorithme récursif Top Down précédent du 4°) , mais cet algorithme est un peu différent des précédents, notamment:

  • Cette fois-ci l'algorithme est itératif, par exemple on pourra créer une boucle for qui parcourt toutes les valeurs \(x\) telles que \(1 \leq x \leq X\). On pourra néanmoins, encore utiliser la Formule de Récurrence \((*)\)

  • À la fin du \(x\)-ième tour, la boucle doit avoir calculé et mis en cache la valeur \(cache[x]\)

  • On peut donc initialiser la variable de \(cache\) directement à l'intérieur de la fonction minPieces, et que contrairement à l'algorithme Top Down, IL N'Y A AUCUN BESOIN de passer la variable \(cache\) en paramètre de la fonction récursive minPieces(S:tuple,X:int)->int

Exemple de résultats pour \(11c\) dans le Système Groland:

X 0 1 2 3 4 5 6 7 8 9 10 11
cache[X] 0 1 1 2 2 1 2 2 3 3 1 2

Exercice 6:[ ]{.newpage}

  1. Proposer un algorithme qui utilise la programmation dynamique itérative Bottom Up, contenant une liste cache à initialiser correctement et une fonction minPieces(X:int,S:tuple,cache:list)->int qui renvoie le nombre minimal de pièces à rendre sur un montant \(X\) dans un système de pièces \(S\) (Europe ou Groland).
  2. (Difficulté 🚀🚀) Modifier cet algorithme pour qu'il ne renvoie pas (seulement) la valeur de la solution (le nombre minimal de pièces à rendre sur \(X\)), mais également la solution au problème du rendu de monnaie (i.e. la répartition des pièces correspondant à ce nombre minimal de pièces).
  3. En utilisant les librairies matplotlib et numpy, modifier l'algorithme précédent pour qu'il construise la courbe représentant la fonction Y(X:int)->float qui, à chaque montant entier \(X\) sur l'axe des abscisses (dont on veut rendre la monnaie), associe sur l'axe des ordonnées la durée Y(X) , mise pour calculer le nombre minimal de pièces à rendre (pour le montant X). On veillera à prendre des valeurs de \(0 \leq X \leq 35\)
  4. Complexité : Que pouvez-vous dire ou intuiter sur la Complexité de cet algorithme?
  5. Que peut-on dire des sous-problèmes? sont-ils indépendants, ou pas?
  6. Optimalité : Que pouvez-vous dire ou intuiter sur l'Optimalité de cet algorithme?