1. Écrire une fonction nbr_pièces_dictmonnaie qui accepte un dictionnaire dont les clefs sont des entiers représentant des centimes et dont les valeurs sont des entiers représentant un nombre de pièce et qui retourne le nombre total de pièces. Ainsi l'appel nbr_pièces_dictmonnaie({1: 10, 4: 2}) doit retourner 12.
2. Écrire une fonction total_dictmonnaie qui accepte un dictionnaire dont les clefs sont des entiers représentant des centimes et dont les valeurs sont des entiers représentant un nombre de pièce et qui retourne le montant total en centimes. Ainsi l'appel total_dictmonnaie({1: 10, 4: 2}) doit retourner 18.
3. Écrire une fonction total_listmonnaie qui accepte une liste de couples d'entiers dont le premier élément représente des centimes et le second un nombre de pièce et qui retourne le montant total en centimes. Ainsi l'appel total_listmonnaie([(1, 10), (4, 2)]) doit retourner 18.
4. Vaut-il mieux privilégier total_dictmonnaie ou total_listmonnaie?

• meme_rendus({1: 3}, {1: 3, 2: 0}) doit renvoyer True.
• meme_rendus({1: 3}, {1: 4}) doit renvoyer False.
• meme_rendus({1: 3}, {1: 3, 2: 1}) doit renvoyer False.

On souhaite écrire une fonction rendu_monnaie_illimite

