Corrigé : 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 des 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).
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⚓︎
- 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\) - Déduire cette pièce de la somme (restante)
-
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
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)\).
-
Quel est le nombre minimal de pièces à rendre sur \(X=39c\) dans le système de pièces de Groland?
Corr
Dans le Système de Groland, le minimum de pièces à rendre sur \(39c\) est \(3\) pièces
-
Quel serait alors le détail des pièces à rendre?
Corr
En effet, \(X = 39c = 13c + 13c + 13c\) donc seulement \(3\) pièces suffisent.
-
Expliquer pourquoi l'algorithme précédent à heuristique gloutonne n'est PAS optimal dans le système de pièces de Groland
Corr
L'algorithme glouton donne la répartition \(X = 39c = 20c + 13c + 5c + 1c\).
Cet algorithme glouton renvoie une solution à \(4\) pièces: il n'est donc PAS Optimal dans le système 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.
-
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 doncla valeur de la solution Corr
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
import time # VALEUR DE LA SOLUTION DE L'ALGORITHME GLOUTON ITÉRATIF def minPieces(S:tuple,X:int)->int: if X==0: return 0 else: mini=0 while X>0: for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] X-=plusGrosse mini+=1 return mini S=(1,2,5,10,13,20,50,100,200) X=33 count = 0 start=time.process_time() m = minPieces(S,X) stop=time.process_time() t = stop - start print("Nombre min de pièces, m=",m,"en t= ",t,"sec")
-
Combien de temps met cet algorithme pour rendre la monnaie sur \(33c\)?
Corr
Sur mon ordinateur, l'algorithme Glouton Itératif met: \(1,24 \times 10^{-5}\) sec
-
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'avanceCorr
Le script est "Corrigé->partieII->ex2IteratifEtSolution.py"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
import time # SOLUTION + VALEUR DE LA SOLUTION DE L'ALGORITHME GLOUTON ITÉRATIF def minPieces(S:tuple,X:int)->int: L=[] if X==0: return 0 else: mini=0 while X>0: for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] L.append(plusGrosse) X-=plusGrosse mini+=1 return mini,L S=(1,2,5,10,13,20,50,100,200) X=67 start = time.process_time() m, L = minPieces(S,X) stop = time.process_time() t = stop - start print("Nombre min de pièces, m=",m,"en t= ",t,"sec") print("Répartition, Pour X= ",X," L = ",L)
-
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éeY(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\)Corr
Le script suivant est "Corrigé->partieII->ex2IteratifMatplotlib.py"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
import time import matplotlib.pyplot as plt # FIGURE MATPLOTLIB DE L'ALGORITHME GLOUTON ITÉRATIF def minPieces(S:tuple,X:int)->int: if X==0: return 0 else: mini=0 while X>0: for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] X-=plusGrosse mini+=1 return mini S=(1,2,5,10,13,20,50,100,200) X=[i for i in range(5000)] Y = [] for x in X: start=time.process_time() m = minPieces(S,x) stop=time.process_time() t = stop - start Y.append(t) plt.title("Algorithme Glouton Itératif") plt.xlabel('montant X à rendre') plt.ylabel('Temps') plt.plot(X, Y, marker="+",markersize=7,markeredgecolor="r") plt.show() # affiche la figure a l'ecran
Algorithme Glouton Itératif du Rendu de Monnaie -
Étudier la Complexité de cet algorithme glouton itératif de rendu de monnaie
Corr
Commençons par remarquer qu'un algorithme de rendu de monnaie a deux données en entrée:
- la somme à rendre \(X\)
- le système de pièces \(S\)
La Complexité de l'algorithme de rendu de monnaie dépend donc de la taille de ces \(2\) paramètres:
-
de la taille de l'entier \(X\):
Rappel / Définition
Si une donnée \(X\) est un nombre entier, Alors sa taille est le nombre de chiffres (\(0\) et \(1\)) de son écriture binaire. Autrement dit :
Lataille d'un nombre entier \(X\) (donné en entrée) est de l'ordre du Logarithme Binaire de sa valeur :
\(\quad taille(X)=\left\lceil log_2 (X)+1 \right\rceil\)) \(\,\, \approx log_2(X)\)
De plus, on sait que: \(X = 2^{log_{2} (X))}\), donc un entier \(X\) est exponentiel en sa taille \(log_2 (X)\)... -
de la taille du système de pièces, noté \(n\)
Ces notations seront préservées dans toute la suite du Corrigé
Étudions maintenant en détail la complexité de l'algorithme glouton itératif du Rendu de Monnaie:1 2 3 4 5 6 7 8 9 10 11 12
def minPieces(S:tuple,X:int)->int: if X==0: return 0 else: mini=0 while X>0: for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] X-=plusGrosse mini+=1 return mini
- Les lignes de \(1\) à la \(5\) sont en \(O(1)\)
- il y a deux boucles imbriquées, chaque ligne inclue dans ces boucles est en \(O(1)\)
- Dans la boucle
while X>0
, il y a \(X\) tours dans le pire des cas (où on enlève des pièces de \(1c\) systématiquement). (on pourrait sûrement faire mieux ici, mais c'est déjà suffisant pour la suite de la réponse) - Dans la boucle
for
, il y \(n\) tours - donc la Complexité de cet algorithme est, dans le pire des cas, de l'ordre de grandeur de \(n \times X = n2^{log_2(X)}=n2^{\text{Taille de } X}\), càd en \(O(2^{\text{Taille de } X})\)
Conclusion : D'après ce qui précède, la complexité est donc Exponentielle en la taille de \(X\)
(TNSI) Algorithme Glouton Récursif pour le Rendu de Monnaie dans le système Européen⚓︎
-
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 doncla valeur de la solution Corr
Pour cette question, il s'agit du fichier "Corrigé->partieII->ex2Recursif.py"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
import time # ALGORITHME GLOUTON RÉCURSIF def minPieces(S:tuple,X:int)->int: global mini if X==0: return 0 else: mini+=1 for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] minPieces(S,X-plusGrosse) return mini S=(1,2,5,10,13,20,50,100,200) X=33 mini=0 start=time.process_time() m = minPieces(S,X) stop=time.process_time() t = stop - start print("Nombre min de pièces, m=",m,"en t= ",t,"sec")
-
Combien de temps met cet algorithme pour rendre la monnaie sur \(33c\)?
Corr
Sur mon ordinateur, l'algorithme glouton Récursif met: \(9,9 \times 10^{-6}\) sec
-
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'avanceCorr
Le script est "Corrigé->partieII->ex2RecursifEtSolution.py"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
import time # SOLUTION DE L'ALGORITHME GLOUTON RÉCURSIF def minPieces(S:tuple,X:int,L:list)->int: global mini if X==0: return 0 else: mini+=1 for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] L.append(plusGrosse) minPieces(S,X-plusGrosse,L) return mini,L L=[] S=(1,2,5,10,13,20,50,100,200) X=67 mini=0 start=time.process_time() m, L = minPieces(S,X,L) stop=time.process_time() t = stop - start print("Nombre min de pièces, m=",m,"en t= ",t,"sec") print("Répartiion, Pour X= ",X," L = ",L)
-
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éeY(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\)Corr
Voici un script qui convient par exemple:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
import time import matplotlib.pyplot as plt # FIGURE MATPLOTLIB DE L'ALGORITHME GLOUTON RÉCURSIF def minPieces(S:tuple,X:int)->int: global mini if X==0: return 0 else: mini+=1 for i in range(len(S)): if S[i]<=X: plusGrosse = S[i] # L.append(plusGrosse) minPieces(S,X-plusGrosse) return mini L=[] S=(1,2,5,10,13,20,50,100,200) X=[i for i in range(5000)] Y = [] for x in X: mini=0 start=time.process_time() m = minPieces(S,x) stop=time.process_time() t = stop - start Y.append(t) # print("X = ",X) # print("Y = ",Y) plt.title("Algorithme Glouton Récursif") plt.xlabel('montant X à rendre') plt.ylabel('Temps') plt.plot(X, Y, marker="+",markersize=7,markeredgecolor="r") plt.show() # affiche la figure a l'ecran
Algorithme Glouton Récursif du Rendu de Monnaie -
Étudier la Complexité de cet algorithme glouton récursif de rendu de monnaie
Corr
TODO
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?
Corr
Très simple, c'est un de ses points forts.
-
Sa Complexité en temps ?
Corr
Très Mauvaise. La Complexité est Exponentielle. Un des très gros points faibles.
-
Son Optimalité?
Corr
- NON OPTIMAL (du moins pas obligatoirement) dans le cas général. C'est donc le très gros POINT FAIBLE de cet algorithme.
- Si le système de pièces est canonique, Alors l'algorithme glouton du rendu de monnaie est Optimal
- Sinon, Si le système de pièces n'est PAS canonique, Alors cet algorithme glouton pour le rendu de monnaie donne:
- SOUVENT une bonne solution, i.e. pas très loin de la solution Optimale
- QUELQUEFOIS/souvent la solution Optimale
- MAIS PAS TOUJOURS LA SOLUTION OPTIMALE. Cette valeur de la solution n'est PAS TOUJOURS optimale dans le cas général (d'un système de pièces quelconques)