Corrigé NSI Métropole 2026 – Jour 2

1 à 3. Adresse réseau, diffusion et nombre de machines

Le poste PC C01 a pour adresse 172.16.2.1/16. Le préfixe /16 signifie que les 16 premiers bits sont fixes.

4 à 6. Routage RIP

RIP minimise le nombre de sauts. Depuis R1 vers R2, le chemin le plus court est R1 → R3 → R2.

Un paquet de PC A01 vers PC B01 suit donc : PC A01 → Switch A → R1 → R3 → R2 → Switch B → PC B01.

Si R3 tombe en panne, une route possible de R1 à R2 est : R1 → R4 → R5 → R2.

7 et 8. Coûts OSPF

Le coût est calculé avec la formule 10^8 / débit.

Entre R1 et R4, OSPF ne choisit pas forcément le lien direct : il choisit le chemin de coût minimal. Le chemin R1 → R3 → R4 coûte 0,1 + 1 = 1,1, alors que le lien direct R1 → R4 en Ethernet coûte 10. OSPF choisit donc R1 → R3 → R4.

9. Pourquoi le code initial ne respecte pas la limite

La constante MAX_ROUTES existe, mais la fonction ajoute directement la route avec append. Aucun test ne vérifie la longueur de la liste avant l’ajout.

10. Classe Routage

class Routage:
    def __init__(self, capacite=5):
        self.capacite = capacite
        self.routes = []

    def ajouter(self, route):
        if len(self.routes) < self.capacite:
            self.routes.append(route)
        else:
            print("Erreur : capacité maximale atteinte")

11. Méthode afficher

def afficher(self):
    for route in self.routes:
        print(" ".join(route))

La méthode parcourt chaque route, puis transforme la liste de routeurs en une chaîne lisible.

1. Valeur de melangee[2][1]

Les indices Python commencent à 0. La ligne d’indice 2 est la troisième ligne de la grille mélangée : [2, 10, 9, 4]. La colonne d’indice 1 contient donc :

2 et 3. Création et mélange de la liste aplatie

valeurs = [k for k in range(1, 17)]

La fonction shuffle modifie la liste en place et renvoie None. Il ne faut donc pas écrire valeurs = shuffle(valeurs).

shuffle(valeurs)

4 et 5. Fonction en_grille

def en_grille(valeurs, n):
    assert len(valeurs) == n * n
    grille = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            grille[i][j] = valeurs[i * n + j]
    return grille

Le point sensible est l’indice i * n + j : on remplit la grille ligne par ligne.

6. Grille résoluble ou non

Dans la grille [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,16,15,14]], les inversions sont : (16,15), (16,14) et (15,14), soit 3 inversions. La tuile vide 16 est à deux déplacements de sa position finale. La somme vaut 3 + 2 = 5, qui est impaire.

7 et 8. Tester et corriger compte_inversions

Un test possible avec deux inversions :

assert compte_inversions([1, 4, 2, 3]) == 2

Correction :

def compte_inversions(valeurs):
    total = 0
    for i in range(len(valeurs)):
        for j in range(i + 1, len(valeurs)):
            if valeurs[i] > valeurs[j]:
                total = total + 1
    return total

9 et 10. Distance de la tuile vide et fonction est_resoluble

def distance_tuile_vide(grille, n):
    num_tuile_vide = n * n
    for i in range(n):
        for j in range(n):
            if grille[i][j] == num_tuile_vide:
                return (n - 1 - i) + (n - 1 - j)

def est_resoluble(valeurs, n):
    grille = en_grille(valeurs, n)
    inv = compte_inversions(valeurs)
    dis = distance_tuile_vide(grille, n)
    return (inv + dis) % 2 == 0

11. Voisins de l’indice 9 dans un taquin 4 × 4

Dans une liste aplatie de 16 cases, l’indice 9 est sur la troisième ligne, deuxième colonne. Ses voisins possibles sont haut, bas, gauche et droite :

12. Mélange par graphe

from random import choice

def melange_graphe(nb_dep, n, graphe):
    valeurs = [i + 1 for i in range(n * n)]
    num_tuile_vide = n * n
    actuelle = num_tuile_vide - 1
    for k in range(nb_dep):
        prochaine = choice(graphe[actuelle])
        valeurs[actuelle], valeurs[prochaine] = valeurs[prochaine], valeurs[actuelle]
        actuelle = prochaine
    return en_grille(valeurs, n)

Cette méthode garantit une grille atteignable depuis la grille rangée, car elle simule de vrais déplacements.

1 et 2. Clés primaires et clés étrangères

Les attributs nom et prenom ne conviennent pas comme clé primaire, car plusieurs utilisateurs peuvent avoir le même nom et le même prénom. On utilise donc un identifiant unique.

Dans inscription, les attributs trajet et passager référencent respectivement id_trajet et id_utilisateur. Comme ces identifiants sont des entiers, les clés étrangères le sont aussi.

3. Nombre de passagers du trajet 1291

SELECT COUNT(*)
FROM inscription
WHERE trajet = 1291;

4. Trajets arrivant à Nancy le 19 juin 2026

SELECT *
FROM trajet
WHERE arrivee = 'Nancy'
  AND heure > '2026-06-19 00:00:00'
  AND heure < '2026-06-20 00:00:00'
ORDER BY heure;

5 et 6. Insertion et mise à jour

INSERT INTO trajet
VALUES (1295, 'Nancy', 'Allain', '2026-06-19 17:45:00', 3, 25);

UPDATE trajet
SET heure = '2026-06-19 18:40:00'
WHERE id_trajet = 1294;

7. Pourquoi la suppression du trajet 1296 échoue

Le trajet 1296 est encore référencé dans la table inscription. La base refuse donc de supprimer une ligne parent tant que des lignes enfants la référencent. C’est une contrainte d’intégrité référentielle liée à la clé étrangère trajet.

8. Passagers transportés par l’utilisatrice 25

SELECT DISTINCT utilisateur.nom, utilisateur.prenom
FROM utilisateur
JOIN inscription ON utilisateur.id_utilisateur = inscription.passager
JOIN trajet ON inscription.trajet = trajet.id_trajet
WHERE trajet.conducteur = 25;

Avec les données fournies, cela concerne les passagers des trajets 1291 et 1295.

9. Dictionnaire du graphe

graphe = {
    'C': ['P1', 'P2'],
    'P1': ['C', 'A'],
    'A': ['P1', 'P2', 'P3'],
    'P2': ['C', 'A', 'M'],
    'P3': ['A', 'M'],
    'M': ['P2', 'P3', 'V'],
    'V': ['M']
}

10 à 12. File et parcours utilisé

Une file fonctionne selon le principe FIFO : premier entré, premier sorti. Dans la fonction dico_distance, les sommets sont explorés par distance croissante depuis le départ : il s’agit d’un parcours en largeur.

Depuis P1, un ordre d’insertion possible est : P1, C, A, P2, P3, M, V. L’ordre peut varier selon l’ordre des voisins dans le dictionnaire, mais les distances obtenues restent les mêmes.

13. Fonction excentricité

def excentricite(graphe, sommet):
    dico = dico_distance(graphe, sommet)
    maxi = 0
    for s in dico:
        if dico[s] > maxi:
            maxi = dico[s]
    return maxi

14. Meilleur point de rendez-vous

On compare les points P1, P2 et P3 avec l’excentricité, c’est-à-dire la plus grande distance à un autre sommet. P2 est le meilleur point : il est à distance 1 de C, A et M, et à distance 2 de V et P3.