Bac NSI 2025 Métropole jour 2

010. Depuis la racine : droite (0), gauche (1), droite (0). L’espace n’est pas un séparateur implicite : c’est une feuille à part entière.

Le texte est espion. On ne découpe pas les bits en blocs de taille fixe : chaque feuille rencontrée indique la fin du code courant. Le dernier bit est consommé exactement à la feuille n, sans reste.

Un parcours en largeur visite les niveaux dans l’ordre des profondeurs. On ne retient que les feuilles rencontrées : leur profondeur est précisément la longueur de leur code. Un parcours en profondeur pourrait atteindre une longue branche avant une feuille plus proche de la racine.

Le premier groupe contient i, u, c, o, d, virgule, p, n, j : 7 × 1 + 2 + 2 = 11 occurrences. Le second contient s, espace et e : 3 + 4 + 4 = 11. Les deux sommes sont égales ; l’écart nul est le plus petit possible.

La hauteur vaut 5 : il y a cinq arêtes sur le plus long chemin racine-feuille, pour o ou d. C’est la longueur maximale d’un code de symbole. Il faut compter les arêtes, pas les six nœuds de ce chemin.

Le texte contient 22 caractères, donc 22 octets ou 176 bits avec la convention ASCII du sujet. Shannon-Fano utilise 8 + 21 + 36 + 10 = 75 bits, soit 9,375 octets de données binaires, arrondis à 10 octets pour les stocker dans des octets complets.

Le rapport est 22 / 10 = 2,2 en comptant cet arrondi : l’ordre de grandeur « environ deux fois moins » est justifié. Le calcul ne comprend pas le coût de transmission de l’arbre ou de la table de codage.

Les quatre lettres de fréquence 1 peuvent être ordonnées autrement au départ. Le code reste valide si chaque partage respecte cet ordre et rapproche les poids. Ici, les lettres fréquentes f et r ont des codes plus courts de deux bits.

def creer_dico_occ(texte):
    dico = {}
    for symbole in texte:
        if symbole in dico:
            dico[symbole] = dico[symbole] + 1
        else:
            dico[symbole] = 1
    return dico

Si le symbole est connu, on augmente son compteur ; sinon son premier passage donne le compteur 1. La boucle examine chaque caractère, y compris les espaces et la virgule. Une chaîne vide produit naturellement un dictionnaire vide.

def somme_occ(tab):
    total = 0
    for symbole, nb_occ in tab:
        total = total + nb_occ
    return total

On additionne le second élément de chaque tuple. Le symbole n’intervient pas dans ce calcul. Pour les douze couples du tableau donné, on obtient 22 ; pour une liste vide, 0.

def shannon(symbole, tab):
    if len(tab) == 1:
        return ""
    else:
        t1, t2 = separe(tab)
        if symbole in [elt[0] for elt in t1]:
            return "1" + shannon(symbole, t1)
        else:
            return "0" + shannon(symbole, t2)

Le test détermine dans quel groupe se trouve la feuille cherchée. On ajoute le bit de la branche avant le suffixe calculé récursivement sur ce groupe. Une seule branche est explorée. Lorsque le groupe contient une seule feuille, il ne reste aucune arête à parcourir, d’où la chaîne vide.

Exemple pour e : le premier partage l’envoie dans le groupe droit, préfixe 0 ; le partage suivant à droite encore, préfixe 00 ; le groupe contient alors seulement e.

Pour les partages non vides utilisés dans l’exemple, la longueur du tableau est un entier strictement décroissant à chaque appel récursif. Elle atteint 1, le cas d’arrêt. C’est le variant attendu dans le raisonnement.

Limite du code fourni : sa fonction separe ne garantit pas deux groupes non vides pour toute fréquence possible. Avec [('b', 1), ('a', 5)], la moitié vaut 3 ; la boucle cumule 1 puis 6 et renvoie le tableau entier et une liste vide. Le prochain appel reprend alors exactement le même tableau. On ne peut donc pas affirmer une terminaison générale sans une hypothèse supplémentaire ou une correction.

Voici une variante qui cherche la meilleure coupure parmi les seules coupures intérieures ; elle assure à la fois deux groupes non vides et l’écart minimal :

