EIS

IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 EIS
IP
B-
BI
 CONSIGNES GÉNÉRALES

DOCUMENTS NON AUTORISES

CE CAHIER D’EXAMEN COMPORTE 22 PAGES + 2 PAGES VIDES
LES RÉPONSES DOIVENT ÊTRE ÉCRITES DANS
LES ESPACES RÉPONSES DÉDIÉES
EN CAS DE BESOIN UTILISER LES PAGES VIDES EN FIN DU CAHIER, DANS
CE CAS, IL FAUT LE SIGNALER DANS LES CASES RÉPONSES ALLOUÉES
L’USAGE DES CALCULATRICES EST INTERDIT
Il FAUT RESPECTER IMPÉRATIVEMENT LES NOTATIONS DE L’ÉNONCÉ
VOUS POUVEZ ÉVENTUELLEMENT UTILISER L’ANNEXE

Le sujet comporte trois parties qui traitent les aspects suivants :

Partie I : Programmation orientée objet (Q1..Q21).
BI
Partie II : Programmation procédurale (Q22..Q25).
Partie III : Base de données relationnelle (Q26..Q36).
B-
IP
L’objectif des parties I et II est d’étudier la performance de quelques algorithmes d’ordon-
nancement de processus dans un système d’exploitation. Un système d’exploitation est un
logiciel qui permet d’exploiter les ressources d’une machine, à titre d’exemples : Windows, Linux,
MacOs, Android, etc.
E

Un processus est défini comme étant un programme chargé en mémoire centrale en vue d’être
exécuté par le processeur. Un processus est donc né lors du chargement d’un programme et se
IS
termine à la fin de l’exécution de ce programme. Un processus peut être à l’un des états suivants :
• Prêt : s’il dispose de toutes les ressources nécessaires à son exécution à l’exception du
processeur.
• Elu : s’il est en cours d’exécution par le processeur.
• Bloqué : s’il est en attente d’un événement ou bien d’une ressource pour pouvoir continuer.
Un ordonnanceur est un processus important du système d’exploitation qui gère l’allocation
du temps processeur. Plusieurs processus peuvent être à l’état "Prêt", dans ce cas l’ordonnanceur
se charge de choisir parmi eux celui qui devra être traité en premier lieu selon une stratégie
d’ordonnancement. Un ordonnanceur fait face à deux problèmes principaux :
— Comment élire un processus à exécuter parmi les processus prêts ?
— Durant combien de temps le processeur est alloué au processus élu ?

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 1/27

Partie I : Programmation Orientée Objet
Dans le but de simuler un ordonnanceur de processus, on propose d’implémenter un ensemble
de classes permettant de mettre en place certaines tâches de l’ordonnanceur :
— Classe Processus : modélise les caractéristiques d’un processus.
— Classe FileProcessus : modélise une liste de processus.
— Classe StrategieOrdonnancement : encapsule toutes les données et méthodes communes
aux différentes stratégies d’ordonnancement (FCFS, SJF et RR). Elle est dédiée à la spéciali-
sation par héritage.
— Classe FCFS : modélise la stratégie d’ordonnancement FCFS (First-Come First-Served).
Elle traite les processus dans l’ordre de leurs soumissions (temps d’arrivée). L’organisation
de la file d’attente des processus prêts est donc du type “First In First Out”.
— Classe SJF : modélise la stratégie d’ordonnancement SJF (Shortest Job First). Elle favorise
les processus présents ayant une durée d’exécution plus courte.
— Classe RR : modélise la stratégie d’ordonnancement RR (Round Robin). C’est une straté-
gie préemptive où le processeur est alloué à chaque processus pour une durée limitée dite
quantum. Le processus élu selon l’ordre de sa soumission est exécuté durant ce quantum,
puis remis en queue de la file d’attente. Ceci engendre une gestion circulaire de la liste des
BI
processus prêts.

Interface de la classe Processus

B-

Attributs
• nomP, chaîne de caractères représentant le nom du processus (supposé unique).
• taP, entier représentant le temps d’arrivée du processus.
IP

• deP, entier représentant la durée totale d’exécution du processus.

• etatP, chaîne de caractères représentant l’état du processus.
E

• trP, entier représentant la durée restante pour l’achèvement de l’exécution du processus

initialisé par deP.
IS

NB : le temps est mesuré en nombre de cycles d’horloge du processeur.

Méthodes à implémenter
Q1. __init__(...) : initialise un processus à partir des paramètres nomP, taP, deP et etatP re-
présentant respectivement le nom du processus, son temps d’arrivée, sa durée d’exécution et
son état.
Exemple 1: L’objet processus P de nom "P", ayant un temps d’arrivée 1, une durée nécessaire
d’exécution 8 et l’état "Elu" est instancié comme suit :

