Présentation

• Dans la zone Euro, les valeurs des pièces sont 1,2,5,10,20,50,100 et 200 (en centimes d'euros). Lorsque l'on doit rendre la monnaie, l'algorithme glouton consiste à donner d'abord des pièces de forte valeur. Par exemple, pour rendre 63 centimes, on donnera succesivement une pièce de 50, une pièce de 10, une pièce de 2 et une pièce de 1.
• Appelons système la suite des valeurs faciales des pièces, rangée par ordre décroissant. Le système sera dit canonique si l'algorithme glouton utilise toujours le plus petit nombre de pièces possible. Le système Euro est canonique; mais le système (4,3,1) ne l'est pas: pour rendre 6, l'algorithme glouton nécessite 3 pièces alors que 2 suffisent.
• Kozen et Zaks ont présenté en 1994 un algorithme décidant si un système est canonique; l'inconvénient de cet algorithme est que son coût peut être exponentiel en la taille du système.
• Pearson a présenté peu après un algorithme de coût polynomial. Son étude n'a pas été publiée dans une revue; elle est heureusement disponible sur le Web, et a servi à concevoir ce sujet.