Exercice 2 - Coût des algorithmes et tris · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 1)

Cet exercice porte sur la programmation orientée objet, la récursivité et les algorithmes gloutons.

Une entreprise souhaite gérer les colis qu'elle expédie à l'aide d'une application informatique. On sait que chaque colis a un identifiant unique, un poids, une adresse de livraison et un état. Pour chacun d'entre eux, trois états sont possibles: « préparé », « transit » ou « livré ».

Pour cela, on a créé une classe Colis avec les attributs suivants:

id: un identifiant unique (de type str);

poids: le poids du colis en kilogrammes (de type float);

adresse: l'adresse de destination (de type str);

etat: l'état du colis (de type str parmi 'préparé', 'transit', 'livré').

Lorsque l'on crée une instance de la classe Colis, l'attribut etat est initialisé à 'préparé' tandis que les valeurs des autres attributs sont passées en paramètres. Voici le début du code Python de la classe Colis:

class Colis:

def __init__(self, id, poids, adresse):

self.id = id

self.poids = poids

self.adresse = adresse

self.etat = 'préparé'

On crée, par exemple, les deux colis suivants:

colisA = Colis('AC12', 5.0, '20 rue de la paix 57000 Metz')

colisB = Colis('AF34', 10.25, '32 rue du centre 57000 Metz')

L'entreprise tente d'optimiser, à l'aide d'un algorithme glouton, le chargement des colis dans un camion ayant une capacité exprimée en kilogrammes, sans tenir compte de la contrainte de volume. La procédure gloutonne adoptée est la suivante: on charge les colis dans le camion en les choisissant par ordre décroissant de leur poids, sans dépasser la capacité du camion.

Pour cela, il est nécessaire de travailler sur une liste de colis triés par ordre de poids décroissants. La fonction tri_decroissant permet de réaliser ce tri.

def tri_decroissant(liste):

n = len(liste)

for i in range(n - 1):

min_pos = i

for j in range(i + 1, n):

if liste[j].poids > liste[min_pos].poids:

min_pos = j

# Échanger les éléments

temp = liste[i]

liste[i] = liste[min_pos]

liste[min_pos] = temp

return liste 6.

Donner le nom du tri utilisé dans la fonction tri_decroissant ainsi que son coût dans le pire des cas.

7.

Citer un autre algorithme de tri qui aurait pu être utilisé, ainsi que son coût dans le pire des cas.