P = Processus ("P", 1, 8, "Elu")

Solution:

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 2/27

 class Processus:
def __init__(self, NomP, TaP, DeP, EtatP):
self.nomP =NomP
self.taP=TaP
self.deP=DeP
self.etatP=EtatP
self.trP = DeP

Q2. __str__(...) : représente textuellement un processus (voir l’exemple 2).

Exemple 2: pour le processus P créé dans l’exemple 1

>>> str(P)
"Nom : P - Temps d’Arrivée : 1 - Durée d’Exécution : 8 - Etat : Elu"
BI

Solution:
B-

def __str__(self):
return "Nom:{} -Temps Arrivee:{} - Duree d'Exécution: {}-Etat:
,→ {}".format(self.nomP,self.taP,self.deP,self.etatP)
IP

ou bien
E

def __str__(self):
IS

return f"Nom : {self.nomP}- Temps d'arrivée: {self.taP}- Durée

,→ d'exécution: {self.deP} - Etat: {self.etatP}"

ou bien

def __str__(self):
return "Nom : " + \
self.nomP + " - Temps d'arrivée : " + str(self.taP) + \
"- Durée d'exécution : " + str(self.deP) + \
"-Etat: " + self.etatP

Q3. __eq__(...) : retourne un booléen indiquant si les deux processus self et other ont le
même nom.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 3/27

 Solution:

def __eq__(self, other):

return self.nomP == other.nomP

ou bien

def __eq__(self,other):
if self.nomP==other.nomP:
return True
else:
return False

Q4. changerEtat(...) : change l’état courant du processus vers l’état ns passé en paramètre.
BI

Solution:
B-
def changerEtat(self, ns):
self.etatP = ns
IP

Interface de la classe FileProcessus

E
Attributs

• data, une liste de processus.

IS

Méthodes à implémenter

Q5. __init__(...) : initialise l’attribut data à une liste vide.

Solution:

class FileProcessus:
def __init__(self):
self.data = []

Q6. __len__(...) : retourne le nombre de processus présents dans l’instance actuelle de FileProcessus.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 4/27

 Solution:

def __len__(self):
return len(self.data)

Q7. __str__(...) : permet de représenter un objet de type FileProcessus par une chaîne
selon le format suivant :
"""
Liste de processus : [
Nom : nomP1 - Temps Arrivée : taP1 - Durée d'Exécution : deP1 - Etat : etatP1,
Nom : nomP2 - Temps Arrivée : taP2 - Durée d'Exécution : deP2 - Etat : etatP2,
...
]
"""

Solution:
BI

def __str__(self):
return "Liste de processus:[\n{} \n]".format(",\n".join('\t' +
B-

,→ str(p) for p in self.data))

IP
ou bien

def __str__(self):
E

ch="Liste de Processus:[\n"
for p in self.data:
IS

ch+=p.__str__()+"\n"
return ch+"]"

Q8. __contains__(...) : reçoit un processus p en paramètre et vérifie s’il est présent dans la
file actuelle.

Solution:

def __contains___(self,p):
return p in self.data

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 5/27

 ou bien ou bien

def __contains__(self,p):
if p in self.data:
return True
return False

BI
B-
IP
E IS

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 6/27

Q9. __getitem__(...) : retourne un processus de la file actuelle dont le nom nomP est passé en
paramètre.

Solution:

def __getitem__(self, nomP):

for p in self.data:
if p.nomP == nomP:
return p

Q10. nomProcessusElu(self) : retourne le nom du premier processus ayant l’état "Elu" dans la
file actuelle, None si aucun processus ne dispose de l’état "Elu".

Solution:

def nomProcessusElu(self):
BI
for p in self.data:
if p.etatP == "Elu":
return p.nomP
B-

Q11. ajouterProcessus(...) : ajoute un processus p passé en paramètre dans la file actuelle

IP
(En faisant la gestion des exceptions nécessaires).

Solution:
E

def ajouterProcessus(self,p):
IS

assert p not in self, "Erreur processus déjà existant !!!"

self.data.append(p)

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 7/27

Q12. retirerProcessus(...) : retire et retourne de la file actuelle le processus de nomP passé
en paramètre.

Solution:

def retirerProcessus(self,nomP):
p = self[nomP]
assert p is not None, "Erreur processus n'est pas représenté !!!"
self.data.remove(p)
return p

Interface de la classe StrategieOrdonnancement

Attributs

• fp : instance de la classe FileProcessus contenant les processus en cours d’ordonnan-

