Sujet du Bac Numérique et Sciences Informatiques 2024 · Asie Jour 1

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation Python, la programmation orientée objet et l'algorithmique.

Une entreprise doit placer des antennes relais le long d'une rue rectiligne. Une antenne relais de portée (ou rayon) $p$ couvre toutes les maisons qui sont à une distance inférieure ou égale à $p$ de l'antenne.

Connaissant les positions des maisons dans la rue, l'objectif est de placer les antennes le long de la rue, pour que toutes les maisons soient couvertes, tout en minimisant le nombre d'antennes utilisées.

La rue est représentée par un axe, et les maisons sont représentées des points sur cet axe:

Les entités manipulées sont modélisées en utilisant la programmation orientée objet.

class Maison:

def __init__(self, position):

self._position = position

def get_pos_maison(self):

return self._position

class Antenne:

def __init__(self, position, rayon):

self._position = position

self._rayon = rayon

def get_pos_antenne(self):

return self._position

def get_rayon(self):

return self._rayon

1.

Donner le code qui crée et initialise deux variables m1 et m2 avec des instances de la classe Maison situées aux abscisses 1 et 3,5 (Figure 1).

2.

On ajoute à présent une antenne ayant un rayon d'action de 1 à la position 2,5:

Donner le code qui crée la variable a correspondant à l'antenne à la position 2,5 avec le rayon d'action 1.

3.

On souhaite modéliser une rue par une liste d'objets de type Maison. Cette liste sera construite à partir d'une autre liste contenant des nombres correspondant aux positions des maisons. La fonction creation_rue réalise ce travail. Elle prend en paramètre une liste de positions et renvoie une liste d'objets de type Maison.

Recopier le schéma ci-dessous et le compléter pour donner une représentation graphique de la situation créée par:

creation_rue([0, 2, 3, 4, 5, 7, 9, 10.5, 11.5])

4.

Compléter le code donné ci-dessous de la fonction creation_rue.

def creation_rue(pos):

pos.sort()

maisons = []

for p in pos:

m = Maison(p)

maisons.append(...) # Ligne 6

return... # Ligne 7

Pour rappel: la commande tab.sort() trie la liste tab.

5.

La méthode couvre de la classe Antenne prend en paramètre un objet de type Maison et indique par un booléen si l'antenne couvre la maison en question ou non. La méthode peut être utilisée ainsi (en supposant que les objets précédents m1, m2 et a existent):

>>> a.couvre(m1)

False

>>> a.couvre(m2)

True

Compléter la fonction couvre, ci-dessous, en veillant à ne pas accéder directement aux attributs d'une maison depuis la classe Antenne (on pourra utiliser les méthodes get_pos_maison, get_pos_antenne et get_rayon).

Pour rappel: la fonction valeur absolue se nomme abs() en Python.

# Méthode à ajouter dans la classe Antenne

def couvre(self, maison):

6.

