نموذج المباراة الوطنية المشتركة CNC 2019: المعلوميات - شعبة PSI لولوج مدارس المهندسين

استُخرج هذا النص آلياً من صور الامتحان وقد يحتوي على أخطاء في القراءة — الصور أعلاه هي المرجع.

— صفحة 1 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Les candidats sont informés que la précision des raisonnements algorithmiques ainsi que le soin apporté
à la rédaction et à la présentation des copies seront des éléments pris en compte dans la notation. ١
convient en particulier de rappeler avec précision les références des questions abordées. Si, au cours de
l'épreuve, un candidat repère ce qui peut lui sembler être une erreur d'énoncé, il le signale sur sa copie et
poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Remarques générales :

* Cette épreuve est composée d’un exercice et d’un problème indépendants ;

* Toutes les instructions et les fonctions demandées seront écrites en Python ;

* Les questions non traitées peuvent être admises pour aborder les questions ultérieures ;
* Toute fonction peut être décomposée, si nécessaire, en plusieurs fonctions.

ند ند ند ند ند اند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند انه

Exercice : (4 points)

Somme et factoriel

1pt Q1- Écrire la fonction factoriel (k) qui reçoit en paramètre un entier positif k et qui renvoie la
valeur du factoriel de k : k! =1*2*3* ...*k.
Exemples :

e  Lafonction factoriel (5) renvoie le nombre :120=1*2*3*4*5
e  Lafonction factoriel (0) renvoie le nombre : 1

05pt = Q2- Déterminer la complexité de la fonction factoriel (k), et justifier votre réponse.

1.5 pt Q3- Écrire la fonction som_fact (L) qui reçoit en paramètre une liste L de nombres entiers
positifs. La fonction renvoie la somme des factoriels des éléments de L.

Exemple :

La fonction som_fact (L) renvoie la valeur de la somme : 5! + 3! + O! + 6! + 1!

1 pt Q4- Déterminer la complexité de la fonction som_fact (L), et justifier votre réponse.

لالم للم لمالم الال لمالمل ا لصل مالم الاقم

Page 1 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 2 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Problème :

Réseau routier

Figure 1 : Extrait du réseau routier du Maroc

Un réseau routier peut être représenté par un dessin qui se compose de points et de traits continus
reliant deux à deux certains de ces points : les points sont les villes, et les lignes sont les routes. On
considère que toutes les routes sont à double sens. Chaque route peut être affectée par une valeur qui peut
représenter le temps ou la distance entre deux villes, …

Étant donné un réseau routier, on pourra s'intéresser à la résolution des problèmes suivants :

= Quel est le plus court chemin entre deux villes ?

= Entre deux villes, quel est le nombre de chemins passant par un nombre de routes donné ?

= Est-il possible de passer par toutes les villes du réseau, sans passer deux fois par une même ville ?,
si oui, quel est le plus court chemin ?

= Entre deux villes, quel est le chemin ayant le moindre coût ?

Partie I :

Modélisation d’un réseau routier

On considère un réseau routier composé de n villes (avec n = 2). Les villes du réseau routier sont
numérotées par des entiers allant de 0 à n-1.

Exemple :

Page 2 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 3 —
Epreuve d’Informatique — Session 2019 - Filière PSI

Figure 2 : Réseau routier composé de 15 routes, et de 8 villes numérotées de 0 à 7.

Pour plus de clarté, tous les exemples de ce problème seront appliqués sur le réseau routier de la figure 2.

Représentation du réseau routier

Pour représenter un réseau routier de n villes, on utilise une matrice symétrique R d'ordre n (n lignes et
n colonnes), telle que :

Pour toutes les villes i et j, telles que O‹i‹n et O‹j‹n,ona:
› R[i,j1]= R[j,i]=1, s’il existe une route qui relie entre la ville i et la ville j ;

Exemple :
Le réseau routier de la figure 2 est représenté par la matrice symétrique R, d’ordre 8, suivante :

NB : Dans la matrice symétrique R, les lignes i et les colonnes j représentent les villes du réseau routier.

1. 1- Représentation de la matrice du réseau routier en Python

Pour représenter la matrice symétrique R d'ordre n, on utilise une liste composée de n listes qui sont
toutes de même longueur n.

Page 3 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 4 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Exemple :