BI
cement.
• horloge : un entier représentant l’instant actuel exprimé en cycles d’horloge.
• stats : un dictionnaire où les clés sont les noms des processus en cours d’ordonnance-
ment. Chaque clé est associée à un tuple contenant des mesures reflétant des critères de
B-

performances qui seront détaillés ultérieurement.

Méthodes à implémenter
IP

Q13. __init__(...) : initialise l’attribut fp à partir du paramètre fp, horloge à zéro et

stats par un dictionnaire vide.
E

Solution:
IS

class StratégieOrdonnacement:
def __init__(self, fp):
self.fp = fp
self.horloge = 0
self.stats = {}

La méthode elire(...) : responsable du choix du processus à exécuter. Cette méthode sera

redéfinie dans les classes filles.

def elire(self):
# pour cette classe le script de cette méthode
# n'est pas demandé

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 8/27

Q14. executer(...) : prend un paramètre q ayant par défaut la valeur None et exécute le
processus élu selon la démarche suivante :
— chercher le nom nomP du premier processus ayant l’état "Elu" dans fp ;
— si aucun processus de fp n’est élu, incrémenter l’horloge d’une unité et interrompre
l’exécution actuelle ;
— sinon retirer de fp le processus p de nom nomP et calculer tep le temps processeur
alloué à son exécution :
— si q est None affecter à q le temps restant pour l’achèvement de p ;
— tep prend le minimum entre le temps restant du processus p et q ;
— mettre à jour horloge en l’incrémentant par tep ;
— mettre à jour le temps restant de l’exécution du processus p en le décrémentant par tep ;
— si le processus p est achevé (le temps restant devient nul) :
— calculer dans tr le temps de réponse du processus p (voir équation 1) ;
— calculer dans tat le temps d’attente du processus p (voir équation 2) ;
— insérer le tuple (tr, tat) dans le dictionnaire stats associé à la clé nomP du processus
p;
BI
NB : Pour un processus Pi quelconque, on a :

trPi = instant actuel de l’horloge − taP Pi

B-

Équation 1 – temps de réponse d’un processus Pi

et
IP

tat Pi = tr Pi − deP Pi
E

Équation 2 – temps d’attente d’un processus Pi

IS

— si le processus p n’est pas encore achevé, changer son état à "Prêt" et le remettre dans
fp.

Solution:

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 9/27

 def executer(self, q = None):
nomP = self.fp.nomProcessusElu()
if nomP is None:
self.horloge += 1
return
p = self.fp.retirerProcessus(nomP)
if q == None:
q = p.trP
de = min(q, p.trP)
p.trP -= de
self.horloge += de
if p.trP == 0:
tr = self.horloge - p.taP
tat = tr - p.deP
self.stats[p.nomP] = (tr, tat)
else:
p.changerEtat("Pret")
BI
self.fp.ajouterProcessus(p)

Q15. simuler(...) : prend en paramètre un entier positif duree (durée totale de la simulation)
B-

et applique itérativement les deux étapes suivantes :

— choix du processus à exécuter via la méthode elire ;
— exécution du processus élu via la méthode executer ;
IP

La simulation s’arrête quand l’horloge dépasse duree ou bien jusqu’à l’achèvement de l’exé-
cution des processus de la file fp.
E

Solution:
IS

def simuler(self, duree = float("inf")):

while self.horloge <= duree and len(self.fp) != 0:
self.elire()
self.executer()

Q16. criteres(...) : calcule et retourne un tuple contenant le temps de réponse moyen (TRM)
et le temps d’attente moyen (TAM) calculés à partir du dictionnaire stats en se basant sur
les formules suivantes :

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 10/27

 TRM : moyenne des temps de réponses des processus achevés :
n
X
tr Pi
i=1
TRM = où n est le nombre total de processus achevés.
n

Équation 3 – Le temps de réponse moyen

TAM : moyenne des temps d’attentes des processus achevés :

n
X
tat Pi
i=1
TAM = où n est le nombre total de processus achevés.
n

Équation 4 – Le temps d’attente moyen

Solution:
BI

def criteres(self):
strr = sum(t[0] for t in self.stats.values())
B-
sta = sum(t[1] for t in self.stats.values())
return (strr/ len(self.stats), sta / len(self.stats) ) if
,→ len(self.stats) != 0 else (float("nan"), float("nan"))
IP

ou bien
E

def criteres(self):
IS
return tuple(np.array(self.stats.values()).mean(axis = 0))

ou bien

