Bac NSI 2025 centres étrangers groupe 1 jour 2

Une clé primaire identifie sans ambiguïté chaque ligne d’une table. Sa valeur est unique et non nulle. id_joueur distingue les personnes, id_equipe les équipes et id_match les rencontres. Les noms peuvent être partagés ou modifiés ; l’identifiant permet aux autres tables de référencer une ligne précise.

L’identifiant permet notamment d’enregistrer plusieurs rencontres entre les mêmes équipes, éventuellement avec le même gagnant et le même score. Utiliser seulement le couple(eq_1,eq_2) comme clé interdirait une revanche entre les mêmes équipes dans les mêmes rôles. Sans nouvel identifiant ni autre attribut discriminant, des rencontres distinctes mais identiques sur tous les champs restants seraient indiscernables.

Les identifiants 26,27,29 et 30 satisfont le filtre. Laure apparaît deux fois car deux personnes différentes portent ce prénom. Sans ORDER BY, l’ordre des lignes n’est pas garanti ; le tableau présente l’ordre de l’extrait pour faciliter la lecture.

SELECT DISTINCT prenom FROM joueur WHERE ann_naiss < 1985;

DISTINCT s’applique aux valeurs projetées, ici au prénom seul. Le résultat comporte Henri, Laure etBrigitte une fois chacun. Il ne supprime aucune personne de la table.

SELECT nom, ann_naiss, num_port FROM joueur WHERE commune = 'Bois-Plage';

La projection respecte les trois colonnes demandées. Le filtre textuel compare à la valeur complète de la commune, avec son trait d’union. Le numéro est conservé comme chaîne, pas converti en entier.

SELECT j.nom, j.prenom
FROM joueur AS j JOIN equipe AS e ON j.id_joueur = e.j_1
WHERE e.nom = 'Les Kangourous';

La jointure suit uniquement j_1. Joindre aussi les trois autres membres répondrait à une autre question. L’absence de cette équipe dans l’extrait n’empêche pas d’écrire la requête sur la base complète ; on ne peut simplement pas annoncer le nom du joueur à partir des lignes visibles.

UPDATE equipe SET points = 5 WHERE id_equipe = 10;

L’identifiant 10 est celui de Volley Warriors dans l’extrait et cible une seule ligne. Une condition sur son nom serait aussi conforme si ce nom identifie bien cette équipe. Sans WHERE, toutes les équipes recevraient 5 points.

DELETE FROM joueur WHERE id_joueur = 35;

La requête demandée est simple, mais le schéma impose une contrainte importante : Volley Warriors référence encore ce joueur dans j_4. Si les clés étrangères sont activées sans cascade adaptée, la suppression sera refusée. Il faut d’abord traiter cette appartenance selon la règle de gestion retenue(remplacement du joueur, annulation d’inscription ou conservation de l’historique). La requête seule ne doit pas être présentée comme forcément exécutable sur les données fournies.

SELECT id_match FROM match WHERE eq_1 = 12 OR eq_2 = 12;

L’équipe peut occuper le premier ou le second rôle. Le OR retient les deux cas ; AND exigerait qu’elle soit les deux équipes du même match. L’équipe gagnante seule ne suffit pas, car les matchs perdus sont aussi des participations.

SELECT m.id_match
FROM match AS m
JOIN equipe AS e ON e.id_equipe = m.eq_1
JOIN joueur AS j ON j.id_joueur = e.j_1
WHERE j.commune = 'Bois-Plage';

La relation se suit en deux étapes : match.eq_1 désigne equipe.id_equipe, puis equipe.j_1 désigne joueur.id_joueur. Le filtre est posé sur la commune de cette personne. Ni l’équipe 2 ni les joueurs 2 à 4 ne doivent intervenir dans la sélection.

SELECT DISTINCT j.nom, j.prenom
FROM match AS m
JOIN equipe AS e ON e.id_equipe = m.eq_1
JOIN joueur AS j ON j.id_joueur = e.j_1
WHERE m.eq_gagnante = m.eq_1
ORDER BY j.nom, j.prenom;

La jointure suit les mêmes rôles que précédemment, puis le filtre exige que l’équipe gagnante soit eq_1. DISTINCT évite qu’une même personne apparaisse plusieurs fois après plusieurs victoires. Le tri s’effectue d’abord sur le nom, puis sur le prénom. La requête ne sélectionne pas les vainqueurs qui jouaient dans l’équipe 2 : cette restriction est explicitement demandée.

