Sujet du Bac Numérique et Sciences Informatiques 2024 · Centres étrangers (Afrique) Jour 2

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation en Python en général, la programmation orientée objet et la récursivité.

On se déplace dans une grille rectangulaire. On s’intéresse aux chemins dont le départ est sur la case en haut à gauche et l’arrivée en bas à droite. Les seuls déplacements autorisés sont composés de déplacements élémentaires d’une case vers le bas ou d’une case vers la droite.

Un itinéraire est noté sous la forme d’une suite de lettres:

D pour un déplacement vers la droite d’une case;

B pour un déplacement vers le bas d’une case.

Le nombre de caractères D est la longueur de l’itinéraire. Le nombre de caractères B est sa largeur.

Ainsi l’itinéraire 'DDBDBBDDDDB' a pour longueur 7 et pour largeur 4. Sa représentation graphique est:

S * *

* *

*

* * * * *

E S représente la case de départ (start). Ses coordonnées sont $(0\text{; }0)$;

* représente les cases visitées;

E représente la case d’arrivée (end).

Partie A – Programmation orientée objet

On représente un itinéraire avec la classe Chemin suivante:

class Chemin:

def __init__(self, itineraire):

self.itineraire = itineraire

longueur, largeur = 0, 0

for direction in self.itineraire:

if direction == "D":

longueur = longueur + 1

if direction == "B":

largeur = largeur + 1

self.longueur = longueur

self.largeur = largeur

self.grille = [['.' for i in range(longueur+1)] for j in range(largeur+1)]

def remplir_grille(self):

i, j = 0, 0 # Position initiale

self.grille[0][0] = 'S' # Case de départ marquée d'un S

for direction in...:

if direction == 'D':

... =... # Déplacement vers la droite

elif direction == 'B':

... =... # Déplacement vers le bas

self.grille[i][j] = '*' # Marquer le chemin avec '*'

self.grille[self.largeur][self.longueur] = 'E' # Case d'arrivée marquée d'un E

1.

Donner un attribut et une méthode de la classe Chemin.

2.

On exécute le code ci-dessous dans la console Python:

chemin_1 = Chemin("DDBDBBDDDDB")

a = chemin_1.largeur

b = chemin_1.longueur

Préciser les valeurs contenues dans chacune des variables a et b.

3.

Recopier et compléter la méthode remplir_grille qui remplace les '.' par des '*' pour signifier que le déplacement est passé par cette cellule du tableau.

4.

Écrire une méthode get_dimensions de la classe Chemin qui renvoie la longueur et la largeur de l'itinéraire sous la forme d'un tuple.

5.

Écrire une méthode tracer_chemin de la classe Chemin qui affiche une représentation graphique d'un itinéraire.

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation en Python en général, la programmation orientée objet et la récursivité.

On se déplace dans une grille rectangulaire. On s’intéresse aux chemins dont le départ est sur la case en haut à gauche et l’arrivée en bas à droite. Les seuls déplacements autorisés sont composés de déplacements élémentaires d’une case vers le bas ou d’une case vers la droite.

Un itinéraire est noté sous la forme d’une suite de lettres:

D pour un déplacement vers la droite d’une case;

B pour un déplacement vers le bas d’une case.

Le nombre de caractères D est la longueur de l’itinéraire. Le nombre de caractères B est sa largeur.

Ainsi l’itinéraire 'DDBDBBDDDDB' a pour longueur 7 et pour largeur 4. Sa représentation graphique est:

S * *

* *

*

* * * * *

E S représente la case de départ (start). Ses coordonnées sont $(0\text{; }0)$;

* représente les cases visitées;

E représente la case d’arrivée (end).

Partie B – Génération aléatoire d'itinéraires

On souhaite créer des chemins de façon aléatoire. Pour cela, on utilise la méthode choice de la bibliothèque random dont on fournit ci-dessous la documentation.

Documentation

random.choice(sequence: list)

Renvoie un élément choisi dans une liste non vide. Si la population est vide, lève IndexError.

On rappelle que l'opérateur * permet de répéter une chaîne de caractères. Par exemple, on a:

>>> "Hello world ! " * 3

'Hello world ! Hello world ! Hello world ! '

L'algorithme proposé est le suivant:

on initialise:

une variable itineraire comme une chaîne de caractères vide,

les variables i et j à 0;

tant que l'on n'est pas sur la dernière ligne ou la dernière colonne du tableau:

