Exercice 3 - Partie D : Arbres binaires de recher… · Bac Numérique et Sciences Informatiques Métropole 2025 (sujet 1)

Cet exercice porte sur l'architecture matérielle (réseau), les arbres binaires de recherche et la programmation Python.

L'entreprise CaféNet possède plusieurs cafés répartis dans différentes villes. Le réseau de la chaîne de cafés est représenté en Figure 1.

Sur le schéma sont représentés 4 routeurs, le réseau du siège social, le réseau du café 1, le réseau du café 2. Dans les réseaux du café 1 et du café 2, des bornes de commandes sont connectées à des switchs (ce sont des boitiers de connexion qui n'ont pas eux-mêmes d'adresse IP). Les 4 routeurs représentés sont composés d'au moins 3 interfaces réseau capable de relier des réseaux ensemble. Chaque interface possède donc une adresse IPV4 sur le réseau auquel elle est reliée.

Les masques des sous-réseaux sont tous 255.255.255.0. Avec ce masque, les trois premiers octets des adresses IP codent l'adresse réseau. Le dernier octet, c'est-à-dire les 8 derniers bits, code l'adresse des machines à l'intérieur de chaque sous-réseau.

Partie D: Arbres binaires de recherche

Le but de cette partie est de classer les adresses IP des différents réseaux afin de faciliter leur recherche.

La fonction ip_bin prend en argument une chaîne de caractères décrivant une adresse IP en notation décimale, et renvoie une chaîne de caractères, de longueur 35 (32 bits et les 3 points), décrivant l'adresse IP en notation binaire.

>>> ip_bin('192.168.10.1')

'11000000.10101000.00001010.00000001'

10.

Donner la chaîne de caractères renvoyée par ip_bin('192.168.20.12').

La fonction precede prend en paramètres deux adresses IP en notation binaire, sous forme de chaînes de caractères identiques à celles renvoyées par la fonction ip_bin. La fonction precede renvoie un booléen qui vaut True si la première adresse IP en paramètre précède la seconde adresse IP.

>>> a = '11000000.10101000.00001010.00000001'

>>> b = '11000000.10101000.00001111.00000001'

>>> precede(a, b)

True

L'algorithme compare bit à bit les deux chaînes binaires, en lisant les chaînes de caractères dans le sens usuel (de gauche à droite). Dans l'exemple ci-dessus, tous les caractères sont identiques jusqu'au sixième caractère du troisième octet. Comme le bit de l'adresse a est inférieur à celui de l'adresse b, on en déduit que l'adresse IP a précède l'adresse IP b.

Si la première adresse IP ne précède pas la seconde, la fonction doit renvoyer False.

L'algorithme de comparaison est traduit dans le langage Python sous la forme suivante:

1 def precede(ip_1, ip_2):

2 for i in range(35):

3 if ip_1[i] < ip_2[i]:

4 return...

5 elif ip_1[i] > ip_2[i]:

6 return...

7 return...

11.

Expliquer dans quel cas la fonction precede exécutera la dernière instruction return de la ligne 7.

12.

Recopier et compléter les lignes 4, 6 et 7 du code de la fonction precede.

Ligne 4: return

Ligne 6: return

Ligne 7: return

Les tables de routage de chaque routeur sont implémentées sous la forme d'arbre binaire de recherche avec la classe Abr.

1 class Abr:

2 def __init__(self, adresse_ip,

3 interface, passerelle,

4 cout):

5 self.adresse_ip = adresse_ip

6 self.interface = interface

7 self.passerelle = passerelle

8 self.cout = cout

9 if adresse_ip != '':

10 self.gauche = Abr('', '', '', 0)

11 self.droite = Abr('', '', '', 0)

12

13 def est_vide(self):

14 return...

Dans cette représentation:

adresse_ip désigne l'adresse IP de la destination;

interface désigne l'interface réseau;

passerelle désigne l'adresse IP du prochain routeur;

cout désigne le nombre de sauts pour atteindre la destination;

par convention, l'arbre binaire vide est une instance de Abr pour laquelle adresse_ip est une chaîne de caractères vide;

un arbre binaire de recherche non vide possède nécessairement un sous-arbre gauche et un sous-arbre droit, éventuellement vides, qui sont tous les deux des arbres binaires de recherche. Ces sous-arbres sont désignés par gauche et droite dans la classe Abr;

si elle n'est pas vide, l'adresse IP du sous-arbre gauche précède l'adresse IP de l'instance parent;

si le sous-arbre droit n'est pas vide, alors l'adresse IP de l'instance parent précède l'adresse IP du sous-arbre droit.

13.

Citer un attribut et citer une méthode de la classe Abr.

14.

Recopier et compléter la ligne 14 du code de la classe Abr.

Ligne 14: return

15.

Justifier, en mobilisant des connaissances de cours, l'intérêt qu'il peut y avoir à représenter la table de routage par un arbre binaire de recherche.

La section de code qui définit modifie est incluse dans la classe Abr.

16 def modifie(self, adresse_ip,

17 interface, passerelle,

18 cout):

19 if self.est_vide():

20 self.adresse_ip = adresse_ip

21 self.interface = interface

22 self.passerelle = passerelle

23 self.cout = cout

24 self.gauche = Abr('', '', '', 0)

25 self.droite = Abr('', '', '', 0)

26 else:

27 self.adresse_ip = adresse_ip

28 self.interface = interface

29 self.passerelle = passerelle

30 self.cout = cout

Les lignes 20 à 23 sont exactement les mêmes que les lignes 27 à 30.

16.

Réécrire le code de la fonction modifie en évitant cette répétition.

La classe Abr est complétée afin de permettre l'ajout de nouvelles lignes à la table de routage, tout en conservant les propriétés que doit posséder un arbre binaire de recherche.

32 def rechercher(self, adresse_ip):

33 if self.est_vide() or adresse_ip==self.adresse_ip:

34 return self

35 elif precede(...):

36 return self.gauche.rechercher(adresse_ip)

37 else:

38 return self.droite.rechercher(adresse_ip)

39

40 def inserer(self, adresse_ip,

41 interface, passerelle,

42 cout):

43 destination = self.rechercher(adresse_ip)

44 destination.modifie(adresse_ip,

45 interface, passerelle,

46 cout)

On rappelle que la fonction precede prend en arguments des adresses IP écrites sous forme binaire.

17.

Recopier et compléter la ligne 35 du code de la fonction rechercher.

Ligne 35: elif precede(

):