Aller au contenu

TD Rendu de Monnaie
& Algorithmes Gloutons⚓︎

Introduction au TD⚓︎

  • Le but de ce TD est de découvrir un problème classique, le Problème du Rendu de Monnaie,
  • et de saisir l'occasion de la résolution de ce problème, pour présenter une nouvelle Méthode/Heuristique de programmation, appellée l'Heuristique Gloutonne.
  • Les Algorithmes utilisant une Heuristique Gloutonne sont appelés des Algorithmes Gloutons.

Introduction au problème du Rendu de Monnaie⚓︎

  • On se donne un certain montant \(X\), à titre d'exemple considérons le montant de \(X=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, pour faire/rendre la monnaie sur \(X=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 précise de pièces correspondant à 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⚓︎

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 \euro\), \(10 \euro\), 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)\)
  • En outre, rien n'empêche d'imaginer des pays imaginaires, avec d'autres systèmes de pièces imaginaires

Heuristique Gloutonne pour le Rendu de Monnaie⚓︎

Pour faire/rendre la monnaie sur un certain montant \(X\), dans le système de pièces \(S\) envisagé, une méthode heuristique, simple et intuitive, est la suivante:

Heuristique Gloutonne ou 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: \(\quad S[i] \leq X\)
  2. Déduire cette pièce de la somme (restante)
  3. Tant que la somme n'est pas nulle, recommencer depuis l'étape \(1\)

    Info

    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.

Valeur de la solution vs Solution, 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. On dit que \(mini=4\) est la valeur de la solution au problème du rendu de monnaie. En effet:
  • la solution au problème du rendu de monnaie est 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\]

En Pratique⚓︎

En pratique, classiquement, dans les algorithmes gloutons, comme souvent en Optimisation :

  • on se concentre d'abord sur la détermination de la valeur de la solution,
  • puis, par la suite, ou quelquefois en même temps que la détermination de la valeur de la solution, on construit la solution

Notion d'Optimalité⚓︎

Cette méthode à heuristique gloutonne semble bien fonctionner, du moins dans le système Européen. On peut montrer en effet, que dans le Système de pièces Européen, l'algorithme glouton donne toujours une valeur de la solution optimale, càd que dans le Système de pièces Européen, l'algorithme glouton 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 dans un autre système de pièces?

Débranché : Rendu de monnaie au Pays Imaginaire de Groland⚓︎

Dans le pays imaginaire de Groland1, 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 (la valeur de la solution) sur \(X=39c\) dans le système de pièces de Groland?
  2. Quel serait alors le détail des pièces à rendre (la solution)?
  3. Expliquer pourquoi l'algorithme précédent à heuristique gloutonne n'est PAS optimal dans le système de pièces de Groland

Algorithme Glouton itératif pour le Rendu de Monnaie dans le système Européen⚓︎

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 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
  2. Combien de temps met cet algorithme pour rendre la monnaie sur \(33c\)?
  3. 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 précise des pièces sur un montant \(X\) choisi à l'avance
  4. En utilisant la librairie matplotlib, modifier l'algorithme itératif 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 5000\)
  5. Étudier la Complexité de cet algorithme glouton itératif de rendu de monnaie

(TNSI) Algorithme Glouton Récursif pour le Rendu de Monnaie dans le système Européen⚓︎

  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. Combien de temps met cet algorithme pour rendre la monnaie sur \(33c\)?
  3. 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
  4. En utilisant la librairie matplotlib, modifier l'algorithme récursif 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 5000\)
  5. Étudier la Complexité de cet algorithme glouton récursif de rendu de monnaie

Conclusion : Résumé de l'Algorithme Glouton pour le Rendu de Monnaie:⚓︎

Que peut-on dire de l'algorithme glouton de rendu de monnaie en ce qui concerne :

  • Sa difficulté de programmation/implémentation?
  • Sa Complexité en temps ?
  • Son Optimalité?

Notes⚓︎