Bac NSI 2025 — Amérique du Nord — Jour 1

Sujet officiel du baccalauréat général, épreuve d'enseignement de spécialité numérique et sciences informatiques, session 2025, Amérique du Nord, jour 1. Durée 3 heures 30, calculatrice non autorisée. 3 exercices indépendants, tous à traiter.

Exercice 1 (6 points) — Arbres binaires, récursivité et programmation orientée objet

Cet exercice porte sur l'identification de végétaux à partir des caractéristiques de leurs folia (feuilles) : simples ou complexes, disposées de façon alternée ou non, insérées en hélice ou non, en forme d'ovale ou de cœur, à bord denté ou non.

Trois exemples de référence :

• le tilleul a des folia simples, disposées de façon alternée mais pas en hélice, en forme de cœur et à bord denté ;
• le ficus a des folia simples, disposées de façon alternée, insérées en hélice, de forme ovale ;
• le robinier a des folia complexes, disposées de façon alternée et non dentées (le noyer a exactement les mêmes caractéristiques et se retrouve donc dans la même catégorie que le robinier).

On utilise pour identifier un végétal un arbre de décision : un arbre binaire dont chaque nœud (rectangle) pose une question à laquelle on répond par oui ou par non, menant soit à un nouveau nœud, soit à une feuille (ovale) contenant la liste des végétaux correspondants (liste éventuellement vide si aucun végétal connu ne correspond, ou à plusieurs éléments si plusieurs végétaux partagent les mêmes caractéristiques observées).

Un extrait de cet arbre (figure 1, incomplet) a la structure suivante, en partant de la racine :

• « Feuilles simples ? » (racine)
  • oui → « Disposées de façon alternée ? »
    • oui → « Insérées en hélice ? »
      • oui → « En forme d'ovale ? »
        • oui → feuille ['Ficus']
        • non → feuille [] (vide)
      • non → (sous-arbre non représenté, distinguant notamment le tilleul via « bord denté » et « en forme de cœur »)
    • non → (non représenté)
  • non → « Disposées de façon alternée ? »
    • oui → « Bord denté ? »
      • oui → feuille ['Sorbier']
      • non → feuille ['Robinier', 'Noyer']
    • non → (non représenté)

1. On observe un végétal dont les folia sont complexes (non simples), disposées de façon alternée et à bord denté. D'après l'arbre de décision, peut-on l'identifier ? Si oui, lequel ?

2. On observe un végétal dont les folia sont simples, disposées de façon alternée, insérées en hélice et non en forme d'ovale. Peut-on l'identifier ? Si oui, lequel ?

L'arbre de décision est représenté en Python à l'aide de deux classes :

class Noeud:
    def __init__(self, question, sioui, sinon):
        self.question = question
        self.sioui = sioui
        self.sinon = sinon
 
class Feuille_resultat:
    def __init__(self, vegetaux):
        self.vegetaux = vegetaux

Noeud a trois attributs : question (chaîne), sioui et sinon (chacun soit un Noeud, soit un Feuille_resultat). Feuille_resultat a un seul attribut vegetaux, une liste (éventuellement vide) de chaînes.

On donne l'arbre de décision 2 ci-dessous (entièrement spécifié cette fois) :

• « Simples ? » (racine)
  • oui → feuille []
  • non → « Alternées ? »
    • oui → « Bord denté ? »
      • oui → feuille ['Sorbier']
      • non → feuille ['Robinier', 'Noyer']
    • non → feuille []

Par exemple, le dictionnaire folia_sorbier = {'Simples ?': False, 'Alternées ?': True, 'Bord denté ?': True} décrit les folia du sorbier pour cet arbre 2.

3. Écrire le code Python permettant de construire l'arbre de décision 2 et de l'affecter à une variable arbre_2.

On souhaite écrire, pour chacune des classes Noeud et Feuille_resultat, une méthode est_resultat (renvoie True pour un Feuille_resultat, False pour un Noeud).

4. Écrire le code de est_resultat pour la classe Noeud. 5. Écrire le code de est_resultat pour la classe Feuille_resultat.

On souhaite connaître le nombre de végétaux identifiables par un arbre.

6. Écrire le code de nb_vegetaux pour la classe Feuille_resultat. 7. Écrire le code de nb_vegetaux pour la classe Noeud (en tenant compte de tous les végétaux identifiables à partir de ce nœud).

On souhaite enfin une méthode liste_questions pour chaque classe, renvoyant la liste (avec doublons possibles, ordre indifférent) des questions présentes dans l'arbre. Pour l'arbre 2, arbre_2.liste_questions() doit renvoyer une liste contenant 'Simples ?', 'Alternées ?', 'Bord denté ?' (dans un ordre quelconque).

