33 - Algorithmes gloutons

Les exercices se font dans Thonny, dans le fichier 33_algorithmes_gloutons.py.

Cours associé : 24 - Algorithmes gloutons .

Exercice 0 : QCM – vérification des prérequis

Pour chaque question, une seule réponse est correcte.

1. Quel est le principe d’un algorithme glouton ?

• A. Il explore toutes les solutions possibles pour trouver la meilleure
• B. Il fait à chaque étape le choix localement optimal, sans revenir en arrière
• C. Il divise le problème en sous-problèmes indépendants
• D. Il trie d’abord les données puis applique une recherche dichotomique

Correction publiée après la séance.

2. Un algorithme glouton donne-t-il toujours la solution optimale ?

• A. Oui, toujours
• B. Non, jamais
• C. Cela dépend du problème
• D. Seulement si les données sont triées

Correction publiée après la séance.

3. Pour rendre 8 centimes avec les pièces [6, 4, 1], l’algorithme glouton choisit d’abord la pièce de 6. Combien de pièces utilise-t-il au total ?

• A. 2 pièces (6, 4)
• B. 3 pièces (6, 1, 1)
• C. 2 pièces (4, 4)
• D. 8 pièces (1, 1, 1, 1, 1, 1, 1, 1)

Correction publiée après la séance.

Exemple travaillé : rendu de monnaie glouton

Problème : rendre 678 centimes avec le système euro [200, 100, 50, 20, 10, 5, 2, 1].

Principe glouton : à chaque étape, choisir la plus grande pièce possible sans dépasser le montant restant.

Trace :

Résultat : [200, 200, 200, 50, 20, 5, 2, 1] → huit pièces.

Algorithme :

def rendu_monnaie(montant, pieces):
    """Renvoie la liste des pièces pour rendre montant centimes."""
    resultat = []
    for p in pieces:           # pièces triées par valeur décroissante
        while montant >= p:
            resultat.append(p)
            montant -= p
    return resultat

Exercice 1 : rendu de monnaie

1. Programmer la fonction rendu_monnaie(montant, pieces) qui renvoie la liste des pièces utilisées.

   Indice

   L’exemple travaillé donne l’algorithme : pour chaque pièce, de la plus grande à la plus petite, la rendre tant que le montant restant est supérieur ou égal à sa valeur, en l’ajoutant à la liste et en la retirant du montant.

2. Tester avec le système [200, 100, 50, 20, 10, 5, 2, 1] pour rendre 678 centimes.

   Indice

   Appeler rendu_monnaie avec le montant 678 et la liste des pièces, dans un print, puis comparer le résultat avec la trace de l’exemple travaillé.

3. Tester avec le système [6, 4, 1] pour rendre 8 centimes. Comparer le résultat glouton avec la solution optimale.

   Indice

   Compter les pièces rendues par l’algorithme, puis chercher à la main une façon de rendre 8 centimes avec moins de pièces.

Correction publiée après la séance.

Exercice 2 : nombre de pièces

Modifier la fonction rendu_monnaie pour qu’elle renvoie un dictionnaire associant chaque valeur de pièce utilisée à son nombre d’occurrences. Par exemple, pour 678 centimes :

{200: 3, 50: 1, 20: 1, 5: 1, 2: 1, 1: 1}

def rendu_monnaie(montant, pieces):
    resultat = {}
    for p in pieces:
        nb = 0
        while montant >= p:
            nb = ...
            montant = ...
        if nb > 0:
            resultat[...] = ...
    return resultat

Correction publiée après la séance.

Exercice 3 : sac à dos fractionnaire

On dispose d’objets ayant chacun un poids et une valeur. On veut remplir un sac de capacité limitée en maximisant la valeur totale. Dans le cas fractionnaire, on peut prendre une fraction d’un objet.

Objets disponibles :