La matrice symétrique R, du réseau routier de la figure 2, est représentée par la liste R, composée de 8
listes, de taille 8 chacune :

R[i] [j] est l'élément de R, à ‏“نوا‎ ligne et la j°"° colonne.
Exemples : R[0][0] est l’élément : 0, et R[0][2] est l'élément : 1

R[i] est la ligne d'indice i dans R.
Exemple : R[0] est la liste [O,1,1,1,0,0,0,0], qui représente la ligne d’indice 0 dans la matrice R.

Q 1- À partir de la matrice symétrique R de la figure 2, donner les résultats des expressions suivantes :

I. 2- Villes voisines
i et j sont deux villes dans un réseau routier représenté par une matrice symétrique R.
Les villes i et j sont voisines, s'il existe une route entre la vaille i et la ville j.

Q 2. a- Écrire la fonction voisines (i, j,R), qui reçoit en paramètres deux villes i et j d’un réseau
routier représenté par la matrice symétrique R. La fonction renvoie True si les villes i et j sont voisines,
sinon, la fonction renvoie False.

Exemples :

e La fonction voisines (3, 0, R) renvoie True ; (les villes 3 et O sont voisines)
e La fonction voisines (3, 5, R) renvoie False. (les villes 3 et 5 ne sont pas voisines)

Q 2. b- Écrire la fonction 1ist_voisines (i,R), qui reçoit en paramètres une ville i d’un réseau
routier représenté par la matrice symétrique R. La fonction renvoie la liste de toutes les villes voisines à la
ville i.

Exemple :

La fonction list_voisines (3, R) renvoie la liste des villes voisines à la ville 3:[0,2,4,6,7]

I. 3- Degré d’une ville

Dans un réseau routier, le degré d'une ville i est le nombre de villes voisines à la ville i.

Q 3- Écrire la fonction degre (i, R), qui reçoit en paramètres une ville i d’un réseau routier représenté
par la matrice symétrique R. La fonction renvoie le degré de la ville i.
Exemples :

e La fonction degre (3, R) renvoie le nombre :5 (La ville 3 possède 5 villes voisines)
e 12 fonction degre (0, R) renvoie le nombre :3 (La ville 0 possède 3 villes voisines)
e La fonction degre (2, R) renvoie le nombre :4 (La ville 2 possède 4 villes voisines)

Page 4 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 5 —
Épreuve d’Informatique — Session 2019 - Filière PSI

1. 4- Liste des degrés des villes

Q 4. Écrire la fonction liste_degres (R), qui reçoit en paramètre la matrice symétrique 8
représentant un réseau routier. La fonction renvoie une liste D contenant des tuples. Chaque tuple de D
est composé de deux éléments : une ville du réseau routier, et le degré de cette ville.

Exemple :
La fonction liste_degres (R) renvoie la liste D suivante :

I. 5- Tri des villes
Q 5. a- Écrire la fonction tri_degres (D), qui reçoit en paramètre la liste D des degrés des villes. La
fonction trie les tuples de la liste D dans l’ordre décroissant des degrés des villes.
Exemple :
Après l'appel de la fonction tri_degres (D), on obtient la liste suivante :

Q 5. b- Écrire la fonction tri_villes(R), qui reçoit en paramètre la matrice symétrique R
représentant un réseau routier. La fonction renvoie la liste des villes triées dans l'ordre décroissant des
degrés des villes.

Exemple :
La fonction tri_villes (R) renvoie la liste des villes triées dans l'ordre décroissant des degrés :

Partie II :

Coloration optimale des villes d’un réseau routier

Une coloration des villes du réseau routier est une affectation de couleurs à chaque ville, de façon à
ce que deux villes voisines soient affectées par deux couleurs différentes. Le nombre minimum de
couleurs nécessaires pour colorier un réseau routier est appelé : nombre chromatique.

La recherche du nombre chromatique est une question qui intervient dans beaucoup de problèmes
concrets :

y L'établissement d'emplois du temps ;
“la gestion de ressources partagées ;
‏آ‎ la compilation dans l'utilisation efficace des registres ;

On cherche à construire une liste © qui contiendra les couleurs des villes. Ces couleurs seront
représentés par des entiers strictement positifs : chaque élément C[k] contiendra la couleur de la ville k
du réseau routier.