def criteres(self):
assert len(self.stats)!=0,"STATS EST VIDE"
L1=[]
L2=[]
for t in self.stats.values():
L1.append(t[0])
L2.append(t[1])
TRM=sum(L1)/len(L1)
TAM=sum(L2)/len(L2)
return TRM,TAM

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 11/27

 Interface de la classe fille FCFS
Méthodes à implémenter

Q17. elire(...) : élit le processus ayant le temps d’arrivée minimal parmi les processus ayant
un temps d’arrivée inférieur ou égal à l’instant actuel de l’horloge.

Solution:

class FCFS(StratégieOrdonnacement):
def elire(self):
p = min(self.fp.data, key = lambda p : p.taP)
if p.taP <= self.horloge:
p.changerEtat("Elu")

ou bien

class FCFS(StratégieOrdonnancement):
BI

def elire(self):
L=[]
for p in self.fp.data:
B-
L.append((p.taP,p))
L.sort()
if L[0][0]<=self.horloge:
L[0][1].changerEtat("Elu")
IP
E

Interface de la classe fille SJF

IS

Méthodes à implémenter

Q18. elire(...) : élit le processus ayant la plus courte durée d’exécution avec un temps d’arrivée
inférieur ou égal au temps courant de l’horloge.

Solution:

class SJF(StratégieOrdonnacement):
def elire(self):
lst = [p for p in self.fp.data if p.taP <= self.horloge]
if len(lst) != 0:
p = min(lst, key = lambda p : p.deP)
p.changerEtat("Elu")

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 12/27

 ou bien

class SJF(StratégieOrdonnancement):
def elire(self):
L=[]
for p in self.fp.data:
if p.taP<=self.horloge:
L.append((p.deP,p))
if len(L)!=0:
L.sort()
L[0][1].changerEtat("Elu")

Interface de la classe fille RR

Attributs
BI

• q : entier positif valeur du quantum alloué aux processus.

Méthodes à implémenter
B-

Q19. __init__(...) initialise un attribut d’instance q à partir du paramètre q.

Solution:
IP

class RR(StratégieOrdonnacement):
E
def __init__(self, fp, q):
super().__init__(fp)
IS
self.q = q

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 13/27

Q20. executer(...) : exécute le processus élu durant le quantum alloué.

Solution:

def executer(self):
super().executer(self.q)

Q21. elire(...) : élit le premier processus de la file ayant un temps d’arrivée inférieur ou égal
au temps courant de l’horloge.

Solution:

def elire(self):
for p in self.fp.data:
if p.taP <= self.horloge:
p.changerEtat("Elu")
break
BI
B-

Partie II : Programmation Procédurale

IP
Dans cette partie on s’intéresse à simuler et à comparer les différentes stratégies d’ordonnancement
appliquées à une file de processus supposés stockés dans un fichier texte où chaque ligne est de la
forme :
E
"nomP#taP#deP#etatP\n"
IS

A#0#3#Prêt
B#1#8#Prêt
C#2#6#Prêt
D#3#4#Bloqué
E#4#4#Prêt
F#6#5#Prêt
G#8#2#Prêt
H#9#1#Prêt

Figure 1 – Extrait d’un fichier texte décrivant une file de processus

Pour un échantillon donné de processus, un algorithme d’ordonnancement est jugé performant

sur la base de la comparaison de deux critères, le temps de réponse moyen (TRM) en premier
lieu et le temps d’attente moyen (TAM) en second lieu.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 14/27

Q22. Écrire une fonction nommée processusTxt qui prend en entrée une ligne contenant les
informations d’un processus comme illustré par la figure 1 et retourne une instance de la
classe Processus.

Solution:

def ProcessusTxt(ligne):
lst = ligne.split("#")
lst[1] = int(lst[1])
lst[2] = int(lst[2])
return Processus(*lst) #return Processus(lst[0], lst[1], lst[2], lst[-1])

Q23. Écrire une fonction nommée chargement qui prend en entrée nomF le nom d’un fichier texte
(comme indiqué sur la figure 1) et retourne une instance de la classe FileProcessus contenant
tous les processus du fichier.

Solution:
BI

def chargement(nomf):
fp = FileProcessus()
B-

f = open(nomf, "r")
for line in f:
p = ProcessusTxt(line.strip())
IP
fp.ajouterProcessus(p)
f.close()
return fp
E IS

Solution: ou bien

def chargement(nomf):
fp = FileProcessus()
f = open(nomf, "r")
L=f.readlines()
L=[i.strip() for i in L]
for ligne in L:
p = ProcessusTxt(ligne)
fp.ajouterProcessus(p)
f.close()
return fp

