Sujet du Bac Numérique et Sciences Informatiques 2022 · Amérique du Nord Jour 2

Cet exercice porte sur les listes, les arbres binaires de recherche et la programmation orientée objet.

Lors d'une compétition de kayak, chaque concurrent doit descendre le même cours d'eau en passant dans des portes en un minimum de temps. Si le concurrent touche une porte, il se voit octroyé une pénalité en secondes. Son résultat final est le temps qu'il a mis pour descendre le cours d'eau auquel est ajouté l'ensemble des pénalités qu'il a subies.

Un gestionnaire de course de kayak développe un programme Python pour gérer les résultats lors d'une compétition.

Dans ce programme, pour modéliser les concurrents et leurs résultats, une classe Concurrent est définie avec les attributs suivants:

nom de type Str qui représente le pseudonyme du compétiteur;

temps de type Float qui est le temps mis pour réaliser le parcours en secondes;

penalites de type Int qui est le nombre de secondes de pénalité cumulées octroyées au concurrent;

temps_tot de type Float qui correspond au temps total, c'est-à-dire au temps mis pour réaliser le parcours auquel on a ajouté les pénalités.

On suppose que tous les concurrents ont des temps différents dans cet exercice.

Le code Python incomplet de la classe Concurrent est donné ci-dessous:

class Concurrent:

def __init__(self, pseudo, temps, penalite):

self.nom = pseudo

self.temps = temps

self.penalite =...

self.temps_tot =...

1. (a)

Recopier et compléter le code du constructeur de la classe Concurrent:

class Concurrent:

def __init__(self, pseudo, temps, penalite):

On exécute l'instruction suivante: c1 = Concurrent("Mosquito", 87.67, 12)

1. (b)

1. (c)

Cet exercice porte sur les listes, les arbres binaires de recherche et la programmation orientée objet.

Lors d'une compétition de kayak, chaque concurrent doit descendre le même cours d'eau en passant dans des portes en un minimum de temps. Si le concurrent touche une porte, il se voit octroyé une pénalité en secondes. Son résultat final est le temps qu'il a mis pour descendre le cours d'eau auquel est ajouté l'ensemble des pénalités qu'il a subies.

Un gestionnaire de course de kayak développe un programme Python pour gérer les résultats lors d'une compétition.

Dans ce programme, pour modéliser les concurrents et leurs résultats, une classe Concurrent est définie avec les attributs suivants:

nom de type Str qui représente le pseudonyme du compétiteur;

temps de type Float qui est le temps mis pour réaliser le parcours en secondes;

penalites de type Int qui est le nombre de secondes de pénalité cumulées octroyées au concurrent;

temps_tot de type Float qui correspond au temps total, c'est-à-dire au temps mis pour réaliser le parcours auquel on a ajouté les pénalités.

On suppose que tous les concurrents ont des temps différents dans cet exercice.

Le code Python incomplet de la classe Concurrent est donné ci-dessous:

class Concurrent:

def __init__(self, pseudo, temps, penalite):

self.nom = pseudo

self.temps = temps

self.penalite =...

self.temps_tot =...

2. Interface de la classe Liste

Pendant la course, des instances de la classe Concurrent sont créées au fur et à mesure des arrivées des concurrents.

On définit une classe Liste pour les stocker au fur et à mesure. Cette classe implémente la structure de données abstraite liste dont l'interface est munie:

du constructeur qui ne prend pas de paramètre et qui crée une liste vide.

Exemple: L = Liste()

de la méthode est_vide qui ne prend pas de paramètre et qui renvoie un booléen: True si la liste est vide ou False sinon.

Exemple: On considère la liste L = <c1, c2, c3> où c1, c2 et c3 sont des instances de Concurrent.

L'appel L.est_vide() renvoie False.

de la méthode tete qui ne prend pas de paramètre et qui renvoie un objet de type Concurrent ayant pour valeur le premier élément de la liste. Cet élément sera appelé tête de la liste dans la suite de l'exercice.

Cette méthode ne s'applique que sur des listes non vides.

Exemple: On considère la liste L = <c1, c2, c3> où c1, c2 et c3 sont des instances de Concurrent.