def separe_robuste(tab):
    assert len(tab) >= 2
    total = somme_occ(tab)
    cumul = 0
    meilleur_ecart = total + 1
    coupure = 1
    for i in range(1, len(tab)):
        cumul = cumul + tab[i - 1][1]
        ecart = abs(total - 2 * cumul)
        if ecart < meilleur_ecart:
            meilleur_ecart = ecart
            coupure = i
    return tab[:coupure], tab[coupure:]

La quantité abs(total - 2 * cumul) est la différence absolue entre les deux sommes. En limitant i entre 1 et len(tab) - 1, aucune branche ne reçoit le tableau entier. Cette amélioration est distincte du code officiel à compléter.

def encode_shannon(texte):
    dico = creer_dico_occ(texte)
    tab = creer_tab_trie(dico)
    resultat = ""
    for symbole in texte:
        resultat = resultat + shannon(symbole, tab)
    return resultat

On calcule les fréquences et le tableau une seule fois pour tout le texte. Chaque caractère utilise ensuite ce même arbre ; recalculer un arbre pour chaque lettre ferait perdre le code commun nécessaire au décodage.

Cette version correspond à l’exercice et fonctionne sur son exemple. Le départage des coupures ex aequo du code fourni diffère de la figure 3 : il donne par exemple j = 100 et p = 10110, tout en conservant 75 bits pour le texte. Pour décoder, on doit utiliser la table réellement produite, pas mélanger ces deux arbres. Pour une utilisation générale, il faut employer une séparation toujours non vide comme celle expliquée en Q11. Un texte composé d’un seul symbole réclame aussi une convention supplémentaire : avec le cas de base fourni, son code est vide. On peut choisir le code 0 et conserver la longueur du message dans le format. Le sujet ne demande pas de définir ce format de fichier.

Plusieurs adhérents peuvent partager un nom de famille. La valeur de nom ne suffit donc pas à identifier une ligne de façon unique. idAdherent, choisi comme clé dans le schéma, distingue les homonymes sans supposer quoi que ce soit sur leurs noms.

Elle renvoie le nom et l’éditeur de chaque jeu, classés par ordre croissant du nom du jeu. Elle ne regroupe pas les jeux par éditeur et ne modifie pas la table.

SELECT nomJeu
FROM emprunt
WHERE dateRendu IS NULL;

NULL se teste avec IS NULL, pas avec = NULL : il représente l’absence de valeur. Le nom du jeu est déjà dans la table d’emprunts, donc aucune jointure n’est nécessaire.

SELECT DISTINCT adherent.nom, adherent.prenom
FROM adherent JOIN emprunt
ON adherent.idAdherent = emprunt.idAdherent
WHERE emprunt.nomJeu = 'Catan';

La jointure relie chaque emprunt à l’adhérent correspondant. DISTINCT élimine les répétitions d’un même couple nom-prénom lorsqu’une personne a emprunté plusieurs fois Catan. Le sujet ne demande pas de limiter aux emprunts actuels.

Deux personnes ayant exactement le même nom et prénom deviennent indiscernables dans cette projection : pour les distinguer, on devrait aussi afficher leur identifiant, mais la question demande seulement nom et prénom.

UPDATE emprunt
SET dateRendu = '2025-06-03'
WHERE idEmprunt = 1538;

Le schéma écrit idEmprunt ; le texte de la question imprime id_emprunt. La requête utilise le nom effectif de la colonne de la figure. L’identifiant permet de viser cet emprunt précis, même si Claire a emprunté plusieurs fois le même jeu.

SELECT nomJeu, categorie
FROM jeu
WHERE anneeSortie >= 2010 AND ageMinimum < 10;

« À partir de 2010 » inclut 2010, alors que « strictement inférieur à 10 » exclut 10. Les deux conditions doivent être vraies simultanément, d’où AND.

Chaque participation relie un adhérent à un événement. idParticipation identifie la ligne, mais ne suffit pas à retrouver les deux entités concernées. Les noms des deux nouvelles colonnes sont proposés : le schéma les laisse à compléter.

dict_emprunts = {}
for jeu in liste:
    if jeu in dict_emprunts:
        dict_emprunts[jeu] = dict_emprunts[jeu] + 1
    else:
        dict_emprunts[jeu] = 1

La liste contient une occurrence par emprunt, pas seulement un exemplaire de chaque nom. On crée la clé au premier emprunt, puis on augmente le compteur aux passages suivants. Une liste vide donne un dictionnaire vide ; aucun jeu absent de la liste n’est inventé avec un compteur nul.

