Sujet du Bac Numérique et Sciences Informatiques 2021 · Centres étrangers (Afrique) Jour 1

Exercice 1

Notion abordée: programmation objet.

Cryptage selon le « Code de César »

Dans cet exercice, on étudie une méthode de chiffrement de chaînes de caractères alphabétiques. Pour des raisons historiques, cette méthode de chiffrement est appelée « code de César ». On considère que les messages ne contiennent que les lettres capitales de l'alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ" et la méthode de chiffrement utilise un nombre entier fixé appelé la clé de chiffrement.

1.

Soit la classe CodeCesar définie ci-dessous:

class CodeCesar:

def __init__(self, cle):

self.cle = cle

self.alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def decale(self, lettre):

num1 = self.alphabet.find(lettre)

num2 = num1+self.cle

if num2 >= 26:

num2 = num2-26

if num2 < 0:

num2 = num2+26

nouvelle_lettre = self.alphabet[num2]

return nouvelle_lettre

On rappelle que la méthode str.find(lettre) renvoie l'indice (index) de la lettre dans la chaîne de caractères str.

Représenter le résultat d'exécution du code Python suivant:

code1 = CodeCesar(3)

print(code1.decale('A'))

print(code1.decale('X'))

2.

La méthode de chiffrement du « code César » consiste à décaler les lettres du message dans l'alphabet d'un nombre de rangs fixé par la clé. Par exemple, avec la clé 3, toutes les lettres sont décalées de 3 rangs vers la droite: le A devient le D, le B devient le E, etc.

Ajouter une méthode cryptage(self, texte) dans la classe CodeCesar définie à la question précédente, qui reçoit en paramètre une chaîne de caractères (le message à crypter) et qui retourne une chaîne de caractères (le message crypté).

Cette méthode cryptage(self, texte) doit crypter la chaîne texte avec la clé de l'objet de la classe CodeCesar qui a été instancié.

>>> code1 = CodeCesar(3)

>>> code1.cryptage("NSI")

'QVL'

def cryptage(self, texte):

3.

Écrire un programme qui:

demande de saisir la clé de chiffrement

crée un objet de classe CodeCesar

demande de saisir le texte à chiffrer

affiche le texte chiffré en appelant la méthode cryptage

4.

On ajoute la méthode transforme(texte) à la classe CodeCesar:

def transforme(self, texte):

self.cle = -self.cle

message = self.cryptage(texte)

self.cle = -self.cle

return message

On exécute la ligne suivante: print(CodeCesar(10).transforme("PSX"))

Que va-t-il s'afficher ? Expliquer votre réponse.

Exercice 2

Notion abordée: structures de données (dictionnaires)

Une ville souhaite gérer son parc de vélos en location partagée. L'ensemble de la flotte de vélos est stocké dans une table de données représentée en langage Python par un dictionnaire contenant des associations de type id_velo: dict_velo où id_velo est un nombre entier compris entre 1 et 199 qui correspond à l'identifiant unique du vélo et dict_velo est un dictionnaire dont les clés sont: "type", "etat", "station".

Les valeurs associées aux clés "type", "etat", "station" de dict_velo sont de type chaînes de caractères ou nombre entier:

"type": chaîne de caractères qui peut prendre la valeur "electrique" ou "classique"

"état": nombre entier qui peut prendre la valeur 1 si le vélo est disponible, 0 si le vélo est en déplacement, -1 si le vélo est en panne

"station": chaînes de caractères qui identifie la station où est garé le vélo.

Dans le cas où le vélo est en déplacement ou en panne, "station" correspond à celle où il a été dernièrement stationné.

Voici un extrait de la table de données:

flotte = {

12: {"type": "electrique", "etat": 1, "station": "Prefecture"},

80: {"type": "classique", "etat": 0, "station": "Saint-Leu"},

45: {"type": "classique", "etat": 1, "station": "Baraban"},

41: {"type": "classique", "etat": -1, "station": "Citadelle"},

26: {"type": "classique", "etat": 1, "station": "Coliseum"},

28: {"type": "electrique", "etat": 0, "station": "Coliseum"},

74: {"type": "electrique", "etat": 1, "station": "Jacobins"},

13: {"type": "classique", "etat": 0, "station": "Citadelle"},

83: {"type": "classique", "etat": -1, "station": "Saint-Leu"},

22: {"type": "electrique", "etat": -1, "station": "Joffre"}

}

flotte étant une variable globale du programme.

Annexe 1: Rappel sur les dictionnaires en langage Python

Action

Instruction et syntaxe

Créer un dictionnaire vide · dico={}

Obtenir un élément d'un dictionnaire existant à partir de sa clé

renvoie une erreur si cle n'existe pas dans le dictionnaire · dico[cle]

Modifier la valeur d'un élément d'un dictionnaire à partir de sa clé · dico[cle]=nouvelle_valeur

Ajouter un élément dans un dictionnaire existant · dico[nouvelle_cle]=valeur

Supprimer et obtenir un élément d'un dictionnaire à partir de sa clé · dico.pop(cle)

Tester l'appartenance d'un élément à un dictionnaire (renvoie un booléen) · cle in dico