• qui accepte deux arguments qui sont
  • un entier représentant un montant en centimes à rendre
  • et une liste d'entiers triés dans l'ordre strictement décroissant représentant les montants des pièces qui peuvent être utilisées pour le rendu (on supposera ici que l'on dispose d'autant de pièces de chaque type que nécessaire). À cette question on supposera que 1 fait partie de cette liste c'est à dire que l'on peut utiliser des pièces de 1 centimes pour le rendu de monnaie si bien que le rendu est toujours possible (quitte à n'utiliser que des pièces de 1 centimes)
• et qui retourne un dictionnaire donnant pour chaque type de pièce (représenté par sa valeur) le nombre de pièces correspondantes à rendre ou bien lève une exception.

Pour cela on utilise un algorithme dit glouton: on rend systématiquement la plus grosse pièce possible (c'est à dire inférieur à ce qu'il reste à rendre). Par exemple

• rendu_monnai(6, [2, 1]) doit renvoyer {2: 3} mais ni {6: 1} ni {2: 4, 1:2}.
• rendu_monnai(4, [3, 2]) échoue car il rend d'abord 3 puis ne peut plus rendre la monnaie.

Écrire une telle fonction rendu_monnaie_illimite et vérifier qu'avec des pièces de valeurs 1, 3 et 4 l'algorithme glouton n'est pas toujours optimal en nombre de pièces utilisées pour le rendu.

On souhaite écrire une fonction rendu_monnaie

• qui accepte deux arguments qui sont
  • un entier représentant le montant en centimes à rendre;
  • et un dictionaire d'entiers qui à chaque montant de pièce existant associe le nombre (qui peut être nul) de pièces de ce type disponibles pour le rendu;
• et qui retourne un dictionnaire donnant pour chaque type de pièce (toujours représenté par sa valeur) le nombre de pièces correspondantes à rendre si le rendu de monnaie est possible et None sinon.

Pour cela on utilisera un algorithme récursif. Aide: pour le calcul de rendu_monnaie(S, dict) on pourra penser à rendre une pièce de monnaie d'un montant montant_piece puis voir si on peut maintenant rendre la monnaie sur S-montant_piece (avec une pièce de ce type en moins!)…

Un premier algorithme glouton auquel on peut penser est le suivant: on tri les demandes par heure de début de conférence (remarquons que cet ordre n'est pas unique car des demandes peuvent être distinctes et commencer à la même heure: la relation binaire utilisée n'est pas une relation d'ordre car elle n'est pas antisymétrique) puis on parcourt les demandes dans cet ordre

• en commençant avec une liste de demandes retenues vide;
• puis
  • si la demande courante n'est pas incompatible avec celles qui ont déjà été retenues alors on ajoute cette demande aux demandes retenues;
  • si la demande courante est incompatible avec une demande déjà retenue (c'est à dire avec cet algorithme avec la dernière demande retenue) alors on passe à la demande suivante.

Remarquons qu'avec cet algorithme si une demande commence strictement avant toutes les autres alors elle sera nécessairement retenue (en premier). Ainsi avec les \(4\) demandes \(\interfo{0}{6}\), \(\interfo{1}{2}\), \(\interfo{3}{4}\), \(\interfo{4}{7}\) et \(\interfo{6}{7}\) représentées graphiquement ci-dessous

l'algorithme

• part d'une liste de demandes acceptées vide;
• y ajoute \(\interfo{0}{6}\);
• ignore dans l'ordre les demandes \(\interfo{1}{2}\), \(\interfo{3}{4}\), \(\interfo{4}{7}\) car elles sont incompatibles avec la demande acceptée \(\interfo{0}{6}\);
• puis ajoute \(\interfo{6}{7}\);

et on obtient donc l'ordonnancement suivant

qui n'est pas optimal car il est possible de planifier \(3>2\) conférences.

1. Copier-coller le code ci-dessous et compléter la fonction teste_tri_liste_demandes_par_date_debut qui doit tester la fonction tri_liste_demandes_par_date_debut (qui doit évidemment avoir un fonctionnement conforme à sa documentation)

   def tri_liste_demandes_par_date_debut(L):
       """Fonction qui retourne une copie triée  la liste de demandes L triée
       par heure de début.
   
       Arguments:
         L: liste de couples (ou de listes de longueur 2) de valeurs
         numériques (entiers ou flottants)
       Retourne:
         une copie de L où les demandes sont triée par heure de début
       """
       if type(L) != tuple and type(L) != list:
           raise Exception("Les demandes doivent être représentées par un tuple/une liste")
       return sorted(L, key=lambda demande: demande[0])
   
   def teste_tri_liste_demandes_par_date_debut():
       assert ...
       assert ...
   
   teste_tri_liste_demandes_par_date_debut()
   

2. Écrire une fonction deux_creneaux_sont_compat qui accepte deux couples de valeurs numériques et retourne True si elles sont compatibles et False sinon (sans hypotheses sur les dates de début ou de fin ou la longueur de ces demandes). Remarquons que deux créneaux sont compatible ssi l'un est tout entier avant ou tout entier après l'autre…
3. En déduire une fonction liste_creneaux_tous_compat_avec_autre_creneau qui accepte une liste de creneaux et un creneau en arguments et qui retourne True si le creneau donné en argument est compatible avec tous les créneaux de la liste et False sinon.
4. Écrire une fonction algo_glouton_min_heure_debut implémentant l'algorithme glouton d'affectation décrit ci-dessus (on utilisera les fonctions tri_liste_demandes_par_date_debut et deux_creneaux_sont_compat).

On change d'algorithme d'affectation pour un autre algorithme glouton: au ileu de minimiser localement (c'est à dire à chaque étape) l'heure de début des demandes retenues on choisit de minimiser localement la longueur des demandes (càd parmi les demandes qui sont compatibles avec celles déjà retenues on choisit la demande \(\interfo{d_{i}}{f_{i}}\) minimisant \(f_{i}-d_{i}\)) tant que cela est possible. Ainsi avec les demandes

l'algorithme

• part d'une liste de demande acceptées vide;
• y ajoute \(\interfo{0}{1}\);
• y ajoute \(\interfo{3}{5}\).

et on obtient donc l'ordonnancement non optimal suivant

1. Copier-coller le code ci-dessous et compléter la fonction teste_tri_liste_demandes_par_longueur qui doit tester la fonction tri_liste_demandes_par_longueur (qui doit évidemment avoir un fonctionnement conforme à sa documentation)

   def tri_liste_demandes_par_longueur(L):
       """Fonction qui retourne une copie triée  la liste de demandes L triée
       par longueurs croissantes.
   
       Arguments:
         L: liste de couples (ou de listes de longueur 2) de valeurs
         numériques (entiers ou flottants)
       Retourne:
         une copie de L où les demandes sont triée par heure de début
       """
       if type(L) != tuple and type(L) != list:
           raise Exception("Les demandes doivent être représentées par un tuple/une liste")
       return sorted(L, key=lambda demande: demande[1]-demande[0])
   
   def teste_tri_liste_demandes_par_longueur():
       L = [[2, 4], [1, 5], [0, 6]]
       res = ??
       assert tri_liste_demandes_par_longueur(L) == res
       L = [[2, 4], [1, 5], [0, 6]]
       res = ??
       assert tri_liste_demandes_par_longueur(L) == res
       L, res = [], []
       assert tri_liste_demandes_par_longueur(L) == res
   
   teste_tri_liste_demandes_par_longueur()
   

2. Écrire une fonction algo_glouton_min_longueur_creneau implémentant l'algorithme glouton d'affectation décrit ci-dessus (on utilisera les fonctions tri_liste_demandes_par_longueur et deux_creneaux_sont_compat).