Problème du rendu de monnaie (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen dont est tirée la discussion sur les systèmes canoniques (correction de l'exercice 1 question 3).
- le livre part 3 : greedy algorithms and dynamic programming de Tim Roughgarden
- page sur le problème du voyageur de commerce du site Interstices
🔖 Synthèse de ce qu'il faut retenir pour le bac
Problème du rendu de monnaie⚓︎
Un problème d'optimisation⚓︎
Problème du rendu de monnaie
On se place dans la position du caissier qui doit rendre en monnaie un certain montant avec un nombre minimal de pièces. On suppose que le caissier dispose en nombre illimité de toutes les valeurs de pièces disponibles. L'ensemble des valeurs de pièces disponibles constitue le système monétaire.
Il s'agit d'un problème d'optimisation dont la spécification est la suivante :
- Entrée du problème : un montant à rendre et une liste de valeurs de pièces d'un système monétaire ; on suppose qu'on dispose d'un nombre illimité de pièces de chaque valeur
- Sortie du problème : une liste de pièces dont la somme est égale au montant à rendre et dont le nombre de pièces est minimal ; ou une liste vide si le montant ne peut être atteint avec les pièces du système
Une heuristique gloutonne⚓︎
Heuristique gloutonne et algorithme glouton
Une heuristique est une méthode de résolution approchée d'un problème.
Face à un problème d'optimisation, une heuristique qui procède par une succession de choix localement optimaux pour construire une solution globalement optimale, en ne remettant jamais en cause les choix précédents, s'appelle une heuristique gloutonne.
Un algorithme qui construit une solution avec une heuristique gloutonne est un algorithme glouton.
Gulo gulo, le Glouton est un animal du Grand Nord qui se caractérise par sa voracité.
Algorithme glouton de rendu de monnaie
La recherche exhaustive d'une solution n'est pas raisonnable : il faudrait déterminer toutes les décompositions en somme de pièces de la monnaie à rendre. Une heuristique gloutonne de construction d'une solution est assez naturelle et peut se résumer en une phrase :
- tant qu'il reste un montant à rendre on choisit la plus grande valeur de pièce disponible inférieure ou égale à la somme et on la retranche du montant à rendre
Si l'algorithme se termine, sa complexité sera excellente, car le choix de la plus grande pièce possible pourra se faire par une boucle descendante si on a classé les valeurs des pièces par ordre décroissant (il s'agit d'un prétraitement).
Deux questions peuvent se poser :
- Question 1 : l'algorithme glouton se termine-t-il toujours ?
- Question 2 : l'algorithme glouton est-il exact ?
Exercice 1
Question 1
On considère le système monétaire européen dont les valeurs des pièces par ordre décroissant sont : 500, 200, 100, 50, 20, 10, 5, 2, et 1.
Donner la liste des pièces rendues avec l'algorithme glouton pour un montant de 34 euros, puis de 47 euros.
\(34 = 20 + 10 + 2 + 2\) soit quatre pièces avec l'algorithme glouton.
\(47 = 20 + 20 + 5 + 2\) soit quatre pièces avec l'algorithme glouton.
On peut démontrer que l'algorithme de rendu de monnaie glouton est toujours optimal dans le système monétaire de l'euro, qui est dit canonique. Voir cet article de Culture Maths.
Question 2
On considère le système monétaire dont les valeurs des pièces par ordre décroissant sont : 30, 24, 12, 6, 3, 1.
L'algorithme glouton rend-il un nombre minimal de pièces sur un montant de 49 euros ?
Avec un algorithme glouton, \(49=30+12+6+1\) ce qui donne un rendu avec quatre pièces. On peut faire mieux en décomposant ainsi : \(49=24 + 24 + 1\) ce qui donne un rendu avec moins de pièces. Dans ce cas l'algorithme glouton n'est pas optimal.
L'optimalité de l'algorithme glouton dépend du système monétaire. Un système monétaire où l'algorithme glouton rend toujours la monnaie en un nombre minimum de pièces est dit canonique. On ne connaît pas de critère simple pour déterminer si un système canonique mais on peut démontrer que le système de l'euro est canonique. Par ailleurs, on peut s'assurer qu'un système est canonique en vérifiant que l'algorithme glouton est optimal pour toutes les sommes inférieures à la somme des deux pièces de valeurs maximales.
Question 3
Donner un exemple de système monétaire et de montant à rendre pour lequel l'algorithme glouton ne se termine pas (en supposant qu'ont peut disposer d'un nombre illimité de pièces de chaque valeur).
Il suffit de prendre un système monétaire sans pièce de \(1\) : il est impossible de rendre la monnaie sur un montant de 1. Si le système monétaire propose de pièces de \(1\), l'algorithme glouton se termine toujours, à condition de ne pas être limité en nombre de pièces de \(1\) !
Exercice 2
💻 Saisir ses réponses sur Capytale
Question 1
Compléter la fonction rendu_glouton
qui prend en paramètres un montant à rendre et une liste de valeurs de pièces disponibles dans l'ordre croissant et construit puis renvoie avec l'algorithme glouton, une liste de pièces dont la somme est égale au montant à rendre. On suppose disposer d'un nombre illimité de pièces de chaque sorte.
A
Z
def rendu_glouton(restant, pieces):
# pieces tableau de valeurs de pièces disponibles dans l'ordre croissant
indice_pieces = len(pieces) - 1
rendu = []
while restant > 0 and indice_pieces >= 0:
if pieces[indice_pieces] <= restant:
restant = restant - pieces[indice_pieces]
rendu.append(pieces[indice_pieces])
else:
indice_pieces = indice_pieces - 1
# rendu possible
return rendu
def test_rendu_glouton():
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_glouton(76, systeme_euro) == [50, 20, 5, 1]
assert rendu_glouton(49, systeme_euro) == [20, 20, 5, 2, 2]
assert rendu_glouton(843, systeme_euro) == [500, 200, 100, 20, 20, 2, 1]
systeme_non_canonique = [1, 3, 6, 12, 24, 30]
assert rendu_glouton(49 , systeme_non_canonique) == [30, 12, 6, 1]
assert rendu_glouton(53 , systeme_non_canonique) == [30, 12, 6, 3, 1, 1]
print("tests réussis pour rendu_glouton")
Caractéristiques d'un algorithme glouton⚓︎
Caractéristiques d'un algorithme glouton
- Un algorithme glouton construit une solution par une succession de choix localement optimaux, en espérant obtenir une solution globalement optimale
- Un algorithme glouton est efficace, car il progresse directement vers une solution sans jamais remettre en question les choix précédents. Sa complexité est souvent facile à établir. Le travail pour effectuer chaque choix glouton est souvent effectué lors d'un prétraitement, par exemple avec un tri de l'entrée.
- Un algorithme glouton n'est pas toujours correct, et s'il l'est, la preuve peut être difficile.
Problème d'ordonnancement⚓︎
Un problème d'optimisation⚓︎
Problème d'ordonnancement
On dispose d'une liste de tâches à effectuer successivement. Deux tâches ne peuvent être exécutées en même temps, comme par exemple des processus sur un processeur. Chaque tâche est caractérisée par un couple d'attributs : (longueur, priorité). La valeur de la priorité est d'autant plus grande que la tâche est importante. On doit définir un ordonnancement de ces tâches c'est-à-dire un ordre d'exécution.
Critère d'ordonnancement : On souhaite terminer chaque tâche le plus tôt possible et achever le plus vite possible les tâches prioritaires.
Exemple
On doit ordonnancer trois tâches :
Tâche | Longueur | Priorité |
---|---|---|
A | 4 | 3 |
B | 5 | 2 |
C | 6 | 1 |
Une tâche est achevée lorsque son exécution et celles de toutes les précédentes sont terminées, il est donc naturel de définir le temps de complétion d'une tâche comme la somme de sa longueur et de celles de toutes les précédentes.
Prenons par exemple l'ordonnancement A -> B -> C :
Tâche | Longueur | Temps de complétion | Priorité |
---|---|---|---|
A | 4 | 4 | 3 |
B | 5 | 9 | 2 |
C | 6 | 15 | 1 |
La qualité de cet ordonnancement peut être mesurée par la somme des temps de complétion pondérés par les priorités, qui se calcule ainsi :
\(4 \times 3 + 9 \times 2 + 15 \times 1 = 45\).
Considérons désormais l'ordonnancement C -> B -> A :
Tâche | Longueur | Temps de complétion | Priorité |
---|---|---|---|
C | 6 | 6 | 1 |
B | 5 | 11 | 2 |
A | 4 | 15 | 3 |
Le temps de complétion moyen pondéré par les priorités est supérieur au premier ordonnancement :
\(6 \times 1 + 11 \times 2 + 15 \times 3 = 73\).
Ce n'est pas surprenant, il vaut mieux traiter la taĉhe A en premier car elle est plus courte et de plus haute priorité.
Muni de notre fonction d'objectif calculant la somme des temps de complétion pondérés par les priorités, notre problème devient un problème d'optimisation dont la spécification est la suivante :
- Entrée du problème : une liste de tâches caractérisées par des couples (longueur, priorite)
- Sortie du problème : un ordonnancement des tâches minimisant la fonction d'objectif
Exercice 5
Ordonnancement dans deux cas particuliers.
Question 1
Si toutes les tâches ont la même longueur, doit-on traiter d'abord les moins prioritaires ou les autres pour minimiser la fonction d'objectif ?
Si toutes les tâches ont la même longueur, les coefficients de la fonction d'objectif (somme des produits temps de complétion \(\times\) priorité) liés aux temps de complétion ne dépendent pas de l'ordonnancement. Minimiser la fonction d'objectif équivaut donc à traiter les priorités dans l'ordre décroissant pour que les plus grandes priorités multiplient les plus petits temps de complétion.
Question 2
Si toutes les tâches ont la même priorité, doit-on traiter d'abord les plus courtes ou les plus longues pour minimiser la fonction d'objectif ?
Si toutes les tâches ont la même priorité, les coefficients de la fonction d'objectif (somme des produits temps de complétion \(\times\) priorité) liés aux priorités ne dépendent pas de l'ordonnancement. Minimiser la fonction d'objectif équivaut donc à traiter les tâches dans un ordre qui minimise la somme des temps de complétion : cela revient à traiter les tâches par longueur croissante car plus une tâche est traitée tôt plus sa longueur contribue aux temps de complétion (au sien et à tous les suivants).
Heuristiques gloutonnes⚓︎
Plusieurs heuristiques gloutonnes
Un ordonnancement peut être vu comme une succession de choix. Il peut donc sembler naturel de définir un critère de choix glouton pour construire une solution au problème par une heuristique gloutonne.
D'après l'étude des deux cas particuliers de l'exercice 5, pour minimiser la fonction d'objectif (l'optimisation globale), il semble naturel de guider notre choix d'optimum local selon deux principes :
- traiter d'abord les tâches de plus petite longueur
- traiter d'abord les tâches de plus haute priorité
Ainsi on recherche un critère de choix glouton de la prochaine tâche qui réduise l'augmentation de la valeur de la fonction d'objectif (on ajoute des valeurs positives) :
- la valeur du critère doit être d'autant plus petite que la priorité est grande
- la valeur du critère doit être d'autant plus grande que la longueur est grande
On recherche alors une fonction croissante selon le paramètre longueur et décroissante selon le paramètre priorité. Deux choix sont :
- la valeur de la différence longueur \(-\) priorité
- la valeur du quotient longueur \(/\) priorité
Une fois qu'on a défini le critère de choix glouton, l'algorithme glouton est simple :
- on réalise un prétraitement en triant les tâches selon le critère
- on sélectionne les tâches dans l'ordre défini par le prétraitement
Pour traiter un ensemble de \(n\) tâches, le coût du tri en prétraitement, en \(O(n \log(n))\) domine celui de la boucle de sélection en \(O(n)\), ce qui donne une complexité en \(O(n \log(n))\).
Il reste à savoir si ces heuristiques gloutonnes sont correctes ...
Exercice 6
💻 Saisir ses réponses sur Capytale
Tri d'une liste avec une fonction clef de tri
Si on affiche la documentation de la fonction sorted
avec help(sorted)
, on obtient :
Help on built-in function sorted in module builtins:
sorted(iterable, /, *, key=None, reverse=False)
Return a new list containing all items from the iterable in ascending order.
A custom key function can be supplied to customize the sort order, and the
reverse flag can be set to request the result in descending order.
On considère un tableau Python tab = [(8, 'MARIE') , (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')]
rassemblant les résultats d'un groupe d'élèves à un devoir noté sur 10.
sorted(tab)
renvoie une copie superficielle du tableau triée dans l'ordre croissant (ordre lexicographique si les éléments sont destuple
) :
[(7, 'SARAH'), (7.5, 'ANNE'), (8, 'ISMAEL'), (8, 'MARIE')]
sorted(tab, reverse=True)
renvoie une copie superficielle du tableau triée dans l'ordre décroissant :
[(8, 'MARIE'), (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')]
-
On définit une fonction qui va nous servir de clef de tri :
🐍 Script Pythondef clef(paire): return (paire[1], paire[0])
sorted(tab, key=clef)
renvoie une copie superficielle du tableau triée dans l'ordre croissant en comparant non pas les valeurs des éléments mais les valeurs de leurs images par la fonctionclef
:
🐍 Script Python[(7.5, 'ANNE'), (8, 'ISMAEL'), (8, 'MARIE'), (7, 'SARAH')]
sorted(tab, key=clef, reverse=True)
renvoie une copie superficielle du tableau triée dans l'ordre décroissant en comparant non pas les valeurs des éléments mais les valeurs de leurs images par la fonctionclef
:
🐍 Script Python[(7, 'SARAH'), (8, 'MARIE'), (8, 'ISMAEL'), (7.5, 'ANNE')]
🗝️ Python propose d'autres fonctions
built-in
d'ordre supérieur qui prennent en paramètre une autre fonction servant de clef paramétrant le traitement : par exemplemax
etmin
.
def critere_nom(paire):
return paire[1]
tab = [(8, 'MARIE') , (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')]
assert min(tab, key=critere_nom) == (7.5, 'ANNE')
assert max(tab, key=critere_nom) == (7, 'SARAH')
On donne ci-dessous une implémentation de l'algorithme d'ordonnancement glouton :
tri_taches
réalise le prétraitement en triant les tâches selon le critère de choix glouton qui peut êtrecritere_diff_glouton
oucritere_ratio_glouton
objectif
calcule la valeur de la fonction objectif (somme des temps de complétion pondérés par les priorités) une fois l'ordonnancement réaliséordonnancement_glouton
réalise l'ordonnancement selon un certain critère de choix glouton avectri_taches
et calcule la valeur de la fonction objecti avecobjectif
, puis renvoie le couple (valeur de l'oobjectif, ordonnancement)
A
Z
Question 1
- Compléter la fonction
objectif
puis la fonctionordonnancement_glouton
. - Vérifier que le test unitaire
test_ordonnancement_glouton
est réussi. - Exécuter
comparaison(critere_ratio_glouton, critere_diff_glouton, 100)
. Quelle conjecture peut-on faire sur le meilleur critère de choix glouton parmi les deux ?
Le critère de choix glouton du quotient longueur \(/\) priorité donne un algorithme glouton d'ordonnancement optimal pour la fonction d'objectif calculant la somme des temps de complétion pondérés par les priorités.
La preuve est disponible dans le livre de Tim Roughgarden part 3 : greedy algorithms and dynamic programming, il a également réalisé deux capsules video. La preuve repose sur un argument d'échange classique dans les preuves de correction d'algorithmes gloutons : on démontre qu'on peut modifier une solution optimale en échangeant des tâches dans son ordonnancement pour qu'elle soit une solution construite par l'algorithme glouton.
Video
import random
def tri_taches(liste_taches, clef):
"""Renvoie le tri de liste_taches
selon la fonction de clef de tri"""
return sorted(liste_taches, key=clef)
def critere_ratio_glouton(tache):
"""Renvoie pour la tache qui est un couple (longueur, priorite)
la valeur du quotient longueur / priorite
"""
longueur, priorite = tache
return longueur / priorite
def critere_diff_glouton(tache):
"""Renvoie pour la tache qui est un couple (longueur, priorite)
la valeur de la différence longueur - priorite
"""
longueur, priorite = tache
return longueur - priorite
def objectif(ordo_taches):
"""
Renvoie la valeur de la fonction objectif pour une liste
de taches (des couples (longueur, priorite) )
La fonction objectif est la somme des temps de complétion pondérés
par les priorités
"""
temps_completion = 0
somme = 0
for tache in ordo_taches:
longueur, priorite = tache
temps_completion = temps_completion + longueur
somme = somme + temps_completion * priorite
return somme
def ordonnancement_glouton(liste_taches, critere_glouton):
"""Renvoie le couple
(valeur de la fonction objectif, ordonnancement des taches selon le critere glouton)"""
ordo = tri_taches(liste_taches, critere_glouton)
return (objectif(ordo), ordo)
def test_ordonnancement_glouton():
liste_taches1 = [(7, 2), (46, 3), (10, 6), (36, 10), (17, 6)]
assert ordonnancement_glouton(liste_taches1, critere_ratio_glouton) == (1338, [(10, 6), (17, 6), (7, 2), (36, 10), (46, 3)])
assert ordonnancement_glouton(liste_taches1, critere_diff_glouton) == (1346, [(10, 6), (7, 2), (17, 6), (36, 10), (46, 3)])
print("tests réussis pour ordonnancement_glouton")
def comparaison(critere1, critere2, nb_exp):
"""
Pour nb_exp listes de taches aléatoires
Renvoie une liste res :
res[0] est le nombre de fois où l'ordonnancement par critere1 et critere2
donnent la même valeur pour la fonction objectif
res[1] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)
que celui par critere2
res[2] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)
que celui par critere2
"""
res = [0, 0, 0]
for _ in range(nb_exp):
liste_taches = [(random.randint(1, 100), random.randint(1, 10)) for _ in range(50)]
c1, _ = ordonnancement_glouton(liste_taches, critere1)
c2, _ = ordonnancement_glouton(liste_taches, critere2)
if c1 < c2:
res[1] += 1
elif c2 < c1:
res[2] += 1
else:
res[0] += 1
return res
#test_ordonnancement_glouton()
#comparaison(critere_ratio_glouton, critere_diff_glouton, 100)