L.tete() a pour valeur c1.

Remarque: Après exécution de L.tete(), la liste L reste inchangée et vaut toujours <c1, c2, c3>.

de la méthode queue qui ne prend pas de paramètre. Cette méthode renvoie la liste sur laquelle elle s'applique privée de son premier élément.

Cette méthode ne s'applique que sur des listes non vides.

Exemple: On considère la liste L = <c1, c2, c3>.

L'appel L.queue() renvoie la liste <c2, c3>.

Remarque: Après exécution de L.queue(), la liste L reste inchangée et vaut toujours <c1, c2, c3>.

de la méthode ajout qui prend en paramètre un concurrent c et qui modifie la liste sur laquelle elle s'applique, en ajoutant c en tête.

Exemple 1: Si L est la liste vide, L.ajout(c) modifie la liste L qui devient <c>.

Exemple 2: Si L est la liste <c1, c2, c3>, L.ajout(c) modifie la liste L qui devient <c, c1, c2, c3>.

On considère le script Python suivant:

c1 = Concurrent("Mosquito", 87.67, 12)

c2 = Concurrent("Python Fute", 89.73, 4)

c3 = Concurrent("Piranha Vorace", 90.54, 0)

c4 = Concurrent("Truite Agile", 84.32, 52)

c5 = Concurrent("Tortue Rapide", 92.12, 2)

c6 = Concurrent("Lievre Tranquille", 93.45, 0)

resultats = Liste()

resultats.ajout(c1)

resultats.ajout(c2)

resultats.ajout(c3)

resultats.ajout(c4)

resultats.ajout(c5)

resultats.ajout(c6)

Après exécution, ce script génère une liste resultats que l'on peut représenter par: <c6, c5, c4, c3, c2, c1>

(a)

On considère la liste resultats ci-dessus. Donner la ou les instruction(s) qui permet(tent) d'accéder à c4.

(b)

Donner la ou les instruction(s) qui permet(tent) d'accéder au temps total du concurrent stocké en tête de la liste resultats.

3. Fonction meilleur_concurrent

On souhaite créer une fonction meilleur_concurrent qui prend en paramètre une liste L de concurrents et qui renvoie l'objet Concurrent correspondant au concurrent le plus rapide. On suppose que la liste est non vide.

Recopier et compléter le code Python, donné ci-dessous, de la fonction meilleur_concurrent.

def meilleur_concurrent(L):

conc_mini = L.... # (1)

mini = conc_mini.temps_tot

Q = L.queue()

while not(Q.est_vide()):

elt = Q.tete()

if elt.temps_tot... mini: # (2)

conc_mini = elt

mini = elt.temps_tot

Q = Q.... # (3)

return... # (4)

(1) Ligne 2: conc_mini = L.

(2) Ligne 7: if elt.temps_tot

mini:

(3) Ligne 10: Q = Q.

(4) Ligne 11: return

Cet exercice porte sur les listes, les arbres binaires de recherche et la programmation orientée objet.

Lors d'une compétition de kayak, chaque concurrent doit descendre le même cours d'eau en passant dans des portes en un minimum de temps. Si le concurrent touche une porte, il se voit octroyé une pénalité en secondes. Son résultat final est le temps qu'il a mis pour descendre le cours d'eau auquel est ajouté l'ensemble des pénalités qu'il a subies.

Un gestionnaire de course de kayak développe un programme Python pour gérer les résultats lors d'une compétition.

Dans ce programme, pour modéliser les concurrents et leurs résultats, une classe Concurrent est définie avec les attributs suivants:

nom de type Str qui représente le pseudonyme du compétiteur;

temps de type Float qui est le temps mis pour réaliser le parcours en secondes;

penalites de type Int qui est le nombre de secondes de pénalité cumulées octroyées au concurrent;

temps_tot de type Float qui correspond au temps total, c'est-à-dire au temps mis pour réaliser le parcours auquel on a ajouté les pénalités.

On suppose que tous les concurrents ont des temps différents dans cet exercice.

Le code Python incomplet de la classe Concurrent est donné ci-dessous:

class Concurrent:

def __init__(self, pseudo, temps, penalite):

self.nom = pseudo

