Bac NSI — Sujet 0.A 2024

Présentation de l'épreuve

Ce sujet est le spécimen officiel 0.A publié en 2024 par l'Éducation nationale pour l'épreuve écrite de spécialité NSI en Terminale. Durée : 3h30, calculatrice interdite. Il comporte 3 exercices indépendants (à traiter tous les trois).

Exercice 1 — Architecture réseau, routeurs et protocoles de routage (6 points)

Un réseau local N1 comprend trois machines : M1 (192.168.1.1/24), M2 (192.168.1.2/24), M3 (192.168.2.3/24). Le « /24 » signifie que l'adresse réseau de N1 est 192.168.1.0. Depuis M1, un utilisateur exécute ping 192.168.2.3 et obtient : Hôte inaccessible.

Question 1. Expliquer ce résultat (la connexion physique entre machines est fonctionnelle).

On ajoute un routeur R1 à N1 : « Un routeur moderne est un ordinateur minimal dédié (carte mère, microprocesseur, ROM, RAM, interfaces réseau), dont le système d'exploitation peut être un Linux allégé ; il doit disposer d'au minimum deux interfaces réseau. »

Question 2. Définir l'acronyme RAM. Expliquer le terme Linux. Expliquer pourquoi un routeur a besoin d'au moins deux interfaces réseau.

Question 3. Attribuer une adresse IP valide à l'interface eth0 de R1, sachant que l'adresse réseau de N1 est 192.168.1.0 (et que M1, M2 utilisent déjà .1 et .2).

Le réseau N1 est maintenant relié à trois autres réseaux locaux N2, N3, N4 par l'intermédiaire de routeurs R1 à R6 : R1 (gateway de N1, interfaces eth0→N1, eth1→R2, eth2→R3), R2 (gateway de N2, eth0→R1, eth1→N2, eth2→R6), R3 (eth0→R1, eth1→R4, eth2→R6), R4 (gateway de N3, eth0→R3, eth1→N3), R6 (gateway de N4, eth0→R2, eth1→R3, eth2→N4).

Protocole RIP (métrique = nombre de routeurs traversés). Table de routage de R1 :

Question 4. Déterminer le chemin parcouru par un paquet de N1 vers N2.

Question 5. Le routeur R3 tombe en panne. Dresser la nouvelle table de routage de R1.

R3 redevient fonctionnel. On passe au protocole OSPF (métrique = somme des coûts, $\text{coût} = 10^8/d$). Types de liaison : Fibre (1 Gb/s), Fast-Ethernet (100 Mb/s), Ethernet (10 Mb/s).

Question 6. Calculer le coût de chacun de ces trois types de liaison.

On donne : R1-R2 Fibre, R1-R3 Ethernet, R3-R4 Fibre, R3-R6 Fast-Ethernet, R2-R6 type inconnu. Table de routage OSPF de R1 :

Question 7. En déduire le type (et le débit) de la liaison R2-R6.

Des travaux font passer la liaison R1-R3 en Fibre.

Question 8. Mettre à jour la table de routage OSPF de R1.

On ajoute un routeur R7 (gateway d'un réseau N5, relié à R2 et R3 par des liaisons Fibre).

Question 9. Calculer, dans la table de R1, les deux nouvelles entrées vers N5 (via eth1 et via eth2).

Exercice 2 — Listes, dictionnaires, correction automatisée de QCM (6 points)

Un institut propose des QCM de 20 questions numérotées 0 à 19, 5 réponses possibles (numérotées 1 à 5), une seule bonne réponse par question. La correction d'une épreuve est une liste corr où corr[i] est la bonne réponse à la question i. Exemple :

corr0 = [4, 2, 1, 4, 3, 5, 3, 3, 2, 1, 1, 3, 3, 5, 4, 4, 5, 1, 3, 3]
copTM = [4, 1, 5, 4, 3, 3, 1, 4, 5, 3, 5, 1, 5, 5, 5, 1, 3, 3, 3, 3]

Question 1. Écrire corrige(cop, corr), qui renvoie la liste des booléens (bonne/mauvaise réponse) pour la copie cop selon corr.

Question 2. Écrire note(cop, corr), qui renvoie directement le nombre de bonnes réponses, sans construire la liste de booléens.

Un paquet de copies est un dictionnaire {nom_candidat: liste_reponses}, par exemple :

p1 = {('Tom', 'Matt'): copTM, ('Lambert', 'Ginne'): [...], ...}

Question 3. Écrire notes_paquet(p, corr), qui renvoie un dictionnaire {nom_candidat: note} (on peut réutiliser note).

Question 4. Peut-on utiliser une liste [nom, prenom] plutôt qu'un couple (nom, prenom) comme clé de dictionnaire ? Justifier.

Question 5. Proposer une autre solution pour distinguer des candidats homonymes, en tenant compte de la sensibilité des données (justifier brièvement).

On donne la fonction suivante (les clés du dictionnaire notes sont des noms de candidats, les valeurs leurs notes) :

def enigme(notes):
    a, b, c = None, None, None
    d = {}
    for nom in notes:
        tmp = c
        if a is None or notes[nom] > a[1]:
            c, b, a = b, a, (nom, notes[nom])
        elif b is None or notes[nom] > b[1]:
            c, b = b, (nom, notes[nom])
        elif c is None or notes[nom] > c[1]:
            c = (nom, notes[nom])
        else:
            d[nom] = notes[nom]
        if tmp != c and tmp is not None:
            d[tmp[0]] = tmp[1]
    return (a, b, c, d)

Question 6. Calculer enigme({('Tom','Matt'):6, ('Lambert','Ginne'):4, ('Carl','Roth'):2, ('Kurt','Jett'):4, ('Ayet','Finzerb'):3}).

Question 7. En déduire ce que calcule enigme en général.

Question 8. Que renvoie enigme s'il y a strictement moins de 3 candidats ?

Question 9. En utilisant enigme, écrire classement(notes) qui renvoie la liste de tous les (nom, note) triée par notes décroissantes.

Le professeur Tager a conçu un QCM où chaque question dépend de la précédente : dès qu'une réponse est fausse, toutes les suivantes le sont aussi. Les listes de correction sont donc de la forme [True,...,True,False,...,False].

def renote_express(copcorr):
    c = 0
    while copcorr[c]:
        c = c + 1
    return c
 
def renote_express2(copcorr):
    gauche, droite = 0, len(copcorr)
    while droite - gauche > 1:
        milieu = (gauche + droite) // 2
        if copcorr[milieu]:
            ...
        else:
            ...
    if copcorr[gauche]:
        return ...
    else:
        return ...

Question 10. Compléter renote_express2 pour qu'elle calcule la même chose que renote_express.

Question 11. Donner les coûts en temps de renote_express et renote_express2 en fonction de la longueur n de la liste.

Question 12. Expliquer comment adapter renote_express2 pour calculer directement la note d'une copie (sans construire de liste de booléens intermédiaire).

Exercice 3 — Graphes, algorithmes de plus court chemin, bases de données (8 points)

La société CarteMap teste un prototype de GPS sur une carte fictive de 7 villes A à G reliées par 9 routes à double sens : A-B (4 km), A-E (4 km), B-F (7 km), B-G (5 km), C-E (8 km), C-D (4 km), D-E (6 km), D-F (8 km), F-G (3 km).

Question 1. Représenter ce graphe pondéré G1.

Question 2. Déterminer le chemin le plus court entre A et D.

Question 3. Donner la matrice d'adjacence pondérée de G1 (sommets dans l'ordre alphabétique).

