Bac NSI 2025 Amérique du Nord jour 2 bis : corrigé 25-NSIPE2

Les mots contiennent 2+9+4+2=17 lettres. La ligne doit mesurer 25 caractères : il faut donc 25−17=8 espaces au total. Ces huit espaces comprennent les séparations ordinaires entre mots ; ce ne sont pas huit espaces ajoutés à trois espaces déjà présents.

La troisième proposition convient :An---algorithm---must--be. Il y a trois intervalles et 8=3×2+2 : deux espaces dans chacun, puis un supplémentaire dans les deux premiers. On obtient donc 3,3,2 espaces de gauche à droite.

assert nb_caracteres + nb_mots - 1 <= justification

Entre nb_mots mots, il faut au moins nb_mots−1 espaces. La somme des lettres seules ne suffit donc pas à décider si la ligne tient. La liste de mots est non vide par contrat. Pour un seul mot, le nombre minimal d’espaces inter-mots vaut 0, ce que cette formule traite correctement.

def ajout_espace(liste_mots, justification):
    nb_caracteres = sum(len(mot) for mot in liste_mots)
    nb_mots = len(liste_mots)
    assert nb_caracteres + nb_mots - 1 <= justification
    nb_espace_total = justification - nb_caracteres
    if nb_mots == 1:
        return liste_mots[0] + ' ' * nb_espace_total
    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 + ' ' * (q + 1) + liste_mots[i]
    for i in range(r + 1, nb_mots):
        reponse = reponse + ' ' * q + liste_mots[i]
    return reponse

Les compléments sont liste_mots[0], q+1 puisq. La première boucle traite exactement r intervalles, de 1 àr inclus. La seconde traite tous les suivants. La concaténation ajoute toujours les espaces avant le mot suivant. La longueur finale vaut la somme des lettres plus tous les espaces distribués, donc la justification demandée.

Le cas d’un seul mot est traité avant la division par nb_mots−1, pour éviter un dénominateur nul. Si r vaut 0, la première boucle est vide et tous les intervalles reçoivent q espaces. Tester une ligne avec un seul mot, un reste nul et un reste non nul couvre les trois mécanismes.

Parcourir les mots dans l’ordre et construire la ligne courante. Avant d’ajouter un mot, compter sa longueur et l’espace qui le sépare du précédent. Si l’ajout tient dans la justification, le conserver sur cette ligne ; sinon, terminer la ligne avant ce mot et démarrer une nouvelle ligne avec lui.À la fin, conserver la dernière ligne.

Le premier mot d’une ligne ne nécessite pas d’espace préalable. Cet algorithme remplit chaque ligne autant que possible : il est glouton. Il produit un découpage valide mais ne garantit pas de minimiser le coût esthétique qui sera défini ensuite.

def affiche_justifie(liste_mots, decoupage, justification):
    for debut, fin in decoupage:
        ligne_justifiee = ajout_espace(liste_mots[debut:fin], justification)
        print(ligne_justifiee)

Chaque tuple désigne une tranche dont la borne finale est exclue. Le déballage fournit directement les deux indices. Un appel à ajout_espace transforme seulement les mots de cette ligne, puis print l’affiche. La fonction n’a pas besoin de renvoyer un texte complet : son contrat demande un affichage.

Le total vaut 9+64+25+49=147. Les espaces supplémentaires sont ceux qui s’ajoutent à l’unique séparation ordinaire entre chaque paire de mots. Par exemple must be a 6 lettres et un espace obligatoire, donc 15−7=8 espaces supplémentaires, coût 64. Pour believed seul, les 7 espaces à droite sont tous supplémentaires.

def cout(i, j, liste_mots, justification):
    longueur = sum(len(mot) for mot in liste_mots[i:j]) + (j - i - 1)
    if longueur > justification:
        return 1000000
    return (justification - longueur) ** 2

La longueur minimale combine les lettres de la tranche et ses j−i−1 séparations.C’est cette longueur qu’il faut comparer à la justification. Lorsque la ligne tient, la différence est le nombre d’espaces supplémentaires. Le carré pénalise davantage une ligne très étirée que plusieurs lignes peu étirées.