8. Écrire le code de liste_questions pour la classe Feuille_resultat. 9. Écrire le code de liste_questions pour la classe Noeud. On rappelle que + concatène deux listes Python.

Pour représenter les caractéristiques d'un végétal, on utilise un dictionnaire dont les clés sont des questions de l'arbre et les valeurs True/False. On souhaite éviter d'utiliser un arbre pour classifier un végétal à partir d'un dictionnaire mal renseigné (clé manquante).

10. Écrire une fonction est_bien_renseigne(dico_vegetal, arbre) qui renvoie True si toutes les questions présentes dans arbre sont des clés de dico_vegetal.

11. Écrire une fonction identifier_vegetaux(arbre, dico_vegetal) qui renvoie la liste (éventuellement vide) des noms des végétaux dont les folia correspondent aux caractéristiques du dictionnaire. Par exemple identifier_vegetaux(arbre_2, folia_sorbier) doit renvoyer ['Sorbier']. On suppose que toutes les questions de arbre sont des clés de dico_vegetal.

Exercice 2 (6 points) — Programmation orientée objet, récursivité et algorithmes gloutons

Une entreprise gère des colis via une classe Colis : id (identifiant unique, str), poids (float, kg), adresse (str), etat (str parmi 'préparé', 'transit', 'livré', initialisé à 'préparé' à la création).

class Colis:
    def __init__(self, id, poids, adresse):
        self.id = id
        self.poids = poids
        self.adresse = adresse
        self.etat = 'préparé'

1. Écrire la méthode passer_transit de la classe Colis, qui met l'état à 'transit'.

On dispose de ajouter_colis(liste, colis), qui ajoute simplement colis en fin de liste (liste.append(colis)).

2. Dans cette question uniquement, un transporteur refuse les colis de plus de 25 kg. Recopier et modifier ajouter_colis pour qu'elle ajoute le colis seulement si son poids est ≤ 25 kg, et affiche "Dépassement du poids maximal autorisé" sinon.

3. Écrire une fonction nb_colis(liste) qui renvoie le nombre de colis d'une liste d'objets Colis.

4. Recopier et compléter les lignes 2 et 4 de :

def poids_total(liste):
    total = ...
    for c in liste:
        total = ...
    return total

5. Écrire une fonction liste_colis_etat(liste, statut) qui renvoie une nouvelle liste contenant les colis de liste dont l'état vaut statut.

L'entreprise charge un camion (capacité en kg) avec un algorithme glouton : on charge les colis par ordre décroissant de poids, sans dépasser la capacité. Le tri est effectué par :

def tri_decroissant(liste):
    n = len(liste)
    for i in range(n - 1):
        min_pos = i
        for j in range(i + 1, n):
            if liste[j].poids > liste[min_pos].poids:
                min_pos = j
        temp = liste[i]
        liste[i] = liste[min_pos]
        liste[min_pos] = temp
    return liste

6. Donner le nom du tri utilisé dans tri_decroissant et son coût dans le pire des cas. 7. Citer un autre algorithme de tri possible, et son coût dans le pire des cas.

Le chargement récursif est défini par (liste triée par poids décroissants, rang un indice de 0 à len(liste) inclus, capacite la charge restante) :

def chargement_glouton(liste, rang, capacite):
    if rang == len(liste):
        return ...
    elif liste[rang].poids <= ...:
        return ... + chargement_glouton(liste, ..., ...)
    else:
        return chargement_glouton(liste, ..., ...)

8. Recopier et compléter chargement_glouton. 9. Expliquer pourquoi l'exécution de chargement_glouton peut lever RecursionError: maximum recursion depth exceeded. 10. Écrire une fonction chargement_glouton2 itérative (liste triée par poids décroissants, capacite), qui renvoie la liste des colis à charger sans dépasser la capacité.

Exercice 3 (8 points) — Graphes, bases de données, tris, algorithmes gloutons et récursivité

Une association d'enfants (0-18 ans) veut former des groupes d'enfants qui s'entendent durant les activités.

Partie A — base de données

Trois tables :

• parent : nom (nom de famille), tel (numéro de téléphone), codep (code postal) ;
• enfant : id (identifiant), prenom, num_parent (téléphone du parent référent — un seul par enfant), annee (année de naissance) ;
• mesentente : enfant1, enfant2 — deux identifiants d'enfants qui ne peuvent pas sortir ensemble.