Page 5 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 6 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Pour construire la liste C des couleurs, on propose d’utiliser un algorithme, appelé : algorithme de
glouton. C'est un algorithme couramment utilisé dans la résolution de ce genre de problèmes, afin
d'obtenir des solutions optimales.

Principe de l’algorithme de glouton :
V est la liste des villes triées dans l’ordre décroissant des degrés des villes
C est une liste de même taille que V, initialisée par des 0
Pour toute ville k de V :
C[k] € première couleur non utilisée par les villes voisines à la ville k
Retourner la liste C

IT. 6- Premier entier qui n’existe pas dans une liste d’entiers

Q 6- Écrire la fonction premier entier (L), qui reçoit en paramètre une liste ‏ا‎ de nombres entiers
positifs. La fonction renvoie le premier entier positif qui n'appartient pas à la liste L.
Exemple :

La fonction premier_entier([0,0,3,1,0,1,0,0]) renvoie le nombre : 2

II. 7- Liste des couleurs des villes voisines à une ville

Q 7- Écrire la fonction couleurs_voisines (k,C,R), qui reçoit en paramètres une ville k d'un
réseau routier représenté par la matrice symétrique R, et la liste C des couleurs des villes du réseau. La
fonction renvoie la liste des C[i] telle que i est une ville voisine à la ville k.
Exemples :

e La fonction couleurs_voisines (4, [ 0, 0, 0, 1, 0, O, 0, 0 ], R) renvoie la liste : [O, O, 1, 0, 0]

e  Lafonction couleurs _voisines (2, [ 0, 0, 0, 1, 2, 0, 0, 0 ], R) renvoie la liste: [O, O, 1, 2]

e La fonction couleurs_voisines (6, [ 0, 0, 3, 1, 2, 0, 0, 0 ], R) renvoie la liste: [1, 2, 0, 0]

e La fonction couleurs voisines (0, [ 0, 0, 3, 1, 2, 0, 3, 0 ], R) renvoie la liste: [O, 3, 1]

II. 8- Coloration des villes

Q 8- Écrire la fonction couleurs_villes (R), qui reçoit en paramètre la matrice symétrique R
représentant un réseau routier. La fonction renvoie la liste C des couleurs des villes, en utilisant le
principe de glouton cité ci-dessus.

Exemple :
La fonction couleurs_villes (R) renvoie la liste des couleurs :C=[2,1,3,1,2,1,3,2]
Dans cette liste C :

e Les villes 0, 4 et 7 ont la même couleur : 2 ;
e  Lesvilles 1,3 et5 ont la même couleur : 1 ;
e Les villes 2 et 6 ont la même couleur : 3.

NB : Dans cet exemple, le nombre chromatique est 3.

Page 6 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 7 —
Épreuve d’Informatique — Session 2019 - Filière PSI
Partie III :

Chemins dans un réseau routier

II. 9- Chemin entre deux villes

Dans un réseau routier, un chemin est un tuple T qui contient des villes du réseau, et qui satisfait les
deux conditions suivantes :

› 61 : Le tuple T contient au moins deux villes du réseau routier ;
›  c2 : Deux villes consécutives dans T sont voisines.

