Exercice 3 - Arbres · Bac Numérique et Sciences Informatiques Polynésie 2026 (jour 2)

Cet exercice porte sur le routage et sur l'utilisation d'une structure arborescente.

Partie A

Rappels:

Une adresse IPv4 est composée de 4 octets, soit 32 bits. Elle est notée a.b.c.d, où a, b, c et d sont les valeurs décimales des 4 octets.

La notation a.b.c.d/n, appelée notation CIDR (Classless Inter Domain Routing), signifie que les n premiers bits à gauche de l'adresse IP représentent la partie « réseau », les bits à droite qui suivent représentent la partie « machine ».

On donne la table de routage suivante:

$ ip route show scope global table 100

default via 10.0.0.5 dev out2

172.16.0.0/25

nexthop via 10.0.0.7 dev out3 weight 1

nexthop via 10.0.0.9 dev out4 weight 1

172.16.0.10 nexthop via 10.0.0.3 dev out1

172.16.0.20 nexthop via 10.0.0.3 dev out1

172.16.0.30 nexthop via 10.0.0.3 dev out1

172.16.0.40 nexthop via 10.0.0.3 dev out1

Un calculateur de masque IPv4 donne les informations suivantes après avoir saisi la commande 172.16.0.0/25:

Partie B

Dans cette partie, on se propose de mettre en œuvre une structure arborescente pour la manipulation d'une table de routage.

IP destination

Prochain saut

168.16.0.100 · 10.0.0.3

168.16.0.200 · 10.0.0.4

203.18.17.10 · 10.0.0.5

0.0.0.0 · 10.0.0.6

168.16.0.10 · 10.0.0.7

203.18.15.30 · 10.0.0.8

203.18.15.20 · 10.0.0.9

203.18.15.10 · 10.0.0.10

Chaque nœud de l'arbre contient un dictionnaire qui associe à une lettre un nœud enfant. Depuis la racine de l'arbre, le chemin parcouru jusqu'à un nœud est une suite d'arêtes pondérées chacune par une lettre. Ce chemin forme un mot.

Si ce mot est une adresse IP de destination dans la table de routage, le nœud contient l'adresse IP du prochain saut. De plus, si le dictionnaire des successeurs n'est pas vide, ce mot est le préfixe d'au moins une adresse IP de prochain saut.

Après insertion des quatre premières lignes, on obtient:

8.

Recopier et compléter l'arbre correspondant à la table de routage proposée.

La classe Noeud est définie comme suit:

1 class Noeud():

2 def __init__(self):

3 self.saut = ''

4 self.dict_adjacence = {}

5 def rechercher_enfant(self, octet):

6 if not (octet in self.dict_adjacence):

7 return...

8 return...

Les instances de cette classe contiennent deux attributs:

saut qui est une chaîne de caractères non nulle lorsque le chemin suivi pour atteindre ce nœud correspond à une adresse IP de destination;

dict_adjacence qui est un dictionnaire contenant des couples octet, enfant.

La classe contient une méthode rechercher_enfant qui prend en paramètre un octet et qui renvoie le nœud correspondant à cet octet depuis le nœud courant. Si l'octet n'est pas enregistré dans le dictionnaire du nœud, la fonction renvoie None.

9.

Compléter les lignes 7 et 8 de la fonction rechercher_enfant donnée ci-dessus.

La classe Arbre est définie comme suit:

1 class Arbre():

2 def __init__(self):

3 self.racine = Noeud()

4 def rechercher(self, ip_dest):

5 # Corps de la fonction rechercher

6...

11 def mystere(self, ip_dest, saut):

12 noeud = self.racine

13 octets = ip_dest.split('.')

14 i = 0

15 while i < len(octets):

16 noeud_suivant = noeud.rechercher_enfant(octets[i])

17 if noeud_suivant is not None:

18 noeud_suivant = Noeud()

19 noeud.dict_adjacence[octets[i]] = noeud_suivant

20 noeud = noeud_suivant

21 i = i+1

22 noeud.saut = saut

Les instances de cette classe contiennent un attribut racine qui est un nœud.

La classe contient deux méthodes:

rechercher qui renvoie le nœud atteint après le parcours du chemin correspondant à ip_dest. Si ip_dest n'est pas dans l'arbre, la fonction renvoie None;

mystere qui prend pour paramètre un ip_dest et un saut.

Pour rappel, la fonction split en Python divise une chaîne de caractères en une liste de sous-chaînes en fonction d'un séparateur spécifié.

Par exemple: 'Bonjour-le-monde'.split('-') donne comme résultat ['Bonjour', 'le', 'monde'].

10.

Compléter le corps (à partir de la ligne 6) de la fonction rechercher.

11.

Expliquer, en justifiant, le rôle de la fonction mystere.

On souhaite maintenant inverser la table de routage c'est-à-dire associer à un saut possible une adresse IP de destination.

12.

On possède un arbre contenant les informations d'une table de routage. Proposer un algorithme permettant d'inverser cette table.