1. Programmer la fonction sac_a_dos_frac(poids_max, objets) où objets est une liste de tuples (poids, valeur).

   Indice

   La fonction sac_a_dos_frac du cours fait ce travail pour des objets (nom, valeur, poids). L’adapter aux tuples (poids, valeur) de l’énoncé : la fonction rapport renvoie alors objet[1] / objet[0], et la boucle s’écrit for poids, valeur in tries:.

2. Tester avec un sac de 10 kg.

   Indice

   Écrire la liste des objets du tableau sous forme de tuples (poids, valeur), par exemple (3, 9) pour l’objet A, puis appeler sac_a_dos_frac(10, objets) et afficher le résultat.

3. Déterminer la complexité temporelle de cette fonction.

   Indice

   Deux étapes se suivent : le tri, dont le coût est en $O(n \log n)$, puis une seule boucle sur les objets. La plus coûteuse des deux donne la complexité.

Correction publiée après la séance.

Exercice 4 : comparaison de stratégies

Pour le problème du sac à dos (entier, sans fraction) avec les données de l’exercice 3, programmer et comparer les trois stratégies gloutonnes (tri par valeur décroissante, tri par poids croissant, tri par ratio décroissant). Afficher le contenu du sac et la valeur totale pour chacune.

def sac_glouton(poids_max, objets, cle_tri):
    tries = sorted(objets, key=cle_tri)
    valeur_totale = 0
    poids_restant = poids_max
    contenu = []
    for poids, valeur in tries:
        if poids <= ...:
            contenu.append((poids, valeur))
            valeur_totale = ...
            poids_restant = ...
    return valeur_totale, contenu

def oppose_valeur(o):
    return -o[1]

def poids_objet(o):
    return ...

def oppose_rapport(o):
    return ...

objets = [(3, 9), (4, 10), (5, 15), (6, 12)]
print(sac_glouton(10, objets, oppose_valeur))

Correction publiée après la séance.

Exercice 5 : limites du glouton

Considérons les objets suivants et un sac de 4 kg :

1. Appliquer l’algorithme glouton (tri par ratio). Quel résultat obtient-on ?

   Indice

   Calculer le rapport valeur/poids de chaque objet, puis prendre les objets dans l’ordre décroissant de ce rapport, tant qu’ils tiennent entiers dans les 4 kg.

2. Trouver « à la main » une meilleure solution.

   Indice

   Essayer les combinaisons de deux objets dont le poids total ne dépasse pas 4 kg.

3. Expliquer pourquoi l’algorithme glouton échoue dans ce cas.

   Indice

   Après le premier choix, combien de kilogrammes restent libres, et peut-on encore s’en servir ? Un algorithme glouton ne revient jamais sur un choix.

Correction publiée après la séance.

Exercice 6 : planification d’activités

Un élève dispose d’une journée et souhaite participer au maximum d’activités. Chaque activité a une heure de début et une heure de fin, et deux activités ne peuvent se chevaucher.

1. Proposer une stratégie gloutonne pour maximiser le nombre d’activités.

   Indice

   L’indication placée sous la question 3 donne la stratégie. Se demander pourquoi : quel critère laisse le plus de temps libre pour les activités suivantes ?

2. Appliquer cette stratégie aux données ci-dessus.

   Indice

   Ranger les activités par heure de fin croissante, puis les examiner dans cet ordre : garder une activité si elle commence au plus tôt à la fin de la dernière activité gardée.

3. Programmer cette stratégie en Python.

Indication : trier les activités par heure de fin croissante et sélectionner chaque activité dont l’heure de début est postérieure ou égale à la fin de la dernière activité choisie.

def heure_fin(activite):
    return activite[2]

def planification(activites):
    triees = sorted(activites, key=heure_fin)
    selection = [triees[0]]
    for i in range(1, len(triees)):
        nom, debut, fin = triees[i]
        if debut >= ...:
            selection.append(...)
    return selection

activites = [("A", 8, 10), ("B", 9, 12), ("C", 10, 11), ("D", 11, 14), ("E", 13, 15), ("F", 14, 16)]
print(planification(activites))

Correction publiée après la séance.