Bac NSI 2025 — Sujet 25-NSIPE2

Sujet officiel du baccalauréat général, épreuve d'enseignement de spécialité numérique et sciences informatiques, session 2025 (le centre d'examen précis n'est pas identifiable dans le texte du sujet). Durée 3 heures 30, calculatrice non autorisée. 3 exercices indépendants, tous à traiter.

Exercice 1 (6 points) — Programmation Python et programmation dynamique

« An algorithm must be seen to be believed. » (Donald Knuth)

En typographie, l'alignement justifié d'un texte donne à chaque ligne la même longueur (la justification), en ajoutant si besoin des espaces supplémentaires. Une espace désigne ici exactement un caractère ' '. On suppose tous les caractères (espaces comprises) de largeur identique, et les mots ne sont ni coupés ni décorés.

Règle de répartition des espaces supplémentaires :

• s'il n'y a qu'un mot, on insère toutes les espaces à sa droite ;
• sinon, on effectue la division euclidienne du nombre total d'espaces à ajouter par le nombre d'emplacements inter-mots, on répartit le quotient entre chaque emplacement, puis on distribue le reste une espace à la fois, de gauche à droite.

Partie A

1. Avec les 4 mots 'An', 'algorithm', 'must', 'be' et une justification de 25 caractères, montrer que le nombre d'espaces nécessaires est 8.

2. Parmi les 4 propositions suivantes (le caractère - représente une espace), déterminer la seule qui respecte les règles de l'alignement justifié pour une justification de 25 caractères :

• An--algorithm---must---be
• An----algorithm--must--be
• An---algorithm---must--be
• An---algorithm--must---be

On considère la fonction ajout_espace(liste_mots, justification), qui prend une liste liste_mots non vide de mots et un entier justification, et renvoie la chaîne justifiée correspondante. On rappelle qu'en Python, le caractère \ en fin de ligne permet de poursuivre une expression sur la ligne suivante sans effet sur son sens.

def ajout_espace(liste_mots: list[str],
                  justification: int) -> str:
    nb_caracteres = sum([len(mot) for mot in liste_mots])
    nb_mots = len(liste_mots)
    assert nb_caracteres + ...
    nb_espace_total = justification - nb_caracteres
    if nb_mots == 1:
        return ... + " " * nb_espace_total
    else:
        q = nb_espace_total // (nb_mots - 1)
        r = nb_espace_total % (nb_mots - 1)
        reponse = liste_mots[0]
        for i in range(1, r + 1):
            reponse = reponse + " " * ... \
                + liste_mots[i]
        for i in range(r + 1, nb_mots):
            reponse = reponse + " " * ... \
                + liste_mots[i]
        return reponse

3. La liste liste_mots peut être trop longue pour tenir sur une ligne de justification donnée. Compléter la précondition (ligne 5) avec le critère à vérifier.

Dans le cas d'au moins deux mots, avec nb_espace_total espaces à répartir entre nb_mots - 1 emplacements, q et r étant le quotient et le reste de la division euclidienne de nb_espace_total par nb_mots - 1 : on place q + 1 espaces pour les r premiers emplacements, puis q espaces pour les suivants.

4. Recopier et compléter les lignes 8, 14 et 17 de ajout_espace.

Partie B

On suppose que la justification est toujours supérieure à la longueur de chaque mot, qui tient donc toujours sur une ligne.

5. Proposer, en langage naturel (sans code), un algorithme permettant de déterminer après quel mot revenir à la ligne, étant donné une justification.

On modélise le découpage d'un texte en lignes par une liste de tuples (début, fin). Par exemple, pour ['An', 'algorithm', 'must', 'be', 'seen', 'to', 'be', 'believed'], le découpage [(0, 2), (2, 5), (5, 7), (7, 8)] signifie : ligne 1 = mots d'indice 0 à 1 (An algorithm), ligne 2 = mots 2 à 4 (must be seen), ligne 3 = mots 5 à 6 (to be), ligne 4 = mot 7 (believed).

6. Recopier et compléter les lignes 5 à 8 de affiche_justifie, qui affiche dans la console les lignes justifiées :

def affiche_justifie(liste_mots: list[str],
                      decoupage: list[(int, int)],
                      justification: int) -> None:
    for ... in decoupage:
        ligne_justifiee = \
            ajout_espace(liste_mots[ ... : ... ], ...)
        ...

Partie C

Les typographes mesurent la qualité esthétique d'une ligne par son coût inesthétique, qu'on cherche à minimiser :

