Sujet du Bac Numérique et Sciences Informatiques 2023 · Polynésie Jour 1

EXERCICE 1 (4 points)

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

L'énoncé de cet exercice utilise les mots clefs du langage SQL suivants: SELECT, FROM, WHERE, JOIN ON, UPDATE, SET, INSERT INTO VALUES, COUNT, ORDER BY.

La ligue féminine de basket-ball publie les données relatives à chaque saison sur le site web de la ligue. On y retrouve des informations concernant les équipes participantes, les calendriers et les résultats des matchs ainsi que les statistiques des joueuses. Dans cet exercice, nous allons nous intéresser à la base de données relationnelle LFB_2021_2022 permettant le stockage et la gestion des données de la saison régulière de basket-ball féminin 2021-2022.

1. Table Equipe

Voici ci-dessous le contenu entier de la relation (table) Equipe:

id_equipe

nom

adresse

telephone

1 · Saint-Amand · 39 avenue du Clos, 59230 Saint-Amand-les-Eaux · 03 04 05 06 07

2 · Basket Landes · 15 place Saint-Roch, 40000 Mont-De-Marsan · 05 06 07 08 09

3 · Villeneuve d'Ascq · 2 rue Breughel, 59650 Villeneuve-d'Ascq · 03 02 01 00 01

4 · Tarbe · Quai de l'Adour, 65000 Tarbes · 05 04 03 02 02

5 · Lyon · 451 cours Emile Zola, 69100 Villeurbanne · 04 05 06 07 08

6 · Bourges · 6 rue du Pré Doulet, 18000 Bourges · 02 03 04 05 06

7 · Charleville-Mézières · Rue de la Vieille Meuse, 08000 Charleville-Mézières · 03 05 07 09 01

8 · Landerneau · Kerouel, 29410 Pleyber-Christ · 02 04 06 08 00

9 · Angers · 330 rue Saint-Léonard, 49000 Angers · 02 00 08 06 04

10 · Lattes Montpellier · 157 rue de la Porte Lombarde, 34970 Lattes · 04 03 02 01 00

11 · Charnay · Allée des Ecoliers, 71850 Charnay-lès-Mâcon · 03 01 09 07 05

12 · Roche Vendée · BP 151, 85004 La Roche-Sur-Yon Cedex · 02 05 08 01 04

On donne ci-contre le schéma relationnel de la table Equipe.

Dans ce schéma, un attribut souligné indique qu'il s'agit d'une clé primaire.

a.

Après le chargement de la table Equipe, expliquer pourquoi la requête suivante produit une erreur:

INSERT INTO Equipe

VALUES (11,"Toulouse","2 rue du Nord, 40100 Dax","05 04 03 02 01");

b.

Expliquer le choix du domaine pour l'attribut telephone.

c.

Donner le résultat de la requête suivante:

SELECT nom, adresse, telephone FROM Equipe WHERE id_equipe = 5;

d.

Donner et expliquer le résultat de la requête suivante:

SELECT COUNT(*) FROM Equipe;

e.

Écrire la requête SQL permettant d'afficher les noms des équipes par ordre alphabétique.

f.

Écrire la requête SQL permettant de corriger le nom de l'équipe dont l' id_equipe est égal à 4. Le nom correct est "Tarbes".

2. Table Joueuse

Sur le site web de la fédération de basket-ball féminin, nous pouvons consulter la composition des équipes. Pour chaque joueuse, on peut y lire en plus de son nom, sa date de naissance, sa taille ainsi que le poste occupé dans l'équipe. Ces informations sont présentées dans une page web dont le titre est « Fiche Joueuse », page construite à partir de la table Joueuse dont voici un extrait:

id_joueuse

nom

prenom

date_naissance

taille

poste

id_equipe

1 · Berkani · Lisa · 19/05/1997 · 176 · 2 · 7

2 · Alexander · Kayla · 05/01/1991 · 193 · 5 · 5

3 · Magarity · Regan · 30/04/1996 · 192 · 4 · 2

4 · Muzet · Johanna · 08/07/1997 · 183 · 3 · 11

5 · Kalu · Ezinne · 26/06/1992 · 173 · 2 · 8

6 · Sigmundova · Jodie Cornelie · 20/04/1993 · 193 · 5 · 9

7 · Dumerc · Céline · 09/07/1982 · 162 · 2 · 2

8 · Slonjsak · Iva · 16/04/1997 · 183 · 3 · 9

9 · Michel · Sarah · 10/01/1989 · 180 · 2 · 6

10 · Lithard · Pauline · 11/02/1994 · 164 · 1 · 1

On donne ci-contre le schéma relationnel de la table Joueuse.

Un attribut souligné indique qu'il s'agit d'une clé primaire. Le symbole # devant un attribut indique qu'il s'agit d'une clé étrangère.

La clé étrangère Joueuse.id_equipe fait référence à la clé primaire Equipe.id_equipe de la table Equipe.

a.

Expliquer pourquoi l'attribut id_equipe a été déclaré clé étrangère.