effectifs = []
for nombre in dict_emprunts.values():
    if nombre not in effectifs:
        effectifs.append(nombre)
effectifs.sort(reverse=True)
meilleurs = effectifs[:3]
podium = [[], [], []]
for rang in range(len(meilleurs)):
    for jeu, nombre in dict_emprunts.items():
        if nombre == meilleurs[rang]:
            podium[2 - rang].append(jeu)

On classe d’abord les effectifs distincts, puis on récupère tous les jeux associés aux trois plus grands. Cela évite qu’un ex aequo à la première place occupe artificiellement la deuxième place. L’indice 2 - rang place le maximum à droite, comme dans l’exemple.

Avec les données fournies, les niveaux sont 25, 22 et 18. Le résultat est [['Agricola', 'Puerto Rico', 'Caylus'], ['Codenames', 'Dominion'], ['Terraforming Mars']]. L’ordre à l’intérieur d’une place n’est pas imposé ; la deuxième liste peut donc inverser Codenames et Dominion. Le script garde des listes vides si moins de trois effectifs distincts existent.

Le message obtenu est PGRDX. Les sommes 32 et 29 dépassent 25 ; on leur retire une fois 26. Une seule soustraction suffit puisque la somme de deux rangs est au maximum 50.

def indice(L, element):
    i = 0
    while L[i] != element:
        i = i + 1
    return i

On part de l’indice 0 et on avance jusqu’à l’égalité. La précondition garantit que la recherche rencontre l’élément avant la fin de la liste. Sans cette précondition, il faudrait tester la borne et décider quoi renvoyer si l’élément est absent.

def lettres_vers_indices(texte):
    resultat = []
    for lettre in texte:
        resultat.append(indice(alphabet, lettre))
    return resultat

On parcourt les lettres dans l’ordre du message et on ajoute chaque rang en fin de liste. Des lettres répétées doivent donner des rangs répétés : on ne construit pas un ensemble.

def chiffrement(msg, cle):
    assert len(cle) >= len(msg), 'impossible'
    indices_msg = lettres_vers_indices(msg)
    indices_cle = lettres_vers_indices(cle)
    n = len(msg)
    indices_msg_chiffre = []
    for k in range(n):
        ind = indices_msg[k] + indices_cle[k]
        if ind >= 26:
            ind = ind - 26
        indices_msg_chiffre.append(ind)
    msg_chiffre = indices_vers_lettres(indices_msg_chiffre)
    return msg_chiffre

Pour chaque position du message, on additionne les deux indices de cette même position. Si la somme atteint 26, on la ramène dans l’alphabet. On reconvertit la liste entière seulement après la boucle.

Une clé plus longue est autorisée ; seuls ses premiers len(msg) caractères sont utilisés. La chaîne vide produit une chaîne vide, et aucun accès d’indice n’est effectué.

Une AssertionError portant le message impossible est levée dès la ligne 2 : la clé contient 4 caractères, alors que le message en contient 6. L’exécution s’arrête avant le chiffrement ; aucun message chiffré n’est renvoyé.

Cette réponse suppose l’exécution habituelle de Python, où les assertions sont actives. Une validation de production devrait utiliser un contrôle explicite si elle doit subsister en mode optimisé.

Le message en clair est BRAVO. Une différence négative est augmentée de 26 pour revenir dans l’intervalle des rangs.

On associe leurs rangs aux lettres du texte chiffré et de la clé, puis on calcule position par position rang_chiffre - rang_cle modulo 26. On remplace chaque résultat par sa lettre. La soustraction inverse l’addition du chiffrement : (m + k - k) modulo 26 = m.

def dechiffrement(msg, cle):
    assert len(cle) >= len(msg), 'impossible'
    indices_msg = lettres_vers_indices(msg)
    indices_cle = lettres_vers_indices(cle)
    n = len(msg)
    indices_msg_dechiffre = []
    for k in range(n):
        ind = indices_msg[k] - indices_cle[k]
        if ind < 0:
            ind = ind + 26
        indices_msg_dechiffre.append(ind)
    msg_dechiffre = indices_vers_lettres(indices_msg_dechiffre)
    return msg_dechiffre

