Bac NSI 2025 Amérique du Nord jour 1

Oui : le sorbier. On suit successivement les branches non de « Feuilles simples ? », oui de « Disposées de façon alternée ? », puis oui de « Bord denté ? ». La feuille atteinte contient un seul nom.

Non. Le chemin oui, oui, oui, non aboutit au résultat vide. L’arbre a bien été parcouru jusqu’à une feuille, mais aucun végétal connu du modèle ne correspond à cette combinaison. Ce n’est ni une erreur d’exécution, ni la preuve qu’un tel végétal ne peut pas exister.

arbre_2 = Noeud('Simples ?', Feuille_resultat([]),
    Noeud('Alternées ?',
        Noeud('Bord denté ?', Feuille_resultat(['Sorbier']),
              Feuille_resultat(['Robinier', 'Noyer'])),
        Feuille_resultat([])))

On construit les feuilles, puis les nœuds qui les référencent. L’ordre des arguments est décisif : question, branche oui, branche non. Les deux résultats vides sont des objets Feuille_resultat([]), et non None.

def est_resultat(self):
    return False

Cette méthode s’insère dans la classe Noeud. Un nœud pose une question : ce n’est jamais un résultat, même si ses deux enfants sont des feuilles.

def est_resultat(self):
    return True

La feuille est un résultat même lorsque sa liste de végétaux est vide. Il ne faut donc pas remplacer cette réponse par len(self.vegetaux) > 0.

def nb_vegetaux(self):
    return len(self.vegetaux)

La feuille contenant robinier et noyer contribue pour 2 ; une feuille vide contribue pour 0. On compte les noms enregistrés, pas les feuilles.

def nb_vegetaux(self):
    return self.sioui.nb_vegetaux() + self.sinon.nb_vegetaux()

Chaque sous-arbre sait se compter grâce à la méthode du même nom. On additionne ces résultats ; le nœud-question ne représente lui-même aucun végétal. Pour arbre_2, on obtient 3 noms.

def liste_questions(self):
    return []

Une feuille ne pose aucune question. La liste vide est aussi l’élément neutre de la concaténation utilisée dans le cas récursif.

def liste_questions(self):
    return ([self.question] + self.sioui.liste_questions()
            + self.sinon.liste_questions())

On rassemble la question courante et les listes des deux descendants. Les crochets autour de self.question sont nécessaires : on concatène trois listes, pas une chaîne et des listes.

def est_bien_renseigne(dico_vegetal, arbre):
    for question in arbre.liste_questions():
        if question not in dico_vegetal:
            return False
    return True

Le test porte sur la présence des clés, pas sur leur valeur : une réponse False est une information valide. On ne renvoie True qu’après avoir vérifié toutes les questions. Un arbre réduit à une feuille n’en exige aucune et satisfait donc la condition.

def identifier_vegetaux(arbre, dico_vegetal):
    if arbre.est_resultat():
        return arbre.vegetaux
    if dico_vegetal[arbre.question]:
        return identifier_vegetaux(arbre.sioui, dico_vegetal)
    return identifier_vegetaux(arbre.sinon, dico_vegetal)

Nous choisissons l’ordre des paramètres de l’exemple, arbre puis dictionnaire. Le texte les présente dans l’autre ordre : une solution cohérente avec cet autre ordre est également correcte si les appels sont adaptés. Le cas d’arrêt renvoie la liste de la feuille. À chaque nœud, une seule branche est parcourue, celle correspondant à la réponse ; on ne concatène pas les deux sous-arbres.

def passer_transit(self):
    self.etat = 'transit'

La méthode modifie l’objet sur lequel elle est appelée. Elle n’a pas besoin d’un paramètre etat, puisque la valeur à affecter est imposée, ni de créer un nouveau colis.

def ajouter_colis(liste, colis):
    if colis.poids <= 25:
        liste.append(colis)
    else:
        print('Dépassement du poids maximal autorisé')

La borne 25 kg est acceptée : le test utilise <=. Dans la branche refusée, la liste doit rester inchangée. Cette restriction ne s’applique pas aux autres questions.

def nb_colis(liste):
    return len(liste)

Le nombre d’objets est la longueur de la liste. Une liste vide donne 0, sans traitement particulier.

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