b.

On souhaite supprimer toutes les informations relatives à une équipe. Expliquer pourquoi on ne peut pas directement supprimer cette équipe dans la table Equipe.

c.

Écrire la requête SQL qui permet d'afficher les noms et les prénoms des joueuses de l'équipe d'Angers par ordre alphabétique des noms. On supposera que l'utilisateur qui écrit cette requête ne connaît pas l'identifiant de l'équipe d'Angers.

3. Résultats des matchs

Les résultats des matchs sont aussi publiés sur le site web de la ligue. Par exemple, pour le match n°10 qui a opposé l'équipe de Villeneuve d'Ascq à l'équipe de Bourges le 23/10/2021 on retrouve les informations suivantes:

Le score final du match a été de 73 points pour l'équipe de Villeneuve d'Ascq qui a joué à domicile (nom affiché à gauche sur la page) contre 78 points pour l'équipe de Bourges qui a joué en déplacement (nom affiché à droite sur la page).

a.

À partir de l'analyse de cet exemple, proposer un schéma relationnel pour la table Match. Si des clés étrangères sont définies, préciser quelles tables et quels attributs elles référencent.

b.

Écrire la requête SQL qui permet l'insertion dans la table Match de l'enregistrement correspondant à l'exemple donné ci-dessus.

4. Statistiques des joueuses

En plus du score final, sur la page web sont affichées des informations relatives aux performances des joueuses pendant le match.

Nous allons retenir ici seulement 3 critères: le nombre de points marqués, les rebonds et les passes décisives effectués.

Voici un extrait des statistiques du match n°53 qui a opposé l'équipe de Landerneau à celle de Charleville-Mézières le 16/04/2022:

a.

Proposer un schéma relationnel pour stocker les informations relatives aux statistiques des joueuses dans la base de données, telles que présentées ci-dessus.

b.

Écrire la requête SQL qui a été utilisée pour afficher la partie « Extrait des statistiques » de l'exemple ci-dessus.

EXERCICE 2 (3 points)

Cet exercice porte sur la gestion des processus et la programmation orientée objet.

On rappelle qu'un processus est l'instance d'un programme en cours d'exécution. Il est identifié par un numéro unique appelé PID. L'ordonnanceur est la composante du système d'exploitation qui gère l'allocation du processeur entre les différents processus. Nous allons nous intéresser à l'algorithme d'ordonnancement du tourniquet dont le fonctionnement est résumé ci-dessous:

Les processus prêts à être exécutés sont placés dans une file d'attente selon leur ordre d'arrivée;

L'ordonnanceur alloue le processeur à chaque processus de la file d'attente un même nombre de cycles CPU, appelé quantum;

Si le processus n'est pas terminé au bout de ce temps, son exécution est suspendue et il est mis à la fin de la file d'attente;

Si le processus est terminé, il sort définitivement de la file d'attente.

1. On considère trois processus soumis à l'ordonnanceur au même instant pour lesquels on donne les informations ci-dessous:

PID

Durée

(en cycles CPU)

Ordre d'arrivée

11

4

1

20

2

2

32

3

3

a.

Si le quantum du tourniquet est d'un cycle CPU, recopier et compléter la suite des PID des processus dans l'ordre de leur exécution:

11, 20, 32, 11,...............

b.

Donner la composition de la suite des PID lorsque le quantum du tourniquet est de deux cycles CPU.

EXERCICE 2 (3 points)

Cet exercice porte sur la gestion des processus et la programmation orientée objet.

On rappelle qu'un processus est l'instance d'un programme en cours d'exécution. Il est identifié par un numéro unique appelé PID. L'ordonnanceur est la composante du système d'exploitation qui gère l'allocation du processeur entre les différents processus. Nous allons nous intéresser à l'algorithme d'ordonnancement du tourniquet dont le fonctionnement est résumé ci-dessous:

Les processus prêts à être exécutés sont placés dans une file d'attente selon leur ordre d'arrivée;

L'ordonnanceur alloue le processeur à chaque processus de la file d'attente un même nombre de cycles CPU, appelé quantum;

Si le processus n'est pas terminé au bout de ce temps, son exécution est suspendue et il est mis à la fin de la file d'attente;

Si le processus est terminé, il sort définitivement de la file d'attente.

2. L'objectif de la suite de l'exercice est d'implémenter en langage Python l'algorithme du tourniquet.

Nous allons utiliser une liste pour simuler la file d'attente des processus et la classe Processus dont le constructeur est donné ci-dessous:

class Processus:

def __init__(self, pid, duree):

self.pid = pid

self.duree = duree

# Le nombre de cycles qui restent à faire:

self.reste_a_faire = duree

self.etat = "Præt" Les états possibles d'un processus sont: "Præt", "En cours d'exécution", "Suspendu" et "Terminé".

a.

Recopier et compléter l'instruction Python suivante permettant de créer la liste d'attente initiale des processus donnés dans le tableau précédent (le processus PID 11 est à l'indice 0 de la liste d'attente):

