Sujet du Bac Numérique et Sciences Informatiques 2025 · Amérique du Nord 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.

Exercice 2 (6 points)

Cet exercice porte sur les arbres binaires et la représentation binaire.

L'échange de données sur les réseaux devient de plus en plus important. Il s'avère que la compression est un élément essentiel dans cet échange. On étudie ici un algorithme de compression, reposant sur le codage de Huffman.

Le codage de Huffman est adapté au texte à compresser car on se sert du nombre d'occurrences des caractères dans le texte. Par exemple, l'arbre de la Figure 1 a été construit pour compresser la phrase "julie fuit la pluie". Le nombre associé à un ensemble de caractères correspond à la somme de leur nombre d'occurrences dans la phrase. Chaque chemin parcouru de haut en bas dans l'arbre définit le code associé au caractère présent en bas: ce code est constitué d'un 0 à chaque fois qu'on est allé à gauche et d'un 1 à chaque fois qu'on est allé à droite, mis bout à bout.

La compression de "julie" donne donc: j → 0100, u → 111, l → 100, i → 101, e → 011, soit 0100111100101011. La compression de " " (caractère espace) donne 00.

1.

Donner un exemple de feuille et la racine de l'arbre de la Figure 1.

2.

On rappelle que la profondeur d'un nœud est égale à la distance en nombre d'arêtes entre ce nœud et la racine. Donner la profondeur du nœud correspondant au caractère p et son code binaire associé.

3.

On remarque que sur la Figure 1, les nœuds associés aux caractères 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.

4.

On définit de façon incomplète la classe Noeud:

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 donnees