Le cumul commence à 0, l’élément neutre de l’addition. On additionne les attributs poids, pas les objets eux-mêmes. Le retour reste après la boucle, sinon seul le premier colis serait compté.

def liste_colis_etat(liste, statut):
    resultat = []
    for colis in liste:
        if colis.etat == statut:
            resultat.append(colis)
    return resultat

La nouvelle liste est distincte de la liste source, mais contient les références vers les mêmes colis. Le filtre ne change ni l’état des colis ni leur ordre relatif.

Il s’agit d’un tri par sélection, de coût quadratique O(n²). À chaque position, le programme cherche le colis le plus lourd parmi ceux qui restent, puis l’échange avec celui de la position courante. Il effectue n(n - 1)/2 comparaisons de poids.

Le nom min_pos est trompeur : le test > sélectionne ici un maximum pour obtenir l’ordre décroissant.

Le tri fusion a un coût O(n log n) dans le pire des cas. On adapte sa comparaison pour conserver les poids décroissants. Un tri par insertion serait aussi une réponse possible, avec un coût quadratique dans le pire des cas, mais il ne donnerait pas le même gain asymptotique.

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

Quand tous les colis ont été examinés, la liste des choix restants est vide. Si un colis entre, on l’ajoute et on retranche son poids. Sinon, on le saute tout en gardant la même capacité. Dans les deux branches, rang augmente : c’est ce qui rapproche du cas d’arrêt.

Un appel est empilé pour chaque colis considéré. Une liste suffisamment longue peut donc dépasser la profondeur de récursion autorisée par Python, même lorsque le programme possède un cas d’arrêt correct. Ce n’est pas nécessairement une récursion infinie : la profondeur peut simplement être trop grande pour l’interpréteur.

def chargement_glouton2(liste, capacite):
    colis_a_charger = []
    for colis in liste:
        if colis.poids <= capacite:
            colis_a_charger.append(colis)
            capacite = capacite - colis.poids
    return colis_a_charger

La capacité représente ici le poids encore disponible. Le programme traite les colis dans le même ordre et prend exactement les mêmes décisions que la version récursive, avec une seule boucle.

Limite importante du libellé : le sujet parle de « maximiser le poids total ». L’algorithme glouton demandé ne garantit pas l’optimum : pour une capacité de 10 kg et les poids 8, 6, 4 kg, il charge 8 kg, alors que 6 + 4 remplit le camion. La solution attendue met en œuvre la procédure imposée ; on ne doit pas lui attribuer une garantie mathématique qu’elle n’a pas.

INT ou INTEGER : une année de naissance est ici un nombre entier. On ne stocke pas une date complète, puisque seul le millésime est demandé.

Dans le modèle simplifié fondé sur les années, imposer une année de naissance comprise entre l’année courante moins 18 et l’année courante évite les naissances futures et les âges hors du public visé. En 2025, cela correspond à 2007 <= annee <= 2025.

Une année seule ne permet pas de vérifier l’âge exact au jour près : l’intervalle décrit le contrôle cohérent avec cette information limitée. Une application réelle stockerait la date de naissance complète pour appliquer une limite exacte d’âge.

num_parent est une clé étrangère vers parent.tel. Chaque numéro utilisé pour un enfant doit correspondre à un parent présent dans la table parent, sous réserve de la gestion éventuelle de valeurs nulles définie par le schéma.

On choisit tel dans le modèle du sujet : il sert à identifier le parent et est référencé par enfant.num_parent. Il doit donc être unique et non nul. Un nom ou un code postal peut être partagé par plusieurs parents.

Cette unicité est une hypothèse du modèle proposé : dans une vraie famille, plusieurs adultes peuvent partager un numéro. On préférerait alors un identifiant indépendant, mais ce n’est pas le schéma demandé.

UPDATE parent SET tel = 33619782812 WHERE tel = 33600782812;

Des enfants référencent encore l’ancien numéro. Modifier seulement la clé du parent laisserait leurs références sans ligne correspondante : la contrainte de clé étrangère bloque donc la mise à jour.

Cette explication suppose, comme le scénario du sujet, un ancien numéro effectivement référencé et l’absence de propagation automatique ON UPDATE CASCADE. Avec une autre politique de référence, cette même instruction pourrait réussir.

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