on tire au sort entre un déplacement à droite ou en bas,

le déplacement est concaténé à la chaîne de caractères itineraire,

si le déplacement est vers la droite, alors j est incrémenté de 1,

si le déplacement est vers le bas, alors i est incrémenté de 1;

il reste à terminer le chemin en complétant par des déplacements afin d'atteindre la cellule en bas à droite.

6. Écrire les lignes manquantes dans le code ci-dessous. Le nombre de lignes effacées dans le code n'est pas indicatif.

from random import choice

def itineraire_aleatoire(m, n):

itineraire = ''

i, j = 0, 0

while i != m and j != n:

if i == m:

itineraire = itineraire + 'D'*(n-j)

if j == n:

itineraire = itineraire + 'B'*(m-i)

return itineraire

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation en Python en général, la programmation orientée objet et la récursivité.

On se déplace dans une grille rectangulaire. On s’intéresse aux chemins dont le départ est sur la case en haut à gauche et l’arrivée en bas à droite. Les seuls déplacements autorisés sont composés de déplacements élémentaires d’une case vers le bas ou d’une case vers la droite.

Un itinéraire est noté sous la forme d’une suite de lettres:

D pour un déplacement vers la droite d’une case;

B pour un déplacement vers le bas d’une case.

Le nombre de caractères D est la longueur de l’itinéraire. Le nombre de caractères B est sa largeur.

Ainsi l’itinéraire 'DDBDBBDDDDB' a pour longueur 7 et pour largeur 4. Sa représentation graphique est:

S * *

* *

*

* * * * *

E S représente la case de départ (start). Ses coordonnées sont $(0\text{; }0)$;

* représente les cases visitées;

E représente la case d’arrivée (end).

Partie C – Calcul du nombre de chemins possibles

Soit $m$ et $n$ deux entiers naturels non nuls. On se place dans le contexte d'un itinéraire de longueur $m$ et de largeur $n$ de dimension $m \times n$.

On note $N(m, n)$ le nombre de chemins distincts respectant les contraintes de l'exercice.

7.

Pour un itinéraire de dimension $1 \times n$ justifier, éventuellement à l'aide d'un exemple, qu'il y a un seul chemin, c'est-à-dire que, quel que soit $n$ entier naturel, on a $N(1, n) = 1$.

De même, $N(m, 1) = 1$.

8.

Justifier que $N(m, n) = N(m - 1, n) + N(m, n - 1)$.

9.

En utilisant les questions précédentes, écrire une fonction récursive nombre_chemins(m, n) qui renvoie le nombre de chemins possibles dans une grille rectangulaire de dimension $m \times n$.

Cet exercice porte sur la programmation objet, la récursivité, les arbres binaires et les systèmes d'exploitation.

Dans cet exercice, on travaille dans un environnement Linux. On considère l'arborescence de fichiers de la figure 1.

Partie A

1.

Le répertoire courant est home. Donner une commande permettant de connaître le contenu du dossier documents.

On suppose que l'on se trouve dans le dossier cours et que l'on exécute la commande mv../../multimedia /home/documents.

2.

Indiquer la modification que cela apporte dans l'arborescence de la figure 1.

Cet exercice porte sur la programmation objet, la récursivité, les arbres binaires et les systèmes d'exploitation.

Dans cet exercice, on travaille dans un environnement Linux. On considère l'arborescence de fichiers de la figure 1.

On considère le code suivant:

class Arbre:

def __init__(self, nom, g, d):

self.nom = nom

self.gauche = g

self.droit = d

def est_vide(self):

return self.gauche is None and self.droit is None

def parcours(self):

print(self.nom)

if self.gauche != None:

self.gauche.parcours()

if self.droit != None:

self.droit.parcours()

3.

Donner une raison qui justifie que le code précédent ne permet pas de modéliser l'arborescence de fichiers de la figure 1.

4.

Donner le nom du parcours réalisé par le code précédent.

5.

Donner la liste des dossiers dans l'ordre d'un parcours en largeur de l'arborescence. On ne demande pas d'écrire ce parcours en Python.

Partie B

Pour pouvoir modéliser l'arborescence de fichiers de la figure 1, on propose l'implémentation suivante. L'attribut fils est une variable de type list contenant tous les dossiers fils. Cette liste est vide dans le cas où le dossier est vide.

class Dossier:

def __init__(self, nom, liste):

self.nom = nom

self.fils = liste # liste d'objets de la classe Dossier

6.