Q24. Écrire une fonction nommée simulerStrategie qui prend en entrée :

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 15/27

 — clsStrategie : une classe représentant une stratégie d’ordonnancement (FCFS, SJF,
RR).
— fp : la file des processus.
— duree : un entier indiquant la durée totale de la simulation.
— q : paramètre optionnel qui prend par défaut None (quantum).
La fonction calcule et retourne un tuple contenant :
— Le pourcentage de processus achevés.
— Le temps de réponse moyen TRM (voir équation 3).
— Le temps d’attente moyen TAM (voir équation 4).
Ces grandeurs sont mesurées pour une simulation de la stratégie indiquée par la stratégie
clsStrategie durant duree (avec un quantum q pour la stratégie RR).

Solution:

def simulerStrategie(clsStrategie, fp, duree, q = None):

nbP = len(fp)
BI
if q is not None:
stg = clsStrategie(fp, q)
else:
stg = clsStrategie(fp)
B-

stg.simuler(duree)
nbR = len(fp)
return ((nbP-nbR)/nbP,) + stg.criteres()
IP

Q25. Écrire un script qui permet d’effectuer les étapes suivantes :

E

(a) Charger la file des processus à partir du fichier texte "Processus.txt" (supposé existant).
IS
(b) Demander à l’utilisateur de saisir deux entiers positifs d et q décrivant respectivement
la durée totale de la simulation et le quantum à utiliser pour la méthode préemptive.
(c) Initialiser 3 Matrices mTermines, mTAM et mTRM (np.ndarray) ayant 3 lignes et d colonnes
où
— Chaque indice de ligne i représente une stratégie d’ordonnancement ( 0 pour FCFS,
1 pour SJF et 2 pour RR).
— Chaque indice de colonne j représente une durée totale de simulation (j+1) en cycles
d’horloge.
(d) La simulation se déroule comme suit :
— Pour chaque stratégie d’ordonnancement i (indice de ligne) et pour chaque indice
de colonne j.
— Copier la liste des processus dans un objet cfp (utiliser la fonction deepcopy du
module copy voir Annexe).
— Remplir mTermines, mTAMet mTRM à patir du résultat de la fonction simulerStrategie tel
que :

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 16/27

 • mTermines[i, j] contiendra le pourcentage de processus terminés suite à la
simulation de la stratégie i pour une durée totale de j+1.
• mTAM[i, j] contiendra le temps d’attente moyen suite à la simulation de la
stratégie i pour une durée totale de j+1.
• mTRM[i, j] contiendra le temps de réponse moyen suite à la simulation de la
stratégie i pour une durée totale de j+1.
(e) Finalement tracer les courbes illustratives des pourcentage de processus achevés, temps
d’attente moyen et temps de réponse moyen pour chaque stratégie et chaque durée de
simulation.

Solution:
BI
B-
IP
E IS

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 17/27

 import numpy as np
from copy import deepcopy
from matplotlib import pyplot as plt
fp = chargement("processus.txt")
while True:
try:
d = int(input(" donner la duree totale de la simulation = "))
except:
pass
else:
if d > 0:
break
while True:
try:
q = int(input(" donner le quantum = "))
except:
pass
else:
if q > 0:
break
mTermines = np.empty((3, d))
BI
mTAM = np.empty((3, d))
mTRM = np.empty((3, d))
strategies = {0:FCFS, 1:SJF, 2:RR}
strategyNames = {0:"FCFS", 1:"SJF", 2: "RR"}
B-
qvals = {0:None, 1:None, 2:q}
for i in range(3):
for j in range(d):
cfp = deepcopy(fp)
IP
q = qvals[i]
stgcls = strategies[i]
mTermines[i,j], mTAM[i,j], mTRM[i,j] = simulerStrategie(stgcls, cfp, j+1,
,→ q)
E
time = np.arange(d)
fig, (ax1, ax2, ax3) = plt.subplots(3, 1)
IS
for i in range(3):
ax1.plot(time, mTermines[i], label = strategyNames[i])
ax2.plot(time, mTAM[i], label = strategyNames[i])
ax3.plot(time, mTRM[i], label = strategyNames[i])
fig.tight_layout()
for ax in (ax1, ax2, ax3):
ax.set_xlabel(" temps ")
ax.legend()
ax1.set_ylabel(" pourcentage ")
ax2.set_ylabel(" TAM ")
ax3.set_ylabel(" TRM ")
plt.show()

Solution: ou bien

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 18/27

 import numpy as np