On crée d’abord la destination des nouvelles références. On déplace ensuite toutes les références des enfants, puis on supprime le parent devenu non référencé. L’ordre évite tout état intermédiaire avec une clé étrangère orpheline.

On conserve les naissances strictement antérieures à 2014 et on classe les années par ordre croissant : 2009, 2012, 2012, 2013. Hawa et Kian peuvent être intervertis : la requête ne précise aucun critère de départage pour les années égales.

SELECT prenom
FROM enfant
WHERE num_parent = 3619861122
ORDER BY prenom;

Le numéro à utiliser est celui de la question, même s’il n’apparaît pas dans l’extrait fourni. Le filtre porte sur num_parent ; le tri sur prenom. Une jointure n’est pas nécessaire puisque ces deux colonnes sont dans enfant.

SELECT enfant.id, enfant.prenom
FROM enfant JOIN parent ON enfant.num_parent = parent.tel
WHERE parent.codep = 38520;

On relie l’enfant à son parent par les colonnes de référence, puis on filtre sur le code postal du parent. L’identifiant de l’enfant ne doit pas être comparé au téléphone : une jointure relie des valeurs de même signification.

La contrainte « ces deux enfants ne peuvent pas être dans le même groupe » est symétrique. Une arête entre A et B interdit le regroupement de A avec B autant que celui de B avec A. Le modèle décrit une incompatibilité de paire, pas l’opinion orientée d’un enfant sur un autre.

Il comporte six sommets et six arêtes. Chaque paire présente deux fois dans les listes de voisinage ne donne qu’une seule arête non orientée. Le triangle Elisabeth-Ian-Luca est conservé, de même que les deux branches menant à Lea et Joseph.

def degre(g, s):
    return len(g[s])

Dans cette représentation d’un graphe simple, les voisins sont exactement les extrémités des arêtes incidentes. On renvoie donc la longueur de la liste associée, et non le nombre total de clés du dictionnaire.

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 j >= 0 and degre(g, sommets[j]) < degre(g, sommet_courant):
            sommets[j + 1] = sommets[j]
            j = j - 1
        sommets[j + 1] = sommet_courant
    return sommets

On mémorise le sommet courant avant de décaler ceux de degré plus petit vers la droite. La condition j >= 0 doit précéder l’accès à la liste grâce au court-circuit de and. Quand la boucle s’arrête, la place libre est j + 1. Les égalités ne sont pas déplacées : ce tri conserve leur ordre initial.

C’est un tri par insertion, de coût quadratique, O(n²), dans le pire des cas. Un sommet peut être déplacé devant tous les sommets déjà traités, donnant jusqu’à 1 + 2 + ... + (n - 1) déplacements. L’hypothèse sur degre rend chaque comparaison constante.

Vérifiez chaque arête : ses deux couleurs sont différentes. Sixtine, isolée, peut prendre n’importe laquelle des couleurs. Le triangle Elise-Octavie-Virgile impose au moins trois couleurs ; cette coloration est donc minimale pour ce graphe précis.

def colorer_graphe(g, dc):
    for s in dc:
        couleur = plus_petite_couleur_hors_voisins(g, dc, s)
        dc[s] = couleur

On choisit la plus petite couleur absente des voisins, puis on l’enregistre immédiatement. Ainsi les sommets suivants voient ce nouveau choix. Modifier les valeurs du dictionnaire pendant le parcours est autorisé : on ne change pas son ensemble de clés.

def welsh_powell(g):
    dc = {s: -1 for s in g}
    for s in sommets_tries(g):
        couleur = plus_petite_couleur_hors_voisins(g, dc, s)
        dc[s] = couleur
    return dc

Tous les sommets doivent être présents dans dc avant la première recherche de couleur, car couleurs_voisins lit aussi les voisins encore non traités. Leur valeur -1 ne bloque aucune couleur positive ou nulle. L’ordre décroissant vient de la liste renvoyée par sommets_tries, et non de l’ordre initial du dictionnaire.

Sur g1, avec le tri stable ci-dessus, on traite Octavie, Virgile, Elise, Pierre, Raphael, Sixtine et on obtient respectivement 0, 1, 2, 1, 0, 0. Cette stratégie produit une coloration valide ; sa minimalité ne découle pas du seul caractère glouton.