E vaut 0x45 et W vaut 0x57. Leur somme vaut 0x9C, soit 156 en décimal. Elle tient déjà sur un octet et n’est donc pas modifiée par la réduction modulo 256.

Elles sont identiques. Les deux mots contiennent les mêmes lettres et la somme est commutative : changer leur ordre ne change ni la somme ni son reste modulo 256. C’est une collision de hachage ; elle ne signifie pas que les mots sont égaux.

def code_hachage(mot):
    somme = 0
    for caractere in mot:
        somme += ord(caractere)
    return somme % 0x100

L’accumulateur commence à 0, la boucle parcourt les caractères du mot et ajoute leur code renvoyé par ord. Le retour réduit seulement la somme finale. On pourrait aussi réduire l’accumulateur à chaque étape : les deux méthodes donnent le même reste final.

0x100 vaut 256. Le modulo renvoie le reste de la division entière par 256, donc un entier entre 0 et 255 inclus. Cela conserve l’octet de poids faible de la somme. Il existe seulement 256 clés : si l’on stocke davantage de mots, des collisions sont inévitables. Le mot vide, si on l’autorisait, aurait pour clé 0.

L’ordre est linéaire :Θ(n). Si le mot doit être placé à la fin, le test mot<liste[i] est effectué pour chacun des n mots avant append. Il peut être effectué une seule fois si le nouveau mot précède le premier. On compte ici les comparaisons entre chaînes, comme demandé ; le coût interne d’une comparaison dépend aussi de la longueur de leur préfixe commun.

c in dico

Pour un dictionnaire, l’opérateur in porte sur les clés. Il ne recherche pas c dans les listes de mots associées.

def ajouter_mot_dict(dict_mots, mot):
    cle = code_hachage(mot)
    if cle not in dict_mots:
        dict_mots[cle] = []
    ajouter_mot_liste(dict_mots[cle], mot)

La clé détermine le groupe. Si ce groupe n’existe pas, on crée sa liste ; sinon, on conserve ses mots. L’insertion ordonnée maintient ensuite la précondition nécessaire à la dichotomie. Ne pas remplacer systématiquement la valeur par[mot], car cela supprimerait tous les mots entrés auparavant avec la même clé. Le contrat fourni autorise les doublons de mots ; une politique d’unicité demanderait un test supplémentaire.

