Bac NSI — Amérique du Nord 2024 (Jour 2)

Présentation de l'épreuve

Sujet officiel du baccalauréat général, épreuve de spécialité Numérique et Sciences Informatiques, session 2024, Amérique du Nord, jour 2 (code sujet 24-NSIJ2AN1). Durée 3h30, calculatrice interdite. Le sujet comporte 3 exercices indépendants, tous à traiter.

Exercice 1 — Le tri de Stooge (6 points)

Pour trier les éléments d'indice i à j (i < j) d'un tableau tab par le tri de Stooge : si les éléments d'indice i et j sont mal placés, on les échange ; puis, s'il y a au moins trois éléments entre les indices i et j, on trie les deux premiers tiers du tableau par cette même méthode, puis les deux derniers tiers, puis à nouveau les deux premiers tiers. Le découpage utilise k = (j - i + 1) // 3 et les indices intermédiaires i+k et j-k.

Code partiel :

def triStooge(tab, i, j):
    if tab[i] > tab[j]:
        echange(tab, i, j)
    if (j - i) > 1:
        k = (j - i + 1)//3
        triStooge(...)  # ligne 6
        triStooge(...)  # ligne 7
        triStooge(...)  # ligne 8

1. Écrire echange(tab, i, j), qui échange sur place les valeurs de tab aux indices i et j (ne renvoie rien).
2. Compléter les lignes 6, 7 et 8.
3. L'algorithme est-il itératif ou récursif ? Justifier.

Soit l'appel triStooge(A, 0, 5) avec A = [5, 6, 4, 2, 3, 1].

4. Déterminer la valeur de k lors de ce premier appel, en justifiant.
5. Dénombrer le nombre d'appels récursifs effectués lors de ce tri (sans compter l'appel initial), sachant que l'arbre des appels a 3 niveaux de profondeur après l'appel initial, chaque nœud ayant 3 enfants dès que (j-i) > 1.
6. Le premier appel se divise en 3 appels : triStooge(A,0,3), triStooge(A,2,5), et un troisième appel de mêmes paramètres que le premier (triStooge(A,0,3), puisque le troisième sous-appel retrie les deux premiers tiers). Le second de ces trois appels, triStooge(A,2,5), se divise à son tour selon le même principe avec k=(5-2+1)//3=1 : déterminer ses trois sous-appels.
7. Reprendre A = [5, 4, 6, 2] et l'appel triStooge(A, 0, 3). Ce dernier commence par comparer tab[0] et tab[3] (5 et 2 : mal placés, échange), puis se divise en 3 appels imbriqués (k=1) : triStooge(A,0,2), triStooge(A,1,3), triStooge(A,0,2). Compléter le tableau de trace suivant (valeur de A avant/après chaque étape) :

8. Le coût en temps, dans le pire des cas, du tri de Stooge est de l'ordre de n^e avec e environ égal à 8/3. Donner un algorithme de tri au coût strictement meilleur.

Exercice 2 — SQL et bases de données (6 points)

Un pharmacien crée son système de gestion des médicaments. Table client(id_client: INT, nom_client: VARCHAR(30), prenom_client: VARCHAR(30), num_secu_sociale: VARCHAR(15)) :

1. Écrire le résultat de SELECT nom_client, prenom_client FROM client ORDER BY nom_client;.

Table medicament(id_medic: INT, nom_medic: VARCHAR(30), categorie: VARCHAR(20), conditionnement: INT, quantite: INT, prix: FLOAT) :

2. Écrire une requête affichant les noms des médicaments de prix strictement inférieur à 3 €.

Madame Sophie Martin présente une ordonnance (Dr Louis Farti, Grenoble, 13 décembre 2023) : Paracétamol 1 gramme CP (boîte de 8), 1 comprimé par prise, au maximum 3 comprimés par jour, pendant 2 jours ; Acide ascorbique 500 mg effervescent (boîte de 10), 1 comprimé par jour pendant 4 semaines. Ces prescriptions sont saisies dans ordonnance(id_ordo, id_client, date_ordo, id_medic, nb_boites) :

