La version numérique du sujet fournie en fichier texte (format *.txt) doit être ouverte en tant que braille informatique. Elle sera affichée en braille 6 points. L’application « bloc-notes » des ordinateurs courants, ou des logiciels spécialisés, peut être utilisée. À défaut, reportez-vous à la version en papier.
Le candidat doit rédiger ses réponses sur un second fichier, et peut demander à un assistant ou à un secrétaire de recopier sa production de façon manuscrite sur une copie.
Un fichier en format *.pdf est également fourni.
La page du document original est indiquée par « PO 1 » pour « page originale n°1 ». Les références aux pages braille (sommaire, références en cours de sujet) font référence au sujet braille embossé.


¨¨po `1
`25-¨¨nsij`1me1
¨braille intégral
¨baccalauréat ¨général
¨épreuve d'enseignement de ¨spécialité
¨session `2025
¨numérique et ¨sciences ¨informatiques
¨volume `1: texte
¨épreuve du mardi `17 juin `2025
¨durée de l'épreuve: `3 heures `30
¨l'usage de la calculatrice n'est pas autorisé.
¨dès que ce sujet vous est remis, assurez-vous qu'il est complet.
¨le sujet comporte `17 pages numérotées de `1 à `17 dans la version originale.
¨la version en braille intégral est composée de deux volumes:
9o ¨volume `1: le sujet de `52 pages numérotées de `1 à `52;
9o ¨volume `2: `3 planches tactiles sur papier thermogonflé.
:¸¨le sujet est composé de trois exercices indépendants.
¨le candidat traite les trois ¸exercices.
¨conformément au code braille, les espaces à remplir présents dans l'original sont symbolisés par les signes `-'
¨sommaire
9o ¨exercice `1 (`6 points) `5
-- ¨partie ¨a `6
-- ¨partie ¨b `10
9o ¨exercice `2 (`6 points) `16
9o ¨exercice `3 (`8 points) `33
-- ¨partie ¨a `35
-- ¨partie ¨b `37
-- ¨partie ¨c `40
-- ¨partie ¨d `42
¨¨po `2
¨exercice `1 (`6 points)
¨cet exercice porte sur les bases de données relationnelles et les requ2tes ¨¨sql.
¨dans cet exercice, on pourra utiliser les clauses du langage ¨¨sql pour:
9o construire des requ2tes d'interrogation à l'aide de ¨¨select, ¨¨from, ¨¨where (avec les opérateurs logiques :¨and, or), join ... ¨on;
9o construire des requ2tes d'insertion et de mise à jour à l'aide de ¨¨update, ¨¨insert, ¨¨delete;
9o affiner les recherches à l'aide de ¨¨distinct, ¨¨order ¨¨by.
¨dans un schéma relationnel, on utilisera les conventions suivantes:
9o la clé primaire d'une relation est définie par son attribut souligné `;(mis en évidence dans la version braille)„';
9o les attributs précédés de ´0 sont les clés étrangères.
¨le guitariste ¨slash possède une incroyable collection de guitares. ¨maud est une grande fan de ¨slash. ¨elle décide de faire un inventaire de la collection de guitares sous la forme d'une base de données relationnelle.
¨partie ¨a
¨dans cette partie, ¨maud utilise la relation suivante: 
inventaire (??id**, marque, modele, annee, num´-ser, prix)
num´-ser représente le numéro de série d'une guitare. ¨il est unique pour chaque guitare d'une m2me marque. ¨le prix est en euro.
¨voici un extrait de la table inventaire.
`;¨tableau linéarisé.„'
inventaire
id; marque; modele; annee; num´-ser; prix.
`1; ¨gibson; ¨les ¨paul ¨goldtop; `1956; @`70562; `100'000.
`2; ¨gibson; ¨les ¨paul ¨goldtop; `1988; `81738349; `20'000.
`3; ¨gibson; ¨les ¨paul ¨standard; `1959; @`90663; `250'000.
`4; ¨gibson; ¨les ¨paul ¨standard; `1987; `81757532; `25'000.
`5; ¨fender; ¨telecaster; `1952; `000230; `150'000.
`6; ¨fender; ¨telecaster; `1965; `81345673; `10'000.
`7; ¨fender; ¨stratocaster; `1956; `001359; `200'000.
`8; ¨fender; ¨stratocaster; `1965; `81757532; `15'000.
¨¨po `3
`1. ¨expliquer pourquoi l'attribut num´-ser ne peut pas 2tre une clé primaire de la relation inventaire.
`2. ¨donner, sous forme de tableau, le résultat de la requ2te suivante appliquée à l'extrait de table précédent.
¸¨¨select marque, modele
¸¨¨from inventaire
¸¨¨where annee `" `1956
`3. ¨écrire une requ2te ¨¨sql permettant d'obtenir toutes les années du modèle ¨les ¨paul ¨standard dans la collection.
`4. ¨écrire une requ2te ¨¨sql permettant d'obtenir tous les modèles de guitares de la marque ¨gibson par ordre croissant de l'année dans la collection.
`5. ¨maud a fait une erreur de saisie pour la guitare d'identifiant id`"1. ¨l'année est en réalité `1957. ¨écrire une requ2te ¨¨sql permettant de corriger cette erreur de saisie.
¨partie ¨b
¨maud change de représentation pour l'inventaire de la collection. ¨dans cette partie, ¨maud utilise maintenant les trois relations suivantes:
marque (??id**, nom)
modele (??id**, nom, ´0id´-marque)
guitare (??id**, ´0id´-modele, annee, num´-ser, prix)
¨dans la relation modele, ´0id´-marque est une clé étrangère reliée à la clé primaire ??id** de la relation marque. ¨dans la relation guitare, ´0id´-modele est une clé étrangère reliée à la clé primaire ??id** de la relation modele.
¨voici des extraits des trois tables marque, modele, guitare.
`;¨tableau en colonne„'
marque
::::::::::
id; nom
`1; ¨gibson
`2; ¨fender
`;¨tableaux linéarisés„'
modele
id; nom; id´-marque.
`1; ¨les ¨paul ¨goldtop; `1.
`2; ¨les ¨paul ¨standard; `1.
`3; ¨telecaster; `2.
`4; ¨stratocaster; `2.
¨¨po `4
guitare
id; id´-modele; annee; num´-ser; prix.
`1; `1; `1956; @`70562; `100'000.
`2; `1; `1988; `81738349; `20'000.
`3; `2; `1959; @`90663; `250'000.
`4; `2; `1987; `81757532; `25'000.
`5; `3; `1952; `000230; `150'000.
`6; `3; `1965; `81345673; `10'000.
`7; `4; `1956; `001359; `200'000.
`8; `4; `1965; `81757532; `15'000.
`6. ¨expliquer brièvement, en justifiant, dans quel ordre les trois tables doivent 2tre créées.
`7. ¨écrire une requ2te ¨¨sql permettant d'obtenir le numéro de série et l'année de toutes les guitares ¨les ¨paul ¨standard de la collection.
¨maud vient d'apprendre que ¨slash a fait cadeau d'une de ses guitares à un ami. ¨elle doit donc la retirer de sa base de données.
`8. ¨écrire une requ2te ¨¨sql permettant de retirer de la collection la guitare d'identifiant id`"3.
¨slash a aussi acheté une guitare d'une marque qu'il n'avait pas encore dans sa collection. ¨maud décide de la rajouter.
`9. ¨écrire l'ensemble des requ2tes ¨¨sql permettant d'ajouter la guitare suivante:
9o marque: ¨¨bc ¨rich
9o modèle: ¨mockingbird
9o année: `1992
9o numéro de série: `92¨r
9o prix: `5'000.
¨on supposera que l'on peut attribuer la valeur `3 pour l'attribut id dans la table marque pour la marque ¨¨bc ¨rich, que l'on peut attribuer la valeur `5 pour l'attribut id dans la table modele pour le modèle ¨mockingbird et que l'on peut attribuer la valeur `9 pour l'attribut id dans la table guitare pour cette guitare.
¨maud souhaite conna3tre la valeur totale des modèles ¨stratocaster de la collection. ¨son ami ¨david lui conseille de regarder la fonction ¨¨sum. ¨la syntaxe pour utiliser cette fonction ¨¨sql peut 2tre similaire à celle-ci:
¨¨po `5
¸¨¨select ¨¨sum(nom´-colonne)
¸¨¨from tab
¨cette requ2te ¨¨sql permet de calculer la somme des valeurs contenues dans la colonne nom´-colonne de la table tab.
`10. ¨écrire une requ2te ¨¨sql permettant de calculer la valeur totale des modèles ¨stratocaster de la collection de ¨slash.
¨¨po `6
¨exercice `2 (`6 points)
¨cet exercice porte sur l'algorithmique, les structures de données, et la gestion de processus.
¨on cherche à créer une application de type :¸liste de t1ches à ¸faire pour aider ¨alice à planifier sa journée. ¨pour cela ¨alice saisit les informations concernant chacune des t1ches qu'elle doit effectuer: elle indique un nom pour la t1che, ainsi que la durée qu'elle estime nécessaire afin de la réaliser. ¨on représente une t1che saisie par ¨alice à l'aide d'un objet de type ¨tache, muni de quatre attributs:
9o le numero de la t1che, saisi par ¨alice;
9o le nom de la t1che, saisi par ¨alice;
9o la duree (un entier exprimé en minute) nécessaire à la réalisation de la t1che saisie par ¨alice;
9o la duree´-restante (un entier exprimé en minute) avant la fin de la t1che. ¨cet attribut sera initialisé avec la durée totale nécessaire à la réalisation de la t1che.
¨avancer de n minutes (n entier positif) dans une t1che consiste à diminuer de n la durée restante de cette t1che. ¨une t1che est terminée si la durée restante est négative ou nulle.
¨lors de la phase de planification de ses t1ches (aucune d'entre elles n'est commencée), ¨alice liste les t1ches suivantes qui doivent 2tre effectuées:
`;¨tableau linéarisé„'
¨numéro; ¨nom; ¨durée; ¨durée restante.
`1; ¨répondre aux e-mails; `45; `45.
`2; ¨ranger ma chambre; `60; `60.
`3; ¨réviser la ¨¨nsi; `90; `90.
`4; ¨s'entra3ner aux échecs; `30; `30.
`5; ¨apprendre le vocabulaire de chinois; `30; `30.
`6; ¨lire ¨fondation; `60; `60.
`7; ¨écrire ma lettre au ¨père ¨no6l; `20; `20.
¨¨po `7
¨on dispose de la classe ¨tache ci-dessous pour représenter les t1ches:
`1 ¸class ¨tache:
`2 ¸def ´-´-init´-´-(self, numero, nom, duree):
`3 self.numero `" numero
`4 self.nom `" nom
`5 self.duree´-initiale `" duree
`6 self.duree´-restante `" duree
`7
`8 ¸def ´-´-repr´-´-(self):
`9 ¸return '´2t'`!str(self.numero)`!'´@'
`1. ¨donner le code ¨python qui permet d'instancier deux variables tache`1 et tache`2 représentant les t1ches:
9o t1che numéro `1: ¨répondre aux e-mails. ¨durée estimée: `45 minutes.
9o t1che numéro `2: ¨ranger ma chambre. ¨durée estimée: `60 minutes.
¨on supposera dans la suite que les variables tache`1, tache`2, ..., tache`7 représentent les t1ches établies par ¨alice lors de la phase de planification.
¨la méthode ´-´-repr´-´- renvoie une représentation de l'instance sous forme d'une cha3ne de caractères. ¨la fonction print utilise cette méthode. ¨ainsi on a:
´@´@´@ print(tache`1)
´2t`1´@
`2. ¨recopier et compléter le code de la méthode avancer de la classe ¨tache qui permet d'avancer la t1che self de n minutes.
`1 ¸def avancer(self, n):
`2 `-'
`3. ¨recopier et compléter le code de la méthode est´-terminee de la classe ¨tache qui renvoie ¨true si la t1che est terminée, ou ¨false sinon.
`1 ¸def est´-terminee(self):
`2 `-'
¨afin d'aider ¨alice à planifier sa journée, on lui propose d'associer à chacune des t1ches une priorité. ¨la priorité d'une t1che est représentée par un entier de la manière suivante: `1 est la priorité minimale et, plus le nombre est grand, plus la t1che associée est prioritaire.
¨pour stocker toutes les t1ches à effectuer, on utilise une file, dans laquelle les éléments sont des tuples (tache, priorite). ¨les éléments stockés dans la file doivent respecter les deux conditions ci-après.
9o ¨condition `1: les éléments sont rangés par ordre décroissant de priorité. ¨l'élément de priorité maximale se trouve au début de la file, l'élément le moins prioritaire se trouve à la fin de la file.
¨¨po `8
9o ¨condition `2: parmi les éléments de m2me priorité, les éléments sont rangés dans l'ordre dans lequel ils ont été insérés dans la file. ¨ainsi, le premier élément de priorité ¸p inséré se trouve devant les éléments de m2me priorité ¸p insérés plus tard.
¨par exemple, si la file de t1ches f est la file:
¤(début)b (´2t`3´@, `4) (´2t`1´@, `3) (´2t`2´@, `3) (´2t`4´@, `1) (´2t`5´@, `1) ¤(fin)b
¨cela signifie que:
9o la t1che de priorité maximale est la t1che numéro `3;
9o les deux t1ches à exécuter en priorité après la t1che numéro `3 sont les t1ches numéro `1 et numéro `2. ¨la t1che numéro `1 a été ajoutée à la file des t1ches à traiter avant la t1che numéro `2;
9o il n'y a pas de t1che de priorité `2;
9o les t1ches les moins prioritaires de la file sont les t1ches numéro `4 et numéro `5. ¨la t1che numéro `4 a été ajoutée avant la t1che numéro `5.
`4. ¨représenter l'état de la file f lorsqu'on lui ajoute successivement la t1che numéro `6 avec la priorité `2, puis la t1che numéro `7 avec la priorité `4 en respectant les conditions `1 et `2 décrites ci-dessus.
¨on suppose déjà définies les méthodes suivantes pour la classe ¨file:
9o ¨file(): crée et renvoie un objet de type ¨file, vide.
9o enfiler(self, e): ajoute l'élément e à la fin de la file f.
9o defiler(self): renvoie, en le supprimant de la file, le premier élément de la file si cela est possible.
9o examiner(self): renvoie, sans le supprimer de la file, le premier élément de la file si cela est possible.
9o est´-vide(self): renvoie ¨true si la file est vide, ou ¨false sinon.
`5. ¨en repartant de la file f suivante:
¤(début)b (´2t`3´@, `4) (´2t`1´@, `3) (´2t`2´@, `3) (´2t`4´@, `1) (´2t`5´@, `1) ¤(fin)b
donner la valeur de f.defiler()¤(`0)b, et représenter le contenu de la file f après l'exécution de cette instruction.
`6. ¨en repartant de la file f suivante:
¤(début)b (´2t`3´@, `4) (´2t`1´@, `3) (´2t`2´@, `3) (´2t`4´@, `1) (´2t`5´@, `1) ¤(fin)b
donner la valeur de f.examiner()¤(`1)b, et représenter le contenu de la file f après l'exécution de cette instruction.
¨¨po `9
¨on souhaite écrire une fonction ajouter´-file´-prio qui prend en paramètres:
9o une file f dont les éléments sont des tuples (tache, priorite) respectant les deux conditions de l'énoncé;
9o une t1che t; 
9o la priorité p de la t1che t;
et qui ajoute le tuple (t, p) à la bonne position dans la file f.
¨on utilise une file auxiliaire f´-aux que l'on remplit en défilant les éléments en début de file f tant que la priorité du premier élément de la file est supérieure ou égale à p. ¨puis on enfile l'élément (t, p) dans la file auxiliaire. ¨on défile ensuite tous les éléments restants de f dans f´-aux et enfin on enfile dans f tous les éléments de f´-aux.
`7. ¨recopier et compléter le code de la fonction ajouter´-file´-prio.
`1 ¸def ajouter´-file´-prio(f, t, p):
`2 f´-aux `" ¨file()
`3 ¸while `-':
`4 `-'
`5 `-'enfiler(`-')
`6 ¸while ¸not `-':
`7 `-'
`8 ¸while ¸not `-':
`9 `-'
`8. ¨donner le co5t d'exécution temporel dans le pire des cas de la fonction ajouter´-´ file´-prio, en fonction du nombre m d'éléments de la file f.
¨une fois qu'¨alice a entré les t1ches qu'elle doit effectuer, leur durée estimée, ainsi que la priorité à laquelle elle doit les effectuer, l'application lui propose un planning en utilisant la technique dite ¨pomodoro:
9o la t1che à effectuer est la t1che qui se trouve en t2te de file;
9o on défile cette t1che de la file des t1ches à effectuer;
9o on avance cette t1che de `25 minutes;
9o si cette t1che n'est pas terminée, on rajoute cette t1che dans la file des t1ches à effectuer, avec la m2me priorité qu'initialement (en utilisant la fonction ajouter´-file´-prio);
9o si cette t1che se termine au cours des `25 minutes, alors ¨alice attend la fin des `25 minutes en se reposant;
9o on continue ces étapes tant que la file des t1ches à effectuer n'est pas vide.
¨¨po `10
¨on rappelle les t1ches à effectuer ci-dessous, classées par ordre de priorité. ¨on considérera que les t1ches sont ajoutées à la file de priorité dans l'ordre du tableau ci-dessous:
`;¨tableau linéarisé.„'
¨numéro; ¨nom; ¨durée; ¨priorité.
`3; ¨réviser la ¨¨nsi; `90; `4.
`7; ¨écrire ma lettre au ¨père ¨no6l; `20; `4.
`1; ¨répondre aux e-mails; `45; `3.
`2; ¨ranger ma chambre; `60; `3.
`6; ¨lire ¨fondation; `60; `2.
`4; ¨s'entra3ner aux échecs; `30; `1.
`5; ¨apprendre le vocabulaire de chinois; `30; `1.
`9. ¨indiquer pour chaque bloc de `25 minutes la t1che qui avance, en suivant le modèle proposé, jusqu'à la fin de toutes les t1ches.
¨on fera particulièrement attention au cas où la t1che n'est pas terminée: celle-ci est rajoutée à la file des t1ches à effectuer (dont elle avait été supprimée) avec la m2me priorité qu'initialement, en respectant les conditions `1 et `2 de l'énoncé.
`10. ¨écrire le code d'une fonction planning qui prend en paramètre une file de priorité f dont les éléments sont des tuples (tache, prio), et qui renvoie une liste de t1ches, dans l'ordre dans lequel elles vont 2tre effectuées par tranche de `25 minutes avec la méthode ¨pomodoro.
¨par exemple, si tache`1, tache`2 et tache`3 sont les t1ches numéro `1, numéro `2 et numéro `3, alors le programme suivant:
`1 file `" ¨file()
`2 ¸for t, p ¸in ¤((tache`1, `3), (tache`2, `3), (tache`3, `4))b:
`3 ajouter´-file´-prio(file, t, p)
`4 print(planning(file))
produit l'affichage:
¤(´2t`3´@, ´2t`3´@, ´2t`3´@, ´2t`3´@, ´2t`1´@, ´2t`2´@, ´2t`1´@, ´2t`2´@, ´2t`2´@)b
¨¨po `11
¨exercice `3 (`8 points)
¨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 cha3ne de cafés est représenté en ¨figure `1.
¨figure `1. ¨schéma d'une partie du réseau
`;¨voir planches tactiles n´o `1 et `2. „'
¨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-m2mes d'adresse ¨¨ip). ¨les `4 routeurs représentés sont composés d'au moins `3 interfaces réseau capables de relier des réseaux ensemble. ¨chaque interface possède donc une adresse ¨¨ipv`4 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 ¨a
¨le gérant veut faire installer une troisième borne de commande dans le café `1.
`1. ¨indiquer les deux seules adresses ¨¨ip valides pour cette nouvelle borne, parmi les quatre adresses ¨¨ip proposées.
(a) `192.168.20.2
(b) `192.168.20.157
(c) `192.168.20.261
(d) `192.168.24.10
¨¨po `12
¨l'adresse de diffusion, appelée aussi adresse de broadcast, est la dernière adresse disponible à l'intérieur d'un réseau local.
`2. ¨déterminer l'adresse de diffusion du réseau du café `1.
`3. ¨déterminer combien de machines informatiques il est encore possible de connecter au réseau du café `1 après l'installation de la troisième borne de commande.
¨le réseau local du café `1 n'a pas besoin de plus de `8 adresses ¨¨ip différentes. ¨ce décompte d'adresses ¨¨ip inclut les adresses ¨¨ip réservées (à savoir l'adresse de diffusion et l'adresse du réseau). ¨il est rappelé que la longueur du masque de sous-réseau est actuellement de `24 bits (c'est-à-dire `3 octets).
`4. ¨expliquer quelle est la longueur maximale du masque de sous-réseau que l'on pourrait choisir pour le réseau local du café `1.
¨partie ¨b
¨¨rip (¨routing ¨information ¨protocol) est un protocole de routage utilisé dans les réseaux ¨¨ip. ¨il est conçu pour réduire le nombre de sauts entre deux réseaux. ¨un "saut" correspond au transfert des données d'un routeur à un autre. ¨le protocole ¨¨rip utilise le nombre de sauts comme critère principal pour évaluer le co5t d'un chemin. ¨autrement dit, il considère que le chemin le plus optimal est celui qui traverse le moins de routeurs.
¨la table de routage du routeur `2 de la ¨figure `1 est représentée `;page braille suivante„':
`;¨tableau linéarisé.„'
¨routeur `2
¨réseau destination; ¨interface de sortie; ¨prochain routeur; ¨nombre de sauts.
`192.168.20.0; `192.168.20.1; aucun; `0.
`172.16.3.0; `172.16.3.1; aucun; `0.
`172.16.4.0; `172.16.4.1; aucun; `0.
`192.168.10.0; `172.16.3.1; `172.16.3.2; `2.
`172.16.0.0; `172.16.4.1; `172.16.4.2; `1.
`172.16.2.0; `172.16.4.1; `172.16.4.2; `1.
`192.168.30.0; `-'; `-'; `-'.
`172.16.1.0; `-'; `-'; `-'.
`5. ¨recopier et compléter les deux dernières lignes de la table de routage du routeur `2.
¨¨po `13
¨la table de routage du routeur `2 contient un réseau de destination pour lequel deux routes différentes sont possibles. ¨la ligne correspondante dans la table de routage aurait donc pu 2tre remplie différemment tout en respectant le protocole ¨¨rip.
`6. ¨identifier, dans la table de routage du routeur `2, le réseau de destination que l'on peut atteindre d'une autre façon et indiquer comment cette ligne de la table de routage pourrait 2tre modifiée.
¨une adresse ¨¨ip qui n'est pas référencée dans la table de routage doit 2tre routée par défaut vers ¨internet.
`7. ¨recopier et compléter la ligne à ajouter à la table de routage du routeur `2.
`;¨tableau linéarisé.„'
¨réseau destination; ¨interface de sortie; ¨prochain routeur. 
autre; `-'; `-'.
¨partie ¨c
¨¨ospf est également un protocole d'échanges de données entre les routeurs qui prend en compte le co5t des routes. ¨le co5t est lié au débit des liaisons entre les routeurs par la formule suivante:
`cout"10^9/debit avec le débit en `bits*s^-1.
`8. ¨recopier et compléter la dernière colonne du tableau ci-dessous:
`;¨tableau linéarisé.„'
¨tableau des co5ts
¨type de connexion; ¨débit en `bit*s^-1; co5t.
¨ethernet; `10 `¨mbit/s^-1´ "10^7 `bit*s^-1; `100.
¨fast ¨ethernet; `100 `¨mbit*s^-1"10^8 `bit*s^-1; `-'.
¨fibre optique; `1 `¨gbit*s^-1"10^9 `bit*s^-1; `-'.
¨¨po `14
¨le schéma ci-dessous met en évidence les types de connexion qui relient les routeurs.
¨figure `2. ¨schéma des types de connexion
`;¨voir planche tactile n´o `3. „'
`9. ¨déterminer la route dont le co5t est minimal pour aller du routeur `1 jusqu'au routeur `4 et calculer son co5t au sens du protocole ¨¨ospf.
¨partie ¨d
¨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 cha3ne de caractères décrivant une adresse ¨¨ip en notation décimale, et renvoie une cha3ne de caractères, de longueur `35 (`32 bits et les `3 points), décrivant l'adresse ¨¨ip en notation binaire.
¨exemple:
´@´@´@ ip´-bin('`192.168.10.1')
'`11000000.10101000.00001010.0 0000001'
`10. ¨donner la cha3ne 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 cha3nes 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.
¨exemple:
´@´@´@ a `" '`11000000.10101 000.00001010.00000001'
´@´@´@ b `" '`11000000.10101 000.00001111.00000001'
´@´@´@ precede(a, b)
¨true
¨¨po `15
¨l'algorithme compare bit à bit les deux cha3nes binaires, en lisant les cha3nes 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)b ´2 ip´-`2¤(i)b:
`4 ¸return `-'
`5 ¸elif ip´-`1¤(i)b ´@ ip´-`2¤(i)b:
`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.
¨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:
9o adresse´-ip désigne l'adresse ¨¨ip de la destination;
9o interface désigne l'interface réseau;
9o passerelle désigne l'adresse ¨¨ip du prochain routeur;
9o cout désigne le nombre de sauts pour atteindre la destination.
¨¨po `16
9o par convention, l'arbre binaire vide est une instance de ¨abr pour laquelle adresse´-ip est une cha3ne de caractères vide;
9o 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;
9o si elle n'est pas vide, l'adresse ¨¨ip du sous-arbre gauche précède l'adresse ¨¨ip de l'instance parent;
9o 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.
`15. ¨justifier, en mobilisant des connaissances de cours, l'intér2t 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 m2mes que les lignes `27 à `30.
`16. ¨réécrire le code de la fonction modifie en évitant cette répétition.
¨¨po `17
¨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.re chercher(adresse´-ip)
`37 ¸else:
`38 ¸return self.droite.re chercher(adresse´-ip)
`39
`40 ¸def inserer(self, adresse´-ip,
`41 interface, passerelle,
`42 cout):
`43 destination `" self.rechercher(adresse´-ip)
`44 destination.modifie(adresse´-i p,
`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.