Le code compare d’abord PYTHON àNSI et appelle(0,1). FONCTION est ensuite inférieur àNSI, donc l’appel suivant est(1,1), où il lit NSI et renvoieTrue. C’est bien la trace du programme fourni, même si elle révèle une incohérence : avec fin exclusive, l’intervalle[1,1[ devrait être vide.

Autre défaut de l’exemple : OBJET est placé après PYTHON, donc la liste annoncée n’est pas triée. Cet appel réussit malgré ces erreurs, il ne les valide pas. Il faut conserver cette trace pour répondre à la question, puis corriger les conventions avant de réutiliser la fonction.

Dans une liste triée, la comparaison au milieu permet d’éliminer environ la moitié de l’intervalle : si le mot cherché est plus petit, tous les mots à droite du milieu sont trop grands ; s’il est plus grand, tous ceux de gauche sont trop petits. Une recherche séquentielle peut devoir examiner chaque mot. Sans tri, l’élimination d’une moitié n’est pas justifiée et la dichotomie peut manquer un mot présent.

L’ordre est logarithmique : O(log₂ n), et Θ(log n) dans le pire cas pour une recherche binaire standard. Après k divisions par 2, il reste environ n/2ᵏ candidats ; on atteint une taille constante lorsque k est de l’ordre de log₂n. Une entrée vide se traite sans comparaison de mots.

La recherche calcule d’abord la clé, puis ne visite que la liste correspondante. Une clé absente suffit à répondreFalse. Une clé présente ne prouve pas que le mot existe, à cause des collisions : il faut chercher dans sa liste triée.

def mot_present(dict_mots, mot):
    cle = code_hachage(mot)
    if cle not in dict_mots:
        return False
    liste = dict_mots[cle]
    return est_present(liste, mot, 0, len(liste))

Pour rendre cette fonction correcte sur tous les cas du contrat, voici la correction nécessaire de est_present :

def est_present(liste, mot, debut, fin):
    if debut >= fin:
        return False
    milieu = (debut + fin) // 2
    if liste[milieu] > mot:
        return est_present(liste, mot, debut, milieu)
    if liste[milieu] < mot:
        return est_present(liste, mot, milieu + 1, fin)
    return True

Trois corrections respectent l’intervalle[debut, fin[ : le cas vide est debut>=fin ; la branche gauche garde debut et utilise milieu comme nouvelle fin exclusive ; la branche droite commence à milieu+1. Le milieu a déjà été comparé, on ne le réintroduit donc pas dans la recherche. Le code initial réinitialisait début à 0 et supprimait un candidat supplémentaire à gauche avec milieu−1.

Un test complet inclut le mot absent après le dernier élément, un mot absent avant le premier, une liste vide et un mot situé à une extrémité. Ces cas font apparaître les erreurs de bornes qu’un succès surNSI ne montre pas.

Par exemple 3 → 9 → 1 → 2 → 4 → 8. Chaque paire respecte une relation de divisibilité et aucun nombre ne se répète. À8, les seuls voisins sont 1,2 et 4, tous déjà présents : le chemin est donc non prolongeable. La question n’exige pas de prouver qu’il est le plus long parmi tous les chemins.

Les entiers 1,2,3,4,5,6,7,8 et 9, dans cet ordre. La borne 10 de range(1,10) est exclue.

La valeur est 1.L’indice 0 désigne le premier objet créé, qui représente l’entier 1. Il ne faut pas confondre l’indice dans la liste et le nombre représenté.

s!=self exclut une liaison du sommet vers lui-même. Le reste nul signifie que s.valeur divise exactement self.valeur.La méthode ajoute alors s aux diviseurs de self et self aux multiples de s : les deux objets connaissent leur relation réciproque. Les valeurs du jeu sont positives, donc le calcul du modulo ne divise jamais par zéro.

jeu_9[5] représente 6. Ses diviseurs propres sont 1,2 et 3, donc la liste contient les objets [jeu_9[0],jeu_9[1],jeu_9[2]], dans cet ordre. Ce ne sont pas les entiers eux-mêmes : on obtient les valeurs par la méthode de la question 7. La consigne écrit parfois jeu au lieu de jeu_9 ; on utilise ici la liste du jeu à neuf sommets.

def creer_jeu(n):
    jeu = []
    for valeur in range(1,n+1):
        sommet = Sommet(valeur)
        sommet.relier_diviseurs(jeu)
        jeu.append(sommet)
    return jeu

La ligne est sommet.relier_diviseurs(jeu). Au moment où l’on crée la valeur v, la liste jeu contient déjà 1 àv−1, donc tous les diviseurs propres possibles de v.L’appel met aussi à jour les listes de multiples des anciens sommets. Le sommet courant est ajouté ensuite. Cette construction utilise l’ordre croissant pour ne tester chaque paire qu’une fois.

def lister_diviseurs(self):
    return [sommet.valeur for sommet in self.diviseurs]

La compréhension transforme une liste d’objets en liste de nombres sans modifier les liaisons. Le même principe donne lister_multiples avec self.multiples.Dans le jeu complet,8 possède les diviseurs 1,2,4 ;2 possède les multiples 4,6,8.L’exemple du PDF qui affiche seulement[4,8] pour 2 oublie 6 et ne correspond pas au graphe complet.

l_div_3 = jeu_9[2].lister_diviseurs()
l_mult_3 = jeu_9[2].lister_multiples()
assert 1 in l_div_3
assert 6 in l_mult_3
assert 9 in l_mult_3

Le nombre 3 est à l’indice 2. Son seul diviseur propre est 1 et ses multiples dans 1..9 sont 6 et 9. Ces assertions prouvent la présence des voisins attendus mais pas l’absence de voisins erronés. Pour renforcer le test, on peut aussi vérifier les listes exactes :

assert l_div_3 == [1]
assert l_mult_3 == [6,9]

L’assertion impose que la file contienne un élément avant le retrait. Si elle est vide, une AssertionError interrompt l’appel au lieu de lire une position invalide.C’est une précondition de defiler, qui rappelle que le programme appelant doit contrôler l’état de la file.

def taille(self):
    return len(self.donnees) - self.decalage

len(donnees) compte aussi les éléments déjà retirés.L’indice decalage est précisément leur nombre. La différence donne donc les éléments encore présents. Par exemple, après trois insertions et deux retraits, la liste physique contient toujours trois cases mais la taille logique vaut 1.

f = File()
assert f.est_vide()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
assert f.taille() == 3
assert f.defiler() == 1
assert f.defiler() == 2
assert f.defiler() == 3
assert f.est_vide()
assert f.taille() == 0

Les valeurs de retour vérifient FIFO : le premier entré sort en premier. Une simple vérification de taille ne détecterait pas une structure qui retire les éléments à l’envers. On peut ensuite enfiler 4 et vérifier qu’il ressort correctement malgré decalage déjà avancé ; la file vide ne nécessite pas ici de vider physiquement donnees.

def rechercher_chemins(jeu):
    chemins_np = []
    f = File()
    for sommet in jeu:
        f.enfiler([sommet])
    while not f.est_vide():
        chemin = f.defiler()
        dernier = chemin[-1]
        voisins = dernier.diviseurs + dernier.multiples
        prolongeable = False
        for voisin in voisins:
            if voisin not in chemin:
                prolongeable = True
                f.enfiler(chemin + [voisin])
        if not prolongeable:
            chemins_np.append(chemin)
    return chemins_np

Chaque départ est placé dans la file comme chemin d’un seul objet. Le booléen prolongeable est remis à False pour chaque chemin, puis passe à True dès qu’au moins un voisin admissible existe. Si aucun prolongement n’a été créé, le chemin courant est terminal et est ajouté au résultat.

Le test voisin not in chemin interdit une répétition dans ce chemin, mais n’interdit pas de réutiliser ce sommet dans un autre candidat. Une visite globale par sommet serait incorrecte : les historiques déjà parcourus changent les prolongements encore autorisés. Chaque branche utilise chemin+[voisin], une nouvelle liste.L’algorithme termine puisque chaque chemin utilise au plus n sommets distincts, mais le nombre de chemins peut être très élevé.

def valeurs_chemin(chemin):
    return [sommet.valeur for sommet in chemin]

Les objets restent nécessaires à la recherche pour accéder aux diviseurs et multiples. La projection sur valeur est réservée à l’affichage et à la liste finale. Cette fonction ne modifie pas le chemin d’origine.

chemins = []
for chemin in rechercher_chemins(jeu_9):
    chemins.append(valeurs_chemin(chemin))

Le nom choisi à la question 13 est valeurs_chemin ; la mention chemin_valeur dans cette consigne est une variante typographique à harmoniser.L’accumulation utilise append pour conserver un chemin par élément. Utiliser extend fusionnerait tous les nombres en une liste plate et ferait perdre les frontières entre chemins.

def extraire_plus_longs_chemins(L_chemins):
    resultats = []
    longueur_max = -1
    for chemin in L_chemins:
        if len(chemin) > longueur_max:
            longueur_max = len(chemin)
            resultats = [chemin]
        elif len(chemin) == longueur_max:
            resultats.append(chemin)
    return resultats

Un nouveau maximum remplace les candidats précédents ; une égalité ajoute une autre solution. Initialiser le maximum à−1 permet de traiter aussi une liste contenant un chemin vide. La liste d’entrée vide renvoie[]. Le résultat reste toujours une liste de chemins, même s’il n’y en a qu’un : l’exemple du PDF affichant une liste plate dans ce cas contredit ce contrat.

assert extraire_plus_longs_chemins([[1,3,6,2,4,8]]) == [[1,3,6,2,4,8]]
assert extraire_plus_longs_chemins([[1,7],[3,1,5],[4,1,7]]) == [[3,1,5],[4,1,7]]

Comparer len(chemin) suffit pour choisir le plus long, même si la longueur mathématique du chemin vaut len(chemin)−1 : soustraire la même constante ne change pas les comparaisons. Dans le jeu à 9 sommets, le maximum est 8 sommets, soit 7 arêtes, et 16 chemins atteignent cette taille.

Pas en pratique.L’énumération de tous les chemins simples entraîne une explosion du travail et de la mémoire, notamment dans la file qui conserve les chemins en attente. Le tableau passe de 377 chemins terminaux pour 9 sommets à 9896 pour 14, avec déjà 5279 à 12. La finitude d’un jeu garantit la terminaison théorique de cette exploration, pas un temps ni une mémoire raisonnables pour une taille arbitraire.

Les quelques valeurs du tableau ne suffisent pas à démontrer une formule asymptotique précise. Mais le mécanisme de branchement explique le risque : à chaque prolongement, plusieurs choix peuvent créer plusieurs listes de candidats. Le coût ne se limite pas au nombre de sommets ni aux seuls chemins finalement conservés.