Exemples :
e  Letuple (2, 0,1, 4,3 ( est un chemin entre la ville 2 et la ville 3, composé de 4 routes ;
e  Letuple ( 7, 6, 4, 5, 6, 3, 4 ) est un chemin entre la ville 7 et la ville 4, composé de 6 routes ;
e  Letuple (3, 1, 4, 7 ) n'est pas un chemin.

Q 9- Écrire la fonction chemin_valide (T,R), qui reçoit en paramètres un tuple T contenant des
villes du réseau routier représenté par la matrice symétrique R. La fonction renvoie True si le tuple T
satisfait les deux conditions c1 et c2 citées ci-dessus, sinon, la fonction renvoie False.

111. 10- Chemin simple entre deux villes

Dans un réseau routier, un chemin simple est un chemin qui passe une seule fois par la même ville.

Exemples :

e Le chemin ( 2, 0, 1, 4, 3 ) est un chemin simple entre la ville 2 et la ville 3 ;
e Le chemin ( 6, 7, 3, 4, 2, 3, 6, 5 ) n’est pas simple.

Q 10- Écrire la fonction chemin_simple (T,R), qui reçoit en paramètres un chemin T dans un
réseau routier représenté par la matrice symétrique R. La fonction renvoie True si le chemin T est un
simple, sinon, la fonction renvoie False.

111. 11- Plus court chemin entre deux villes

On suppose que la fonction liste_chemins (i, j,R), reçoit en paramètres deux villes i et j d’un
réseau routier représenté par la matrice symétrique R. Cette fonction renvoie une liste qui contient tous
les chemins simples entre la ville i et la ville j.

Exemple :
La fonction liste_chemins (1, 5, R) renvoie la liste de tous les chemins simples entre les villes 1 et 5 :

Page 7 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 8 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Le plus court chemin entre une ville i et une ville j est un chemin simple entre la ville i et la ville j, et
qui traverse le moins de villes.

NB : On peut trouver plusieurs plus courts chemins entre deux villes.

Q 11- Écrire la fonction pe_chemins (i, j, R), qui reçoit en paramètres deux villes i et j d’un réseau
routier représenté par la matrice symétrique R. Cette fonction renvoie la liste de tous les plus courts
chemins entre la ville i et la ville j.

Exemples :

e La fonction pc_chemins (0, 7, R) renvoie la liste [ (0 , 3 , 7) ] ;
e La fonction pc_chemins (7, 1, R) renvoie la liste :

Partie IV :

Calcul du nombre de chemins entre deux villes

Dans cette partie, on considère que le module numpy est importé :
from numpy import *

On suppose que le réseau routier est représenté par la matrice symétrique R, et que la matrice R est
créée par la méthode array() du module numpy.

Exemple :

Dans cette partie, on propose de résoudre le problème suivant :
Soit p un entier strictement positif.

Quel est le nombre de chemins (simples ou non) entre une ville i et une ville j, passant exactement
par p routes ?

Par exemple, dans le réseau routier de la figure 2, pour aller de la ville 1 à la ville 3, en passant
exactement par 5 routes, on peut trouver plusieurs chemins, dont voici quelques uns :

Pour résoudre ce problème, on doit procéder ainsi :

= Calculer la matrice M = R” (matrice symétrique R élevée à la puissance p)
= Chaque élément M[i][j] représente le nombre de chemins, entre la ville i et la ville j, passant
par p routes ;
= La matrice M est symétrique aussi. Le nombre de chemins, entre la ville i et la ville j, est le
même que celui entre la ville j et la ville i.
Page 8 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 9 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Exemples :
31213011 4 8 810 5 5 5 2
1 3 2 31 1 18) 8 4 8 510 2 5 |5]
2 2 4 2 2 1 1 8 8 81111 5 6 5
1 3 252 3 2 1 10 511 815 5 11 10
31225 1 2 3 5 10 1115 8 10 11 5
6011318321 5 2 5 510 4 8 8
1.1.2 2 2 2 4 2 5 5 61111 8 8 8
1011 1 3 1 2 3 2 510 5 8 84

Par exemple, entre la ville 1 et la ville 7 :

e |lya0 chemins qui passent exactement par deux routes (dans la matrice M = ‏ضع‎ ;
e  |lya5 chemins qui passent exactement par trois routes (dans la matrice M = R°).

IV. 12- Produit matriciel

Rappel :

On considère la matrice A, de m lignes et n colonnes, et la matrice B de n lignes et p colonnes. En
effectuant le produit matriciel de À et B, on obtient la matrice C de m lignes et p colonnes, sachant que
les coefficients de la matrice C sont calculés par la formule suivante :

12-1
Cy = ›, Air * Brj
k=0

Q 12. Écrire la fonction produit_matriciel (A,B), qui reçoit en paramètres deux matrices
symétriques A et 8, de même dimension. La fonction calcule et renvoie une nouvelle matrice symétrique
C, qui contient le produit matriciel de À et B. La fonction doit économiser le temps de calcul, en calculant
une seule fois les coefficients symétriques dans la matrice C.

TV. 13- Calcule de la puissance par ‘exponentiation rapide’

Lorsqu'il s'agit d’une matrice carrée, le calcul de la puissance devient crucial. L’exponentiation rapide
est un algorithme qui permet de minimiser le nombre de multiplications effectuées dans le calcul de la
puissance.

Pour calculer x”, le principe de l’exponentiation rapide est le suivant :
e Sin=1 alors x"=x

e 50 65) pair alors x"=(x")"?
Sinestimpair alors x"=x.(x%) 2