Écrire le code Python d'une méthode est_vide qui renvoie True lorsque le dossier est vide et False sinon.

7.

Écrire le code Python permettant d'instancier une variable var_multimedia de la classe Dossier représentant le dossier multimedia de la figure 1. Attention: cela nécessite d'instancier tous les nœuds du sous-arbre de racine multimedia.

8.

Recopier et compléter sur votre copie le code Python de la méthode parcours suivante qui affiche les noms de tous les descendants d'un dossier en utilisant l'ordre préfixe.

def parcours(self):

print(...)

for f in...:

...

9.

Justifier que cette méthode parcours termine toujours sur une arborescence de fichiers.

10.

Proposer une modification de la méthode parcours pour que celle-ci effectue plutôt un parcours suffixe (ou postfixe).

11.

Expliquer la différence de comportement entre un appel à la méthode parcours de la classe Dossier et une exécution de la commande UNIX ls.

On considère la variable var_videos de type Dossier représentant le dossier videos de la figure 1. On souhaite que le code Python var_videos.mkdir("documentaires") crée un dossier documentaires vide dans le dossier var_videos.

12.

Écrire le code Python de la méthode mkdir.

13.

Écrire en Python une méthode contient(self, nom_dossier) qui renvoie True si l'arborescence de racine self contient au moins un dossier de nom nom_dossier et False sinon.

14.

Avec l'implémentation de la classe Dossier de cette partie, expliquer comment il serait possible de déterminer le dossier parent d'un dossier donné dans une arborescence donnée. On attend ici l'idée principale de l'algorithme décrite en français. On ne demande pas d'implémenter cet algorithme en Python.

15.

Proposer une modification dans la méthode __init__ de la classe Dossier qui permettrait de répondre à la question précédente beaucoup plus efficacement et expliquer votre choix.

Cet exercice porte sur le codage binaire, les bases de données relationnelles et les requêtes SQL.

Cet exercice est composé de deux parties peu dépendantes entre elles.

Lorsqu'il y a un accident, les pompiers essaient d'intervenir sur les lieux le plus rapidement possible avec les équipes et le matériel adéquats. On s'intéresse à l'étude d'un système informatique simplifié permettant de répondre à certaines de leurs problématiques.

Chaque pompier possède des aptitudes opérationnelles qui lui permettent de tenir un rôle. Lors du départ d'un véhicule (on parle d'agrès), il faut a minima un conducteur et un chef d'agrès.

Pour simplifier, on considère que:

un Véhicule Tout Usage (VTU) ne requiert que le duo conducteur et chef d'agrès, donc deux pompiers;

un Véhicule de Secours et d'Assistance aux Victimes (VSAV) requiert, en plus du duo conducteur et chef d'agrès, un équipier, donc trois pompiers;

un Fourgon Pompe Tonne (FPT) requiert, en plus du duo conducteur et chef d'agrès, un chef d'équipe et un équipier, donc quatre pompiers.

On souhaite entrer dans une base de données l'ensemble de ces informations afin de pouvoir conserver un historique des interventions.

Partie A – Encodage binaire

Afin de gagner de la place mémoire, on décide de coder l'ensemble des aptitudes sur un entier de 8 bits plutôt que d'écrire en toutes lettres « équipier », « chef d'équipe », etc. Cet ensemble d'aptitudes formera la qualification du pompier considéré.

Un personnel non formé est codé par 0;

l'aptitude « équipier » est codée par le bit de rang 0 (celui de poids le plus faible), soit $2^0$;

l'aptitude « chef d'équipe » est codée par le bit de rang 1, soit $2^1$;

l'aptitude « chef d'agrès » est codée par le bit de rang 2, soit $2^2$;

enfin, l'aptitude « conducteur » est codée par le bit de rang 3, soit $2^3$.

Remarque: un chef d'équipe étant nécessairement équipier, on lui ajoute cette aptitude dans son codage. De même, un chef d'agrès est nécessairement un chef d'équipe et un équipier: on lui ajoute ces aptitudes dans son codage.

1.

Justifier que la qualification décimale 11 correspond à un chef d'équipe conducteur.

2.

Déterminer le codage décimal de la qualification chef d'agrès conducteur.

3.

Expliquer pourquoi dans la situation décrite, un pompier ne peut pas avoir de qualification dont le codage décimale est 4.

4.

Avec ce codage sur un octet, indiquer combien de nouvelles aptitudes peuvent être définies.

5.