liste_attente = [Processus(...,...),.........,.........]

b.

Recopier (sans les commentaires) et compléter les trois méthodes suivantes de la classe Processus:

def execute_un_cycle(self):

"""Met à jour le reste à faire après l'exécution d'un cycle.""" def change_etat(self, nouvel_etat):

"""Change l'état du processus avec la valeur passée en paramètre.""" def est_termine(self):

"""Renvoie True si le processus est terminé, False sinon, en se basant sur le reste à faire."""

c.

La fonction tourniquet ci-dessous implémente l'algorithme décrit dans l'exercice. Elle prend en paramètres une liste d'objets Processus donnés par ordre d'arrivée et un nombre entier positif correspondant au quantum. La fonction renvoie la liste des PID dans l'ordre de leur exécution par le processeur.

Compléter le code manquant:

1 def tourniquet(liste_attente, quantum):

2 ordre_execution = []

3 while liste_attente != []:

4 # On extrait le premier processus

5 processus = liste_attente.pop(0)

6 processus.change_etat("En cours d'exécution")

7 compteur_tourniquet = 0

8 while <condition ligne 8>:

9 ordre_execution.append(<valeur ligne 9>)

10 processus.execute_un_cycle()

11 compteur_tourniquet = compteur_tourniquet + 1

12 if <condition ligne 12>:

13 processus.change_etat("Suspendu")

14 liste_attente.append(processus)

15 else:

16 processus.change_etat(<valeur ligne 16>)

17 return ordre_execution

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

1. Cette partie comprend plusieurs questions générales:

a.

Donner le rôle de l'instruction de la ligne 1 du code précédent.

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

1. Cette partie comprend plusieurs questions générales:

b.

Expliquer le résultat suivant:

>>> 0.1 + 0.2 == 0.3

False

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

1. Cette partie comprend plusieurs questions générales:

c.

Expliquer l'erreur suivante:

>>> point_A = (3, 4)

>>> point_A[0]

3

>>> point_A[0] = 2

Traceback (most recent call last):

File "<console>", line 1, in <module>

TypeError: 'tuple' object does not support item assignment

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

2. On définit la classe Segment ci-dessous:

from math import sqrt

class Segment:

def __init__(self, point1, point2):

self.p1 = point1

self.p2 = point2

self.longueur =....... # à compléter a.

Recopier et compléter la ligne 6 du constructeur de la classe Segment.

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

La fonction liste_segments donnée ci-dessous prend en paramètre une liste de points et renvoie une liste contenant les objets Segment qu'il est possible de construire à partir de ces points. On considère les segments [AB] et [BA] comme étant confondus et on ajoutera un seul objet dans la liste.

def liste_segments(liste_points):

n = len(liste_points)

segments = []

for i in range(......):

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

# On construit le segment à partir des points i et j.

seg =..........................

segments.append(seg) # On l'ajoute à la liste.

return segments

b)

Recopier la fonction sans les commentaires et compléter le code manquant.

c)

Donner en fonction de $n$ la longueur de la liste segments. Le résultat peut être laissé sous la forme d'une somme.

d)

Donner, en fonction de $n$, la complexité en temps de la fonction liste_segments.

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

3. L'objectif de cette partie est d'écrire la fonction de recherche des deux points les plus proches en utilisant la méthode diviser-pour-régner.

On dispose de deux fonctions: moitie_gauche (respectivement moitie_droite) qui prennent en paramètre une liste et qui renvoient chacune une nouvelle liste contenant la moitié gauche (respectivement la moitié droite) de la liste de départ. Si le nombre d'éléments de celle-ci est impair, l'élément du centre se trouve dans la partie gauche.

Exemples:

>>> liste = [1, 2, 3, 4]

>>> moitie_gauche(liste)

[1, 2]

>>> moitie_droite(liste)

[3, 4]

>>> liste = [1, 2, 3, 4, 5]

>>> moitie_gauche(liste)

[1, 2, 3]

>>> moitie_droite(liste)

[4, 5]

Rechercher les deux points les plus proches revient à rechercher le plus court segment parmi ceux qui ont été construits à partir du nuage de points.

a.

Écrire la fonction plus_court_segment qui prend en paramètre une liste d'objets Segment et renvoie l'objet Segment dont la longueur est la plus petite.

On procédera de la façon suivante:

Tester si le cas de base est atteint, c'est-à-dire lorsque la liste contient un seul segment;

Découper la liste en deux listes de tailles égales (à une unité près);

Appeler récursivement la fonction pour rechercher le minimum dans chacune des deux listes;

Comparer les deux valeurs récupérées et renvoyer la plus petite des deux.

4. On considère les trois points A (3; 4), B (2; 3) et C (-3; -1).

a.

Donner l'instruction Python permettant de construire la variable nuage_points contenant les trois points A, B et C.

b.

En utilisant les fonctions de l'exercice, écrire les instructions Python qui affichent les coordonnées des deux points les plus proches du nuage de points nuage_points.