num_parent de enfant est une clé étrangère référençant tel de parent ; enfant1 et enfant2 de mesentente référencent id de enfant.

Extrait de la table enfant :

1. Donner le type de l'attribut annee de enfant. 2. Quelle contrainte de domaine supplémentaire serait pertinente pour annee ? 3. Donner un attribut de enfant qui suit une contrainte de référence. 4. Proposer, en justifiant, une clé primaire pour parent.

Suite à une erreur de saisie, le vrai téléphone d'un parent (33619782812) a été transformé en 33600782812. On tente de corriger avec :

UPDATE parent SET tel = 33619782812 WHERE tel = 33600782812;

Cette requête lève une erreur.

5. Expliquer pourquoi.

6. Recopier et compléter cette suite de commandes, qui corrige le téléphone du parent nommé 'Bauges' (code postal 73340, téléphone erroné 33600782812, vrai téléphone 33619782812) :

INSERT INTO parent VALUES ('Bauges', 33619782812, 73340);
UPDATE enfant SET num_parent = ... WHERE num_parent = ...;
DELETE FROM parent WHERE tel = ...;

7. D'après la table enfant fournie, donner le résultat de :

SELECT prenom FROM enfant WHERE annee < 2014 ORDER BY annee;

8. Proposer une requête donnant, par ordre alphabétique, les prénoms des enfants du parent de téléphone 3619861122. 9. Proposer une requête donnant les identifiants et prénoms des enfants dont le parent habite au code postal 38520.

Partie B — graphes et algorithmique

On modélise le graphe non orienté des mésententes par un dictionnaire (sommet → liste des voisins). Exemple, le graphe g1 :

g1 = {'Elise': ['Octavie', 'Virgile'],
      'Octavie': ['Elise', 'Pierre', 'Virgile'],
      'Pierre': ['Octavie', 'Raphael'],
      'Raphael': ['Pierre', 'Virgile'],
      'Sixtine': [],
      'Virgile': ['Elise', 'Octavie', 'Raphael']}

10. Expliquer pourquoi cette situation ne nécessite qu'un graphe non orienté.

11. Dessiner (décrire) le graphe g2 :

g2 = {'Adrien': ['Elisabeth', 'Lea'],
      'Elisabeth': ['Adrien', 'Ian', 'Luca'],
      'Ian': ['Elisabeth', 'Joseph', 'Luca'],
      'Joseph': ['Ian'],
      'Lea': ['Adrien'],
      'Luca': ['Elisabeth', 'Ian']}

12. Écrire une fonction degre(g, s) qui renvoie le degré du sommet s dans le graphe g (nombre d'arêtes issues de s).

13. Recopier et compléter les lignes 7 à 10 de sommets_tries, qui renvoie les sommets de g triés par degré décroissant :

def sommets_tries(g):
    sommets = [sommet for sommet in g]
    n = len(sommets)
    for i in range(1, n):
        sommet_courant = sommets[i]
        j = i - 1
        while ... and ...:
            sommets[...] = sommets[...]
            j = j - 1
        ...
    return sommets

14. Préciser le tri utilisé, et son coût dans le pire des cas selon le nombre n de sommets (on suppose degre de coût constant).

Pour former des groupes, on colore le graphe (deux sommets reliés par une arête n'ont jamais la même couleur). Les couleurs sont des entiers ≥ 0 ; −1 signifie « pas de couleur ». Exemple, g1 colorée avec 6 couleurs :

dc1 = {'Elise': 0, 'Octavie': 1, 'Pierre': 2, 'Raphael': 3, 'Sixtine': 4, 'Virgile': 5}

15. Recopier et colorer g1 en n'utilisant que 3 couleurs (0, 1 et 2).

On dispose de :

def couleurs_voisins(g, dc, s):
    return [dc[v] for v in g[s]]
 
def plus_petite_couleur_hors_voisins(g, dc, s):
    couleur = 0
    n = len(g)
    cvoisins = couleurs_voisins(g, dc, s)
    while couleur < n:
        if couleur not in cvoisins:
            return couleur
        couleur = couleur + 1
    return couleur

16. Recopier et compléter colorer_graphe, qui colore g dans l'ordre des clés de dc (dont les valeurs sont toutes à −1 en pré-condition) :

def colorer_graphe(g, dc):
    for s in dc:
        couleur = ...
        ... = couleur

17. L'algorithme de Welsh-Powell colore les sommets par degré décroissant. Recopier et compléter :

def welsh_powell(g):
    dc = ...
    for ...
        ...
        ...
    return dc