Exercice 1 - Algorithmes et complexité · Bac Numérique et Sciences Informatiques Asie 2026 (jour 1)

Partie B

Jessica a en charge d’amener les costumes et accessoires pour les représentations. Afin de minimiser les allers-retours, elle essaie d’optimiser le chargement de son véhicule à l’aide d’un programme.

Pour chaque représentation, elle a récupéré les informations utiles sous forme d’un dictionnaire de dictionnaires. Les sous-dictionnaires contiennent le nombre d’éléments nécessaires, le volume unitaire ainsi que le poids unitaire. Par exemple:

dmateriel = {

'costume_A': {'nb': 3, 'volume': 2, 'poids': 1},

'costume_B': {'nb': 1, 'volume': 6, 'poids': 2},

'chaise_bois': {'nb': 40, 'volume': 50, 'poids': 4},

'chapeau_A': {'nb': 2, 'volume': 3, 'poids': 1},

'chapeau_B': {'nb': 4, 'volume': 7, 'poids': 1},

}

8.

Pour optimiser le volume chargé dans son véhicule, Jessica se dit qu'une bonne stratégie serait de remplir son véhicule du matériel le plus volumineux en premier puis de finir de le remplir par du petit matériel.

Préciser à quel type d'algorithme vu en cours cette stratégie fait référence.

9.

Pour le moment, on suppose que la fonction clefs_triees_selon_volume prend en paramètre un dictionnaire dmatos contenant le matériel et renvoie la liste des clefs de dmatos triée dans l'ordre croissant des volumes unitaires associés à chacune des clefs. Ainsi on a:

>>> clefs_triees_selon_volume(dmateriel)

['costume_A', 'chapeau_A', 'costume_B', 'chapeau_B', 'chaise_bois']

Citer un algorithme de tri vu en cours et donner un ordre de grandeur de son coût en temps d'exécution en fonction de la taille $n$ de la liste à trier.