On considère que chacune des quatre aptitudes aurait pu être codée par une chaîne de 10 caractères dont chaque caractère utilise 1 octet en mémoire.

Choisir, avec justification, l'économie mémoire que le codage sur un entier de 8 bits permet de faire comparée au codage basé sur les chaînes de caractères:

Cet exercice porte sur le codage binaire, les bases de données relationnelles et les requêtes SQL.

Cet exercice est composé de deux parties peu dépendantes entre elles.

Lorsqu'il y a un accident, les pompiers essaient d'intervenir sur les lieux le plus rapidement possible avec les équipes et le matériel adéquats. On s'intéresse à l'étude d'un système informatique simplifié permettant de répondre à certaines de leurs problématiques.

Chaque pompier possède des aptitudes opérationnelles qui lui permettent de tenir un rôle. Lors du départ d'un véhicule (on parle d'agrès), il faut a minima un conducteur et un chef d'agrès.

Pour simplifier, on considère que:

un Véhicule Tout Usage (VTU) ne requiert que le duo conducteur et chef d'agrès, donc deux pompiers;

un Véhicule de Secours et d'Assistance aux Victimes (VSAV) requiert, en plus du duo conducteur et chef d'agrès, un équipier, donc trois pompiers;

un Fourgon Pompe Tonne (FPT) requiert, en plus du duo conducteur et chef d'agrès, un chef d'équipe et un équipier, donc quatre pompiers.

On souhaite entrer dans une base de données l'ensemble de ces informations afin de pouvoir conserver un historique des interventions.

Partie B — Base de données relationnelle

On considère maintenant la base de données relationnelle suivante:

La table personnel est composée:

du matricule unique du pompier;

de son nom;

de sa qualification (selon le codage vu avant);

d'un attribut qui précise s'il est actif (1) ou inactif (0).

La table agres est composée:

de son identifiant;

du jour où l'agrès se tient prêt à intervenir;

du type de véhicule;

de l'identifiant du chef d'agrès;

de l'identifiant du conducteur;

de l'identifiant du chef d'équipe si le véhicule le nécessite, sinon le champ est à NULL;

de l'identifiant de l'équipier si le véhicule le nécessite, sinon le champ est à NULL.

La table moyen est composée:

de l'identifiant de l'agrès appelé sur intervention;

de l'identifiant de l'intervention.

La table intervention est composée:

de son identifiant;

du jour de début d'intervention (sauf pour les longues interventions où il correspond au jour de l'agrès);

de l'heure de début d'intervention.

On rappelle que COUNT(*) permet de compter le nombre de lignes extraites lors d'une requête. Par exemple, pour afficher le nombre de personnes dans la table personnel, on exécute la requête:

SELECT COUNT(*) FROM personnel;

DISTINCT permet de retirer les doublons des réponses. Par exemple, pour afficher tous les noms distincts de la table personnel, on exécute la requête:

SELECT DISTINCT(nom) FROM personnel;

On considère l'extrait de la base de données ci-dessous:

6.

Expliquer la différence entre une clé primaire et une clé étrangère.

7.

Expliquer pourquoi la requête suivante génère une erreur pour l'extrait de données.

INSERT INTO moyen (idagres, idinter) VALUES (1,5);

8.

Proposer une requête SQL qui met à jour l'heure de l'intervention du « 15 février 2024 de 01 heure 44 minutes et 06 secondes » à « 10 heures 44 minutes et 06 secondes ».

9.

Préciser le résultat de la requête suivante pour l'extrait de données.

SELECT nom FROM personnel

WHERE actif = 0;

10.

Proposer une requête SQL qui permet d'afficher les noms des personnels conducteurs actifs. On notera qu'un conducteur possède un attribut qualif supérieur ou égal à 16.

11.

Écrire l'affichage obtenu après exécution des deux requêtes ci-dessous sur l'extrait de la base de données. Expliquer ce que chacune des requêtes affiche en général.

Requête A

SELECT COUNT(*) FROM agres

WHERE jour = '2024-03-27';

Requête B

SELECT COUNT(*) FROM moyen AS m

INNER JOIN agres AS a ON a.id = m.idagres

WHERE a.jour = '2024-03-27';

12.

Proposer une requête qui renvoie sans répétition tous les noms des chefs d'agrès assignés à un véhicule le 15 février 2024.

13.

Proposer une requête qui renvoie sans répétition tous les noms des chefs d'agrès engagés en intervention le 11 juin 2024.