Exercice 1 · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2 bis)

Exercice 1 [6 points]

Cet exercice porte sur la programmation en Python et la programmation dynamique.

Dans cet exercice, on se réfère à la citation suivante de Donald Knuth:

« An algorithm must be seen to be believed. »

En typographie, il existe plusieurs manières d'aligner un texte: aligner à gauche, centrer, aligner à droite et justifier.

L'alignement justifié permet d'obtenir que chaque ligne ait la même longueur appelée justification. Pour cela et pour chacune des lignes, on ajoute si nécessaire des espaces supplémentaires. Dans tout cet exercice, on désigne par une espace exactement un caractère d'espacement, tel que contenu dans la chaîne Python ' '.

On répartit ces espaces supplémentaires ainsi:

s'il n'y a qu'un mot on insère les espaces à droite de celui-ci;

sinon: on effectue la division euclidienne du nombre total d'espaces nécessaires pour compléter la ligne par le nombre d'emplacements inter-mots (entre les mots);

on répartit le quotient d'espaces entre chaque emplacement inter-mot;

puis, s'il reste des espaces à distribuer, on les répartit une par une de gauche à droite.

Dans toute la suite, pour simplifier, on considère que tous les caractères, espaces comprises, ont la même largeur. Les mots ne sont ni coupés, ni décorés (gras, italique, etc.).

Partie A

1.

On considère les quatre premiers mots 'An', 'algorithm', 'must', 'be' de la citation de Donald Knuth avec un alignement justifié de 25 caractères, c'est-à-dire que la ligne contient 25 caractères au total, en comptant les lettres et les espaces.

Montrer que, pour cette justification, le nombre d'espaces nécessaires est de 8.

2.

On souhaite répartir ces 8 espaces entre ces quatre mots.

Déterminer la seule proposition, parmi les quatre propositions ci-après, respectant les règles de l'alignement justifié définies précédemment, pour une justification de 25 caractères. Le caractère - représente ici une espace.

On considère le code de la fonction ajout_espace, donnée ci-après, qui prend en paramètres une liste liste_mots non vide de chaînes de caractères représentant un ensemble de mots et un entier justification représentant la justification. La fonction renvoie une chaîne de caractères constituée des mots de liste_mots à laquelle on ajoute des espaces pour la justifier selon justification.

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.

Dans la fonction ajout_espace ci-dessus, il peut arriver que la liste de mots liste_mots soit trop longue pour tenir sur une seule ligne de justification donnée. Compléter la précondition de cette fonction à la ligne 5 avec un critère que doit vérifier la liste liste_mots, pour être justifiable sur une seule ligne.

4.

Recopier et compléter les lignes 8, 14 et 17 du code de la fonction ajout_espace.

Partie B

5.

Proposer un algorithme en langage naturel permettant de déterminer après quel mot d'un texte revenir à la ligne, étant donné une certaine justification. On attend uniquement une explication précise de l'algorithme, pas sa programmation en Python.

6.

Recopier et compléter les lignes 5 à 8 du code de la fonction affiche_justifie, donné ci-après, qui prend en paramètres une liste de mots, une liste de découpage et une justification puis affiche dans la console Python les lignes justifiées correspondantes.

def affiche_justifie(liste_mots: list[str],

decoupage: list[(int, int)],

justification: int) -> None:

# début de la boucle d'affichage justifié

for... in decoupage:

ligne_justifiee = \

ajout_espace(liste_mots[...:... ],...)

...

Partie C

Dans cette partie, on utilise une fonction qui mesure le défaut d'esthétique, appelé coût inesthétique, que l'on cherche à minimiser. Le coût inesthétique d'une ligne est le carré du nombre d'espaces supplémentaires nécessaires à la justification de cette ligne. Le coût inesthétique d'un texte est la somme des coûts de chaque ligne.

7.

Étant donné une justification de 15 caractères, la liste de mots ['An', 'algorithm', 'must', 'be', 'seen', 'to', 'be', 'believed'] et la liste de découpage [(0, 2), (2, 4), (4, 7), (7, 8)], compléter les trois dernières lignes du tableau ci-après:

Coût total du découpage: 147

Indice du mot de début · Indice du mot de fin + 1 · Nombre de mots · Nombre de caractères · Nombre d'espaces supplémentaires pour atteindre 15 caractères · coût

0 · 2 · 2 · 11 · 3 · 9

2 · 4

4 · 7

7 · 8

8.

Écrire le code d'une fonction cout qui prend en paramètres deux indices i et j, une liste de chaînes de caractères liste_mots et un entier justification représentant le nombre total de caractères souhaités par ligne. Elle renvoie le coût inesthétique de la ligne commençant au mot liste_mots[i] et finissant au mot liste_mots[j-1] si le nombre de caractères (espaces inter-mots comprises) de l'ensemble de ces mots est inférieur ou égal à justification et un million sinon.

9.

Étant donnée une liste de $n$ mots (avec $n \ge 50$), en remarquant qu'on peut revenir à la ligne ou non après chaque mot sauf le dernier, indiquer s'il est raisonnable de déterminer une solution minimisant le coût inesthétique en testant toutes ces possibilités.

On utilise la programmation dynamique implémentée par l'IA dans la fonction justifie_dynamique suivante:

def justifie_dynamique(liste_mots: list[str], justification: int)->list[(int, int)]:

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 à la fonction cout lorsqu'on exécute la fonction justifie_dynamique en fonction de $n$ le nombre de mots dans la liste.

11.

Établir à partir du code de la fonction justifie_dynamique la relation qui existe entre les éléments de la liste cout_mini.

12.

Proposer une modification de la fonction justifie_dynamique pour qu'elle renvoie, en plus du découpage, le coût inesthétique de celui-ci.