assert cout(0,2,liste_mots,15) == 9
assert cout(0,4,liste_mots,15) == 1000000
assert cout(5,8,liste_mots,15) == 1

Le contrat utilisé par les algorithmes porte sur une tranche non vide,0≤i< j≤n. Le nombre 1000000 est la pénalité imposée par le sujet pour une ligne impossible ; une implantation générale utiliserait plutôt l’infini pour que cette pénalité ne puisse jamais être préférable à un coût valide très grand.

Non en général. Il y a n−1 positions possibles de retour à la ligne, avec deux choix indépendants à chacune : couper ou ne pas couper. Donc 2ⁿ⁻¹ découpages potentiels. Pour 50 mots, cela donne 2⁴⁹=562949953421312 possibilités avant même leur évaluation. Beaucoup sont invalides, mais les énumérer toutes reste prohibitif.

Le nombre exact est n+n(n−1)/2=n(n+1)/2, donc Θ(n²) appels. Chaque indicei effectue un appel initial cout(i, n), puis n−i−1 appels dans la boucle surj. La somme forme une série arithmétique.

La question porte sur le nombre d’appels, pas sur le temps total. Si chaque cout parcourt une tranche pour additionner ses longueurs, ces appels ne coûtent pas tous un temps constant. Une somme préfixe des longueurs pourrait accélérer ce calcul, mais ne change pas le décompte quadratique des appels demandés ici.

Notons C[i] le coût minimal du suffixe commençant au moti et posons C[n]=0. Pour chaquei, on choisit l’indicej qui termine la première ligne :C[i] = min(cout(i,j,liste_mots,justification) + C[j] pour i<j≤n). Le code traite j=n dans l’initialisation, et les autres j dans la boucle.

Les indicesi sont parcourus en décroissant : lorsque C[i] est calculé, tous les C[j] avecj> i sont déjà connus. Chaque candidat combine le coût de sa première ligne avec le meilleur coût possible de tout ce qui suit. Le tableau indice_retour_ligne_mini mémorise ensuite le choixj pour reconstruire un découpage, au lieu de recalculer les décisions.

Pour les huit mots et une justification 15, on obtient C=[19,42,10,41,74,1,16,49]. Le découpage optimal[(0,2),(2,5),(5,8)] coûte 9+9+1=19, contre 147 pour le découpage de la question 7.

return decoupage, (cout_mini[0] if n > 0 else 0)

Cette instruction remplace le return final.C[0] représente le coût optimal de tout le texte ; le coût d’un texte vide est 0. Le résultat devient un tuple(découpage, coût), par exemple([(0,2),(2,5),(5,8)],19) pour la phrase avec justification 15. Il n’est pas nécessaire de recalculer les coûts des lignes : ils ont déjà servi à la programmation dynamique.

La feuille (j,1) convient ; toute autre feuille de caractère serait aussi un exemple. La racine regroupe tous les caractères et porte le poids 19 : son nom suit l’ordre espace-j-f-e-l-i-p-t-a-u. Une feuille n’a pas d’enfant ; la racine n’a pas de parent.

Sa profondeur vaut 4 arêtes et son code est 1100 : droite, droite, gauche, gauche depuis la racine. La profondeur est donc ici aussi la longueur du code. La racine est à la profondeur 0.

Chaque occurrence d’un caractère utilise autant de bits que son code. Si un caractère apparaît f fois et a une profondeur d, il contribue f×d bits au texte compressé. Réduire la profondeur d’un caractère fréquent économise donc davantage de bits que réduire celle d’un caractère rare. Le but est de minimiser cette somme pondérée des longueurs, pas de rendre toutes les feuilles également profondes.

La profondeur n’est pas strictement décroissante avec chaque fréquence à cause des contraintes de structure et des égalités. La propriété utile est globale : le code de Huffman minimise la longueur pondérée parmi les codes préfixes construits pour ces fréquences.

