Aller au contenu principal

TD1 - Le rendu de monnaie

Objectifs
  1. Comprendre les limites d’un algorithme glouton ;
  2. Explorer toutes les solutions d’un problème ;
  3. Identifier les calculs redondants ;
  4. Introduire la programmation dynamique (mémoïsation).
TD

Le TD se fait sur papier.

Problème

On cherche à rendre une somme d'argent avec un nombre minimal de pièces, à partir d’un système de pièces donné.

C’est un problème d’optimisation.

Approche gloutonne : une bonne idée ?​

On considère les pièces suivantes :
1, 2, 5, 10, 20, 50, 100, 200

Rappel

Un algorithme glouton consiste à prendre à chaque étape la plus grande pièce possible.

Exemple : rendre 13€.

  • 10€ → reste 3€
  • 2€ → reste 1€
  • 1€ → reste 0€

➡️ Total : 3 pièces

✏️Exercices
  1. 1
    Appliquer l’algorithme glouton pour rendre 28€.
  2. 2
    Même question sans pièce de 1€, pour 36€.
  3. 3
    Dans quels cas l’algorithme glouton semble-t-il fonctionner ?
Limite

Un algorithme glouton :

  • ne revient jamais en arrière ;
  • peut donner une solution non optimale, voire aucune solution.

👉 Il faut donc envisager une autre approche.

Explorer toutes les solutions​

On cherche maintenant toutes les façons possibles de rendre une somme.

Exemple : rendre 5€

  • 5 → 1 pièce
  • 2 + 2 + 1 → 3 pièces
  • 2 + 1 + 1 + 1 → 4 pièces
  • 1 + 1 + 1 + 1 + 1 → 5 pièces

👉 On peut représenter cela avec un arbre de possibilités.

✏️Exercices
  1. 1
    Combien existe-t-il de façons différentes de rendre 5€ ?
  2. 2
    Quelle est la solution utilisant le moins de pièces ?
  3. 3
    Quelle est la solution utilisant le plus de pièces ?

On considère maintenant les pièces : 2, 5, 10

  1. 4
    Lister toutes les façons de rendre 12€.
  2. 5
    Quelle est la solution optimale ?
  3. 6
    Dessiner l’arbre des possibilités.
Problème

Explorer toutes les solutions :

  • garantit de trouver la meilleure,
  • mais devient très coûteux quand le montant augmente.

👉 Pourquoi ?

Construire une solution progressive​

👉 On construit maintenant les solutions de bas en haut (Approche bottom-up).

✏️Exercices

On considère les pièces : 1, 2, 5 ainsi que le tableau suivant, où la première ligne correspond au montant à rendre et la deuxième ligne au nombre minimal de pièces nécessaires pour ce montant :

Montant (€)0123456
Nb pièces min011
  1. 1
    Compléter le tableau jusqu’à 6€.
  2. 2
    Pour calculer 6€, quelles valeurs déjà connues utilise-t-on ?
  3. 3
    En déduire une règle générale pour calculer le nombre minimal de pièces pour un montant donné.
Observation

Pour calculer une valeur :

  • on utilise des résultats déjà connus ;
  • on évite les recalculs.

👉 C’est le principe de la programmation dynamique.

Vers la programmation dynamique​

On considère cet algorithme récursif :

liste_Piece = [1,2,5,10,20,50,100,200]

def rendu_monnaie_rec(montant : int) -> int:
    '''
    Retourne le nombre minimal de pièces nécessaires pour rendre le montant donné.
    :param montant: le montant à rendre
    :return: le nombre minimal de pièces nécessaires pour rendre le montant donné
    '''
    if montant == 0:
        return 0
    else:
        mini = 1000
        for i in range(len(liste_Piece)):
            if liste_Piece[i] <= montant:
                nbPiece = 1 + rendu_monnaie_rec(montant - liste_Piece[i])
                if nbPiece < mini:
                    mini = nbPiece
        return mini
✏️Exercices
  1. 1
    Expliquer le fonctionnement de cet algorithme.
  2. 2
    Pourquoi cet algorithme refait-il plusieurs fois les mêmes calculs ?
  3. 3
    Faire le lien avec les répétitions observées dans l’arbre.

Ajouter de la mémoire (mémoïsation)​

✏️Exercices
  1. 1
    Quelle information faudrait-il mémoriser pour éviter les recalculs ?
  2. 2
    À quel moment du programme faudrait-il consulter cette mémoire ?
  3. 3
    À quel moment faudrait-il la mettre à jour ?

Compléter l’algorithme​

def rendu_monnaie(pieces : list, montant : int) -> int:
    '''
    Retourne le nombre minimal de pièces nécessaires pour rendre le montant donné, en utilisant la mémoïsation.
    :param pieces: la liste des pièces disponibles
    :param montant : le montant à rendre
    :return: le nombre minimal de pièces nécessaires pour rendre le montant donné
    '''
    memoire = [...]  # Doit initialiser une liste avec des valeurs -1 pour indiquer que les résultats ne sont pas encore calculés
    return rendu_monnaie_dynamique(..., ..., ...)

def rendu_monnaie_dynamique(pieces : list, montant : int, memoire : list) -> int:
    '''
    Retourne le nombre minimal de pièces nécessaires pour rendre le montant donné, de façon dynamique.
    :param pieces: la liste des pièces disponibles
    :param montant: le montant à rendre
    :param memoire: une liste pour mémoriser les résultats déjà calculés
    :return: le nombre minimal de pièces nécessaires pour rendre le montant donné
    '''
    if ... :        #Quand on a plus rien à rendre
        return 0
    elif ... :      #Si on a déjà calculé le résultat pour ce montant, on le retourne
        return ...
    else:
        mini = 1000
        for i in range(len(...)):
            if pieces[i] <= ... :
                nb = 1 + rendu_monnaie_dynamique(..., ..., ...)
                if nb < mini:
                    mini = nb
        memoire[...] = ...  #Mise à jour de la mémoire
        return ...
✏️Exercices
  1. 1
    Compléter les parties manquantes de l’algorithme.
  2. 2
    Expliquer le rôle de memoire.
  3. 3
    Que permet d'éviter la condition sur la mémoire ?
  4. 4
    En quoi cet algorithme est-il plus efficace que la version récursive simple ?

Comparaison des performances​

✏️Exercices
  1. 1
    Quelle version est la plus rapide ? Justifier.
  2. 2
    Résumer en une phrase la différence entre les deux approches.
  3. 3
    Donner une définition simple de la programmation dynamique à partir de ce TD.
Bonus

Tester les deux algorithmes pour rendre 1000€ avec les pièces suivantes : 1, 2, 5, 10, 20, 50, 100, 200 sur python, et, à l'aide de la bibliothèque time, mesurer le temps d'exécution de chaque algorithme.