• le coût inesthétique d'une ligne est le carré du nombre d'espaces supplémentaires nécessaires à sa justification (une espace est toujours due entre deux mots consécutifs d'une ligne ; les espaces supplémentaires sont celles ajoutées en plus) ;
• le coût inesthétique d'un texte pour un découpage donné est la somme des coûts de chaque ligne.

7. Pour une justification de 15 caractères, la liste ['An', 'algorithm', 'must', 'be', 'seen', 'to', 'be', 'believed'] et le découpage [(0, 2), (2, 4), (4, 7), (7, 8)], reproduire et compléter les trois dernières lignes du tableau ci-dessous (coût total du découpage : 147) :

8. Écrire le code d'une fonction cout(i, j, liste_mots, justification) qui renvoie le coût inesthétique de la ligne liste_mots[i:j] si elle tient sur une ligne de justification caractères (espaces inter-mots comprises), et un million sinon. Exemples : cout(0, 2, liste_mots, 15) vaut 9, cout(0, 4, liste_mots, 15) vaut 1000000, cout(5, 8, liste_mots, 15) vaut 1.

9. Pour une liste de n mots (n ≥ 50), on peut revenir à la ligne ou non après chaque mot sauf le dernier. Est-il raisonnable de chercher le découpage optimal en testant toutes ces possibilités ?

On demande à une IA générative un code Python de justifie_dynamique(liste_mots, justification) par programmation dynamique ; elle propose :

def justifie_dynamique(liste_mots: list[str],
                        justification: int) -> list[(int, int)]:
    """Renvoie une liste contenant un découpage de
    'liste_mots' justifiée selon 'justification'."""
    n = len(liste_mots)
    cout_mini = [0] * n
    indice_retour_ligne_mini = [0] * n
    for i in range(n-1, -1, -1):
        cout_mini[i] = cout(i, n, liste_mots, justification)
        indice_mini = n
        for j in range(i+1, n):
            best = cout_mini[j] + cout(i, j, liste_mots, justification)
            if best < cout_mini[i]:
                cout_mini[i] = best
                indice_mini = j
        indice_retour_ligne_mini[i] = indice_mini
    decoupage = []
    k = 0
    while k < n:
        decoupage.append((k, indice_retour_ligne_mini[k]))
        k = indice_retour_ligne_mini[k]
    return decoupage

10. Donner l'ordre de grandeur du nombre d'appels à cout lors de l'exécution de justifie_dynamique, en fonction de n. 11. Établir, à partir du code, la relation entre les éléments de la liste cout_mini. 12. Proposer une modification de justifie_dynamique pour qu'elle renvoie, en plus du découpage, son coût inesthétique.

Exercice 2 (6 points) — Arbres binaires et représentation binaire

On étudie la compression de texte par le codage de Huffman, qui exploite le nombre d'occurrences des caractères. L'arbre arb_julie ci-dessous a été construit pour compresser "julie fuit la pluie" : chaque nœud interne porte l'ensemble des caractères qu'il regroupe et la somme de leurs occurrences ; chaque feuille porte un caractère et son nombre d'occurrences.

Racine (-j-f-e-l-i-p-t-a-u, 19), avec :

• branche 0 → (-j-f-e, 7), qui se sépare en (-, 3) (branche 0, feuille : le caractère espace, 3 occurrences) et (j-f-e, 4) (branche 1), qui se sépare en (j-f, 2) (branche 0 : (j,1) puis (f,1)) et (e, 2) (branche 1, feuille) ;
• branche 1 → (l-i-p-t-a-u, 12), qui se sépare en (l-i, 6) (branche 0 : (l,3) puis (i,3)) et (p-t-a-u, 6) (branche 1), qui se sépare en (p-t-a, 3) (branche 0 : (p,1) puis (t-a,2) qui se sépare en (t,1) et (a,1)) et (u, 3) (branche 1, feuille).

Le code d'un caractère s'obtient en concaténant les 0 (gauche) et 1 (droite) du trajet racine → feuille. Ainsi j → 0100, u → 111, l → 100, i → 101, e → 011, l'espace → 00 : la compression de "julie" donne 0100111100101011.

1. Donner un exemple de feuille de arb_julie, et sa racine. 2. Donner la profondeur du nœud correspondant au caractère p, et son code binaire associé. 3. Les nœuds les plus fréquents ont une profondeur plus petite. Expliquer l'intérêt de cette propriété pour le codage binaire de la phrase.

On définit incomplètement la classe Noeud (nom : chaîne de caractères séparés par des tirets, nb_occu : somme des occurrences correspondantes) :

class Noeud:
    def __init__(self, nom, nb_occu, fils_g, fils_d):
        ....nom = nom
        ....nb_occu = nb_occu
        ....fils_g = fils_g
        ....fils_d = fils_d
 
    def __str__(self):
        """Renvoie une chaine contenant les données du noeud (nom et nombre d'occurrences)."""
        return '(' + ... .nom + ',' + str(...) + ')'

4. Recopier et compléter les lignes 3, 4, 5, 6 et 13 de la classe Noeud.

On veut une fonction liste_occurrences(chaine) renvoyant la liste des tuples (c, nb_occu) (c un caractère de chaine, nb_occu son nombre d'occurrences). Exemple : liste_occurrences('julie fuit la pluie') renvoie [('j', 1), ('u', 3), ('l', 3), ('i', 3), ('e', 2), (' ', 3), ('f', 1), ('t', 1), ('a', 1), ('p', 1)].

def liste_occurrences(chaine):
    dico = ...
    for c in chaine:
        if c in ...:
            dico[c] = dico[c] + 1
        else:
            ...
    liste_res = ...
    for cle in dico:
        liste_res....
    return ...

5. Recopier et compléter liste_occurrences.

Pour élaborer l'arbre, on trie d'abord la liste des tuples par occurrence croissante, avec un tri par insertion (on rappelle que l.insert(i, ele) insère ele à la position i dans l) :

def tri_liste(liste_a_trier):
    liste_triee = []
    for i in range(0, ...):
        element = liste_a_trier[i]
        ...
        while (j < len(liste_triee) and
               element[1] >= liste_triee[j][1]):
            ...
        liste_triee.insert(..., ...)
    return liste_triee

6. Recopier et compléter tri_liste. 7. Écrire une fonction conversion_en_noeuds qui convertit une liste de tuples (c, nb_occu) en liste de nœuds.

On insère un nœud dans une liste de nœuds déjà triée par nb_occu croissant :

def insere_noeud(noeud, liste_noeud):
    j = 0
    while j < len(liste_noeud) and ... > ...:
        ...
    liste_noeud.insert(..., ...)

8. Recopier et compléter insere_noeud.

On construit l'arbre en répétant, jusqu'à n'avoir plus qu'un seul nœud (la racine) : extraire les deux nœuds de plus faible nb_occu, créer un nœud père les regroupant, l'insérer dans la liste.

def construit_arbre(liste):
    while ... > 1:
        noeud1 = liste.pop(0)
        noeud2 = liste.pop(0)
        nom_noeud_pere = noeud1.nom + "-" + noeud2.nom
        nb_occu_noeud_pere = ...
        noeud_pere = Noeud(...)
        insere_noeud(..., liste)
    return ...

9. Recopier et compléter construit_arbre, qui renvoie le nœud racine.

On admet disposer de codage_arbre(arbre), qui renvoie par exemple pour arb_julie : {' ': '00', 'j': '0100', 'f': '0101', 'e': '011', 'l': '100', 'i': '101', 'p': '1100', 't': '11010', 'a': '11011', 'u': '111'}.

10. Indiquer la structure de données utilisée par codage_arbre. 11. Écrire une fonction compresse(texte, codage) qui renvoie la chaîne binaire compressée. Exemple : compresse('julie', {' ': '00', 'j': '0100', 'f': '0101', 'e': '011', 'l': '100', 'i': '101', 'p': '1100', 't': '11010', 'a': '11011', 'u': '111'}) renvoie '0100111100101011'.

Exercice 3 (8 points) — Programmation objet, graphes et bases de données

Partie A

Un parc d'attractions est représenté par un graphe : sommets = attractions (chacune avec une durée en minutes), arêtes = durée (en minutes) pour aller d'une attraction à l'autre. Toutes les attractions ont des noms uniques.

Attractions et durées : Petits chevaux (6 min), Grand huit (11 min), Grande roue (10 min), Train fantôme (9 min). Trajets : Petits chevaux–Grand huit (7 min), Petits chevaux–Grande roue (4 min), Petits chevaux–Train fantôme (3 min), Grand huit–Train fantôme (5 min), Grande roue–Train fantôme (6 min).

class Attraction:
    def __init__(self, nom, duree):
        self.nom = nom
        self.duree = duree
        self.voisines = []

Représentation partielle en Python :

a1 = Attraction("Grand huit", 11)
a2 = Attraction("Petits chevaux", 6)
a3 = Attraction("Train fantôme", 9)
a4 = Attraction("Grande roue", 10)
a1.voisines = [(a2,7), (a3,5)]
a2.voisines = [(a1,7), (a3,3), (a4,4)]
a3.voisines = [(a1,5), (a2,3), (a4,6)]
a4.voisines = ...

Par mesure de sécurité, la grande roue est ralentie : sa durée est maintenant de 12 minutes.

1. Écrire une ligne de code pour effectuer cette modification. 2. Donner et expliquer la valeur de a2.voisines[2][1]. 3. Expliquer la ligne 7 (a3.voisines = ...) du code. 4. Recopier et compléter la ligne 8 (a4.voisines = ...). 5. Expliquer pourquoi cette modélisation utilise un graphe non orienté.

Une balade est un chemin du graphe, modélisé par un tableau d'attractions ; sa durée est la somme des durées de ses sommets et de ses arêtes. Par exemple [a1, a2, a3, a1, a3] est une balade.

6. Calculer la durée de la balade [a1, a2, a3] et expliquer le calcul. 7. Expliquer pourquoi [a2, a1, a4, a3] n'est pas une balade.

On suppose que deux objets Attraction peuvent être comparés avec ==.

8. Écrire sont_voisines(a, b) qui renvoie True si les deux attractions sont voisines. 9. Écrire est_balade(tableau) qui renvoie True si le tableau donné est une balade.

Pour automatiser la création de balades sans répétition, on propose un parcours de graphe à partir d'une attraction, avec un tableau représentant la balade en construction :

def parcours(attr, deja_vues, balade, nb):
    if not attr.nom in deja_vues:
        deja_vues[attr.nom] = True
        if nb == 0 or sont_voisines(attr, balade[nb-1]):
            balade[nb] = attr
            nb = nb + 1
        for voisine in attr.voisines:
            nb = parcours(voisine[0], deja_vues, balade, nb)
    return nb

10. Donner le type de parcours effectué par parcours. 11. Un tableau balade = [None, None, None, None] (parc à 4 attractions). Déterminer son contenu après parcours(a4, {}, balade, 0) (avec les voisines d'origine, a4.voisines obtenue à la question 4). 12. On modifie a2.voisines = [(a1,7), (a3,3)] et a4.voisines = [(a3,6)]. Déterminer le contenu de tableau après parcours(a3, {}, tableau, 0) avec tableau = [None, None, None, None]. 13. Déduire des appels précédents le nom de la structure de données utilisée pour deja_vues, et expliquer son rôle en une phrase.

Partie B

Les visiteurs volontaires reçoivent un bracelet magnétique permettant de les identifier et de les photographier à des points clés du parc ; les photos leur sont proposées à la vente. Les données personnelles sont stockées en France, avec droit de consultation, retrait et rectification.

Trois relations : visiteur(id : int, nom : text, prenom : text, date : text) — date au format 'AAAA-MM-JJ' ; photo(id : int, #id_visiteur : int, #id_attraction : int, heure : text, prix : float) — heure au format 'HH:MM' ; attraction(id : int, nom : text, duree : int).

Les opérateurs de comparaison classiques s'appliquent aussi aux chaînes de caractères (ex. '2025-01-01' > '2024-01-01' est vrai). SUM(prix) renvoie la somme des valeurs de prix.

14. Expliquer ce qu'est une clé primaire, puis ce qu'est une clé étrangère. 15. Écrire une requête donnant les noms et prénoms (sans doublons) des visiteurs présents le 11 janvier 2025.

Un visiteur, Alan TURING, est venu plusieurs fois en 2024 et a, à chaque fois, acheté toutes les photos proposées.

16. Écrire une requête donnant la somme totale payée par Alan TURING pour des photos au parc en 2024.

Suite à un problème technique, les gérants ont utilisé :

SELECT visiteur.nom, prenom
FROM visiteur JOIN photo ON visiteur.id = photo.id_visiteur
JOIN attraction ON attraction.id = photo.id_attraction
WHERE attraction.nom = 'Grande roue'
  AND heure = '12:34'
  AND date = '2024-07-26';

17. Expliquer ce qu'ils voulaient savoir.

18. Le parc veut désormais proposer, pour un même cliché, plusieurs formats et supports (A5, A6, poster, porte-clé…). Proposer des modifications de la base de données pour prendre en charge cette nouvelle offre.