du noeud (nom et nombre d'occurrences)

"""

return '(' +....nom + ',' + str(...) + ')'

Recopier et compléter les lignes 3, 4, 5, 6 et 13 de la classe Noeud ci-dessus:

5.

On souhaite créer une fonction liste_occurrences:

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...

Recopier et compléter le code de la fonction liste_occurrences:

6.

Recopier et compléter le code de la fonction tri_liste:

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

7.

Une fois la liste triée, il faut ensuite transformer la liste de tuples en liste de nœuds. Écrire la fonction conversion_en_noeuds qui convertit une liste de tuples en liste de nœuds.

8.

Recopier et compléter le code de la fonction insere_noeud qui modifie la liste liste_noeud passée en paramètre:

def insere_noeud(noeud, liste_noeud):

j = 0

while j < len(liste_noeud) and... >...:

...

liste_noeud.insert(...,...)

9.

Recopier et compléter le code de la fonction construit_arbre, qui renvoie le nœud correspondant à la racine de l'arbre:

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...

10.

Indiquer la structure de données renvoyée par la fonction codage_arbre:

11.

Écrire une fonction compresse qui, à partir du texte et de la structure renvoyée par codage_arbre, renvoie la suite binaire sous forme d'une chaîne de caractères représentant le texte compressé.

Exercice 3 (8 points)

Cet exercice porte sur la programmation objet en langage Python, les graphes et les bases de données.

Partie A

Nous avons représenté un parc d’attractions par un graphe. Les sommets de ce graphe sont des attractions. Chaque attraction a une durée (en minutes). Les arêtes de ce graphe représentent la durée (en minutes) pour aller d’une attraction à une autre. Dans ce parc d’attractions, toutes les attractions ont des noms uniques.

Les attractions sont représentées par des objets de la classe Attraction dont le code est donné ci-dessous.

class Attraction:

def __init__(self, nom, duree):

self.nom = nom

self.duree = duree

self.voisines = []

Le graphe précédent peut être représenté, d’une façon incomplète, en langage Python ainsi:

Par mesure de sécurité, les gérants du parc d'attractions ont ralenti la vitesse de rotation de la grande roue. Sa durée est maintenant de 12 minutes.

1.

En considérant la modélisation du parc d'attractions ci-dessus, écrire une ligne de code permettant de faire cette modification.

2.

Donner et expliquer la valeur de l'expression a2.voisines[2][1].

3.

Expliquer la ligne 7 de ce code.

4.

Recopier et compléter la ligne 8 de ce code.

5.

Expliquer pourquoi cette modélisation du parc d'attractions est réalisée avec un graphe non orienté.

Pour faciliter la gestion du parc d'attractions, ses dirigeants proposent aux usagers des balades dans le parc. Une balade est un chemin du graphe représentant le parc d'attractions. Les usagers choisissant une balade doivent faire les attractions dans l'ordre de parcours du chemin. La durée d'une balade est la durée totale pour parcourir la balade, c'est-à-dire la somme des durées de ses sommets et de ses arêtes.

En langage Python, on modélise une balade par un tableau de sommets du graphe. Par exemple, le tableau [a1, a2, a3, a1, a3] est une balade du graphe précédent.

6.

Calculer la durée en minutes de la balade représentée par le tableau [a1, a2, a3] et expliquer le calcul effectué en une phrase.

7.

Expliquer pourquoi le tableau [a2, a1, a4, a3] n'est pas une balade du parc d'attractions.

On considère qu'il est possible de comparer des objets de la classe Attraction entre eux à l'aide de l'opérateur ==.

8.

Écrire une fonction sont_voisines qui prend comme arguments deux attractions de la classe Attraction et qui renvoie True si ces deux attractions sont voisines et False sinon.

def sont_voisines(attr1, attr2):

9.

Écrire une fonction est_balade qui prend comme argument un tableau de sommets de type Attraction et qui renvoie True si ce tableau est une balade et False sinon.

def est_balade(tableau):

Les gérants du parc d'attractions souhaitent automatiser la création de balades, de telle sorte que désormais chaque attraction apparaisse au maximum une fois dans la balade. Pour cela, ils proposent de faire un parcours de graphe à partir d'une des attractions du parc, avec un tableau pouvant représenter une balade en paramètre. Pendant le parcours du graphe, si une attraction est atteignable depuis la dernière attraction placée dans la balade, alors elle est ajoutée à la balade.

Le code suivant est proposé:

1 def parcours(attr, deja_vues, balade, nb):

2 if not attr.nom in deja_vues:

3 deja_vues[attr.nom] = True

4 if nb == 0 or sont_voisines(attr, balade[nb-1]):

5 balade[nb] = attr

6 nb = nb + 1

7 for voisine in attr.voisines:

8 nb = parcours(voisine[0], deja_vues, balade, nb)

9 return nb

10.

Donner le type de parcours effectué par la fonction parcours ci-dessus.

Chaque attraction apparaît au maximum une fois dans une balade. Ainsi, un tableau représentant la balade peut être initialisé à [None, None, None, None] si le parc d'attractions n'a que 4 attractions. Si à l'issue du parcours, les attractions n'ont pas été toutes utilisées, il sera possible de créer une copie partielle du tableau contenant uniquement les éléments différents de None.

11.

Déterminer ce que contient le tableau balade après l'exécution du code ci-dessous, en utilisant les variables a1, a2, a3 et a4:

>>> balade = [ None for _ in range(4) ]

>>> parcours(a4, {}, balade, 0)

12.

Déterminer maintenant ce que contient le tableau tableau après l'exécution du code ci-dessous:

>>> a2.voisines = [(a1,7), (a3,3)]

>>> a4.voisines = [(a3,6)]

>>> tableau = [ None for _ in range(4) ]

>>> parcours(a3, {}, tableau, 0)

13.

Déduire des appels à la fonction parcours le nom de la structure de données utilisée pour la variable deja_vues et expliquer en une phrase son rôle.

Exercice 3 (8 points)

Cet exercice porte sur la programmation objet en langage Python, les graphes et les bases de données.

Partie A

Nous avons représenté un parc d’attractions par un graphe. Les sommets de ce graphe sont des attractions. Chaque attraction a une durée (en minutes). Les arêtes de ce graphe représentent la durée (en minutes) pour aller d’une attraction à une autre. Dans ce parc d’attractions, toutes les attractions ont des noms uniques.

Les attractions sont représentées par des objets de la classe Attraction dont le code est donné ci-dessous.

class Attraction:

def __init__(self, nom, duree):

self.nom = nom

self.duree = duree

self.voisines = []

Le graphe précédent peut être représenté, d’une façon incomplète, en langage Python ainsi:

Partie B: Bases de données

Dans cette partie de l'exercice, on pourra utiliser les clauses du langage SQL pour: construire des requêtes d'interrogation à l'aide de SELECT, FROM, WHERE (avec les opérateurs logiques AND, OR), JOIN... ON; construire des requêtes d'insertion et de mise à jour à l'aide de UPDATE, INSERT, DELETE; affiner les recherches à l'aide de DISTINCT, ORDER BY.

Les visiteurs qui sont d'accord reçoivent un bracelet magnétique à l'entrée du parc d'attractions. Ce bracelet permet de les identifier et de les prendre en photos à différents points clés des attractions. Ces photos leur sont ensuite proposées à la vente. Le système est calibré pour ne pas prendre de photos des personnes ne le souhaitant pas. Les données personnelles associées sont stockées en France et les utilisateurs disposent, conformément à la loi, d'un droit de consultation, de retrait et de rectification.

Pour gérer ces photos et leur vente, le parc d'attractions utilise une base de données. La figure suivante présente une représentation des trois relations de cette base dont les clés primaires sont les attributs soulignés, appelés id dans chaque relation et dont les clés étrangères sont précédées d'un caractère #. Pour chaque attribut est indiqué le nom de l'attribut, et son type après le symbole: le type int représente des entiers, le type text des chaînes de caractères et le type float des nombres flottants.

L'attribut date de la relation visiteur est une chaîne de caractères au format 'année-mois-jour', l'année étant écrite sur 4 chiffres, le mois sur 2 chiffres et le jour sur 2 chiffres. Par exemple, le 1er février 2025 sera représenté par la chaîne de caractères '2025-02-01'. L'attribut heure de la relation photo est une chaîne de caractères au format 'heures:minutes', en utilisant 2 chiffres pour les heures et 2 chiffres pour les minutes. Par exemple, l'heure 5 heures 49 minutes sera représentée par '05:49'.

14.

Expliquer ce qu'est une clé primaire, puis ce qu'est une clé étrangère.

15.

En langage SQL, les opérateurs de comparaison classiques peuvent être utilisés pour comparer des chaînes de caractères entre elles. Par exemple, la condition '2025-01-01' > '2024-01-01' serait évaluée à vrai.

La fonction d'agrégation SUM permet de renvoyer la somme des valeurs d'un attribut. Par exemple, le code ci-dessous permet de déterminer le prix total des photos de la relation photo:

SELECT SUM(prix)

FROM photo;

Écrire une requête en langage SQL qui permet d'obtenir les noms et prénoms des visiteurs présents le 11 janvier 2025 sans doublons.

16.

Un visiteur, Alan TURING, est venu plusieurs fois dans le parc d'attractions en 2024. À chaque visite, il a acheté toutes les photos proposées.

Écrire une requête en langage SQL qui permet d'obtenir la somme totale de ce qu'Alan TURING a payé pour des photos au parc d'attractions en 2024.

17.

Suite à un problème technique, les gérants ont utilisé la requête suivante:

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';

Expliquer ce qu'ils voulaient savoir.

18.

Les gérants du parc d'attractions décident d'étoffer leur offre d'achat de photos en proposant pour un cliché plusieurs formats et supports (A5, A6, poster, porte-clé, …).

Proposer des modifications de la base de données précédente pour qu'elle puisse prendre en charge cette nouvelle offre.