class Noeud:
    def __init__(self, nom, nb_occu, fils_g, fils_d):
        self.nom = nom
        self.nb_occu = nb_occu
        self.fils_g = fils_g
        self.fils_d = fils_d
    def __str__(self):
        return '(' + self.nom + ',' + str(self.nb_occu) + ')'

self désigne l’instance dont les attributs sont initialisés. La conversion str de nb_occu permet de le concaténer aux chaînes de caractères.__str__ renvoie le texte, elle ne l’affiche pas directement. Les enfants serontNone pour une feuille et des objetsNoeud pour un nœud interne.

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

Une première occurrence crée le compteur à 1 ; les suivantes l’incrémentent. Le dictionnaire conserve l’ordre d’apparition des clés, ce qui donne l’ordre attendu dans l’exemple. La seconde boucle convertit les associations en tuples, un tuple par caractère distinct. La somme des compteurs doit être égale à la longueur du texte, espaces inclus.

liste_occurrences('julie fuit la pluie')
# [('j',1),('u',3),('l',3),('i',3),('e',2),
#  (' ',3),('f',1),('t',1),('a',1),('p',1)]

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

j part de 0 pour chaque élément et avance tant que les poids déjà présents sont inférieurs ou égaux. Le nouvel élément est inséré après ces poids et avant le premier poids strictement plus grand. La comparaison>= conserve l’ordre relatif des tuples de même fréquence : ce tri est stable. Il ne modifie pas liste_a_trier, mais construit une autre liste.

La garde j<len(liste_triee) est placée en premier pour éviter un accès hors limites. Quand le nouvel élément est le plus grand, j atteint la longueur et insert l’ajoute à la fin. Un élément de poids minimal est inséré à l’indice 0.

def conversion_en_noeuds(liste):
    return [Noeud(c, nb, None, None) for c, nb in liste]

Chaque tuple fournit le nom du caractère et son poids. Comme ces nœuds représentent encore des caractères seuls, leurs deux enfants valentNone.L’ordre est conservé : une liste de tuples triée devient une liste de nœuds triée selon le même poids.

def insere_noeud(noeud, liste_noeud):
    j = 0
    while j < len(liste_noeud) and noeud.nb_occu > liste_noeud[j].nb_occu:
        j += 1
    liste_noeud.insert(j, noeud)

La comparaison stricte imposée par le squelette insère le nouveau nœud avant les nœuds de même poids. La liste reste triée, mais cette convention d’égalité diffère de celle du tri précédent. Elle contribue à reproduire précisément l’arbre de la figure lorsque plusieurs combinaisons de mêmes poids sont possibles. La fonction modifie la liste et ne renvoie pas une nouvelle liste.

def construit_arbre(liste):
    assert len(liste) > 0
    while len(liste) > 1:
        noeud1 = liste.pop(0)
        noeud2 = liste.pop(0)
        nom_noeud_pere = noeud1.nom + '-' + noeud2.nom
        nb_occu_noeud_pere = noeud1.nb_occu + noeud2.nb_occu
        noeud_pere = Noeud(nom_noeud_pere,nb_occu_noeud_pere,noeud1,noeud2)
        insere_noeud(noeud_pere, liste)
    return liste[0]

Les deux pop(0) extraient successivement les deux premiers éléments de la liste triée. Le poids du père est leur somme et ses enfants sont les deux objets extraits. Le nom concatène leurs noms pour décrire les caractères regroupés. Le père est réinséré à sa place selon son poids, ce qui maintient la précondition de l’itération suivante.

Chaque tour enlève deux nœuds actifs et en remet un : la longueur de la liste diminue de 1. Avec k caractères distincts, on effectue k−1 regroupements. Dans cet exemple, les deux premières feuilles regroupées sont j et f, de poids 1 chacune. La liste d’entrée est modifiée. La garde précise que construire cet arbre attend au moins une feuille ; le texte vide demanderait une convention d’arbre vide séparée.

C’est un dictionnaire Python. Ses clés sont les caractères et ses valeurs les chaînes de bits de leurs codes. Chaque caractère doit apparaître une seule fois comme clé ; les codes peuvent avoir des longueurs différentes.