self.temps = temps

self.penalite =...

self.temps_tot =...

4. Pour simplifier le stockage des résultats, on décide de stocker les objets de la classe Concurrent dans un arbre binaire de recherche. Chaque nœud de cet arbre est donc un objet Concurrent.

Dans cet arbre binaire de recherche, en tout nœud:

le concurrent enfant à gauche est plus rapide que le nœud;

le concurrent enfant à droite est moins rapide que le nœud.

Pour implémenter la structure d'arbre binaire de recherche, on dispose d'une classe Arbre munie, entre autres, d'une méthode ajout qui prend en paramètre un objet c de type Concurrent et qui modifie l'arbre binaire sur lequel elle s'applique, en y ajoutant le concurrent c tout en maintenant la propriété d'arbre binaire de recherche.

On ajoute dans un arbre vide successivement les concurrents de la liste resultats en partant de la tête de la liste (soit, dans le cas présent, c6, puis c5, puis c4,...).

Dessiner l'arbre binaire de recherche obtenu. On rappelle le temps total de chaque concurrent:

Concurrent

c6

c5

c4

c3

c2

c1

temps_tot

93,45

94,12

136,32

90,54

93,73

99,67

Exercice 2 (4 points)

Cet exercice porte sur les systèmes d'exploitation et la gestion des processus par un système d'exploitation.

Cet exercice pourra utiliser des commandes de systèmes d'exploitation de type UNIX telles que cd, ls, mkdir, rm, rmdir, mv, cat.

1.

Dans un système d'exploitation de type UNIX, on considère l'arborescence des fichiers suivante dans laquelle les noms de dossiers sont en italique et ceux des fichiers sont en gras:

On souhaite, grâce à l'utilisation du terminal de commande, explorer et modifier les répertoires et fichiers présents.

On suppose qu'on se trouve actuellement à l'emplacement /home/morgane.

a)

Parmi les quatre propositions suivantes, donner celle correspondant à l'affichage obtenu lors de l'utilisation de la commande ls.

b)

On suppose maintenant qu'on se trouve dans le répertoire /home/morgane/lycee/NSI.

c)

d)

2.

On rappelle qu'un processus est une instance d'application. Un processus peut être démarré par l'utilisateur, par un périphérique ou par un autre processus appelé parent.

La commande UNIX ps présente un cliché instantané des processus en cours d'exécution.

On a exécuté la commande ps (avec quelques options qu'il n'est pas nécessaire de connaître pour la réussite de cet exercice). Un extrait du résultat de la commande est présenté ci-dessous:

Rappels:

— l'UID est l'identifiant de l'utilisateur propriétaire du processus;

— le PID est l'identifiant du processus;

— le PPID est l'identifiant du processus parent;

— C indique l'utilisation processeur;

— STIME est l'heure de démarrage du processus;

— TTY est le nom du terminal de commande auquel le processus est attaché;

— TIME est la durée d'utilisation du processeur par le processus;

— CMD le nom de commande utilisé pour démarrer le processus.

a)

b)

c)

d)

3.

On considère les trois processus $P_1$, $P_2$ et $P_3$, tous soumis à l'instant 0 dans l'ordre 1, 2, 3:

Nom du processus

Durée d'exécution en unité de temps

Ordre de soumission

$P_1$

3

1

$P_2$

1

2

$P_3$

4

3

a)

Dans cette question, on considère que les processus sont exécutés de manière concurrente selon la politique du tourniquet: le temps est découpé en tranches nommées quantums de temps.

Les processus prêts à être exécutés sont placés dans une file d'attente selon leur ordre de soumission.

Lorsqu'un processus est élu, il s'exécute au plus durant un quantum de temps. Si le processus n'a pas terminé son exécution à l'issue du quantum de temps, il réintègre la file des processus prêts (côté entrée). Un autre processus, désormais en tête de la file (côté sortie) des processus prêts, est alors à son tour élu pour une durée égale à un quantum de temps maximum.

Indiquer dans chacune des cases le processus exécuté à chaque cycle. Le quantum correspond à une unité de temps.

0 à 1

1 à 2

2 à 3

3 à 4

4 à 5

