Bac NSI 2025 Asie jour 1

x = 0 et y = 20. La boucle s’exécute dix fois : à chaque tour, x perd 1 et y gagne 1. L’invariant x + y = 20 est conservé et la condition devient fausse pour x nul.

Le code source d’un programme est une suite finie de caractères : lettres, chiffres, espaces, retours à la ligne et symboles. Cette suite peut donc être stockée dans une chaîne. Il faut conserver ses retours à la ligne et son indentation pour préserver le sens du programme.

Une variable qui décroît n’assure pas à elle seule l’arrêt : la condition doit devenir fausse. Dans le programme 6, on teste l’égalité à 0 et non le signe de x.

arret_essai1 exécute le programme puis renvoie True si l’exécution arrive à son terme. Si le programme boucle indéfiniment, la fonction reste bloquée dans exec et ne renvoie jamais False. Elle ne décide donc pas le problème de l’arrêt.

Attendre plus longtemps ou ajouter une limite de temps ne résout pas le problème : un programme peut finir après cette limite.

On aligne le motif sur une portion du texte et on compare ses caractères en partant de la droite. À la première différence, des informations pré-calculées sur le motif permettent de décaler cet alignement de plusieurs positions sans perdre d’occurrence possible. Si tous les caractères correspondent, une occurrence est trouvée.

Dans la variante du « mauvais caractère » étudiée en NSI, le caractère du texte responsable de l’échec sert à choisir un décalage cohérent avec ses positions dans le motif.

def arret_essai2(programme):
    return not recherche("while", programme)

recherche renvoie déjà un booléen ; not inverse sa valeur. Ce test porte sur du texte brut, même si « while » apparaît dans une chaîne ou un commentaire.

for element in iter(int, 1):
    pass

Ce premier contre-exemple ne contient pas « while ». L’itérateur appelle int(), qui renvoie toujours 0, jusqu’à rencontrer 1 : cela n’arrive jamais. Le test textuel renvoie donc True alors que la boucle ne termine pas.

while False:
    pass

Le second texte contient « while », mais la boucle n’effectue aucun tour : le programme termine. Une fonction qui s’appelle récursivement sans fin illustre aussi l’idée dans un modèle théorique, mais en Python concret elle finit généralement par lever RecursionError ; le premier contre-exemple évite cette confusion.

def terminaison_inverse(programme):
    if arret(programme):
        boucle_infinie()

Si arret annonce une terminaison, on lance une boucle infinie. Sinon, le corps conditionnel est ignoré et la fonction atteint sa fin. L’existence de arret est ici une hypothèse pour raisonner, pas une fonction disponible en Python.

Supposons que ce programme termine. Alors arret(programme_paradoxal) est vrai, donc terminaison_inverse boucle indéfiniment : contradiction.

Supposons maintenant qu’il ne termine pas. arret renvoie alors faux, donc terminaison_inverse atteint sa fin : nouvelle contradiction. Les deux réponses possibles contredisent le comportement exigé ; l’hypothèse d’un décideur universel est impossible.

Il n’existe pas de fonction calculable qui, pour tout programme, termine toujours et répond correctement s’il termine. Le problème de l’arrêt est indécidable. Cela n’interdit pas de prouver la terminaison de programmes particuliers, comme les programmes 1 ou 3.

Non. La contradiction utilise la capacité à représenter un programme comme une donnée, à effectuer un test et à boucler. Elle concerne le calcul algorithmique général, pas une faiblesse de la syntaxe de Python. Changer de langage universel ou accélérer la machine ne supprime pas cette impossibilité.

Il y a 10 caractères, espace compris. Le texte occupe donc 10 octets = 80 bits. Ne pas compter seulement les lettres : l’espace est un symbole codé lui aussi.

53 49 58 20 41 4E 41 4E 41 53

On lit chaque caractère dans l’ordre : S, I, X, espace, A, N, A, N, A, S. La répétition d’un caractère répète son code fixe ; A vaut 41 et N vaut 4E.

Un tableau peut présenter les symboles dans un autre ordre sans changer le résultat. Le total vaut 10.

Elle est égale au nombre total de symboles du texte, donc à sa longueur : chaque position contribue exactement une fois à l’effectif du caractère qu’elle contient. Pour txt, elle vaut 10.

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

Un symbole déjà rencontré voit son compteur augmenter de 1 ; un nouveau symbole est initialisé à 1 puisqu’on vient de le lire. Le dictionnaire vide est la bonne réponse pour un texte vide. Le retour vient après le parcours complet.

On fixe ici l’ordre initial des égalités à I, X, SP, S, N, A, par poids croissant. À poids égal, un nouvel arbre est inséré avant les arbres déjà présents, comme l’impose la règle du sujet. Le choix initial entre symboles de même effectif peut produire d’autres arbres corrects : les codes ne sont pas uniques.

Le poids de la racine vaut 10, la somme des occurrences de tous les symboles, donc la longueur du texte. Chaque greffe conserve le poids total de la forêt : les deux poids retirés sont remplacés par leur somme.

Un parcours en profondeur convient, par exemple préfixe, en transportant le chemin depuis la racine. On ajoute 0 en descendant à gauche et 1 à droite ; lorsqu’on atteint une feuille, la chaîne accumulée est le code de son symbole. Le point essentiel est de conserver le chemin, pas seulement de lister les feuilles.