def compresse(texte, codage):
    resultat = ''
    for caractere in texte:
        resultat += codage[caractere]
    return resultat

Le parcours respecte l’ordre du texte et concatène les codes sans séparateur.L’arbre de Huffman produit un code préfixe : aucun code de feuille n’est le préfixe d’un autre, ce qui permet de retrouver les frontières lors du décodage en parcourant l’arbre. La table doit contenir tous les caractères du message ; sinon l’accès au dictionnaire échoue, ce qui signale un codage inadapté.

assert compresse('julie',codage) == '0100111100101011'
assert compresse('',codage) == ''

Le mot julie utilise 16 bits avec cette table. La phrase complète utilise 61 bits de données, contre 152 pour 19 caractères à 8 bits. Cette comparaison n’inclut pas le stockage ou la transmission de l’arbre : pour un message aussi court, cet overhead peut peser davantage que l’économie.

a4.duree = 12

La variablea 4 référence la grande roue. On modifie son attributduree ; les temps de déplacement des arêtes restent inchangés. Aucune nouvelle instance n’est nécessaire.

La valeur est 4.L’indice 2 sélectionne le troisième tuple des voisines de a2, soit(a4,4).L’indice 1 de ce tuple sélectionne ensuite la durée du trajet,4 minutes. Ce n’est ni la durée de la grande roue ni son numéro.

Le train fantôme est relié au grand huit en 5 minutes, aux petits chevaux en 3 minutes et à la grande roue en 6 minutes. Les premières composantes sont les objetsAttraction correspondants ; les secondes sont les durées des trajets. Cette liste sert à retrouver à la fois les connexions et leurs poids.

a4.voisines = [(a2,4),(a3,6)]

La grande roue est reliée aux petits chevaux et au train fantôme. Les liaisons sont enregistrées dans les deux sens puisqu’on utilise un graphe non orienté. Il n’existe pas de liaison directe entre a4 et a1.

Les chemins du parc peuvent être parcourus dans les deux sens avec les mêmes durées dans ce modèle. Une seule arête représente donc la liaison réciproque. Si un trajet était à sens unique ou avait des durées différentes selon le sens, une représentation orientée serait nécessaire ; ce n’est pas l’hypothèse du sujet.

On additionne les attractions 11+6+9=26 minutes et les trajetsa 1-a2=7 minutes, puis a2-a3=3 minutes. La balade dure donc 26+7+3=36 minutes. On compte chaque attraction parcourue, y compris celle de départ et celle d’arrivée.

Les attractionsa 1 et a4 ne sont pas directement voisines. Le passage du grand huit à la grande roue rompt donc la condition de chemin, même si les deux autres transitions existent. Il ne suffit pas que toutes les attractions soient présentes dans le graphe.

def sont_voisines(a,b):
    for voisine, duree in a.voisines:
        if voisine == b:
            return True
    return False

Chaque élément de a.voisines est un tuple : on compare sa première composante àb. Un test b in a.voisines comparerait l’objetb à des tuples et ne répondrait pas correctement. La durée est déballée mais n’intervient pas dans le booléen. Un voisin trouvé permet un retourTrue ;False doit attendre la fin de la boucle.

def est_balade(tableau):
    for i in range(len(tableau) - 1):
        if not sont_voisines(tableau[i], tableau[i + 1]):
            return False
    return True

La boucle traite les n−1 transitions entre n attractions. Le premier défaut suffit à répondreFalse ;True après la boucle signifie que toutes les transitions ont été validées. Cette version accepte une balade d’une attraction et, par convention de test de toutes les transitions, le tableau vide. Si l’application exige au moins une attraction, il faudrait ajouter cette précondition explicitement.

Les répétitions ne sont pas interdites par cette question : elles le seront dans la création automatique décrite ensuite. Il ne faut donc pas ajouter un test d’unicité qui rejetterait l’exemple[a1,a2,a3,a1,a3].

Un parcours en profondeur : l’appel récursif explore une voisine et ses descendantes avant de passer à la voisine suivante. Le dictionnairedeja_vues évite de retraiter une attraction déjà rencontrée, ce qui empêche les cycles de provoquer une récursion sans fin.