5 à 6

6 à 7

7 à 8

P1

b)

Dans cette question, on considère que les processus sont exécutés en appliquant la politique du « plus court d'abord »: les processus sont exécutés complètement dans l'ordre croissant de leurs temps d'exécution, le plus court étant exécuté en premier.

Indiquer dans chacune des cases le processus exécuté à chaque cycle:

0 à 1

1 à 2

2 à 3

3 à 4

4 à 5

5 à 6

6 à 7

7 à 8

4.

On considère trois ressources $R_1$, $R_2$ et $R_3$ et trois processus $P_1$, $P_2$ et $P_3$ dont les files d'exécution des instructions élémentaires sont indiquées ci-dessous:

Processus $P_1$

Demande $R_1$

Demande $R_2$

Libère $R_1$

Libère $R_2$

Processus $P_2$

Demande $R_2$

Demande $R_3$

Libère $R_2$

Libère $R_3$

Processus $P_3$

Demande $R_3$

Demande $R_1$

Libère $R_3$

Libère $R_1$

a)

Rappeler les différents états d'un processus et expliquer pourquoi il y a ici risque d'interblocage, en proposant un ordre d'exécution des instructions élémentaires le provoquant.

b)

Proposer un ordre d'exécution des instructions élémentaires sans interblocage.

Exercice 3 (4 points)

Cet exercice porte sur les bases de données relationnelles et le langage SQL.

Cet exercice utilise les mots du langage SQL suivants: SELECT, FROM, WHERE, JOIN ON, UPDATE, SET, DELETE, COUNT, AND, OR.

Une salle de cinéma propose un site Web à ses abonnés afin d'effectuer des réservations de séances en ligne. Deux tarifs sont proposés: plein et réduit (-16 ans, sénior +65 ans, étudiants, …). Le site est associé à une base de données dont le modèle relationnel contient les quatre relations décrites ci-dessous:

Un attribut souligné correspond à une clé primaire et un attribut précédé du symbole # à une clé étrangère.

Voici un extrait de quelques enregistrements des relations Film, Séance et Abonné:

idFilm

titre

réalisateur

durée

1

Le sens de la famille

Jean-Patrick Benes

90

2

Les croods 2

Joel Crawford

95

8

Black widow

Cate Shortland

134

…

Extrait de la relation Film, les durées sont en minutes.

idSéance

idFilm

date

heure

35

1

2021-10-11

21:00

737

8

2021-10-11

21:00

738

8

2021-10-13

16:15

…

Extrait de la relation Séance.

idAbonné

nom

prénom

mail

1

Henry

Jean

jean.henry@envoi.fr

2

Jacquin

Morgane

jacquin.morgane@mail.com

13

Dupont

Charles

charles.dupont@envoi.fr

…

Extrait de la relation Abonné.

1. (a)

Définir le rôle d'une clé primaire.

1. (b)

Définir le rôle d'une clé étrangère.

1. (c)

Déterminer, en justifiant, si un abonné peut réserver plusieurs fois une même séance.

1. (d)

M. Charles Dupont réserve trois places au tarif plein et deux places au tarif réduit pour assister à la projection du film "Black widow" le 11 octobre 2021 à 21:00. À l'aide des extraits des relations donnés précédemment, recopier et compléter l'enregistrement correspondant dans la relation Réservation ci-dessous:

idAbonné

idSéance

nbPlaces_plein

nbPlaces_réduit

2. (a)

Parmi les trois requêtes SQL suivantes, recopier celle qui permet d'afficher le titre et le réalisateur des films de moins de 120 minutes.

2. (b)

En SQL, la fonction COUNT() permet de compter le nombre d'enregistrements dans une table. Exprimer en langage naturel la requête SQL suivante:

SELECT COUNT(*)

FROM Séance

WHERE date="2021-10-22" OR date="2021-10-23";

On remarquera que les dates apparaissent sous la forme "aaaa-mm-jj". Par exemple, le 11 octobre 2021 apparaît sous la forme "2021-10-11".

3. Écrire en SQL les requêtes permettant d'effectuer les tâches suivantes:

(a)

(b)

On remarquera que les heures apparaissent sous la forme "hh:mm".