Objet itérable contenant les clés (ce n'est pas un objet de type list) · dico.keys()

Objet itérable contenant les valeurs (ce n'est pas un objet de type list) · dico.values()

Objet itérable contenant les couples (clé,valeur) · dico.items()

Afficher les associations cle:valeur du dictionnaire dico · for cle in dico:

print(cle, dico[cle])

1.

1.a.

1.b.

1.c.

2. Voici le script d'une fonction:

def proposition(choix):

for v in flotte:

if flotte[v]["type"] == choix and flotte[v]["etat"] == 1:

return flotte[v]["station"]

2.a.

2.b.

3.

3.a.

3.b.

4.

On dispose d'une table de données des positions GPS de toutes les stations, dont un extrait est donné ci-dessous. Cette table est stockée sous forme d'un dictionnaire.

Chaque élément du dictionnaire est du type: 'nom de la station': (latitude, longitude)

stations = {

'Prefecture': (49.8905, 2.2967),

'Saint-Leu': (49.8982, 2.3017),

'Coliseum': (49.8942, 2.2874),

'Jacobins': (49.8912, 2.3016)

}

On admet que l'on dispose d'une fonction distance(p1, p2) permettant de renvoyer la distance en mètres entre deux positions données par leurs coordonnées GPS (latitude et longitude). Cette fonction prend en paramètre deux tuples représentant les coordonnées des deux positions GPS et renvoie un nombre entier représentant cette distance en mètres.

Par exemple, distance((49.8905, 2.2967), (49.8912, 2.3016)) renvoie 9591.

Écrire une fonction qui prend en paramètre les coordonnées GPS de l'utilisateur sous forme d'un tuple et qui renvoie, pour chaque station située à moins de 800 mètres de l'utilisateur:

le nom de la station;

la distance entre l'utilisateur et la station;

les identifiants des vélos disponibles dans cette station.

Une station où aucun vélo n'est disponible ne doit pas être affichée.

4.

Exercice 3

Notion abordée: les arbres binaires de recherche.

Un arbre binaire est soit vide, soit un nœud qui a une valeur et au plus deux fils (le sous-arbre gauche et le sous-arbre droit).

$X$ est un nœud, sa valeur est $X\text{.valeur}$

$G1$ est le fils gauche de $X$, noté $X\text{.fils\_gauche}$

$D1$ est le fils droit de $X$, noté $X\text{.fils\_droit}$

Un arbre binaire de recherche est ordonné de la manière suivante:

Pour chaque nœud $X$,

les valeurs de tous les nœuds du sous-arbre gauche sont strictement inférieures à la valeur du nœud $X$

les valeurs de tous les nœuds du sous-arbre droit sont supérieures ou égales à la valeur du nœud $X$

Ainsi, par exemple, toutes les valeurs des nœuds $G1$, $G2$ et $G3$ sont strictement inférieures à la valeur du nœud $X$ et toutes les valeurs des nœuds $D1$, $D2$ et $D3$ sont supérieures ou égales à la valeur du nœud $X$.

Voici un exemple d'arbre binaire de recherche dans lequel on a stocké dans cet ordre les valeurs:

$[26, 3, 42, 15, 29, 19, 13, 1, 32, 37, 30]$

L'étiquette d'un nœud indique la valeur du nœud suivie du nom du nœud.

Les nœuds ont été nommés dans l'ordre de leur insertion dans l'arbre ci-dessous.

'29, noeud04' signifie que le nœud nommé noeud04 possède la valeur 29.

1.

On insère la valeur 25 dans l'arbre, dans un nouveau nœud nommé noeud11.

Recopier l'arbre binaire de recherche étudié et placer la valeur 25 sur cet arbre en coloriant en rouge le chemin parcouru.

Préciser sous quel nœud la valeur 25 sera insérée et si elle est insérée en fils gauche ou en fils droit, et expliquer toutes les étapes de la décision.

2.

Préciser toutes les valeurs entières que l'on peut stocker dans le nœud fils gauche du nœud04 (vide pour l'instant), en respectant les règles sur les arbres binaires de recherche ?

3.

Voici un algorithme récursif permettant de parcourir et d'afficher les valeurs de l'arbre:

Parcours(A) # A est un arbre binaire de recherche

Afficher(A.valeur)

Parcours(A.fils_gauche)

Parcours(A.fils_droit)

3.a. Écrire la liste de toutes les valeurs dans l'ordre où elles seront affichées.

3.b. Choisir le type de parcours d'arbres binaires de recherche réalisé parmi les propositions suivantes: Préfixe, Suffixe ou Infixe

4.

En vous inspirant de l'algorithme précédent, écrire un algorithme Parcours2 permettant de parcourir et d'afficher les valeurs de l'arbre A dans l'ordre croissant.

Exercice 4: Étude d'un réseau informatique

Soit un réseau informatique dont le schéma structurel simplifié est représenté ci-dessous. Il est composé de 8 PC, 3 switchs et 3 routeurs.

Dans cet exercice, on utilisera l'adressage CIDR composé d'une adresse IPv4 et d'une indication sur le masque de sous-réseau. Par exemple: 172.16.1.10 / 16 signifie:

Adresse IP: 172.16.1.10

Masque de sous-réseau en notation CIDR: 16

Partie A: ÉTUDE DE L'ADRESSAGE IP

1.

Sur le document réponse 1 de l'exercice 4, encadrer tous les sous-réseaux présents dans le réseau global.

2.

Étude du PC7 dont l'adresse IP est: 192.168.20.10 / 24.

2.a.

Combien d'octets sont nécessaires pour composer une adresse IP(v4) ?

octets

2.b.

Compléter la ligne 2 du tableau en convertissant la notation décimale de l'adresse IP en notation binaire (8 bits par octet).

Octet

1er octet

2e octet

3e octet

4e octet

Décimal (Ligne 1)

192

168

20

10

Binaire (Ligne 2)

11000000

00010100

2.c.

La notation CIDR /16 pour une adresse IP signifie que le masque de sous-réseau a les 16 bits de poids fort de son adresse IP à la valeur 1. C'est-à-dire: 11111111.11111111.00000000.00000000.

Compléter la ligne 3 du tableau en donnant le codage binaire du masque de sous-réseau en notation CIDR /24:

Masque /24

Octet 1

Octet 2

Octet 3

Octet 4

Binaire (Ligne 3)

2.d.

En déduire, à la ligne 4 du tableau, l'écriture décimale pointée du masque de sous-réseau:

255.

.

.

L'adresse du réseau peut s'obtenir en réalisant un ET logique bit à bit entre l'adresse IP du PC7 et le masque de sous-réseau.

Octet 1

Octet 2

Octet 3

Octet 4

. 168.

.

3.

Connexion du PC8 au réseau: On désire connecter le PC8 au réseau précédent (Switch 2). Parmi les propositions suivantes, cochez les adresses IP possibles pour le PC8:

Partie B: Une fonction pour convertir une adresse IP en décimal pointé en notation binaire

On dispose de la fonction dec_bin:

qui prend en paramètre d'entrée un nombre entier compris entre 0 et 255

qui retourne une liste de 8 éléments correspondant à la conversion du nombre en écriture décimale en notation binaire. Chaque élément de cette liste est de type entier.

Exemples d'exécution de la fonction dec_bin:

dec_bin(10) retourne la liste [0,0,0,0,1,0,1,0]

dec_bin(255) retourne la liste [1,1,1,1,1,1,1,1]

Écrire une fonction en langage Python que l'on appellera IP_bin qui:

prend en paramètre d'entrée une liste de 4 entiers compris entre 0 et 255 correspondant à l'adresse IP en notation décimale

retourne une liste de 4 listes correspondant à l'adresse IP en notation binaire.

La fonction IP_bin peut faire appel à la fonction dec_bin.

>>> IP_bin([192, 168, 0, 1])

[[1,1,0,0,0,0,0,0],[1,0,1,0,1,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1]]

Exercice 5

Notion abordée: structures de données: les piles.

Dans cet exercice, on considère une pile d'entiers positifs. On suppose que les quatre fonctions suivantes ont été programmées préalablement en langage Python:

empiler(P, e): ajoute l'élément e sur la pile P;

depiler(P): enlève le sommet de la pile P et retourne la valeur de ce sommet;

est_vide(P): retourne True si la pile est vide et False sinon;

creer_pile(): retourne une pile vide.

Dans cet exercice, seule l'utilisation de ces quatre fonctions sur la structure de données pile est autorisée.

1.

Exécuter les appels de fonctions successifs à partir de la pile d'origine $P$. Indiquer le contenu de la pile (les valeurs du haut vers le bas) et ce que renvoie la fonction utilisée dans chaque cas (indiquer None si la fonction ne retourne aucune valeur).

Étape 0

Pile d'origine P

Étape 1

empiler(P, 8)

Étape 2

depiler(P)

Étape 3

est_vide(P)

[ ] (vide)

[ 4 ] (sommet)

[ 7 ]

[ 1 ]

[ 5 ] (fond)

Retour de la fonction:

2.

On propose la fonction ci-dessous, qui prend en argument une pile P et renvoie un couple de piles:

def transforme(P):

Q = creer_pile()

while not est_vide(P):

v = depiler(P)

empiler(Q, v)

return (P, Q)

Si la pile initiale P contient (du sommet au fond) les éléments 4, 7, 1, 5, déterminer l'état des piles P et Q renvoyées par l'exécution de transforme(P).

3.

Écrire une fonction en langage Python maximum(P) recevant une pile P comme argument et qui renvoie la valeur maximale de cette pile. On ne s'interdit pas qu'après exécution de la fonction, la pile soit vide.

4.

On souhaite connaître le nombre d'éléments d'une pile à l'aide de la fonction taille(P).

Par exemple, pour une pile contenant les éléments 9, 4, 7, 1, 12, taille(P) retournera l'entier 5.

4.a.

Proposer une stratégie écrite en langage naturel et/ou expliquée à l'aide de schémas, qui permette de mettre en place une telle fonction.

4.b.

Donner le code Python de cette fonction taille(P) (on pourra utiliser les cinq fonctions déjà programmées).