[a4, a2, a1, a3]

Les voisines sont traitées dans l’ordre des listes données. Tous les autres appels concernent alors des noms déjà présents dans deja_vues et n’ajoutent rien. La valeur de retour vaut 4, mais la question porte sur le contenu du tableau modifié.

[a3, a1, a2, None]

Depuis a3, on visite d’aborda 1, puis a2, qui sont ajoutées. La découverte suivante de a4 se produit après le retour récursif à a3, mais la dernière attraction de la balade reste a2. Or a4 n’est plus voisine de a2 : elle est marquée vue sans être ajoutée. Le compteur final vaut 3 et la dernière case resteNone.

Cet exemple montre que le parcours des sommets et la balade produite ne sont pas la même liste. Le code garantit des transitions valides entre les attractions ajoutées, mais ne garantit pas d’inclure toutes les attractions ni de produire la balade la plus longue.

C’est un dictionnaire : l’appel fournit {} et le code associe chaque nom d’attraction à True. Son rôle est de mémoriser les attractions déjà traitées pour ne pas les explorer plusieurs fois. Les noms sont uniques par hypothèse, donc ils peuvent servir de clés de visite.

Une clé primaire identifie une ligne par une valeur unique et non nulle. Une clé étrangère référence une clé d’une autre relation et doit correspondre à une ligne existante, lorsque la référence n’est pas autorisée à être nulle. Ici, photo.id_visiteur relie chaque cliché à une visite et photo.id_attraction à une attraction.

SELECT DISTINCT nom, prenom FROM visiteur WHERE date = '2025-01-11';

Le filtre porte sur la date complète au format du schéma.DISTINCT élimine les paires nom-prénom répétées dans le résultat. Il ne supprime aucune visite enregistrée dans la base.

SELECT SUM(p.prix)
FROM photo AS p JOIN visiteur AS v ON v.id = p.id_visiteur
WHERE v.nom = 'TURING' AND v.prenom = 'Alan'
  AND v.date >= '2024-01-01' AND v.date < '2025-01-01';

La jointure rattache chaque photo à sa visite, ce qui permet de sélectionner le nom, le prénom et les dates de 2024. Le filtre de date couvre toute l’année et exclut 2025.L’hypothèse « toutes les photos achetées » autorise la somme des prix proposés ; sans elle, il manquerait une information d’achat.

Une jointure vers attraction n’est pas nécessaire pour ce total.SUM additionne les prix des lignes retenues. Si aucune ligne ne correspond, SQL renvoie généralementNULL ; COALESCE pourrait donner 0 pour un affichage, mais n’est pas requis par la question.

Les gérants cherchent les noms et prénoms des visiteurs photographiés sur la grande roue à12h 34 lors de leur visite du26juillet 2024. Les jointures relient chaque cliché à son visiteur et à son attraction. Le résultat ne signifie pas que toutes les personnes présentes dans le parc à cette heure ont été photographiées, ni que ces photos ont été achetées. La requête n’utilise pas DISTINCT : une personne peut réapparaître si plusieurs clichés satisfont les filtres.

Conserver photo pour le cliché et ses informations de prise de vue, puis ajouter une relation support décrivant chaque format et une relation offre_photo reliant un cliché à un support avec son prix. La clé composée(id_photo,id_support) empêche de créer deux offres identiques pour le même couple. Les deux identifiants sont des clés étrangères vers photo et support.

Le prix, qui dépend désormais de l’offre, est déplacé de photo vers offre_photo. Les anciennes valeurs doivent être migrées vers une offre de support standard avant la suppression de l’attributinitial. Il faut éviter une colonne textuelle contenant « A5, A6, poster » : elle mélangerait plusieurs valeurs et ne permettrait pas d’associer proprement chaque prix à son support.

Ce modèle décrit ce qui est proposé à la vente. Si le parc veut aussi enregistrer les quantités effectivement achetées, une relation d’achat sera nécessaire, mais cela représente un besoin supplémentaire à celui de l’offre demandé ici.