4.

(a)

(b)

On souhaite écrire une requête SQL permettant de supprimer la séance dont l'attribut idSéance vaut 135. Déterminer la contrainte d'intégrité que pourrait violer cette requête.

(c)

Exercice 4 (4 points)

Cet exercice porte sur les arbres binaires et leurs algorithmes associés.

Un éleveur de chiens gère les informations sur ses animaux à l'aide d'un logiciel qui mémorise le pédigrée de chacun de ses chiens. Le pédigrée d'un chien correspond à son arbre généalogique. Une structure arbre de pédigrée est définie récursivement, soit par un arbre vide, noté $\emptyset$, soit par un arbre binaire où:

la valeur du nœud est une chaîne de caractères qui représente le nom de l'animal;

le sous-arbre gauche est l'arbre de pédigrée du père du chien;

le sous-arbre droit est l'arbre de pédigrée de la mère du chien.

On représente donc graphiquement un arbre de pédigrée comme l'arbre A suivant:

Pour alléger la représentation d'un arbre de pédigrée, on ne notera pas les arbres vides, l'arbre précédent sera donc représenté comme ci-dessous.

Dans cet arbre,

le père de Mango est Domino et sa mère Pinkie;

les parents de Douchka ne sont pas connus;

Iris est la mère de Pinkie;

la mère de Tango n'est pas connue.

Pour manipuler les arbres de pédigrée, on dispose des quatre fonctions suivantes:

La fonction racine qui prend en paramètre un arbre de pédigrée non vide et renvoie la valeur de la racine.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, racine(A) vaut "Mango".

La fonction gauche qui prend en paramètre un arbre de pédigrée non vide et renvoie son sous-arbre gauche correspondant à l'arbre de pédigrée du père.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, gauche(A) est l'arbre représenté graphiquement ci-après:

La fonction droit qui prend en paramètre un arbre de pédigrée non vide et renvoie son sous-arbre droit correspondant à l'arbre de pédigrée de la mère.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, droit(A) vaut l'arbre représenté graphiquement ci-après:

La fonction est_vide qui prend en paramètre un arbre de pédigrée et renvoie True si l'arbre est vide ou False sinon.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, est_vide(A) vaut False.

Pour toutes les questions de l'exercice, on suppose que tous les chiens d'un même pédigrée ont un nom différent.

1.

On considère l'arbre de pédigrée B suivant:

a)

b)

On appelle feuille d'un arbre de pédigrée, un nœud dont les sous-arbres gauche et droit sont vides.

c)

d)

2.

a)

Recopier et compléter la fonction récursive Python present ayant pour paramètres un arbre de pédigrée arb et le nom d'un chien nom et qui renvoie True si ce nom est présent dans l'arbre de pédigrée ou False sinon.

def present(arb, nom):

if est_vide(arb):

return...

elif racine(arb) ==...:

return...

else:

return present(...,...) or present(...,...)

Pour toute la suite de l'exercice, on pourra utiliser la fonction present même si la question 2.(a) n'a pas été traitée.

b)

Écrire une fonction Python parents ayant pour paramètre un arbre de pédigrée arbre d'un chien et qui renvoie le p-uplet des deux parents de ce chien dans l'ordre père, mère. Si un des parents est inconnu, il sera noté "".

Exemple: parents(B) vaut ("Eclair", "Nougat").

3.

a)

On dit que deux chiens sont frères et sœurs s'ils ont le même père ou la même mère. On considère les trois arbres de pédigrée suivants:

b)

Écrire une fonction Python frere_soeur ayant pour paramètres deux arbres de pédigrée arbre1 et arbre2 correspondant à deux chiens. Cette fonction renvoie True si les deux chiens ont le même père ou la même mère ou False sinon.

4.

Étant donné l'arbre de pédigrée d'un chien, on considère que:

le niveau 0 est le niveau de la racine contenant le nom du chien;

le niveau 1 est le niveau des parents du chien;

le niveau 2 est le niveau des grands-parents du chien;

etc.

Proposer une fonction Python nombre_chiens ayant pour paramètres un arbre de pédigrée arb et un entier n et qui renvoie le nombre de noms connus dans l'arbre de pédigrée arb au niveau n.

