Exercice 3 - Parties B et C : Routage RIP · Bac Numérique et Sciences Informatiques Asie 2026 (jour 2)

Exercice 3 (8 points)

Cet exercice porte sur la programmation Python et le routage RIP.

On étudie dans cet exercice des robots qui peuvent se déplacer et communiquer entre eux.

Partie A: Gestion des déplacements du robot

Chaque robot peut se déplacer en avant et tourner de 90 degrés à droite ou à gauche. Il reçoit ses instructions sous la forme d'une chaîne de caractères contenant des lettres et éventuellement des entiers et des parenthèses. S'il lit un 'A', le robot avance d'une distance correspondant à "un pas" (valeur fixée dans les réglages du robot). Il tourne à droite s'il lit un 'D' et à gauche s'il lit un 'G'.

Insérer un entier dans la chaîne permet de répéter une action ou une suite d'actions écrites entre parenthèses.

'12A' est équivalent à 'AAAAAAAAAAAA', '3(AD)' est équivalent à 'ADADAD'.

La figure 1 représente le parcours du robot lorsqu'il reçoit la chaîne '3ADA'

Partie B: Communication et routage

On considère un réseau de robots. Chaque robot peut communiquer par radio avec les robots qui se trouvent à proximité.

Si deux robots sont assez proches l'un de l'autre, ils peuvent communiquer directement. Lorsque deux robots sont trop éloignés l'un de l'autre, le message est relayé de robot en robot jusqu'à son destinataire.

On représente un réseau de robots par un graphe dont les arêtes symbolisent la possibilité de communiquer entre deux robots.

Exemple: Dans la configuration ci-dessous, si le robot numéro 4 veut envoyer un message au robot 12, il devra le transmettre au robot 46 qui le transmettra alors au robot 12.

Le routage des messages est effectué à l'aide du protocole RIP qui minimise la distance calculée en nombre de sauts réalisés entre deux routeurs. Chaque robot joue le rôle d'un routeur: il maintient une table de routage dans laquelle figurent les informations permettant de joindre les autres robots connus.

Une table de routage contient trois colonnes:

la colonne « destination » donne l'identifiant du robot à atteindre;

la colonne « prochain robot » donne l'identifiant du prochain robot sur le chemin vers la destination;

la colonne « distance » indique le nombre total de transmissions à effectuer pour joindre la destination.

Exemple: Le réseau suivant est constitué par les robots 46, 4, 57, 91, 22 disposés comme dans le graphe ci-dessous.

La table de routage du robot 91 est:

destination

prochain robot

distance

4 · 4 · 1

46 · 22 · 3

22 · 22 · 1

57 · 22 · 2

On suppose maintenant qu'à la suite d'un déplacement du robot 4, une liaison directe avec le robot 46 est possible:

8.

Indiquer les modifications apportées à la table de routage du robot 91.

Un nouveau robot, portant l'identifiant 87, rejoint le réseau en contactant le robot numéro 91. Il lui envoie sa table de routage:

Table de routage du robot 87:

destination

prochain robot

distance

91 · 91 · 1

63 · 63 · 1

36 · 63 · 2

9.

Décrire les nouvelles modifications à apporter à la table de routage du robot 91.

Partie C: Programmation du routage

Afin de gérer la communication entre les robots du réseau, on implémente la classe Module_comm et chaque robot possède une instance de cette classe.

class Module_comm:

def __init__(self, id_robot):

self.identifiant = id_robot

self.table_routage = {}

Chaque clé du dictionnaire table_routage est l'identifiant d'un robot du réseau. La valeur associée est un dictionnaire donnant le premier robot sur le chemin vers ce robot ainsi que le nombre total de transmissions c'est-à-dire le nombre de sauts à effectuer.

La table du routage du robot 91 de la figure 3 est implémentée comme suit:

{

4: {"prochain": 4, "distance": 1},

46: {"prochain": 22, "distance": 3},

22: {"prochain": 22, "distance": 1},

57: {"prochain": 22, "distance": 2}

}

10.

La méthode ajouter_voisin prend en paramètre l'identifiant d'un robot avec lequel il peut directement communiquer puis crée une entrée dans le dictionnaire table_routage.

Écrire le code de la méthode ajouter_voisin.

def ajouter_voisin(self, id_robot):

11.

La méthode nombre_sauts prend en paramètre l'identifiant d'un robot et renvoie le nombre de sauts nécessaires pour communiquer avec ce robot. Pour cette implémentation, on fixe le nombre de sauts maximum à 15.

Si l'identifiant reçu par nombre_sauts ne figure pas dans la table de routage, la fonction renvoie la valeur 16.

Recopier et compléter la ligne 5 du code de la méthode nombre_sauts:

def nombre_sauts(self, identifiant):

if identifiant not in self.table_routage:

return 16

else:

return...

Ligne 5: return

12.

Écrire le code de la méthode voisins qui renvoie la liste de tous les robots avec lesquels il peut directement communiquer.

def voisins(self):

13.

Afin de ne pas communiquer d'informations inutiles, on souhaite communiquer à un robot voisin l'extrait de la table de routage qui contient uniquement les lignes pour lesquelles ce robot voisin n'est lui-même pas le prochain robot sur la route.

La méthode communiquer_extrait_table prend en paramètre l'identifiant d'un robot voisin et communique cet extrait de la table de routage. L'extrait de table renvoyé est de type dictionnaire et il possède la même structure que la table de routage complète.

Écrire le code de la méthode communiquer_extrait_table.

def communiquer_extrait_table(self, voisin):