Cette table correspond exactement à notre arbre de la question 6. Un autre arbre valide peut permuter certains bits : il faut surtout assurer la cohérence entre arbre, table et texte codé.

Les feuilles n’ont pas toutes la même profondeur : ici S, N et A ont des codes de 2 bits, l’espace de 3 bits, I et X de 4 bits. Les caractères fréquents reçoivent globalement les chemins courts. La propriété de préfixe, aucun code complet n’étant le début d’un autre, permet de les concaténer sans séparateur.

00 | 1010 | 1011 | 100 | 11 | 01 | 11 | 01 | 11 | 00

0010101011100110111011100

Les barres de la première ligne sont des repères de correction : elles ne sont pas stockées. La concaténation finale contient 25 bits.

Le taux vaut (80 - 25) / 80 = 55 / 80 = 0,6875, soit 68,75 %. Cette valeur appartient à l’intervalle annoncé.

Le calcul demandé compare uniquement le texte codé, sans ajouter le stockage de la table ou de l’arbre et sans arrondir aux octets. Sur un si petit message, ces métadonnées peuvent annuler le gain réel d’un fichier complet : c’est une limite du modèle, pas une erreur du calcul.

SELECT "id-kimono"
FROM location
WHERE fin = '';

La convention dit « chaîne vide », pas NULL. Le filtre doit donc utiliser une égalité avec deux apostrophes.

SELECT COUNT(*)
FROM kimono
WHERE "taille-kimono" = 130;

On compte les lignes de l’inventaire des kimonos, et non les lignes de location : un kimono jamais loué appartient tout de même au club.

SELECT adherent.nom, adherent.prenom
FROM adherent JOIN location
ON adherent."numero-licence" = location."numero-licence"
WHERE location."id-kimono" = 42 AND location.fin = '';

La jointure retrouve l’adhérent à partir de sa licence. Les deux conditions du filtre sont indispensables : identifier le kimono et ne conserver que sa location actuelle.

UPDATE adherent
SET "taille-adherent" = "taille-adherent" + 10
WHERE "taille-adherent" < 160;

La partie droite utilise l’ancienne valeur pour calculer la nouvelle. Un adhérent de 150 cm passe à 160 cm ; celui qui mesure déjà 160 cm ne change pas. Le mot UPDATE, nécessaire à cette question, complète la liste indicative de mots SQL donnée au début.

DELETE FROM location WHERE "id-kimono" = 25;
DELETE FROM kimono WHERE "id-kimono" = 25;

On supprime d’abord ses locations, qui référencent le kimono, puis sa ligne d’inventaire. L’ordre inverse risquerait de violer une contrainte de référence. Dans un service réel, on pourrait archiver le matériel plutôt qu’effacer son historique ; ici le sujet demande bien la suppression.

M12102021NIRRE01 est un numéro possible, en retenant le sexe masculin supposé par la question et le suffixe disponible 01. On assemble M, 12102021, NIRRE, 01. Le suffixe pourrait être un autre entier de 01 à 99 pour distinguer une collision.

Il est né le 23 septembre 1974. Un nom possible est Martin : ses cinq premières lettres, MARTI, correspondent au numéro et il possède plus de cinq caractères. Le numéro ne permet pas de retrouver le nom complet de façon unique.

'STEPHANIE'

tab_adherents[0]['numero-licence']

On choisit d’abord le dictionnaire de Clémence à l’indice 0, puis la clé qui contient sa licence.

def nombre_adherents(table, annee):
    compteur = 0
    for adherent in table:
        if adherent['annee'] == annee:
            compteur = compteur + 1
    return compteur

On compare deux chaînes de même format. Le compteur augmente pour chaque concordance, et non pour chaque année différente. Une table vide ou une année absente donne 0.

def adherent_plus_age(table):
    annee_min = table[0]['annee']
    resultat = []
    for adherent in table:
        annee = adherent['annee']
        if annee < annee_min:
            annee_min = annee
            resultat = [adherent]
        elif annee == annee_min:
            resultat.append(adherent)
    return resultat

Une année plus petite désigne une personne plus âgée. Quand on découvre un nouveau minimum, on remplace la liste des candidats ; quand l’année est égale au minimum, on ajoute l’adhérent. Initialiser à la première année évite un seuil artificiel. L’hypothèse de non-vacuité rend table[0] valide.

def verification_licence(adherent):
    numero = adherent['numero-licence']
    prefixe = (adherent['sexe'] + adherent['jour'] + adherent['mois']
               + adherent['annee'] + adherent['nom'][:5].upper())
    return extraire(numero, 0, 14) == prefixe

Les quatorze premiers caractères déterminent les renseignements à comparer. Le suffixe de deux chiffres ne se déduit pas du seul dictionnaire : il sert à distinguer des collisions dans le registre. upper() rend la comparaison du nom conforme aux majuscules exigées.

Ce code répond au contrôle de concordance demandé. Pour contrôler en plus le format complet, on peut vérifier une longueur de 16 et un suffixe numérique entre 01 et 99, mais cela ne prouve toujours pas que le numéro est unique dans toute la fédération.