Exemple: nombre_chiens(B, 3) vaut 4 car les noms des chiens mentionnés dans l'arbre de pédigrée au niveau 3 sont "Ulk", "Maya", "Museau" et "Noisette".

Exercice 5 (4 points)

Cet exercice porte sur les tableaux à deux dimensions et la programmation Python en général.

Partie A

Dans cette partie, on s'intéresse à un dessin pixelisé en noir et blanc dans lequel chaque ligne est obtenue séquentiellement à partir de la ligne juste au-dessus d'elle.

Au départ, on dispose donc de la ligne du haut et on déduit les lignes en dessous les unes après les autres.

Les règles sont les suivantes:

pour chaque ligne, le pixel complètement à droite et le pixel complètement à gauche sont blancs;

pour les autres pixels, un pixel est noir si les deux pixels à droite et gauche du pixel juste au-dessus de ce pixel ne sont pas de la même couleur, sinon il est blanc.

Le pixel noté "$x$" est donc blanc si les pixels notés "$a$" et "$b$" sont de la même couleur ou noir sinon.

1. (a)

Dans cette question uniquement, on considère un dessin de cinq lignes et huit colonnes.

La première ligne est colorée comme ci-dessous:

En respectant les règles de coloration, on complète la figure en ajoutant la deuxième ligne:

De même, en ajoutant la troisième ligne:

Donner le contenu binaire (0 pour blanc, 1 pour noir) des deux dernières lignes (lignes d'indice 3 et 4) sous forme de tableau de 8 valeurs (ex: [0, 0, 1,...]):

Dans la suite de cet exercice:

les lignes sont numérotées du haut vers le bas, en commençant à 0;

les colonnes sont numérotées de la gauche vers la droite, en commençant à 0.

1. (b)

On considère le pixel de la ligne 4 et de la colonne 1.

Ligne:

Colonne:

Ligne:

Colonne:

1. (c)

Plus généralement, on considère le pixel de la ligne li et de la colonne co (ni sur la première ligne, ni sur les colonnes extrêmes).

Ligne:

Colonne:

Ligne:

Colonne:

2. (a)

On suppose que le tableau image a été rempli en respectant les règles jusqu'à la ligne li - 1. On suppose $0 < \text{co} < 7$.

Donner la condition (en Python) portant sur les valeurs de la ligne li - 1 pour que image[li][co] prenne la valeur 1:

2. (b)

Compléter la fonction Python remplir_ligne qui prend en paramètre le tableau image et un entier li:

def remplir_ligne(image, li):

image[li][0] = 0

image[li][7] = 0

for... in range(...,...):

...

2. (c)

Écrire une fonction remplir qui prend en paramètre le tableau image et modifie les valeurs des cases du tableau des lignes restantes:

Partie B

À un tableau de taille 8 contenant des 0 ou des 1, on associe l'entier dont la représentation binaire est donnée par ce tableau.

Par exemple, le tableau [0, 0, 0, 1, 0, 0, 1, 0] représente le nombre binaire 00010010, correspondant à 18 en base 10.

1. (a)

Soit le tableau [0, 0, 1, 0, 1, 1, 0, 0]. Déterminer la représentation en base 10 de l'entier correspondant:

1. (b)

Écrire la fonction Python conversion2_10 qui prend en paramètre un tableau tab de taille 8 composé de 0 et 1, et qui renvoie l'entier correspondant écrit en base 10:

1. (c)

Réciproquement, donner le tableau associé à l'entier 78 dont l'écriture en base 10 est 78:

Dans la suite, on suppose qu'on dispose de la fonction Python conversion10_2, qui prend en paramètre un entier $n$ compris entre 0 et 255, et qui renvoie le tableau tab correspondant.

2. (a)

On rappelle que pour chaque ligne de l'image, le pixel complètement à gauche et le pixel complètement à droite restent blancs. En déduire une ou des précondition(s) sur l'entier $n$:

2. (b)

Compléter la fonction generer(n, k):

def generer(n, k):

tab = [None for i in range(k)]

image = [[0 for j in range(8)] for i in range(k+1)]

...

return tab