3. Écrire la requête ajoutant la troisième cliente Nathalie Durand (carte Vitale n° 2 69 05 49 588 157 80), avec id_client = 3.
4. Donner les attributs devant être déclarés clés étrangères de ordonnance, et préciser leur utilité.
5. Indiquer, pour les lignes 7 et 8, le nombre de boîtes prescrites (justifier à partir du texte de l'ordonnance et du conditionnement de chaque médicament).
6. Écrire la requête mettant à jour la quantité en stock d'Acide ascorbique suite à cette délivrance.
7. Calculer le coût total des médicaments fournis à Mme Martin (sans écrire de requête, en justifiant le calcul à partir du prix par boîte).
8. Écrire la requête affichant le nom du médicament pour l'ordonnance d'id_ordo 6.

Exercice 3 — Programmation objet, réseaux et sécurisation (8 points)

Un réseau local relie les machines d'Alice (192.168.1.1) et de Bob (192.168.1.2) ; l'adresse de diffusion est 192.168.1.255 (réservée), le masque 255.255.255.0.

Partie A.

1. Donner une adresse IP possible pour la machine de Charlie afin qu'elle communique avec Alice et Bob, en justifiant toutes les conditions à respecter.

Le réseau sert à des transactions en monnaie nsicoin entre trois utilisateurs :

class Transaction:
    def __init__(self, expediteur, destinataire, montant):
        self.expediteur = expediteur
        self.destinataire = destinataire
        self.montant = montant

2. Dans un intervalle de dix minutes, Alice envoie dix nsicoin à Charlie, puis Bob envoie cinq nsicoin à Alice. Écrire la liste Python de ces transactions.

Pour tracer toutes les transactions, on utilise une blockchain :

class Bloc:
    def __init__(self, liste_transactions, bloc_precedent):
        self.liste_transactions = liste_transactions
        self.bloc_precedent = bloc_precedent  # de type Bloc
 
class Blockchain:
    def __init__(self):
        self.tete = self.creer_bloc_0()
 
    def creer_bloc_0(self):
        """Cree le premier bloc, qui distribue 100 nsicoin a chaque
        utilisateur (expediteur pseudo-utilisateur Genesis)."""
        liste_transactions = [
            Transaction("Genesis", "Alice", 100),
            Transaction("Genesis", "Bob", 100),
            Transaction("Genesis", "Charlie", 100)
        ]
        return Bloc(liste_transactions, None)

Les trois premiers blocs d'une blockchain (tête = bloc2) sont : bloc0 (les 3 transactions Genesis ci-dessus) ; bloc1 (Alice->Charlie 50 ; Charlie->Bob 30) ; bloc2 (Bob->Charlie 20 ; Bob->Charlie 20 ; Charlie->Alice 30).

3. Pourquoi la valeur de l'attribut bloc_precedent du bloc0 est-elle None ?
4. Donner la valeur de l'attribut bloc_precedent du bloc1 pour qu'il soit lié au bloc0.
5. À l'aide des classes Bloc et Blockchain, écrire le code créant un objet ma_blockchain représentant cette situation.
6. Donner le solde en nsicoin de Bob à l'issue du bloc2.
7. Écrire la méthode ajouter_bloc(self, liste_transactions) de Blockchain, qui crée un nouveau bloc (à partir des transactions passées et du bloc courant en tête) et l'ajoute à la chaîne.
8. Lorsqu'un utilisateur ajoute un bloc, il l'envoie à tous les autres membres. Donner le nom et la valeur de l'adresse IP à utiliser pour cet envoi.
9. On veut doter Bloc d'une méthode récursive calculer_solde(self, utilisateur) renvoyant le solde d'un utilisateur à l'issue de ce bloc (cas de base : bloc sans précédent, solde 0 ; cas général : appel récursif sur le bloc précédent, puis ajustement selon les transactions de ce bloc où l'utilisateur est expéditeur ou destinataire). L'écrire.
10. Écrire l'appel permettant de calculer le solde actuel d'Alice à partir de ma_blockchain.

Partie B — Sécurisation. On enrichit Bloc de trois attributs : hash_bloc_precedent (le hash du bloc précédent, ou "0" s'il n'y en a pas), nonce (entier, 0 par défaut), hash (calculé par calculer_hash, non détaillé ici). Propriétés du hash : il dépend de tout le contenu du bloc et uniquement de lui ; il se calcule rapidement ; la moindre modification du bloc change complètement le hash ; il est impossible de retrouver le bloc à partir de son hash ; deux blocs de même hash sont identiques. « Miner » un bloc consiste à trouver une valeur de nonce telle que le hash commence par "00".

11. Expliquer en quoi consiste la recherche exhaustive de cette valeur de nonce.
12. Donner, en justifiant, la valeur de hash_bloc_precedent du bloc0.
13. Le hash étant codé sur 256 bits, donner le calcul du nombre de hash possibles.
14. Compléter le code de minage_bloc :

def minage_bloc(self):
    """modifie le nonce d'un bloc pour que son hash commence par '00'
    en enumerant tous les entiers naturels en partant de 0."""
    self.nonce = 0
    self.hash = self.calculer_hash()
    while ... :
        self.nonce = ...
        self.hash = ...