La fonction strategie_1 est donnée ci-dessous. L'objectif est de placer des antennes dans une rue. Elle est fournie à la société qui place les antennes. La fonction prend en paramètre une liste d'objets de type Maison (qu'on supposera triée par abscisse croissante) et le rayon d'action des antennes ( float). Cette fonction renvoie une liste d'objets de type Antenne ayant ce rayon d'action et couvrant toutes les maisons de la rue.

def strategie_1(maisons, rayon):

''' Prend en paramètre une liste de maisons et le rayon

d'action des antennes et renvoie une liste d'antennes

'''

antennes = [Antenne(maisons[0].get_pos_maison(), rayon)]

for m in maisons[1:]:

if not antennes[-1].couvre(m):

antennes.append(Antenne(m.get_pos_maison(), rayon))

return antennes

Pour rappel:

tab[1:] correspond aux éléments de tab à partir de l'indice 1 jusqu'à la fin de la liste;

tab[-1] correspond au dernier élément de la liste tab.

Indiquer ce que renvoie cette suite d'instructions après exécution:

>>> maisons = creation_rue([0, 2, 3, 4, 5, 7, 9, 10.5, 11.5])

>>> antennes = strategie_1(maisons, 2)

>>> print([a.get_pos_antenne() for a in antennes])

7.

Une amélioration est possible et la société qui pose les antennes souhaite implémenter l'algorithme suivant:

considérer les maisons dans l'ordre des abscisses croissantes;

dès qu'une maison n'est pas couverte, placer une antenne à la plus grande abscisse telle qu'elle couvre cette maison. Par exemple, si la maison d'abscisse 5 est la première maison non couverte, alors, on placera l'antenne en $5 + r$ si $r$ est le rayon d'action de l'antenne.

On considère la rue composée des maisons situées aux abscisses [0, 2, 3, 4, 5, 7, 9, 10.5, 11.5]. Recopier et compléter le schéma ci-dessous en indiquant l'emplacement des antennes selon cette nouvelle stratégie. On suppose que le rayon d'action est toujours 2.

8.

Cet algorithme étant a priori plus économe en antennes, proposer une fonction strategie_2, sur le modèle de strategie_1 qui implémente cette nouvelle stratégie.

9.

Comparer le coût en nombre d'opérations des deux stratégies en fonction du nombre $n$ de maisons dans la rue. On admet que le coût de la fonction append est constant.

EXERCICE 2 (6 points)

Cet exercice porte sur les graphes, la programmation, la structure de pile et l'algorithmique des graphes.

On s'intéresse à la fabrication de pain. La recette est fournie sous la forme de tâches à réaliser. Cette recette est réalisée par une personne seule.

(a) Préparer 500g de farine.

(b) Préparer 1/3 de litre d'eau (33cl).

(c) Préparer 1 c. à café de sel.

(d) Préparer 20g de levure de boulanger.

(e) Faire tiédir l'eau dans une casserole.

(f) Délayer la levure dans l'eau tiède.

(g) Laisser reposer la levure 5 minutes.

(h) Préparer un grand saladier.

(i) Verser la farine dans le saladier.

(j) Verser le sel dans le saladier.

(k) Mélanger la farine et le sel puis creuser un puits.

(l) Verser l'eau mélangée à la levure dans le puits.

(m) Pétrir jusqu'à obtenir une pâte homogène.

(n) Couvrir à l'aide d'un linge humide et laisser fermenter au moins 1h30.

(o) Disposer dans le fond du four un petit récipient contenant de l'eau.

(p) Préchauffer un four à 200 degrés Celsius.

(q) Fariner un plan de travail.

(r) Verser la pâte à pain sur le plan de travail.

(s) Pétrir rapidement la pâte à pain.

(t) Disposer la pâte dans un moule à cake.

(u) Mettre au four pour 15 à 20 minutes, arrêter le four et sortir le pain.

La figure 1 représente les différentes tâches et les dépendances entre ces tâches sous la forme d'un graphe. Chaque sommet du graphe représente une tâche à réaliser. Les dépendances entre les tâches sont représentées par les arcs entre les sommets.

Par exemple, il y a une flèche sur l'arc qui part du sommet d'étiquette (l) et qui atteint le sommet d'étiquette (m) car il faut avoir réalisé la tâche “ Verser l'eau mélangée à la levure dans le puits. ” (l) avant de pouvoir réaliser la tâche “ Pétrir jusqu'à obtenir une pâte homogène. ” (m).

1.

Dire, sans justifier, s'il s'agit d'un graphe orienté ou non orienté.

2.

D'après le graphe, dire s'il est possible d'effectuer les réalisations dans chacun des ordres suivants (répondre par Oui ou Non):

— réaliser la tâche (f) puis la tâche (g):

— réaliser la tâche (g) puis la tâche (f):

— réaliser la tâche (i) puis la tâche (j):

— réaliser la tâche (j) puis la tâche (i):

3.

Donner toutes les tâches qu'il faut nécessairement avoir réalisées depuis le début pour pouvoir réaliser la tâche (k). Ne donner que les tâches nécessaires.

4.

Indiquer, sans justifier, si le graphe de la Figure 1 contient un cycle.

Graphe de tâches

On s'intéresse désormais de manière plus générale à un graphe de tâches avec des dépendances.

Les sommets sont nommés par des indices. Comme précédemment, un arc orienté d'un sommet d'indice $i$ à un sommet d'indice $j$ signifie que la tâche représentée par le sommet d'indice $i$ doit être réalisée avant la tâche représentée par le sommet d'indice $j$.

5.

Déterminer un ordre permettant de réaliser toutes les tâches représentées dans le graphe de la Figure 2 en respectant les dépendances entre les tâches.

Voici une matrice d'adjacence d'un graphe écrite en langage Python et telle que si M[i][j] == 1 alors il existe un arc qui va du sommet d'indice $i$ au sommet d'indice $j$. Par exemple, M[0][1] == 1 alors il existe un arc qui va du sommet d'indice 0 au sommet d'indice 1.

M = [ [0, 1, 0, 0, 0],

[0, 0, 1, 0, 0],

[0, 0, 0, 1, 0],

[0, 1, 0, 0, 1],

[0, 0, 0, 0, 0] ]

6.

Représenter le graphe associé à cette matrice d'adjacence. Les noms des sommets seront leurs indices.

7.

Déterminer s'il est possible de trouver un ordre permettant de réaliser les tâches représentées par le graphe de la question 6 en respectant leurs dépendances. Si oui, donner l'ordre. Si non, expliquer pourquoi.

Voici le code Python d'une fonction mystere.

def mystere(graphe, s, n, ouverts, fermes, resultat):

""" Paramètres:

graphe un graphe représenté par une matrice d'adjacence

s l'indice d'un sommet du graphe

n le nombre de sommets du graphe

ouverts une liste de booléens permettant de savoir

si le traitement d'un sommet a été commencé

fermes une liste de booléens permettant de savoir

si le traitement d'un sommet a été terminé

Retour: False s'il y a eu un "problème", True sinon.

Le paramètre resultat sera modifié ultérieurement.

"""

if ouverts[s]:

return False

if not fermes[s]:

ouverts[s] = True

for i in range(n):

if graphe[s][i] == 1:

val = mystere(graphe, i, n, ouverts, fermes,

resultat)

if not val:

return False

ouverts[s] = False

fermes[s] = True

#...

return True

8.

En utilisant la matrice M donnée précédemment, déterminer si la variable ok vaut True ou False à l'issue des instructions suivantes:

n = len(M)

ouverts = [ False for i in range(n) ]

fermes = [ False for i in range(n) ]

ok = mystere(M, 1, n, ouverts, fermes, None)

Décrire précisément les appels effectués à la fonction mystere et les valeurs des tableaux ouverts et fermes lors de chaque appel (on pourra compléter le tableau ci-dessous):

Appel mystere

variable ouverts

variable fermes

Avant l'appel mystere

[F, F, F, F, F]

[F, F, F, F, F]

mystere(M, 1, 5, [F,F,F,F,F], [F,F,F,F,F], None)

[F, T, F, F, F]

[F, F, F, F, F]

mystere(M, 2, 5, [F,T,F,F,F], [F,F,F,F,F], None)

[F, T, T, F, F]

[F, F, F, F, F]

9.

De manière générale, expliquer dans quel cas cette fonction mystere renvoie False.

L'objectif est d'utiliser la fonction mystere pour écrire une fonction ordre_realisation qui, lorsque c'est possible, détermine l'ordre de réalisation des tâches d'un graphe donné par sa matrice d'adjacence en respectant les dépendances entre les tâches.

Une structure de données de pile est représentée par une classe Pile qui possède les méthodes estVide, empiler et depiler.

Lorsqu'il en existe un, un ordre de réalisation des tâches sera représenté par un objet de classe Pile contenant tous les sommets du graphe de manière à ce que les tâches qu'il faut réaliser en premier se retrouvent au sommet de la pile.

La fonction ordre_realisation est écrite de la manière suivante:

def ordre_realisation(graphe):

n = len(graphe)

ouverts = [ False for i in range(n) ]

fermes = [ False for i in range(n) ]

ordre = Pile()

ok = True

s = 0

while (ok and s < n):

ok = mystere(graphe, s, n, ouverts, fermes, ordre)

s = s + 1

if ok:

return ordre

return None

11.

Sachant que dans la fonction mystere, la ligne 24 peut être remplacée par une ou plusieurs instructions, donner ce qu'il faut écrire pour que, lorsque c'est possible, ordre_realisation renvoie effectivement un ordre de réalisation des tâches du graphe.

EXERCICE 2 (6 points)

Cet exercice porte sur les graphes, la programmation, la structure de pile et l'algorithmique des graphes.

On s'intéresse à la fabrication de pain. La recette est fournie sous la forme de tâches à réaliser. Cette recette est réalisée par une personne seule.

(a) Préparer 500g de farine.

(b) Préparer 1/3 de litre d'eau (33cl).

(c) Préparer 1 c. à café de sel.

(d) Préparer 20g de levure de boulanger.

(e) Faire tiédir l'eau dans une casserole.

(f) Délayer la levure dans l'eau tiède.

(g) Laisser reposer la levure 5 minutes.

(h) Préparer un grand saladier.

(i) Verser la farine dans le saladier.

(j) Verser le sel dans le saladier.

(k) Mélanger la farine et le sel puis creuser un puits.

(l) Verser l'eau mélangée à la levure dans le puits.

(m) Pétrir jusqu'à obtenir une pâte homogène.

(n) Couvrir à l'aide d'un linge humide et laisser fermenter au moins 1h30.

(o) Disposer dans le fond du four un petit récipient contenant de l'eau.

(p) Préchauffer un four à 200 degrés Celsius.

(q) Fariner un plan de travail.

(r) Verser la pâte à pain sur le plan de travail.

(s) Pétrir rapidement la pâte à pain.

(t) Disposer la pâte dans un moule à cake.

(u) Mettre au four pour 15 à 20 minutes, arrêter le four et sortir le pain.

La figure 1 représente les différentes tâches et les dépendances entre ces tâches sous la forme d'un graphe. Chaque sommet du graphe représente une tâche à réaliser. Les dépendances entre les tâches sont représentées par les arcs entre les sommets.

Par exemple, il y a une flèche sur l'arc qui part du sommet d'étiquette (l) et qui atteint le sommet d'étiquette (m) car il faut avoir réalisé la tâche “ Verser l'eau mélangée à la levure dans le puits. ” (l) avant de pouvoir réaliser la tâche “ Pétrir jusqu'à obtenir une pâte homogène. ” (m).

Une structure de données de pile est représentée par une classe Pile qui possède les méthodes suivantes:

la méthode estVide qui renvoie True si la pile représentée par l'objet est vide, False sinon;

la méthode empiler qui prend en paramètre un élément et l'ajoute au sommet de la pile;

la méthode depiler qui renvoie la valeur du sommet de la pile et enlève cet élément.

10.

Déterminer la valeur associée à la variable elt après l'exécution des instructions suivantes:

>>> essai = Pile()

>>> essai.empiler(3)

>>> essai.empiler(2)

>>> essai.empiler(10)

>>> elt = essai.depiler()

>>> elt = essai.depiler()

EXERCICE 3 (8 points)

Cet exercice porte sur la programmation Python, la programmation orientée objet, les bases de données relationnelles et les requêtes SQL.

Partie A

Une entreprise, présente sur différents sites en France, attribue à chacun de ses employés un numéro de badge unique.

Dans le tableau ci-dessous, on donne le numéro de badge, le nom, le prénom et les années de naissance et d’entrée dans l’entreprise de quelques salariés.

numéro badge · nom · prénom · année de naissance · année d’entrée

112 · LESIEUR · Isabelle · 1982 · 2005

2122 · VASSEUR · Adrien · 1962 · 1980

135 · HADJI · Hakim · 1992 · 2015

Pour chaque personne, on souhaite stocker les informations dans un objet de la classe Personne définie ci-dessous:

class Personne():

def __init__(self, num, n, p, a_naiss, a_entree):

self.num_badge = num

self.nom = n

self.prenom = p

self.annee_naissance = a_naiss

self.annee_entree = a_entree

1.

Écrire à l'aide du tableau précédent, l'instruction permettant de créer l'objet personneA de la première personne du tableau: LESIEUR Isabelle.

2.

Donner l'instruction permettant d'obtenir le numéro de badge de l'objet personneA instancié à la question précédente.

3.

On souhaite ajouter une méthode annee_anciennete à la classe Personne qui donne le nombre d'années d'ancienneté d'une personne au sein de l'entreprise. Par exemple: Madame LESIEUR Isabelle a une ancienneté dans l'entreprise de 19 ans en considérant que nous sommes en 2024.

Recopier et compléter le code suivant de la méthode annee_anciennete:

def annee_anciennete(self):

return...

On considère la classe Personnel qui modélise la liste du personnel d'une entreprise et dont le début de l'implémentation est la suivante:

class Personnel:

def __init__(self):

self.liste = []

4.

Écrire la méthode ajouter permettant d'ajouter un objet de type Personne à la liste du personnel de l'entreprise de la classe Personnel.

5.

Écrire la méthode effectif de la classe Personnel. Cette méthode devra renvoyer le nombre de personnes présentes dans l'entreprise.

6.

Recopier et compléter la méthode donne_nom de la classe Personnel. Cette méthode prend en paramètre le numéro de badge d'une personne et renvoie le nom de la personne correspondant à ce badge si elle existe, ou None sinon.

def donne_nom(..., num):

for elt in self.liste:

if... == num:

return...

return...

7.

Lors de la célèbre cérémonie des vœux, l'entreprise souhaite mettre à l'honneur les personnes ayant exactement 10 ans d'ancienneté dans l'entreprise. Écrire une méthode de la classe Personnel nb_personne_honneur qui prend en paramètre l'année de la cérémonie et qui retourne le nombre de personne(s) à mettre à l'honneur.

8.

Écrire une méthode plus_anciens de la classe Personnel qui retourne la liste des numéros de badge des personnes ayant la plus grande ancienneté dans l'entreprise.

EXERCICE 3 (8 points)

Cet exercice porte sur la programmation Python, la programmation orientée objet, les bases de données relationnelles et les requêtes SQL.

Partie A

Une entreprise, présente sur différents sites en France, attribue à chacun de ses employés un numéro de badge unique.

Dans le tableau ci-dessous, on donne le numéro de badge, le nom, le prénom et les années de naissance et d’entrée dans l’entreprise de quelques salariés.

numéro badge · nom · prénom · année de naissance · année d’entrée

112 · LESIEUR · Isabelle · 1982 · 2005

2122 · VASSEUR · Adrien · 1962 · 1980

135 · HADJI · Hakim · 1992 · 2015

Pour chaque personne, on souhaite stocker les informations dans un objet de la classe Personne définie ci-dessous:

class Personne():

def __init__(self, num, n, p, a_naiss, a_entree):

self.num_badge = num

self.nom = n

self.prenom = p

self.annee_naissance = a_naiss

self.annee_entree = a_entree

Partie B

On utilise maintenant une base de données relationnelle. La table Personnel dont un extrait est donné ci-dessous contient toutes les données importantes sur le personnel de l'entreprise. L'attribut num_centre désigne le numéro du centre dans lequel travaille une personne.

Personnel

num_badge · nom · prenom · num_centre · annee_naiss · annee_debut

112 · LESIEUR · Isabelle · 1 · 1982 · 2005

2122 · VASSEUR · Adrien · 2 · 1962 · 1980

135 · HADJI · Hakim · 1 · 1992 · 2015

L'attribut num_badge est la clé primaire pour la table Personnel.

9.

Décrire par une phrase en français le résultat de la requête SQL suivante:

SELECT nom, prenom

FROM Personnel

WHERE num_centre = 2;

10.

Monsieur HADJI Hakim vient d'obtenir une mutation pour le centre numéro 3. Donner la requête permettant de modifier son numéro de centre sachant que son numéro de badge est 135.

On souhaite proposer plus d'informations sur les différents centres de l'entreprise. Pour cela, on crée une deuxième table Centre avec les attributs suivants:

num de type INT;

nom de type TEXT;

num_tel de type TEXT;

ville de type TEXT.

Table Centre

num · nom · num_tel · ville

1 · Normandie · 0450646859 · Caen

2 · PACA · 0450646859 · Marseille

11.

Expliquer l'intérêt d'utiliser deux tables ( Personnel et Centre) au lieu de regrouper toutes les informations dans une seule table.

12.

Expliquer comment les tables Centre et Personnel sont mises en relation.

13.

Écrire une requête permettant d'avoir les noms des personnes travaillant dans le centre de Lille et ayant été embauchées entre 2015 (inclus) et 2020 (inclus).

Le centre de Normandie vient d'être fermé, mais les personnes de ce centre n'ont pas encore été affectées dans leur nouveau centre. On souhaite mettre à jour la table Centre en premier à l'aide de la requête suivante.

DELETE *

FROM Centre

WHERE nom = 'Normandie';

14.

Expliquer pourquoi cette requête a renvoyé une erreur.