La structure reste la même. Deux changements algorithmiques suffisent : soustraire au lieu d’additionner, puis ajouter 26 si le résultat est négatif. Tous les noms de variables désignant le résultat sont adaptés pour ne pas lire par erreur une ancienne liste.

Un chiffrement symétrique utilise un secret partagé entre les interlocuteurs, généralement la même clé pour chiffrer et déchiffrer. Un chiffrement asymétrique utilise une paire liée mathématiquement : une clé publique peut être diffusée, l’autre reste privée. Pour envoyer confidentiellement à Bob, on chiffre avec sa clé publique et il déchiffre avec sa clé privée.

Cette distinction porte sur les clés et leur distribution. À elle seule, elle ne dit pas que l’identité d’un expéditeur a été prouvée.

Bob utilise sa clé privée, associée à la clé publique employée par Alice. Il ne doit pas transmettre cette clé privée à Alice : elle est précisément le secret qui réserve le déchiffrement à Bob.

La clé publique de Bob est publique : un tiers peut donc chiffrer son propre message avec elle et prétendre être Alice. Le fait que Bob puisse déchiffrer le message prouve qu’il lui était destiné, pas qui l’a écrit.

Il faut ajouter un mécanisme d’authentification de l’expéditeur, par exemple une signature vérifiée avec une clé publique d’Alice dont l’identité a été établie. La confidentialité et l’authenticité répondent à deux questions distinctes.

HTTPS est HTTP transporté dans une connexion TLS. Le client vérifie le certificat du serveur, notamment le nom de domaine et la chaîne de confiance, puis un échange cryptographique établit des clés de session. Les données HTTP circulent ensuite avec chiffrement symétrique authentifié, qui protège leur confidentialité et permet de détecter les modifications.

Les mécanismes asymétriques servent notamment à l’authentification et à l’établissement des clés ; le trafic applicatif n’est pas chiffré lettre par lettre avec une clé publique. Les détails exacts de l’échange dépendent de la version et des paramètres TLS.

HTTPS/TLS assemble plusieurs fonctions nécessaires : authentifier le serveur, établir les clés, protéger la confidentialité et l’intégrité des échanges, tout en utilisant un chiffrement symétrique efficace pour les données. Un simple chiffrement avec une clé publique n’authentifie pas à lui seul l’expéditeur ni le propriétaire réel de cette clé.

La formulation « intégralement » du sujet doit être nuancée : HTTPS ne garantit pas que le site est honnête et n’authentifie pas automatiquement Alice auprès de Bob. L’identité d’un utilisateur exige encore un mécanisme adapté, comme une connexion à un compte ou un certificat client.

Aucune réponse n’a été reçue pour les quatre requêtes envoyées à l’adresse visée. Marc s’est trompé de réseau : il faut lancer ping 192.168.110.115, puisque le troisième octet du réseau de l’entreprise est 110, et non 100.

Une absence de réponse ne prouve pas à elle seule que la machine est éteinte : elle peut aussi venir d’un filtrage ou d’une erreur de routage. Ici, l’erreur d’adresse est directement visible dans les données de l’énoncé.

255.255.255.224. Les trois premiers octets valent 255 ; le dernier vaut 128 + 64 + 32 = 224. Le masque contient 27 bits à 1, soit un préfixe /27.

Le /27 laisse 32 - 27 = 5 bits pour les hôtes : il contient donc 2⁵ = 32 adresses au total, de .96 à .127.

Parmi elles, .96 est l’adresse réseau et .127 celle de diffusion : 30 sont attribuables à des interfaces hôtes. Le sujet emploie « total d’adresses pouvant être attribuées » après avoir compté 256 adresses pour un /24 ; on explicite donc les deux nombres pour éviter de confondre capacité totale et hôtes utilisables.

10000110, car 134 = 128 + 4 + 2. Les huit positions de l’octet sont conservées.

La commande n°2 vise Marc, dans le même sous-réseau que Zoé : c’est la réponse attendue si l’on raisonne sur la communication locale directe.

Limite de l’énoncé : il dit aussi que les sous-réseaux sont reliés par des routeurs. Avec un routage et des règles de filtrage permettant la communication, la commande n°1 peut également réussir. Les seules adresses ne permettent donc pas de conclure qu’elle a échoué. Le succès n°2 est cohérent avec une liaison locale ; son exclusivité demanderait des informations supplémentaires sur le routage ou le filtrage.