Exercice 3 - Partie A : Graphes · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2 bis)

Exercice 3 (8 points)

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

Partie A

Nous avons représenté un parc d’attractions par un graphe. Les sommets de ce graphe sont des attractions. Chaque attraction a une durée (en minutes). Les arêtes de ce graphe représentent la durée (en minutes) pour aller d’une attraction à une autre. Dans ce parc d’attractions, toutes les attractions ont des noms uniques.

Les attractions sont représentées par des objets de la classe Attraction dont le code est donné ci-dessous.

class Attraction:

def __init__(self, nom, duree):

self.nom = nom

self.duree = duree

self.voisines = []

Le graphe précédent peut être représenté, d’une façon incomplète, en langage Python ainsi:

Par mesure de sécurité, les gérants du parc d'attractions ont ralenti la vitesse de rotation de la grande roue. Sa durée est maintenant de 12 minutes.

1.

En considérant la modélisation du parc d'attractions ci-dessus, écrire une ligne de code permettant de faire cette modification.

2.

Donner et expliquer la valeur de l'expression a2.voisines[2][1].

3.

Expliquer la ligne 7 de ce code.

4.

Recopier et compléter la ligne 8 de ce code.

5.

Expliquer pourquoi cette modélisation du parc d'attractions est réalisée avec un graphe non orienté.

Pour faciliter la gestion du parc d'attractions, ses dirigeants proposent aux usagers des balades dans le parc. Une balade est un chemin du graphe représentant le parc d'attractions. Les usagers choisissant une balade doivent faire les attractions dans l'ordre de parcours du chemin. La durée d'une balade est la durée totale pour parcourir la balade, c'est-à-dire la somme des durées de ses sommets et de ses arêtes.

En langage Python, on modélise une balade par un tableau de sommets du graphe. Par exemple, le tableau [a1, a2, a3, a1, a3] est une balade du graphe précédent.

6.

Calculer la durée en minutes de la balade représentée par le tableau [a1, a2, a3] et expliquer le calcul effectué en une phrase.

7.

Expliquer pourquoi le tableau [a2, a1, a4, a3] n'est pas une balade du parc d'attractions.

On considère qu'il est possible de comparer des objets de la classe Attraction entre eux à l'aide de l'opérateur ==.

8.

Écrire une fonction sont_voisines qui prend comme arguments deux attractions de la classe Attraction et qui renvoie True si ces deux attractions sont voisines et False sinon.

def sont_voisines(attr1, attr2):

9.

Écrire une fonction est_balade qui prend comme argument un tableau de sommets de type Attraction et qui renvoie True si ce tableau est une balade et False sinon.

def est_balade(tableau):

Les gérants du parc d'attractions souhaitent automatiser la création de balades, de telle sorte que désormais chaque attraction apparaisse au maximum une fois dans la balade. Pour cela, ils proposent de faire un parcours de graphe à partir d'une des attractions du parc, avec un tableau pouvant représenter une balade en paramètre. Pendant le parcours du graphe, si une attraction est atteignable depuis la dernière attraction placée dans la balade, alors elle est ajoutée à la balade.

Le code suivant est proposé:

1 def parcours(attr, deja_vues, balade, nb):

2 if not attr.nom in deja_vues:

3 deja_vues[attr.nom] = True

4 if nb == 0 or sont_voisines(attr, balade[nb-1]):

5 balade[nb] = attr

6 nb = nb + 1

7 for voisine in attr.voisines:

8 nb = parcours(voisine[0], deja_vues, balade, nb)

9 return nb

10.

Donner le type de parcours effectué par la fonction parcours ci-dessus.

Chaque attraction apparaît au maximum une fois dans une balade. Ainsi, un tableau représentant la balade peut être initialisé à [None, None, None, None] si le parc d'attractions n'a que 4 attractions. Si à l'issue du parcours, les attractions n'ont pas été toutes utilisées, il sera possible de créer une copie partielle du tableau contenant uniquement les éléments différents de None.

11.

Déterminer ce que contient le tableau balade après l'exécution du code ci-dessous, en utilisant les variables a1, a2, a3 et a4:

>>> balade = [ None for _ in range(4) ]

>>> parcours(a4, {}, balade, 0)

12.

Déterminer maintenant ce que contient le tableau tableau après l'exécution du code ci-dessous:

>>> a2.voisines = [(a1,7), (a3,3)]

>>> a4.voisines = [(a3,6)]

>>> tableau = [ None for _ in range(4) ]

>>> parcours(a3, {}, tableau, 0)

13.

Déduire des appels à la fonction parcours le nom de la structure de données utilisée pour la variable deja_vues et expliquer en une phrase son rôle.