¶ Exercice 1 - Le rendu de monnaie
Dans cet exercice, on considère une somme à rendre à la suite d’un achat en liquide. Les pièces désignent indifféremment les véritables pièces que les billets.
Les valeurs des pièces appartiennent à un système monétaire, qui détermine les pièces à possibles pour rendre la monnaie.
Les différents systèmes monétaires utilisables sont représentés sous la forme d'une liste d'entiers classés dans l'ordre décroissant.
systeme_français = [100, 50, 20, 10, 5, 2, 1]
systeme_britanique = [60, 30, 24, 12, 6, 2, 1]
La quantité de pièces à rendre est représentée sous la forme d'un dictionnaire, où les clefs sont les valeurs des pièces et les valeurs associées sont les quantités de chacune des pièces.
Voici le dictionnaire obtenu pour rendre 31 € :
resultat = {20:1, 10:1, 1:1}
Question 1 - En utilisant une méthode gloutonne, écrire la fonction rendu_monnaie. Cette fonction prend en paramètre un entier représentant la somme à rendre et une liste d'entiers représentant le système monétaire à utiliser. Elle retourne un dictionnaire représentant les pièces à rendre.
def rendu_monnaie(somme:int, systeme:list) -> dict :
return
Question 2 - Essayer votre fonction afin de rendre la somme de 49 € à l'aide du système français.
Question 3 - Essayer votre fonction afin de rendre la somme de 49 € à l'aide du système britannique.
Dans ce deuxième cas, la solution est composée de 4 pièces, et ne correspond pas à la solution optimale. L'algorithme glouton ne donne pas toujours une solution optimale au problème.
Question 4 - Essayer votre fonction afin de rendre la somme de 49 € à l'aide du système suivant systeme = [50,30,15,10,5,3].
Ici, si vous n'avez pas pris en compte ce cas, votre programme provoque une erreur. En effet, il n'est pas possible de rendre 49 € avec ce système.
Question 5 - Modifier votre fonction pour retourner False lorsque que la solution n'est pas possible.
Dans ce cas, une solution exacte n'existe pas. L'algorithme glouton ne donne pas toujours une solution précise au problème.
¶ Exercice 2 - Somme maximale
On cherche à sélectionner cinq nombres de la liste suivante en cherchant à avoir leur somme la plus grande possible et en s'interdisant de choisir deux nombres voisins.
Comme on souhaite avoir la plus grande somme finale, la stratégie gloutonne consiste à choisir à chaque étape le plus grand nombre possible dans les choix restants.
Question 1 - À l'aide d'un algorithme glouton, écrire la fonction somme_max. Cette fonction prend en paramètre une liste de nombres. Elle retourne un tuple composé de la liste des nombres choisi et de la somme totale.
- On utilisera la liste précédente
l = [15, 4, 20, 17, 11, 8, 11, 16, 7, 14, 2, 7, 5, 17, 19, 18, 4, 5, 13, 8]. - Pour bloquer la sélection des nombres voisins lors du choix du maximum, on pourra utiliser une seconde liste de booléens, qui indique si ce nombre peut être choisi ou non.
def somme_max(l:list) -> tuple :
return
Selon l'algortihme glouton, vous devez obtenir
([20, 19, 16, 15, 14], 84)comme résultat. Ce n'est pas un résultat optimal.
Question 2 - À là main, trouver le résultat optimal de ce problème.
¶ Exercice 3 - Problème du sac à dos
Vous décidez de partir en vacances et vous souhaitez emporter avec vous les objets permettant de maximiser votre confort. Cependant, votre sac ne peut supporter qu'une masse maximale de 15 kg, contrainte imposée par la compagnie aérienne.
On dispose donc d’un sac pouvant supporter un poids maximal donné et de divers objets ayant chacun une masse en kg et un nombre symbolisant leurs degrés de confort. Plus ce nombre est grand, plus l'objet est confortable.
Il s’agit de choisir les objets à emporter dans le sac afin maximiser le confort tout en respectant la contrainte du poids maximal. C’est un problème d’optimisation avec contrainte.
¶ Exemple 1
On considère les objets suivants et un sac de 15kg :
| objet | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| masse (kg) | 7 | 6 | 4 | 3 | 2 | 1 |
| confort | 91 | 72 | 48 | 27 | 26 | 2 |
On pourra représenter la liste des objets sous la forme d'un tuple : ("A", 7, 91).
¶ Stratégie 1 - Le plus grand degré de confort
Dans cette stratégie, on choisit de prendre l'objet ayant le plus grand degré de confort, sans excéder la capacité maximale du sac.
Question 1 - En utilisant une méthode goutonne, écrire une fonction strategie1. Cette fonction prend en paramètre la liste des objets et la capacité maximale du sac. Elle retourne un tuple composé de la liste des objets, de la somme des degrés de confort et de la capacité restante dans le sac.
def strategie1(objets:list, poids_sac:int) -> tuple:
return
Avec cette stratégie, vous devez trouver la liste des objets A, B et E pour un total de 189 de confort. Il reste 0kg de capacité dans le sac.
¶ Stratégie 2 - La masse la plus faible
Dans cette stratégie, on choisit de prendre l'objet ayant la masse la plus faible, sans excéder la capacité maximale du sac.
Question 2 - Écrire une fonction strategie2. Cette fonction prend en paramètre la liste des objets et la capacité maximale du sac. Elle retourne un tuple composé de la liste des objets, de la somme des degrés de confort et de la capacité restante dans le sac.
def strategie2(objets:list, poids_sac:int) -> tuple:
return
Avec cette stratégie, vous devez trouver la liste des objets F, E, D et C pour un total de 103 de confort. Il reste 5kg de capacité pour le sac.
¶ Stratégie 3 - Le plus grand rapport
Dans cette stratégie, on choisit de prendre l'objet ayant le plus grand rapport , sans excéder la capacité maximale du sac.
Question 3 - Écrire une fonction strategie3. Cette fonction prend en paramètre la liste des objets et la capacité maximale du sac. Elle retourne un tuple composé de la liste des objets, de la somme des degrés de confort et de la capacité restante dans le sac.
- Il faudra calculer le rapport .
def strategie3(objets:list, poids_sac:int) -> tuple:
return
Avec cette stratégie, vous devez trouver la liste des objets A, E, B pour un total de 189 de confort. Il reste 0kg de capacité pour le sac.
Dans ce cas, selon les caractéristiques des objets, on remarque que la stratégie 1 et la stratégie 3 sont les plus optimales, avec un confort de 189.
¶ Exemple 2
On considère maintenant les objets suivants et un sac de 2kg :
| objet | A | B | C |
|---|---|---|---|
| masse (kg) | 1.5 | 2 | 0.3 |
| confort | 2 | 5 | 4 |
Question 4 - En utilisant les trois fonctions précédentes, trouver la stratégie permettant d'obtenir le résultat le plus optimal.
Dans ce cas, selon les caractéristiques des objets, on remarque de la stratégie 2 est la plus optimale, avec un confort de 6.
Conclusion : Pour le problème du sac à dos, ce n'est pas toujours la même stratégie qui fournit la meilleure solution, et cette solution n'est pas forcément optimale !
¶ Exercice 4 - Problème de planning
Vous participez à un festival de musique proposant des concerts à différents horaires. Voici les horaires des concerts :
| Concert | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| Horaire | 16h00 - 17h00 | 16h30 - 17h30 | 17h00 - 18h30 | 17h30 - 18h00 | 18h00 - 19h00 | 19h00 - 21h00 | 19h30 - 20h00 | 20h00 - 21h30 | 21h00 - 22h00 | 22h00 - 23h30 |
On peut représenter ces informations avec le schéma ci-dessous.
Malheureusement, il n'est pas possible d'assister à tous les concerts, car certains ont lieu à des moments communs. Vous souhaitez réfléchir à un algorithme vous permettant d'assister à un maximum de concert.
¶ Représentation des données
Pour simplifier, on pourra représenter les différents horaires par un nombre entiers selon le schéma suivant.
En python, on pourra organiser les informations à l'aide d'un dictionnaire :
- Les clés sont les différents concerts : A, B, C...
- Les valeurs sont des listes composés de 2 éléments : l'horaire de début et l'horaire de fin
concerts = { 'A': [1, 2],
'B': [1.5, 2.5],
'C': [2, 3.5],
'D': [2.5, 3],
'E': [3, 4],
'F': [4, 6],
'G': [4.5, 5],
'H': [5, 6.5],
'I': [6, 7],
'J': [7, 8]
}
¶ Évènements compatibles
Deux concerts sont dits compatibles s'ils ne se déroulent pas au même moment. Par exemple :
- Les concerts A et B ne sont pas compatibles.
- Les concerts A et E sont compatibles.
Cette notion de compatibilités pourra être utiles dans la suite de l'exercice.
Question 1 - Écrire une fonction concerts_compatibles. Cette fonction prend en paramètre une chaine de caractères identifiant un concert et un dictionnaire de concerts.
Elle retourne l'ensemble des concerts compatibles avec le concert dont l'identifiant est passé en paramètre de la fonction.
def concerts_compatibles(id_concert: str, dico_concert: dict) -> dict:
return
¶ Résolution du problème
¶ Stratégie 1
Cette première stratégie consiste à choisir le concert dont l'heure de début arrive le plus tôt parmi tous les spectacles compatibles.
Question 2 - Écrire une fonction plus_tot. Cette fonction prend en paramètre un dictionnaire de concerts (selon la forme indiquée à la question 1). Elle retourne l'identifiant du concert qui commence le plus tôt.
def plus_tot(dico_concert:dict) -> str :
return
Question 3 - En utilisant cette première stratégie gloutonne, écrire une fonction strategie1. Cette fonction prend en paramètre un dictionnaire de concerts (selon la forme indiquée à la question 1).
Elle retourne la liste des concerts (leurs identifiants) dans l'ordre de participation.
def strategie1(dico_concert:dict) -> list :
return
La solution de cet algorithme est la suite de concerts suivant :
['A', 'C', 'F', 'I', 'J'], soit un total de 5 concerts. Cette solution est correcte, mais n'est pas solution optimale.
¶ Stratégie 2
Cette secondes stratégie consiste à choisir le concert dont l'heure de fin arrive le plus tard parmi tous les spectacles compatibles.
Question 4 - Écrire une fonction plus_tard. Cette fonction prend en paramètre un dictionnaire de concerts (selon la forme indiquée à la question 1). Elle retourne l'identifiant du concert qui termine le plus tard.
def plus_tard(dico_concert:dict) -> str :
return
Question 5 - En utilisant cette seconde stratégie gloutonne, écrire une fonction strategie2. Cette fonction prend en paramètre un dictionnaire de concerts (selon la forme indiquée à la question 1).
Elle retourne la liste des concerts (leurs identifiants) dans l'ordre de participation.
def strategie2(dico_concert:dict) -> list :
return
La solution de cet algorithme est la suite de concerts suivant :
['B', 'D', 'E', 'F', 'I', 'J'], soit un total de 6 concerts. Cette solution est correcte et optimale.
¶ Exercice 5 - Problème du voyageur de commerce
Un voyageur de commerce doit parcourir une certaine liste de villes (un seul passage par ville) dont il connaît les distances entre deux villes quelconques.
Il souhaite connaitre l'ordre des villes par lesquelles il doit passer afin de réaliser la distance la plus courte et ensuite revenir à la ville de départ.
Pour notre exemple, on considère les 6 villes suivantes, où les distances entre chacun d'elles sont représentées dans le tableau.
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | 0 | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | 0 | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | 0 | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | 0 | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | 0 | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | 0 |
¶ La méthode par force brute
Une solution possible pour trouver le meilleur trajet serait de générer tous les chemins possibles et de repérer le chemin le plus court.
La formule pour trouver le nombre de chemins dépend du nombre de villes à parcourir. Avec un nombre de villes , la formule est .
Pour notre exemple avec 6 villes, il y aurait 60 parcours différents, ce qui reste abordable.
Avec 4 villes supplémentaires, le problème devient plus complexe.
Question 1 - Exécuter ce code afin de calculer le nombre de parcours existants avec 10 villes.
>>> import math
>>> math.factorial(10-1)//2
Plus de 180 000 possibilités différentes. Pour un problème comportant juste 10 villes !
Question 2 - Essayer maintenant avec 12 villes.
>>> import math
>>> math.factorial(12-1)//2
Environ 20 millions de parcours. Il est alors impossible d'utiliser cette solution pour avoir un résultat pertinent en termes de coût. Il faut utiliser une autre solution.
¶ La méthode gloutonne
On utilise le dictionnaire des distances suivants :
distances = { 'brest':{'brest':0, 'bordeaux':598, 'lille':708, 'lyon':872, 'marseille':1130, 'paris':572},
'bordeaux':{'brest':598, 'bordeaux':0, 'lille':802, 'lyon':520, 'marseille':637, 'paris':554},
'lille':{'brest':708, 'bordeaux':802, 'lille':0, 'lyon':650, 'marseille':1002, 'paris':225},
'lyon':{'brest':872, 'bordeaux':520, 'lille':650, 'lyon':0, 'marseille':367, 'paris':465},
'marseille':{'brest':1130, 'bordeaux':637, 'lille':1002, 'lyon':367, 'marseille':0, 'paris':777},
'paris':{'brest':572, 'bordeaux':554, 'lille':225, 'lyon':465, 'marseille':777, 'paris':0},
}
Question 3 - En utilisant un algorithme glouton, écrire la fonction parcours. Cette fonction prend en paramètre un dictionnaire ou une liste permettant de stocker les distances entre chaque ville et une chaine de caractères représentant la ville de départ. Elle retourne un tuple composé de la liste des villes à traverser et de la distance totale.
def parcours(distances:dict, depart) -> tuple:
return
Question 4 - Essayer votre fonction en partant de Lyon. Vous devez obtenir le trajet ['lyon', 'marseille', 'bordeaux', 'paris', 'lille', 'brest', 'lyon' pour un total de 3 363 km.