from copy import deepcopy
from matplotlib import pyplot as plt
fp = chargement("processus.txt")
while True:
d=int(input("Donner la durée totale de la simulation:"))
if d>0:
break
while True:
q=int(input("Donner le quantum:"))
if q>0:
break
mTermines=np.zeros((3,d))
mTAM=np.zeros((3,d))
mTRM=np.zeros((3,d))
stgs=[FCFS,SJF,RR]
for i in range(2):
for j in range(d):
BI
cfp = deepcopy(fp)
mTermines[i,j], mTAM[i,j], mTRM[i,j] = simulerStrategie(stgs[i],cfp,
,→ j+1)
cfp = deepcopy(fp)
B-
mTermines[2,j], mTAM[2,j], mTRM[2,j] = simulerStrategie(stgs[2],cfp, j+1,q)
t = np.arange(d)
plt.subplot(311)
plt.plot(t, mTermines[0])
IP
plt.plot(t, mTAM[0])
plt.plot(t, mTRM[0])
E
plt.subplot(312)
plt.plot(t, mTermines[1])
IS
plt.plot(t, mTAM[1])
plt.plot(t, mTRM[1])
plt.subplot(313)
plt.plot(t, mTermines[2])
plt.plot(t, mTAM[2])
plt.plot(t, mTRM[2])
plt.show()

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 19/27

 Partie III : Base de Données Relationnelle
Le ministère du transport fait appel à votre expertise pour manipuler une base de données rela-
tionnelle dans l’objectif de gérer en partie l’infrastructure ferroviaire à l’échelle nationale.

Règles de gestion et contraintes à considérer

— Dans notre contexte une gare ferroviaire de voyageurs est un lieu d’arrêt des trains pour
la montée et la descente des passagers.
— Une gare peut jouer le rôle d’arrêt, de départ et/ou arrêt transitoire et/ou arrêt de
terminus.
— Dans une gare de départ ou de terminus un train est mis au repos pendant un certain
nombre d’heures.
— Une ville peut contenir une ou plusieurs gares.
— Un voyage permet de desservir un ensemble de gares.
— Tout voyage par train doit nécessairement avoir une gare de départ, une gare de terminus
et éventuellement un ensemble de gares d’arrêts transitoires.
BI
Le schéma relationnel de la base de données ayant le nom "ferroviaire.db" est défini par
les relations suivantes :

■ Ville(idVille, nomVille, nbHabitants)

B-

La table Ville, stocke les différentes informations relatives aux villes, est caractérisée par
les attributs suivants :
— idVille : identifiant pour distinguer les différentes villes, clé primaire de type entier.
IP

— nomVille : dénomination d’une ville, de type chaîne de caractères.

— nbHabitants : nombre d’habitants d’une ville, de type entier.
E

