Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Métropole 2 remplacement 2025

Cet exercice porte principalement sur les bases de données, les graphes et la programmation de base en Python.

Un supermarché utilise une base de données qui contient des informations sur les produits, les fournisseurs, les commandes passées et leurs détails. Le modèle relationnel de cette base est donné par le schéma ci-dessous:

Dans ce schéma, les clés primaires sont soulignées et les clés étrangères sont précédées du symbole #. Le type de chaque attribut est indiqué entre parenthèses.

On considère l'extrait de la base de données ci-dessous:

Table Commandes

id_commande · date_commande · total_commande

1 · 03/06/2025 · 176.00

2 · 08/12/2024 · 1150.00

3 · 21/04/2025 · 155.00

8.

Déterminer le plus court chemin (en termes de distance) entre Toulouse et Calais.

9.

Écrire la liste des sommets dans l'ordre d'un parcours en profondeur à partir de Calais (les sommets sont toujours pris dans l'ordre alphabétique s'il y a un choix à faire).

10.

Écrire la liste des sommets dans l'ordre d'un parcours en largeur à partir de Calais (les sommets sont toujours pris dans l'ordre alphabétique s'il y a un choix à faire).

Pour implémenter ce graphe, on utilise le dictionnaire en Python ci-dessous:

graphe = {'Paris': {'Strasbourg': 490, 'Lyon': 465,

'Nantes': 385, 'Calais': 300},

'Strasbourg': {'Paris': 490, 'Lyon': 470,

'Calais': 600},

'Lyon': {'Paris': 465, 'Strasbourg': 470,

'Toulouse': 405, 'Nantes': 600},

'Nantes': {'Paris': 385, 'Lyon': 600,

'Bordeaux': 340, 'Calais': 550},

'Calais': {'Paris': 300, 'Strasbourg': 600,

'Nantes': 550},

'Toulouse': {'Lyon': 405, 'Bordeaux': 250,

'Marseille': 400},

'Marseille': {'Toulouse': 400},

'Bordeaux': {'Nantes': 340, 'Toulouse': 250}

}

Dans cette implémentation, il manque la route entre Lyon et Marseille.

11.

Écrire les instructions permettant d'ajouter dans le dictionnaire graphe la route entre les villes de Lyon et Marseille sachant que la distance les séparant est de 315 km.

12.

Écrire une fonction distance qui prend en paramètres le dictionnaire graphe et deux villes (de type str) et qui renvoie la distance entre ces deux villes si elles sont adjacentes, ou None sinon.

def distance(graphe, ville1, ville2):

Pour déterminer le chemin entre deux villes quelconques (s'il en existe un) dans le dictionnaire graphe, on utilise la fonction trouver_chemin(graphe, ville_depart, ville_destination) qui renvoie la liste des villes parcourues. On suppose que cette fonction est codée en Python.

13.

Écrire une fonction distance_totale qui prend en paramètre le dictionnaire graphe et deux villes (de type str) et qui renvoie la distance entre ces deux villes s'il existe un chemin entre elles sinon elle retourne None.

def distance_totale(graphe, ville_depart, ville_destination):

On décide désormais de prendre en compte le temps nécessaire pour parcourir les distances entre les villes.

Ainsi les arêtes du graphe sont pondérées à l'aide d'une liste contenant la distance (en km arrondie à l'unité) et la durée (en heure arrondie à deux décimales) nécessaire pour effectuer le trajet entre les deux villes.

Exemple: >>> graphe['Paris']

{'Strasbourg': [490, 6.37], 'Lyon': [465, 5.58], 'Nantes': [385, 3.47], 'Calais': [300, 3.3]}

14.

À partir de l'exemple précédent, déterminer la valeur de graphe['Paris']['Nantes'][1].

La fonction ratio_duree_distance ci-dessous prend en paramètre le dictionnaire graphe. Elle permet de calculer le ratio durée/distance pour toutes les arêtes du graphe et de l'ajouter à la pondération de chaque arête:

1 def ratio_duree_distance(graphe):

2 for ville, connexions in...:

3 for destination, valeurs in...:

4 distance, duree =...

5 ratio =...

6 graphe[ville][destination].append(...)

7 return graphe

15.

Recopier et compléter la fonction ratio_duree_distance.

def ratio_duree_distance(graphe):

Un élève souhaite utiliser ChatGPT pour trouver un algorithme qui détermine le chemin à privilégier entre deux villes. Il fournit son script Python contenant le dictionnaire graphe (et son descriptif) et les fonctions précédentes. Il écrit le prompt suivant:

« Écris un algorithme, en langage naturel, pour trouver un chemin entre deux villes en minimisant le ratio durée/distance où à chaque étape, on choisira l'arête avec le ratio le plus faible. »

16.

Déterminer le nom que l'on donne à un algorithme qui construit une solution étape par étape, comme celui demandé par l'élève.

17.

Déterminer le chemin trouvé grâce à cet algorithme entre Toulouse et Calais.