Q 13- Écrire la fonction puissance (R, n), reçoit en paramètres la matrice symétrique R représentant
un réseau routier, et un entier strictement positif n. En utilisant le principe de l’exponentiation rapide, la
fonction calcule et renvoie la matrice R".

Page 9 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 10 —
Épreuve d’Informatique — Session 2019 - Filière PSI
Partie V :

Base de données et langage SOL

Réseau routier pondéré :

On associe à chaque route du réseau routier une valeur appelée : poids. Le poids de chaque route est la
longueur de cette route, exprimée en km (kilomètre). Ainsi, le réseau routier est appelé : réseau routier
pondéré.

Exemple :

Figure 3 : Réseau routier pondéré par les longueurs des routes en km

Le coût d’un chemin :

Dans un réseau routier pondéré, le coût d’un chemin est égale à la somme des poids des routes qui
composent ce chemin.

Exemples :
Dans le réseau routier pondéré de la figure 3 :

e  Lecoût du chemin (1,0, 3, 6) est : 460 = 120+250+90
e  Lecoût du chemin (4,6,5,7,3) est : 780 = 120+200+200+260
e  Lecoût du chemin (0,1,2,3, 4,5, 6,7) est: 1040 = 120+100+140+150+150+200+180

Dans cette partie, on propose de manipuler le réseau routier pondéré par une base de données composée
de deux tables : la table : Villes et la table : Chemins.

Villes

code (entier)

Chemins

chemin (texte)
nom (texte) nb_routes (entier)
couleur (entier) cout (réel)
ville depart (entier)

ville_arrivee (entier)

Page 10 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 11 —
Épreuve d’Informatique — Session 2019 - Filière PSI

Structure de la table ‘Villes’ :

La table Villes contient les villes du réseau routier.

Le champ code contient les entiers : 0, 1, 2, 3, …, N-1, sachant que n est le nombre de villes
dans le réseau routier. Chaque entier représente une seule ville du réseau routier.

Le champ nom contient les noms des villes ;

Le champ couleur contient des entiers strictement positifs, qui représentent les couleurs des
villes.

Exemples d'enregistrements dans les tables ‘Villes’ :

code | nom
Agadir

couleur

Essaouira
Marrakech
Ouarzazate
Safi
Tanger

O|S|OUIN|F|O

Structure de la table ‘Chemins’ :

La table Chemins est composée de 5 champs :

Le champ chemin contient tous les chemins simples qui existent entres les villes du réseau
routier. Chaque chemin est représenté par une chaîne de caractères, qui contient les villes du
chemin, séparées par le caractère '-" (tiré de 6).

Exemple : La chaîne '1-0-3-61 représente le chemin (1,0, 3, 6)

Le champ nb_routes contient le nombre de routes dans chaque chemin ;

Le champ cout contient les coûts des chemins ;

Le champ ville_depart contient le code de la ville de départ de chaque chemin ;

Le champ ville_arrivee contient le code de la ville d'arrivée de chaque chemin.

Exemples d'enregistrements dans la table ‘Chemins’ :

chemin | nb_routes | cout ville_depart | ville_arrivee

WDJ|OJ|JS|OJO|N|FJOJH

Page 11 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏

— صفحة 12 —
Épreuve d’Informatique — Session 2019 - Filière PSI

V. 14- Déterminer les clés primaires et les clés étrangères dans les tables Villes et Chemins.

Justifier votre réponse.

V. 15- Écrire, en algèbre relationnelle, la requête qui donne le résultat suivant :

Les codes et noms des villes ayant la couleur 1 ou la couleur 2 dans le réseau routier.

Écrire, en langage SQL, les requêtes qui donne les résultats suivants :

V. 16- Le nombre de routes dans le réseau routier.

V. 17- Le nombre chromatique du réseau routier.

V. 18- Les noms des villes et le degré de chaque ville, ayant le degré compris strictement entre 4 et 9, triés
dans l’ordre décroissant des degrés.

V. 19- Modifier les coûts de tous les chemins qui passent par la route "0-1", en ajoutant la valeur 50 à
chacun de ces chemins.

V. 20- Le plus petit coût des chemins qui passent par toutes les villes du réseau routier.

Page 12 sur 12

نماذج المباريات من موقع وظيفة إنفو ‎wadifa-info.com‏