■ Gare(idGare, nomGare,#idVille)
La table Gare, stocke les informations des gares, est caractérisée par les attributs suivants :
IS

— idGare : identifiant de la gare, clé primaire de type chaîne de caractères.

— nomGare : dénomination distinctive attribuée à la gare de type chaîne de caractères.
— idVille : référence le numéro de la ville où se trouve la gare, de type entier, clé
étrangère qui fait référence à la table Ville.

■ Train(idTrain, dateMiseService,capacite)
La table Train, stocke les informations relatives aux trains, est caractérisée par :
— idTrain : identifiant du train, clé primaire de type chaîne de caractères.
— dateMiseService : date de mise en service du train, de type Date ("AAAA-MM-JJ")
— capacite : capacité d’accueil maximale du train, de type entier.

■ Voyage(idVoyage, dateHeureDepart, dateHeureArrivee, #idGareDepart,# idGareTerminus,

#idTrain)
La table Voyage, stocke les informations des voyages, est caractérisée par les attributs
suivants :
— idVoyage : identifiant du voyage, clé primaire de type chaîne de caractères.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 20/27

 — dateHeureDepart : date et heure de départ pour un voyage assuré par un train à
partir de sa gare de départ, de type datetime ("AAAA-MM-JJ HH:MM:SS").
— dateHeureArrivee : date et heure d’arrivée pour un voyage, assuré par un train, à
sa gare terminus, de type datetime ("AAAA-MM-JJ HH:MM:SS").
— idGareDepart : identifiant de la gare de départ de type chaîne de caractères, clé
étrangère qui fait référence à la table Gare.
— idGareTerminus : identifiant de la gare terminus de type chaîne de caractères, clé
étrangère qui fait référence à la table Gare.
— idTrain : identifiant du train qui assure le voyage de type chaîne de caractères, clé
étrangère qui fait référence à la table Train.

■ Desservir(#idVoyage, #idGareArret, dateHeurePassage)

La table Desservir, stocke l’ensemble des gares desservies pour un voyage, est caracté-
risée par les attributs suivants :
— idVoyage : identifiant d’un voyage, de type chaîne de caractères, clé étrangère qui
fait référence à la table Voyage.
— idGareArret : identifiant d’une gare de type chaîne de caractères, clé étrangère qui
fait référence à la table Gare.
BI
— dateHeurePassage : date et heure de passage d’un train à la gare, de type datetime
("AAAA-MM-JJ HH:MM:SS").
NB : idVoyage et idGareArret ensemble forment la clé primaire de la table
B-
Desservir.
Il est aussi à noter que la table Desservir ne stocke pas les gares de départ et de
terminus pour un voyage donné.
IP

Travail demandé
E IS
Algèbre relationnelle

Exprimer en algèbre relationnelle les requêtes permettant de :

Q26. Donner les noms des villes qui contiennent des gares desservies par le voyage d’identifiant
"V23".

Solution:

Π

Ville ▷◁
idVille
Gare ▷◁ σ
idGare idGareArret idVoyage "V23"
(Desservir)

nomVille = =

Q27. Quels sont les noms des villes dont le nombre d’habitants dépasse 100000 et qui ne contiennent
aucune gare.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 21/27

 Solution:

σ ▷◁
  
Π
nomVille nbHabitants>100000
(Ville)
idVille Π
idVille
(Ville) − Π
idVille
(Gare)

Ou bien

Π
nomVille

σ
nbHabitants
>100000

(Ville) − Π
nomVille

Ville ▷◁
idVille
Gare


SQL

Q28. Écrire la requête SQL qui permet de créer la table Desservir en respectant les contraintes
d’intégrité déjà su-citées. Les autres tables sont supposées déjà créées.

Solution:
BI

CREATE TABLE Desservir

(
B-
idVoyage TEXT REFERENCES Voyage,
idGareArret TEXT REFERENCES Gare,
dateHeurePassage DATETIME,
PRIMARY KEY(idVoyage, idGareArret)
IP

);
E
create table Desservir
(
idVoyage text,
IS

idGareArret text,
dateheurePassage datetime,
primary key(idVoyage,idGareArret),
foreign key(idVoyage) references Voyage(idVoyage),
foreign key(idGareArret) references Gare(idGare)
)

Dans la suite on suppose que les tables de la base de données sont remplies en respectant les
contraintes et les règles de gestion su-citées.

Répondre aux questions suivantes par des requêtes SQL.

Q29. Si le train d’identifiant "TR77" circule le premier juin 2023 à 8h, déterminer toutes les
informations relatives à son voyage.

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 22/27

 Solution:

SELECT *
FROM Voyage
WHERE (idTrain = 'TR77')
AND (dateHeureDepart >= '2023-06-01 08:00:00')
AND (dateHeureArrivee <= '2023-06-01 08:00:00')

Q30. Déterminer le nombre de gares pour chaque ville.

Solution:

SELECT idVille , COUNT(*) AS NBGares

FROM Gare
GROUP BY idVille
BI
B-
Q31. Donner toutes les informations relatives aux gares qui sont à la fois gare de départ et gare
terminus pour un même voyage.
IP
Solution:

/*Solution 1*/
E

SELECT DISTINCT G.*

FROM Voyage AS V, Gare AS G
IS

WHERE (idGareDepart = idGare) AND (idGareDepart = idGareTerminus)

ou bien

/*Solution 2*/
SELECT *
FROM Gare
WHERE IdGare IN
(
SELECT idGareDepart
FROM Voyage
WHERE idGareDepart = idGareTerminus
);

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 23/27

Q32. Déterminez pour chaque voyage le nom de la ville de départ, le nom de la ville d’arrivée
ainsi que les dates et heures de départ et d’arrivée.

Solution:

SELECT V1.nomVille AS DEPART, dateheureDepart, V2.nomVille AS ARRIVEE, dateheureArrivee

FROM Voyage AS V, Gare AS G1, Gare AS G2, Ville AS V1, Ville AS V2
WHERE (G1.idGare = idGareDepart)
AND (G2.idGare=idGareTerminus)
AND (G1.idville=V1.idVille)
AND (G2.idville=V2.idVille)

Q33. Donner toutes les informations des voyages qui desservent le maximum de gares.

Solution:
BI
B-
IP
E IS

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 24/27

 SELECT V.*
FROM Desservir AS D, Voyage AS V
WHERE D.idVoyage =V.idVoyage
GROUP BY V.idVoyage
HAVING COUNT(*)= (
SELECT MAX(NB)
FROM (
SELECT COUNT(*) AS NB
FROM Desservir
GROUP BY idVoyage
)
)
/* ou bien */
SELECT *
FROM Voyage AS V
WHERE idVoyage IN (
SELECT idVoyage FROM
(
BI

SELECT idVoyage, COUNT(*) AS NBV

FROM Desservir
GROUP BY idVoyage
B-
HAVING NOT EXISTS
(
SELECT *
FROM Desservir
IP

GROUP BY idVoyage
HAVING COUNT(*) > NBV
)
E
)
)
IS

SQLITE

Dans la suite les fonctions demandées doivent être écrites en Python en désignant par cur le
curseur d’exécution de requêtes.

Q34. Écrire la fonction trainV qui prend comme paramètres :

— cur : le curseur d’exécution des requêtes ;
— idV : l’identifiant d’un voyage ;
retourne idT l’identifiant du train qui a assuré le voyage idV.

Solution:

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 25/27

 def trainV(cur,idV):
q = """
SELECT idTrain
FROM Voyage
WHERE (idVoyage = ?)
"""
cur.execute(q, [idV])
r = cur.fetchall()
if len(r) == 0:
raise Exception(" Voyage inexistant !!!")
else:
return r[0][0]

Q35. Écrire la fonction circuitVoyage qui prend comme paramètres :

— cur : le curseur d’exécution des requêtes ;
BI
— idV : l’identifiant d’un voyage ;
retourne un dictionnaire dont :
— la clé est un tuple composé de l’identifiant du voyage idV et l’identifiant du train qui
B-
l’assure.
— la valeur est une liste de tuples où chaque tuple contient le nom de la ville, la gare, la date
et heure dans un ordre chronologique croissant. L’extrait qui suit montre un exemple :
IP

{('V01', 'TR10'):
[('GABES', 'GARE-GAB', '2023-01-15 11:15:00'),
E

('SFAX', 'GARE-MAH', '2023-01-15 12:30:00'),

('SFAX', 'GARE-SF', '2023-01-15 13:15:00'),
IS

('SOUSSE', 'GARE-SOU', '2023-01-15 15:15:00'),

('TUNIS', 'GARE-TUN', '2023-01-15 18:00:00')]
}

Solution:

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 26/27

 def circuitVoyage(cur,idV):
q1 = """
SELECT V1.nomVille,
G1.nomGare,
V.dateHeureDepart,
V2.nomVille,
G2.nomGare,
V.dateHeureArrivee
FROM Voyage AS V,
Gare AS G1,
Ville AS V1,
Gare AS G2,
Ville AS V2
WHERE (V.idGareDepart = G1.idGare)
AND (G1.idVille = V1.idVille)
AND (V.idGareArrivee = G2.idGare)
AND (G2.idVille = V2.idVille)
BI
AND (V.idVoyage = ?)
"""
cur.execute(q1, [idV])
r = cur.fetchall()
B-
if len(r) == 0:
raise Exception(" Erreur, voyage inexistant!!!")
q2 = """
SELECT nomVille, nomGare, dateHeurePassage,
IP

FROM Ville AS V,
Gare AS G,
Desservir AS D
E

WHERE (D.idVoyage = ?)
AND (D.idGareArret = G.idGare)
IS

AND (G.idVille = V.idVille)

ORDER BY dateHeurePassage
"""
cur.execute(q2, [idV])
l = cur.fetchall()
l.insert(0, r[0][:3])
l.append(r[0][3:])
return {(idV, trainV(cur,idV)) : l}

Q36. Écrire la fonction circuitsVoyages qui prend en paramètre cur et retourne la liste des
dictionnaires des circuits de tous les voyages en faisant appel à la fonction circuitVoyage de
la question Q35. L’extrait qui suit montre un exemple :

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 27/27

 [
{('V01', 'TR10'):
[('GABES', 'GARE-GAB', '2023-01-15 11:15:00'),
('SFAX', 'GARE-MAH', '2023-01-15 12:30:00'),
('SFAX', 'GARE-SF', '2023-01-15 13:15:00'),
('SOUSSE', 'GARE-SOU', '2023-01-15 15:15:00'),
('TUNIS', 'GARE-TUN', '2023-01-15 18:00:00')
]},
{('V02', 'TR12'):
[('TUNIS', 'GARE-TUN', '2023-03-01 16:00:00'),
('SOUSSE', 'GARE-KAL', '2023-03-01 17:15:00'),
('SOUSSE', 'GARE-SOU', '2023-03-01 18:00:00')
]}
]

Solution:
BI

def circuitsVoyages(cur):
q = """
B-
SELECT idVoyage
FROM Voyage
"""
cur.execute(q)
IP

return [ ciruitVoyage(cur, t) for (t,) in cur.fetchall()]

E IS

Concours MP, PC et T Session Juin 2023 Epreuve d’Informatique Page 28/27

 EIS
IP
B-
BI