Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Épreuve d’Informatique – Session 2019 – Filière MP Page 1 sur 12 Les candidats

Épreuve d’Informatique – Session 2019 – Filière MP Page 1 sur 12 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. Il 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. ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈ Exercice : (4 points) Médian d’une liste de nombres Q 1- Écrire la fonction grands(L,x) qui reçoit en paramètres une liste de nombres L, et un élément x de L. La fonction renvoie le nombre d’éléments de L qui sont supérieurs strictement à x. Q 2- Déterminer la complexité de la fonction grands (L, x), et justifier votre réponse. Q 3- Écrire la fonction petits(L,x) qui reçoit en paramètres une liste de nombres L, 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 L, si les deux conditions suivantes sont vérifiées : • Le nombre d’éléments de L, qui sont supérieurs strictement à m, est inférieur ou égale à n/2 • Le nombre d’éléments de L, qui sont inférieurs strictement à m, est inférieur ou égale à n/2 Exemple : On considère la liste L = [ 25 , 12 , 6 , 17, 3 , 10 , 20 , 12 , 15 , 38 ], de taille n=10. L’élément 12 est un médian de L, car : • 3 éléments de L sont supérieurs strictement à 12, et 3 ≤ n/2 ; • 5 éléments de L sont inférieurs strictement à 12, et 5 ≤ n/2. 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. Q 5- Déterminer la complexité de la fonction median(L), et justifier votre réponse. 1 pt 0.5 pt 0.5 pt 1 pt 1 pt Épreuve d’Informatique – Session 2019 – Filière MP Page 2 sur 12 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. Exemples d’enregistrements dans la table ‘Personnes’ : code nom prenom dateNaiss 1 Boudara Mohamed 1996-10-15 2 Mernissi Salima 2000-03-29 3 Sabri Ahmed 2001-02-20 4 Oubaidi Mouniya 1990-05-25 5 Jamali Ahmed 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 471 Fans Discussion à propos de divers sujets 6 2016-09-14 96 Famille Les membres de la grande famille 25 2016-10-10 … … … … Épreuve d’Informatique – Session 2019 – Filière MP Page 3 sur 12 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 471 2018-01-30 4 253 2016-09-25 5 253 2018-01-22 7 253 2017-07-29 8 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’. Épreuve d’Informatique – Session 2019 – Filière MP Page 4 sur 12 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 : 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 0 ≤ i < n et 0 ≤ j < p, tels que : G[i,j]=1 , si la 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 : 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 Épreuve d’Informatique – Session 2019 – Filière MP Page 5 sur 12 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). 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 : G = array ([[1,1,1,1,0,0,1,1,1,1] , [1,1,1,0,0,1,1,0,1,1] , [1,1,0,0,1,1,0,0,1,1] , [1,1,1,0,0,0,0,1,1,1] , [1,0,1,1,1,0,1,1,1,1] , [1,0,0,1,1,1,0,1,1,0] , [1,1,0,1,1,0,1,0,0,0] , [1,0,1,0,0,1,1,0,0,1] , [1,0,0,0,1,1,1,0,1,1] , [1,1,1,0,0,1,1,1,1,1] ] , float) 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 C copie de la matrice G ; 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 C. On pose k le nombre d’échanges de lignes dans la matrice C ; 3. Calculer le déterminant D de uploads/S4/ mp-pdf 1 .pdf