On travaille ensuite sur un graphe non pondéré G2 (mêmes 7 villes, plus 2 villes H et I) : A-B, A-C, A-H, B-I, C-E, C-D, G-E, G-F, H-G, H-I, I-F.

Question 4. Proposer une implémentation de G2 par un dictionnaire Python.

Question 5. Proposer un parcours en largeur de G2 depuis A.

CarteMap veut les itinéraires traversant le moins de villes possible. Exemple : pour A→E, l'itinéraire A-C-E traverse 1 ville (C) contre 2 pour A-H-G-E. On donne le programme :

tab_itineraires = []
 
def cherche_itineraires(G, start, end, chaine=[]):
    chaine = chaine + [start]
    if start == end:
        return chaine
    for u in G[start]:
        if u not in chaine:
            nchemin = cherche_itineraires(G, u, end, chaine)
            if len(nchemin) != 0:
                tab_itineraires.append(nchemin)
    return []
 
def itineraires_court(G, dep, arr):
    cherche_itineraires(G, dep, arr)
    tab_court = ...
    mini = float('inf')
    for v in tab_itineraires:
        if len(v) <= ... :
            mini = ...
    for v in tab_itineraires:
        if len(v) == mini:
            tab_court.append(...)
    return tab_court

Exemple : itineraires_court(G2, 'A', 'F') renvoie [['A','B','I','F'], ['A','H','G','F'], ['A','H','I','F']].

Question 6. Pourquoi cherche_itineraires est-elle qualifiée de récursive ?

Question 7. Expliquer son rôle dans le programme.

Question 8. Compléter itineraires_court.

Question 9. En testant itineraires_court(G2,'A','E') puis, sans relancer le programme, itineraires_court(G2,'A','F'), on obtient deux fois [['A','C','E']] (résultat incorrect pour le second appel). En relançant le programme entre les deux appels, les résultats redeviennent corrects. Expliquer ce problème.

CarteMap ajoute des données sur les villes et opte pour une base de données relationnelle plutôt qu'un fichier texte.

Question 10. Pourquoi un SGBD est-il préférable à un simple fichier texte ici ?

Tables :

ville : id, nom, num_dep, nombre_hab, superficie — (1,Annecy,74,125694,67), (2,Tours,37,136252,34.4), (3,Lyon,69,513275,47.9), (4,Chamonix,74,8906,246), (5,Rennes,35,215366,50.4), (6,Nice,06,342522,72), (7,Bordeaux,33,249712,49.4).

sport : id, nom, type, note, id_ville — (1,Richard Bozon,piscine,9,4), (2,Bignon,terrain multisport,7,5), (3,Ballons perdus,terrain multisport,6,1), (4,Mortier,piscine,8,2), (5,Block'Out,mur d'escalade,8,2), (6,Trabets,mur d'escalade,7,4), (7,Centre aquatique du lac,piscine,9,2).

Question 11. Donner le schéma relationnel de ville. Expliquer le rôle de id_ville dans sport.

Question 12. Résultat de SELECT nom FROM ville WHERE num_dep = 74 AND superficie > 70; ?

Question 13. Requête listant les noms de toutes les piscines de la table sport.

Question 14. La note de « Ballons perdus » passe de 6 à 7 : écrire la requête de mise à jour.

Question 15. Écrire l'insertion de Toulouse (id 8, département 31, superficie 118 km², 471941 habitants en 2023).

Question 16. Requête listant les noms des murs d'escalade disponibles à Annecy.