Modèle de concours : CNC 2019 Informatique (MP) — Concours National Commun
En bref
Ce document est une ancienne épreuve écrite du concours de Concours d'accès aux écoles d'ingénieurs organisé par Concours National Commun (CNC) — CPGE (2019), publiée sur Wadifa Info en consultation et téléchargement PDF gratuits, avec une correction proposée.
- Organisme
- Concours National Commun (CNC) — CPGE
- Grade
- Concours d'accès aux écoles d'ingénieurs
- Spécialité
- Informatique
- Année
- 2019
- Pages
- 12
- Langue des questions
- français
- Correction
- correction proposée disponible sur cette page
📝 Texte des questions (extrait automatiquement des pages scannées)
Ce texte est extrait automatiquement des images de l'épreuve et peut contenir des erreurs de lecture — les images ci-dessus font foi.
— صفحة 1 — Épreuve d’Informatique — Session 2019 — Filière MP 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. |l 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 de deux parties tous 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. ENRRNNNENNEENNERNREANNEEERN EE م وال Exercice : (4 points) Médian d’une liste de nombres 1pt Q 1- Écrire la fonction grands (L,x) qui reçoit en paramètres une liste de nombres با et un élément x de L. La fonction renvoie le nombre d'éléments de L qui sont supérieurs strictement à x. 1 pt Q 2- Déterminer la complexité de la fonction grands (L, x), et justifier votre réponse. 05pt Q 3- Écrire la fonction petits(L,x) qui reçoit en paramètres une liste de nombres با et un élément x de L. La fonction renvoie le nombre d’éléments de L qui sont inférieurs strictement à x. L est une liste de taille n qui contient des nombres, et m un élément de L. L'élément m est un médian de ا si les deux conditions suivantes sont vérifiées : e Le nombre d'éléments de ا qui sont supérieurs strictement à m, est inférieur ou égale à n/2 e Le nombre d'éléments de ا qui sont inférieurs strictement à m, est inférieur ou égale à n/2 Exemple : On considère la liste ]جا 25, 12,6, 17,3,10,20,12,15,38], de taille n=10. L'élément 12 est un médian de ما car : e 3 éléments de ا sont supérieurs strictement à 12, et3‹n/2 ; e 5 éléments de ا sont inférieurs strictement à 12, et 5 ‹ 2. 1pt Q 4- Écrire la fonction median (L) qui reçoit en paramètre une liste de nombres L non vide, et qui renvoie un élément médian de la liste L. 05pt —Q 5- Déterminer la complexité de la fonction median(L), et justifier votre réponse. Page 1 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 2 — Épreuve d’Informatique — Session 2019 - Filière MP Partie I : Bases de données et langage SQL Dans les réseaux sociaux, on peut créer des groupes, et d'inviter des personnes à ces groupes. Dans le but de faire des statistiques sur les groupes et leurs membres, nous avons créé une base de données relationnelle composée de trois tables : Personnes, Membres et Groupes. A- Structure de la table ‘Personnes’ : La table ‘Personnes’ contient les personnes qui ont créé des groupes, et les personnes qui ont accepté l'invitation pour se joindre aux groupes, et devenir membres de ces groupes. Le champ code de type entier, contient un entier positif unique pour chaque personne ; Le champ nom de type texte, contient le nom de chaque personne ; Le champ prenom de type texte, contient le prénom de chaque personne ; Le champ dateNaiss de type date, contient la date de naissance de chaque personne. cers Exemples d’enregistrements dans la table ‘Personnes’ : prenom dateNaiss 1 | Boudara Mohamed 1996-10-15 2 | Mernissi Salima 2000-03-29 3 | Sabri Ahmed 2001-02-20 1990-05-25 1997-09-08 6 | Bekkali Hamza 1999-11-05 7 | Chafi Asmaa 2002-03-13 8 | Chahbouni | Soukaina 2000-01-20 B- Structure de la table ‘Groupes’ : La table ‘Groupes’ contient des informations relatives à chaque groupe. + Le champ id de type entier, contient les identifiants des groupes. L'identifiant de chaque groupe est unique ; Le champ nom de type texte, contient les noms des groupes ; Le champ description de type texte, contient un texte qui précise les objectifs de chaque groupe ; Le champ codeCr, de type date, contient les codes des personnes ayant créé les groupes ; Le champ dateCr, de type date, contient la date de création de chaque groupe. Exemples d’enregistrements dans la table “Groupes” : | id | nom description codeCr dateCr 253 | Amis Les amis les plus proches 2 | 2017-07-09 Discussion à propos de divers sujets | 6) 2016-09-14 |. 86 | Famille | Les membres de la grande famille 2016-10-10 Page 2 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 3 — Épreuve d’Informatique — Session 2019 — Filière MP C- Structure de la table ‘Membres’ : La table ‘Membres’ est composée de trois champs : + Le champ code de type entier, contient les codes des personnes qui ont accepté l'invitation pour devenir membres aux groupes ; + Le champ id de type entier, contient les identifiants des groupes ; + Le champ dateM de type date, contient les dates aux quelles chaque personne a rejoint un groupe. Exemples d’enregistrements dans la table ‘Membres’ : code id dateM 1 253 | 2017-09-18 3 2018-01-30 4 253 | 2016-09-25 253 | 2018-01-22 253 | 2017-07-29 471 | 2016-11-10 I. 1- Déterminer les clés primaires et les clés étrangères dans les tables de cette base de données. Justifier votre réponse. Écrire, en langage SQL, les requêtes qui donnent les résultats suivants : I. 2- Les personnes qui sont nées le mois 6, triées dans l’ordre croissant des âges (du moins âgée au plus âgée). I. 3- Les identifiants des groupes, les dates de création des groupes et les noms et prénoms des personnes ayant crée ces groupes. I. 4- Écrire la requête I. 3 en algèbre relationnelle. I. 5- Les noms et les descriptions des groupes qui contiennent au moins 1000 personnes, triés dans l’ordre décroissant des nombres de personnes. I. 6- Les codes, les noms et les prénoms de toutes les personnes (créateur et membres) qui appartiennent au groupe ayant le nom :'Sport'. I. 7- Supprimer les personnes qui n’appartiennent à aucun groupe. I. 8- Modifier dans la table 'Membres', pour que tous les membres du groupe ayant le nom ‘Sport’ deviennent membres du groupe ayant le nom ‘Voyage’. Page 3 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 4 — Épreuve d’Informatique — Session 2019 — Filière MP Partie II : Grille binaire Une grille binaire de n lignes et p colonnes, est une grille dans laquelle chaque case est de couleur blanche, ou bien de couleur noire. Exemple : 012 3 4 5 6 7 8 9 10 11 SON © ت٠ + DIN ا © Figure 1 : Exemple de grille binaire de 10 lignes et 12 colonnes Représentation de la grille binaire : Pour représenter une grille binaire de n lignes et p colonnes, on utilise une matrice G de n lignes et p colonnes. Chaque case de la grille G est représentée par un tuple (i, j) avec O‹i‹ net0‹j‹p, tels que : › G[i,j]=1, sila couleur de la case (i, j) est blanche ; › G[i,j]=0, si la couleur de la case (i, j) est noire. Exemple : La grille binaire de la figure 1 est représentée par la matrice G de 10 lignes et 12 colonnes, suivante : نم نم © نم نم كم كم نم js سم نا نت © رجور ps js js js jp انا انا انا ان نم نم نم نم © © نا © © ني © © نم © بم نانم © ني ات نا نم © © نم © نانم نانم لم نم لم نم نم رح نم نم نا اط نات © © ير در رةه هت © نا نام © D نا D نم نا © © بر ير ير © © © ني نم = نم = نا O © نم نا ير © نم نم Page 4 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 5 — Épreuve d’Informatique — Session 2019 — Filière MP II. 1- Calcul du déterminant d’une grille binaire carrée Une grille binaire carrée est une grille binaire dans laquelle le nombre de lignes et le nombre de colonnes sont égaux. Exemple : Grille binaire carrée d’ordre 10 (10 lignes et 10 colonnes). © خا تح با USA © ب- :© تك Dans cette section (II. 1), on suppose que le module numpy est importé : from numpy import * On suppose que la matrice carrée G, qui représente la grille binaire carrée, est créée par la méthode array( ( du module numpy. Exemple : La grille binaire carrée d'ordre 10 est représentée par la matrice carrée G suivante : J 1 درطا ل 100 7 1 11م م20 ,7 1ن لاما م 0و0 7 [- ,0,1 ما لاملا ا ام ام 1 float) , ] 1 ,1 ,1 ا لون 110 Dans le but de calculer le déterminant d’une matrice carrée G qui représente une grille binaire carrée, on propose d'utiliser la méthode du ‘pivot de Gauss’, dont le principe est le suivant : 1. Créer une matrice © copie de la matrice 6 ; 2. En utilisant la méthode du pivot de Gauss, transformer la matrice C en matrice triangulaire inférieure, ou bien en matrice triangulaire supérieure, en comptant le nombre d’échanges de lignes dans la matrice ©. On pose k le nombre d'échanges de lignes dans la matrice © ; 3. Calculer le déterminant D de la matrice triangulaire © ; 4. Le déterminant de la matrice M est égal à : D + (—1)®. Page 5 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 6 — Épreuve d’Informatique — Session 2019 — Filière MP Q 1. a- Écrire la fonction copie_matrice (G), qui reçoit en paramètre une matrice carrée G qui représente une grille binaire carrée, et qui renvoie une matrice C copie de la matrice G. Q 1. b- Écrire la fonction echange_lignes (C,i, j), qui reçoit en paramètres une matrice carrée © qui représente une grille binaire carrée. La fonction échange les lignes i et j dans la matrice C. Q 1. c- Écrire la fonction triangulaire (C), qui reçoit en paramètre une matrice carrée © qui représente une grille binaire carrée. En utilisant la méthode du Pivot de Gauss, la fonction transforme la matrice © en matrice triangulaire inférieure ou bien triangulaire supérieure, tout en comptant le nombre de fois qu’il y 2 eu échange de lignes dans la matrice ©. La fonction doit retourner le nombre d'échanges de lignes. Exemple : Après l’appel de la fonction triangulaire(C), on obtient la matrice triangulaire supérieure suivante : 08. -L 0. 0. 1. 8 0. 6 80. 8. 0 0. 686 0. 1.2 1. -1.2 8 û 0. #6 0. 0 0. 0. 0. 1. 80 6 8. 0. 0. 0 8e. )9.2 8 0. 8 2 La fonction triangulaire(C) renvoie le nombre d’échanges de colonnes dans C : 4 Q 1. d- Écrire la fonction deteminant (G), qui reçoit en paramètre une matrice G qui représente une grille binaire carrée. En utilisant la méthode du pivot de Gauss, la fonction renvoie la valeur du déterminant de G, Exemple : La fonction determinant (G) renvoie : -4 II. 2- Représentation de la grille binaire par une liste de listes Dans la suite de cette partie, pour représenter une grille binaire de n lignes et p colonnes, on utilise une liste G contenant n listes toutes de même longueur p. Chaque case de la grille G est représentée par un tuple (i, j) avec O‹i‹ net 0 ‹j‹p, tels que : › G[i][j]=1, sila couleur de la case (i , j) est blanche ; › G[i][j]=0, sila couleur de la case (i , j) est noire. Pour plus de clarté, tous les exemples qui suivront, seront appliqués sur la grille binaire de la figure 1. Page 6 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 7 — Épreuve d’Informatique — Session 2019 — Filière MP Exemple : La grille binaire de la figure 1 est représentée par la liste G suivante, composée de 10 listes, de taille 12 chacune : G[i] [5] est l'élément qui se trouve à la i“”* ligne et la j*""° colonne dans G. Exemples : G[0][3] est l'élément 1 e G[1][4] est l’élément 0. G[i] est la ligne d'indice i dans G. Exemples : e G[2]estla liste [1,1,0,0,1,1,0,0, 1,1, 1, 1], qui représente la ligne d'indice 2 dans G. e G[5] estlaliste [1,0,0,1,1,1,0,1, 1,0, 0,0], qui représente la ligne d'indice 5 dans G. À partir de la liste 6, de l'exemple ci-dessus, donner le résultat de chacune des expressions -2 و suivantes : IT. 3- Position valide d’une case Q 3- Écrire la fonction valide (i, j,G), qui reçoit en paramètres deux entiers i et j. La fonction renvoie True, si i et j sont positifs, et s'ils représentent, respectivement la ligne et la colonne d'une case qui existe dans la grille binaire G, sinon, la fonction renvoie False. Exemples : e La fonction valide (0, 3, G) renvoie : True e La fonction valide (7, 15, G) renvoie : False e La fonction valide (-2, -8, G) renvoie : False Page 7 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 8 — Épreuve d’Informatique — Session 2019 — Filière MP IL. 4- Couleur d’une case Q 4- Écrire la fonction couleur (t, G), qui reçoit en paramètres un tuple t qui représente une case dans la grille binaire G. La fonction renvoie 1 si la couleur de la case t est blanche, sinon, elle renvoie 0. Exemples : e La fonction couleur ( (0, 3), G) renvoie le nombre : 1 e La fonction couleur ( (0, 4), G) renvoie le nombre : 0 IT. 5- Cases voisines Dans une grille binaire, deux cases sont voisines, si elles ont la même couleur et si elles ont un seul côté en commun. Exemples : e Les cases a et b sont voisines ; e Les cases b et c sont voisines ; e Les cases b et d sont voisines ; e Les cases b et e ne sont pas voisines, (b et ع n'ont pas la même couleur) ; e Les cases a et c ne sont pas voisines, (a et c n’ont aucun côté en commun) ; e Les cases a et a ne sont pas voisines (a et a n'ont pas un seul côté en commun). Écrire la fonction list_voisines (t, G), qui reçoit en paramètres un tuple t représentant une -5 و case dans la grille binaire G. La fonction renvoie la liste des cases voisines à la case t, dans la grille G. Exemples : e La fonction list_voisines ( (5, 4), G) renvoie la liste : [ (4, 4), (6, 4), (5, 3), (5, 5) ] e La fonction list_voisines ( (2, 4), G) renvoie la liste : [ (2, 5) ] e La fonction list_voisines ( (5, 1), G) renvoie la liste : [ (4, 1), (5, 2) ] e La fonction list_voisines ( (7, 2), G) renvoie la liste : [ ] 11. 6- Chemin dans une grille On considère une liste L de tuples qui représentent des cases dans une grille binaire G. La liste L est un chemin dans la grille G, si la liste L satisfait les trois conditions suivantes : c1- LaÔliste ا contient au moins deux cases de la grille G ; c2- Toutes les cases de ا sont différentes deux à deux, (pas de doublon dans L) ; c3- Deux cases consécutives dans L sont voisines. Exemples : La liste L est un chemin dans la grille G. La liste T n'est pas un chemin dans la grille 6 Page 8 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 9 — Épreuve d’Informatique — Session 2019 — Filière MP Q 6- Écrire la fonction chemin (L, G), qui reçoit en paramètres une liste ا de tuples représentant des cases dans la grille binaire G. La fonction renvoie True si la liste L est un chemin dans G, sinon, la fonction renvoie False. II. 7- Compression d’un chemin dans une grille binaire La compression d'un chemin dans une grille binaire, consiste à remplacer, dans ce chemin, chaque suite d’au moins trois cases voisines qui se trouvent sur la même ligne ou bien sur la même colonne, par deux cases seulement : la première case et la dernière case. Exemples : e Cas d’une suite d'au moins 3 cases voisines, qui se trouvent sur la même ligne : وق 1,2,3,4,5,6,7 › La suite des cases voisines : (2, 1), (2, 2), (2, 3), …, (2, 8), sera remplacée par : (2, 1), (2, 8) | 8 ض 7 : 6 ض 5 ض 4 ض 3 : 2 , 1 | › La suite des cases voisines : (2, 8), (2, 7), (2, 6), …, (2, 1), sera remplacée par : (2, 8), (2, 1). e Cas d'une suite d'au moins 3 cases voisines, qui se trouvent sur la même colonne : 5 5 ير حل on 7 8 Page 9 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 10 — Épreuve d’Informatique — Session 2019 — Filière MP Q 7- Écrire la fonction compresse_chemin (L), qui reçoit en paramètre une liste L qui contient un chemin dans une grille binaire. La fonction renvoie la liste qui contient le chemin compressé de L. Exemples : La fonction compresse_chemin(L) renvoie la liste : [ (0, 0), (9, 0), (9, 2) ] La fonction compresse_chemin(L) renvoie la liste : [ (0, 0), (1, 0), (1, 1), (2, 1), (2, 0), (3, 0) ] II. 8- Appartenance d’une case à un chemin compressé Q 8- Écrire la fonction appartient (t, L), qui reçoit en paramètres une liste L contenant un chemin compressé dans une grille binaire, et un tuple t représentant une case. La fonction renvoie True si le chemin compressé L passe par la case t, sinon, la fonction renvoie False. Exemples : On considère le chemin compressé, de l'exemple précédent : L = [ (0, 0) , (9, 0) , (9, 2) ] e Les cases (0, 0), (1, 0), (2, 0), (8, 0), (9, 1) appartiennent au chemin L ; e La case (0, 2) n'appartient pas au chemin L. 11. 9- Longueur d’un chemin compressé Dans une grille binaire, la longueur d’un chemin compressé, est égale au nombre total des cases par les quelles passe ce chemin. Exemples : e La longueur du chemin compressé [ (0, 0), (9, 0), (9, 2) ] est : 12 ; Q 9- Écrire la fonction, de complexité linéaire, longueur_chemin (L), qui reçoit en paramètre une liste L qui contient un chemin compressé. La fonction renvoie la longueur du chemin L. 11. 10- Chemin entre deux cases On suppose que a et b sont deux tuples qui représentent deux cases distinctes, de même couleur, dans une grille binaire G. Un chemin entre les cases a et b, s'il existe, est un chemin compressé, tel que le tuple a est son premier élément, et le tuple b est son dernier élément. NB : On peut trouver plusieurs chemins entre les cases a et b. Exemple : Les chemins suivants sont des chemins compressés entre les cases a = (0, 3) et b = (4, 4) : 4 4,2 3,0 4,2 حي بح ب Page 10 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 11 — Épreuve d’Informatique — Session 2019 — Filière MP Q 10. a- Écrire la fonction chemins (G,a,b, chemin), reçoit en paramètres deux tuples a et b distincts qui représentent deux cases de même couleur, dans la grille binaire G. Le paramètre chemin est une liste initialisée par la liste vide. Cette fonction renvoie une nouvelle liste contenant tous les chemins entre la case a et la case b dans la grille G. Exemples : e La fonction chemins (G, (0, 3), (4, 4), [ ]) renvoie la liste des chemins suivants : e La fonction chemins (G, (6, 0), (7, 2), [ ]) renvoie la liste : [ ] Q 10. b- Écrire la fonction list_chemins (G, a, b), reçoit en paramètres deux tuples a et b qui représentent deux cases quelconques dans la grille binaire G. Cette fonction renvoie la liste de tous les chemins compressés entre la case a et la case b, dans la grille G. Exemples : e La fonction list_chemins (G, (0, 3), (4, 4), [ ]) renvoie la liste des chemins compressés suivants : e La fonction list_chemins (G, (6, 0), (8, 1), [ ]) renvoie la liste : [ ] 11. 11- Tri d’une liste de chemins Q 11- Écrire la fonction tri_chemins (R), qui reçoit en paramètre une liste R contenant tous les chemins compressés entre deux cases dans une grille binaire. La fonction trie les chemins compressés de R dans l’ordre croissant des longueurs des chemins. La longueur d'un chemin telle qu'elle est définie dans la question II. 9 NB : Ne pas utiliser la méthode sort( ), ni la fonction sorted( ). Exemple : On considère la liste R suivante, qui contient 3 chemins compressés dans la grille binaire G. Après l’appel de la fonction tri_chemins (R), on obtient la liste triée suivante : Page 11 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com — صفحة 12 — Épreuve d’Informatique — Session 2019 — Filière MP IT. 12- Plus courts chemins entre deux cases a et b sont deux tuples qui représentent deux cases dans une grille binaire G. Le plus court chemin entre a et b est le chemin compressé entre a et b ayant la plus petite longueur. NB : On peut trouver plusieurs plus courts chemins entre les cases a et b. Q 12- Écrire la fonction plus_court_chemins (G, a, b), qui renvoie la liste de tous les plus courts chemins compressés entre deux cases a et b. Exemples : e La fonction plus_court_chemins ((0, 3), (4, 4), G) renvoie la liste des deux chemins suivants : e La fonction plus_court _chemins ((6, 0), (7, 2), G) renvoie la liste : [ [ IT. 13- Zone d’une case dans une grille binaire On considère un tuple t qui représente une case dans une grille binaire G. La zone de la case t est l'ensemble qui contient la case t, et toutes les cases de la grille binaire G, qu’on peut joindre par un chemin à partir de la case t. Exemples : e La zone de la case (8, 2) est l’ensemble composé des cases suivantes : e La zone de la case (9, 6) est l’ensemble composé des cases suivantes : e La zone de la case (7, 2) est l’ensemble composé d’une seule cases : (7, 2) Q 13-Écrire la fonction compte_zones (G), qui reçoit en paramètre une grille binaire 6, et qui renvoie le nombre de zones dans la grille binaire G. Exemple : La fonction compte_zone (G) renvoie le nombre : 10 Page 12 sur 12 نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
✅ Correction proposée
Il s'agit d'une correction proposée, rédigée par l'équipe wadifa-info pour vous aider à comprendre la méthode — ce n'est pas un corrigé officiel de l'administration organisatrice.
Ce sujet est l'épreuve d'Informatique du Concours National Commun (CNC) 2019, filière MP, qui ouvre l'accès aux écoles d'ingénieurs marocaines depuis les classes préparatoires (CPGE). La durée et le coefficient ne figurent pas sur les pages scannées. Le sujet compte 12 pages et se compose de trois blocs indépendants, tous en Python ou en SQL : un exercice sur le médian d'une liste (4 points), une Partie I de bases de données (SQL et algèbre relationnelle) sur des groupes de réseau social et une Partie II, un problème sur une grille binaire (déterminant par le pivot de Gauss avec numpy, voisinage, chemins, compression, parcours en profondeur, tri, comptage de zones). Type : problème. Voici une correction méthodologique proposée.
💡 Avant de commencer : les trois blocs sont indépendants et chaque question de la Partie II réutilise les fonctions précédentes (valide, list_voisines, compresse_chemin, longueur_chemin). Écrivez-les courtes et justes dès le départ : vous les appellerez ensuite sans les réécrire. Une question non traitée peut être admise pour la suite. Faites vite l'exercice et le SQL (des points presque garantis), puis gardez du temps pour la récursivité de II.10 et le parcours de II.13. Nous avons vérifié tous les exemples chiffrés ci-dessous en exécutant le code sur la grille de la figure 1.
Exercice : médian d'une liste de nombres (4 pts)
Q1 : grands(L, x)
def grands(L, x):
c = 0
for e in L:
if e > x:
c += 1
return c
Q2 : complexité de grands
La boucle parcourt les n éléments une seule fois et fait à chaque tour une comparaison, plus éventuellement une addition, en temps constant. Complexité : O(n), linéaire, dans tous les cas (meilleur comme pire), avec n = len(L).
Q3 : petits(L, x)
def petits(L, x):
c = 0
for e in L:
if e < x:
c += 1
return c
Remarque sur l'exemple de l'énoncé : dans L = [25, 12, 6, 17, 3, 10, 20, 12, 15, 38], 5 éléments sont strictement supérieurs à 12 (25, 17, 20, 15, 38) et 3 sont strictement inférieurs (6, 3, 10). L'énoncé inverse les deux nombres, mais la conclusion reste vraie : 5 ≤ 5 et 3 ≤ 5, donc 12 est bien un médian. Signalez ce point sur votre copie, comme le demandent les consignes.
Q4 : median(L)
def median(L):
n = len(L)
for m in L:
if grands(L, m) <= n/2 and petits(L, m) <= n/2:
return m
La fonction renvoie toujours une valeur. En effet, si l'on trie L, l'élément d'indice ⌊n/2⌋ a au plus ⌊n/2⌋ éléments strictement plus petits et au plus n − 1 − ⌊n/2⌋ ≤ n/2 éléments strictement plus grands. Un médian existe donc toujours et la boucle finit par le trouver.
Q5 : complexité de median
Chaque tour de boucle appelle grands et petits, soit O(n). Au pire, on fait n tours (le médian est en fin de liste) : O(n2). Au mieux, le premier élément est un médian : O(n). Pour aller plus loin : trier puis prendre L[n//2] donne O(n log n).
Partie I : bases de données et SQL
Remarque sur l'énoncé : le champ codeCr est dit « de type date ». C'est une coquille : il contient des codes de personnes, il est donc entier. Il faut le signaler sur la copie.
I.1 : clés primaires et clés étrangères
- Personnes : clé primaire code, car c'est un entier unique pour chaque personne.
- Groupes : clé primaire id, car l'identifiant de chaque groupe est unique. Clé étrangère codeCr, qui référence Personnes(code) : le créateur est une personne de la table Personnes.
- Membres : clé primaire composée (code, id). Une personne peut appartenir à plusieurs groupes et un groupe a plusieurs membres, donc ni code ni id seul n'est unique (l'exemple contient 253 plusieurs fois). En revanche, une personne ne rejoint un groupe donné qu'une seule fois. Clés étrangères : code, qui référence Personnes(code), et id, qui référence Groupes(id). Membres est la table d'association de la relation plusieurs-à-plusieurs.
I.2 : personnes nées au mois 6, de la moins âgée à la plus âgée
SELECT * FROM Personnes
WHERE strftime('%m', dateNaiss) = '06'
ORDER BY dateNaiss DESC;
La personne la moins âgée a la date de naissance la plus récente, d'où le tri DESC sur la date. On peut aussi écrire MONTH(dateNaiss) = 6 en MySQL, ou dateNaiss LIKE '%-06-%' si les dates sont au format texte AAAA-MM-JJ.
I.3 : groupes, date de création, nom et prénom du créateur
SELECT G.id, G.dateCr, P.nom, P.prenom
FROM Groupes G JOIN Personnes P ON G.codeCr = P.code;
I.4 : la requête I.3 en algèbre relationnelle
πGroupes.id, Groupes.dateCr, Personnes.nom, Personnes.prenom ( Groupes ⋈Groupes.codeCr = Personnes.code Personnes )
On préfixe les attributs parce que « nom » existe dans les deux tables. On peut aussi écrire une sélection sur le produit cartésien : π…(σcodeCr = code(Groupes × Personnes)).
I.5 : groupes d'au moins 1000 personnes, par nombre décroissant
SELECT G.nom, G.description
FROM Groupes G JOIN Membres M ON G.id = M.id
GROUP BY G.id, G.nom, G.description
HAVING COUNT(*) >= 1000
ORDER BY COUNT(*) DESC;
La condition porte sur un agrégat : elle va donc dans HAVING, pas dans WHERE. Ici on compte les membres (table Membres). Si l'on veut compter aussi le créateur, qui n'est pas forcément dans Membres, on remplace COUNT(*) par COUNT(*) + 1. Écrivez sur la copie l'hypothèse que vous retenez.
I.6 : toutes les personnes (créateur et membres) du groupe « Sport »
SELECT P.code, P.nom, P.prenom
FROM Personnes P JOIN Membres M ON P.code = M.code
JOIN Groupes G ON G.id = M.id
WHERE G.nom = 'Sport'
UNION
SELECT P.code, P.nom, P.prenom
FROM Personnes P JOIN Groupes G ON P.code = G.codeCr
WHERE G.nom = 'Sport';
UNION élimine les doublons, par exemple si le créateur est aussi inscrit dans Membres.
I.7 : supprimer les personnes qui n'appartiennent à aucun groupe
DELETE FROM Personnes
WHERE code NOT IN (SELECT code FROM Membres)
AND code NOT IN (SELECT codeCr FROM Groupes);
Un créateur appartient à son groupe (I.6 le compte parmi les personnes du groupe). Le supprimer violerait de plus la clé étrangère codeCr. On ne supprime donc que les personnes qui ne sont ni membre ni créateur.
I.8 : les membres de « Sport » deviennent membres de « Voyage »
UPDATE Membres
SET id = (SELECT id FROM Groupes WHERE nom = 'Voyage')
WHERE id = (SELECT id FROM Groupes WHERE nom = 'Sport');
Cette requête suppose que les noms de groupes sont uniques (chaque sous-requête renvoie une seule valeur). Point fin : si une personne est déjà membre de « Voyage », la mise à jour crée un doublon (code, id) et viole la clé primaire. Il faut d'abord exécuter :
DELETE FROM Membres WHERE id = (SELECT id FROM Groupes WHERE nom = 'Sport')
AND code IN (SELECT code FROM Membres WHERE id = (SELECT id FROM Groupes WHERE nom = 'Voyage'));
Partie II : grille binaire
II.1 Q1.a : copie_matrice(G)
def copie_matrice(G):
n = len(G)
C = zeros((n, n))
for i in range(n):
for j in range(n):
C[i, j] = G[i, j]
return C
En une ligne : return G.copy(). Ne pas écrire C = G : ce n'est qu'un second nom pour le même tableau, et le pivot de Gauss modifierait G.
II.1 Q1.b : echange_lignes(C, i, j)
def echange_lignes(C, i, j):
for k in range(len(C)):
C[i, k], C[j, k] = C[j, k], C[i, k]
Piège numpy : C[i], C[j] = C[j], C[i] est faux. C[j] et C[i] sont des vues : après la première affectation, la ligne i contient déjà l'ancienne ligne j, et les deux lignes finissent égales. On peut aussi écrire C[[i, j]] = C[[j, i]].
II.1 Q1.c : triangulaire(C)
def triangulaire(C):
n = len(C)
k = 0
for j in range(n):
p = j
while p < n and abs(C[p, j]) < 1e-12:
p += 1
if p < n:
if p != j:
echange_lignes(C, p, j)
k += 1
for i in range(j + 1, n):
C[i] = C[i] - (C[i, j] / C[j, j]) * C[j]
return k
Pour chaque colonne j, on cherche un pivot non nul à partir de la ligne j (on compare à 1e-12 plutôt qu'à 0 à cause des flottants), on le remonte par un échange compté dans k, puis on annule les coefficients sous le pivot. Si toute la colonne est nulle sous la diagonale, on passe à la colonne suivante : le déterminant sera nul. L'opération Li ← Li − c·Lj ne change pas le déterminant, alors que chaque échange le multiplie par −1. Complexité : O(n3). Sur la matrice d'exemple, cette version fait bien 4 échanges. La forme triangulaire obtenue peut différer de celle affichée dans l'énoncé selon le choix des pivots (elle n'est pas unique), mais le déterminant est le même. L'énoncé écrit « échanges de colonnes » : il faut lire « de lignes ».
II.1 Q1.d : determinant(G)
def determinant(G):
C = copie_matrice(G)
k = triangulaire(C)
D = 1
for i in range(len(C)):
D = D * C[i, i]
return D * (-1) ** k
Le déterminant d'une matrice triangulaire est le produit de ses coefficients diagonaux. Vérification sur l'exemple de l'énoncé : les pivots sont 1, −1, −1, −1, −1, 1, 2, 1, −1, 2. Leur produit vaut (−1)5 × 4 = −4, et avec k = 4 on obtient D × (−1)4 = −4, conforme à l'énoncé (valeur confirmée par numpy.linalg.det).
II.2 Q2 : expressions sur la liste G (figure 1)
- G[4][2] → 1 (ligne 4 : [1,0,1,1,1,0,1,1,1,1,1,1], indice 2).
- len(G[3]) → 12 (nombre de colonnes).
- G[5] → [1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0].
- len(G) → 10 (nombre de lignes).
II.3 Q3 : valide(i, j, G)
def valide(i, j, G):
return 0 <= i < len(G) and 0 <= j < len(G[0])
Résultats : valide(0, 3, G) → True, valide(7, 15, G) → False (15 ≥ 12), valide(−2, −8, G) → False. Attention : sans le test i ≥ 0, G[−2] serait accepté par Python (indice négatif).
II.4 Q4 : couleur(t, G)
def couleur(t, G):
i, j = t
return G[i][j]
La case vaut 1 si elle est blanche et 0 si elle est noire, donc on renvoie directement sa valeur. couleur((0, 3), G) → 1 et couleur((0, 4), G) → 0.
II.5 Q5 : list_voisines(t, G)
def list_voisines(t, G):
i, j = t
R = []
for (x, y) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
if valide(x, y, G) and G[x][y] == G[i][j]:
R.append((x, y))
return R
On teste les quatre cases qui ont un côté commun avec t (haut, bas, gauche, droite), sans les diagonales, en gardant celles qui existent et ont la même couleur. Dans cet ordre, on retrouve exactement les exemples : (5, 4) → [(4, 4), (6, 4), (5, 3), (5, 5)] ; (2, 4) → [(2, 5)] ; (5, 1) → [(4, 1), (5, 2)] ; (7, 2) → [ ].
II.6 Q6 : chemin(L, G)
def chemin(L, G):
if len(L) < 2:
return False
for k in range(len(L)):
if not valide(L[k][0], L[k][1], G) or L[k] in L[k+1:]:
return False
for k in range(len(L) - 1):
if L[k+1] not in list_voisines(L[k], G):
return False
return True
Le code teste les trois conditions dans l'ordre : c1 (au moins deux cases), c2 (pas de doublon) et c3 (cases consécutives voisines). Pour T = [(0,0), (1,1), …], le résultat est False dès le premier couple ((0,0) et (1,1) sont en diagonale), et (1,1) apparaît deux fois. Le test de doublons coûte O(len(L)2) ; len(set(L)) == len(L) le fait en O(len(L)).
II.7 Q7 : compresse_chemin(L)
def compresse_chemin(L):
R = [L[0]]
for k in range(1, len(L) - 1):
d1 = (L[k][0] - L[k-1][0], L[k][1] - L[k-1][1])
d2 = (L[k+1][0] - L[k][0], L[k+1][1] - L[k][1])
if d1 != d2:
R.append(L[k])
R.append(L[-1])
return R
Idée : une case intérieure est supprimée exactement quand elle est au milieu d'un alignement, c'est-à-dire quand le déplacement pour y arriver est égal au déplacement pour en repartir. On ne garde que la première case, la dernière et les « coins » (changements de direction). Une suite d'au moins trois cases alignées se réduit bien à ses deux extrémités, et un coin peut terminer une suite et commencer la suivante. Exemple 1 : [(0,0), …, (9,0), (9,1), (9,2)] → [(0,0), (9,0), (9,2)]. Exemple 2 : la direction change à chaque pas, donc le chemin reste inchangé. Complexité : O(len(L)).
II.8 Q8 : appartient(t, L)
def appartient(t, L):
if t in L:
return True
for k in range(len(L) - 1):
(a, b), (c, d) = L[k], L[k+1]
if a == c == t[0] and min(b, d) <= t[1] <= max(b, d):
return True
if b == d == t[1] and min(a, c) <= t[0] <= max(a, c):
return True
return False
Deux cases consécutives d'un chemin compressé délimitent un segment horizontal (même ligne) ou vertical (même colonne). La case t est sur le chemin si elle se trouve sur l'un de ces segments. Avec L = [(0,0), (9,0), (9,2)] : (0,0), (1,0), (2,0), (8,0) et (9,1) → True ; (0,2) → False.
II.9 Q9 : longueur_chemin(L), en complexité linéaire
def longueur_chemin(L):
s = 1
for k in range(len(L) - 1):
s += abs(L[k+1][0] - L[k][0]) + abs(L[k+1][1] - L[k][1])
return s
Chaque segment ajoute autant de cases nouvelles que sa longueur |Δi| + |Δj| (l'un des deux termes est nul). On ajoute 1 pour la case de départ. Les cases d'un chemin étant toutes distinctes, rien n'est compté deux fois. Vérification : [(0,0), (9,0), (9,2)] → 1 + 9 + 2 = 12 ; [(0,0), (1,0), (1,1), (2,1), (2,0), (3,0), (3,1)] → 1 + 6 = 7. Une seule boucle sur L : O(len(L)).
II.10 Q10.a : chemins(G, a, b, chemin), tous les chemins de a à b
def chemins(G, a, b, chemin):
chemin = chemin + [a]
if a == b:
return [chemin]
R = []
for v in list_voisines(a, G):
if v not in chemin:
R = R + chemins(G, v, b, chemin)
return R
On fait un retour sur trace (parcours en profondeur) : on ajoute la case courante au chemin partiel et on relance la fonction sur chaque voisine pas encore visitée. Quand on atteint b, on enregistre le chemin complet. L'écriture chemin + [a] crée une nouvelle liste : les branches ne se partagent pas le chemin partiel, donc aucun « dépilement » n'est nécessaire. Comme dans les exemples de l'énoncé, cette fonction renvoie des chemins non compressés. chemins(G, (6,0), (7,2), [ ]) → [ ], car (7,2) est une case blanche isolée (ses quatre voisines sont noires). Le nombre de chemins, et donc le coût, peut être exponentiel ; sur la figure 1, on obtient 42 chemins entre (0,3) et (4,4).
II.10 Q10.b : list_chemins(G, a, b)
def list_chemins(G, a, b):
if a == b or couleur(a, G) != couleur(b, G):
return []
return [compresse_chemin(c) for c in chemins(G, a, b, [])]
Ici a et b sont quelconques. On traite d'abord les cas sans chemin (cases identiques ou de couleurs différentes), puis on compresse chaque chemin trouvé. list_chemins(G, (6,0), (8,1)) → [ ] : (6,0) est blanche et (8,1) noire. Les exemples de l'énoncé passent un quatrième argument [ ] par erreur : la signature n'en a que trois.
II.11 Q11 : tri_chemins(R), sans sort ni sorted
def tri_chemins(R):
for i in range(1, len(R)):
x = R[i]
lx = longueur_chemin(x)
j = i - 1
while j >= 0 and longueur_chemin(R[j]) > lx:
R[j+1] = R[j]
j -= 1
R[j+1] = x
return R
C'est un tri par insertion, en place et stable, avec la longueur de II.9 comme clé. Sur l'exemple, les longueurs valent 12, 10 et 10. On obtient [chemin de longueur 10 passant par (0,2), chemin de longueur 10 passant par (0,1), chemin de longueur 12], exactement l'ordre attendu, car la stabilité conserve l'ordre des deux chemins de longueur 10. Complexité : O(r2·m) pour r chemins de taille au plus m. Un tri fusion donnerait O(r log r · m).
II.12 Q12 : plus_court_chemins(G, a, b)
def plus_court_chemins(G, a, b):
R = list_chemins(G, a, b)
if R == []:
return []
m = longueur_chemin(R[0])
for c in R:
m = min(m, longueur_chemin(c))
return [c for c in R if longueur_chemin(c) == m]
On calcule la longueur minimale, puis on garde tous les chemins qui l'atteignent (il peut y en avoir plusieurs). Sur la figure 1, entre (0,3) et (4,4), la longueur minimale est 10. Elle est atteinte par exactement deux chemins : [(0,3), (0,2), (1,2), (1,1), (3,1), (3,2), (4,2), (4,4)] et [(0,3), (0,1), (3,1), (3,2), (4,2), (4,4)], conformément à l'énoncé. Entre (6,0) et (7,2) → [ ]. Les exemples de l'énoncé passent les arguments dans l'ordre (a, b, G) : respectez la signature (G, a, b). Un parcours en largeur (BFS) trouverait la distance minimale bien plus vite, mais l'énoncé demande tous les plus courts chemins compressés, et réutiliser list_chemins est la réponse attendue.
II.13 Q13 : compte_zones(G)
def compte_zones(G):
n, p = len(G), len(G[0])
vu = [[False] * p for _ in range(n)]
nb = 0
for i in range(n):
for j in range(p):
if not vu[i][j]:
nb += 1
vu[i][j] = True
pile = [(i, j)]
while pile != []:
t = pile.pop()
for (x, y) in list_voisines(t, G):
if not vu[x][y]:
vu[x][y] = True
pile.append((x, y))
return nb
Une zone est une composante connexe du graphe dont les sommets sont les cases et les arêtes relient les cases voisines. On balaie la grille : chaque case non encore visitée commence une nouvelle zone (nb += 1), puis un parcours avec une pile marque toute sa zone. On marque une case au moment où on l'empile, pour ne jamais l'empiler deux fois. Chaque case est empilée une seule fois et a au plus 4 voisines : complexité O(n·p). Sur la figure 1, la fonction renvoie 10, comme l'énoncé. La zone de (8,2) est bien {(8,2), (7,3), (8,3), (7,1), (8,1), (9,3), (7,4), (9,4)} et celle de (7,2) se réduit à {(7,2)}. N'utilisez pas chemins() ici : son coût est exponentiel.
💡 À retenir et à réviser pour l'informatique du CNC (MP) : (1) les complexités de base (boucle simple O(n), boucles imbriquées O(n2), pivot de Gauss O(n3)) avec une justification d'une ligne ; (2) numpy : copie avec .copy() plutôt qu'une simple affectation, échange de lignes (piège des vues), pivot de Gauss avec comptage des échanges et test à epsilon sur les flottants ; (3) SQL : clés primaires composées et clés étrangères, jointures, GROUP BY avec HAVING, UNION, sous-requêtes dans DELETE et UPDATE, traduction en algèbre relationnelle (π, σ, ⋈) ; (4) grilles et graphes : voisinage à 4 cases avec test de validité, retour sur trace récursif (chemin + [a]), parcours en profondeur ou en largeur avec un tableau « vu », composantes connexes ; (5) tris écrits à la main (insertion, fusion) et stabilité. Réflexe payant : vérifiez chaque fonction sur les exemples de l'énoncé, et signalez les coquilles (ici les comptes 3/5 inversés de l'exercice, codeCr « de type date », « échanges de colonnes », l'ordre des arguments en II.10.b et II.12).
Questions fréquentes sur ce sujet
Ce sujet est-il téléchargeable gratuitement ?
Le corrigé est-il inclus ?
Quel organisme et quel grade concerne ce sujet ?
De quelle session s'agit-il et dans quelle langue ?
Où trouver d'autres sujets du même concours ?
Vous préparez ce concours ?
Modèles similaires
Source : concours d'accès aux écoles et instituts supérieurs — document archivé tel que reçu ; l'avis officiel du concours fait foi.
}