Annales CNC Informatique [PDF]

Zitiervorschau

Annales CNC – Informatique

OMAR ZEKRAOUI

Concours National Commun

Annales des épreuves écrites d’informatique

Filières : MP – PSI - TSI Années : 2017 – 2018 - 2019

Document réalisé par : OMAR ZEKRAOUI Professeur d’informatique CPGE IBN TIMIYA - Marrakech

Page 1 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Sommaire CNC 2019 - Filière MP ................................................................................................. 3 CNC 2019 - Filière PSI ............................................................................................... 15 CNC 2019 - Filière TSI ............................................................................................... 27 CNC 2018 - Filière MP ............................................................................................... 37 CNC 2018 - Filière PSI ............................................................................................... 49 CNC 2018 - Filière TSI ............................................................................................... 60 CNC 2017 - Filières MP-PSI-TSI ............................................................................... 69 Correction CNC 2019 – MP ........................................................................................ 81 Correction CNC 2019 – PSI ........................................................................................ 87 Correction CNC 2019 – TSI........................................................................................ 91 Correction CNC 2018 – MP ........................................................................................ 94 Correction CNC 2018 – PSI ........................................................................................ 98 Correction CNC 2018 – TSI...................................................................................... 102 Correction CNC 2017 – MP - PSI - TSI ................................................................... 105

Page 2 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2019 - Filière MP Sommaire

Exercice : (4 points)

Médian d’une liste de nombres 1 pt

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.

1 pt

Q 2- Déterminer la complexité de la fonction grands (L, x), et justifier votre réponse.

0.5 pt

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 : • •

1 pt

3 éléments de L sont inférieurs strictement à 12, et 3 ≤ n/2 ; 5 éléments de L sont supé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.

0.5 pt

Q 5- Déterminer la complexité de la fonction median(L), et justifier votre réponse.

Page 3 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie I : Bases de données et langage SQL Dans les réseaux sociaux, on peut créer des groupes, et 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 1 2 3 4 5 6 7 8 …

prenom

dateNaiss

Boudara Mernissi Sabri Oubaidi Jamali Bekkali Chafi

Mohamed Salima Ahmed Mouniya Ahmed Hamza Asmaa

1996-10-15 2000-03-29 2001-02-20 1990-05-25 1997-09-08 1999-11-05 2002-03-13

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 entier, 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 253 471 96

Amis Fans Famille …

description Les amis les plus proches Discussion à propos de divers sujets Les membres de la grande famille …

codeCr

dateCr

2 6 25 …

2017-07-09 2016-09-14 2016-10-10 …

Page 4 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 3 4 5 7 8 …

253 471 253 253 253 471 …

2017-09-18 2018-01-30 2017-09-25 2018-01-22 2017-07-29 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 de 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 de nom ‘XXXX’ deviennent membres du groupe de nom ‘YYYY’.

Page 5 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 :

0

1

2

3

4

5

6

7

8

9

10

11

0 1 2 3 4 5 6 7 8 9 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 :

Page 6 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 la matrice triangulaire C ; 4. Le déterminant de la matrice G est égal à : D * (-1)

k

Page 7 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 C 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 C qui représente une grille binaire carrée. En utilisant la méthode du Pivot de Gauss, la fonction transforme la matrice C en matrice triangulaire inférieure ou bien triangulaire supérieure, tout en comptant le nombre de fois qu’il y a eu échange de lignes dans la matrice C. 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 :

La fonction triangulaire(C) renvoie le nombre d’échanges de lignes 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 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.

Pour plus de clarté, tous les exemples qui suivront, seront appliqués sur la grille binaire de la figure 1. Page 8 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 =[ [1,1,1,1,0,0,1,1,1,1,1,1] [1,1,0,0,1,1,0,0,1,1,1,1] [1,0,1,1,1,0,1,1,1,1,1,1] [1,1,0,1,1,0,1,0,0,0,1,0] [1,0,0,0,1,1,1,0,1,1,1,1]

,[1,1,1,0,0,1,1,0,1,1,1,1] ,[1,1,1,0,0,0,0,1,1,1,1,1] ,[1,0,0,1,1,1,0,1,1,0,0,0] ,[1,0,1,0,0,1,1,0,0,1,1,1] ,[1,1,1,0,0,1,1,1,1,1,1,1]

, , , ,

]

G[i][j] est l’élément qui se trouve à la ième ligne et la jème colonne dans G. Exemples : • G[0][3] est l’élément 1 • G[1][4] est l’élément 0.

G[i] est la ligne d’indice i dans G. Exemples : • G[2] est la liste [1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1, 1, 1, 1], qui représente la ligne d’indice 2 dans G. • G[5] est la liste [1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1, 0, 0, 0], qui représente la ligne d’indice 5 dans G. Q 2- À partir de la liste G, de l’exemple ci-dessus, donner le résultat de chacune des expressions suivantes : G[4][2] , len(G[5]) , G[3] , len(G)

II. 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 :

• • •

La fonction valide (0, 3, G) renvoie : True La fonction valide (7, 15, G) renvoie : False La fonction valide (-2, -8, G) renvoie : False Page 9 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

II. 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 :

• •

La fonction couleur ( (0, 3), G) renvoie le nombre : 1 La fonction couleur ( (0, 4), G) renvoie le nombre : 0

II. 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 : • • • • • •

Les cases a et b sont voisines ; Les cases b et c sont voisines ; Les cases b et d sont voisines ; Les cases b et e ne sont pas voisines, (b et e n’ont pas la même couleur) ; Les cases a et c ne sont pas voisines, (a et c n’ont aucun côté en commun) ; Les cases a et a ne sont pas voisines (a et a n’ont pas un seul côté en commun).

Q 5- Écrire la fonction list_voisines(t,G), qui reçoit en paramètres un tuple t représentant une case dans la grille binaire G. La fonction renvoie la liste des cases voisines à la case t, dans la grille G. Exemples : • • • •

La fonction list_voisines ( (5, 4), G) renvoie la liste : [ (4, 4), (6, 4), (5, 3), (5, 5) ] La fonction list_voisines ( (2, 4), G) renvoie la liste : [ (2, 5) ] La fonction list_voisines ( (5, 1), G) renvoie la liste : [ (4, 1), (5, 2) ] La fonction list_voisines ( (7, 2), G) renvoie la liste : [ ]

II. 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 L contient au moins deux cases de la grille G ; c2 - Toutes les cases de L sont différentes deux à deux, (pas de doublon dans L) ; c3 - Deux cases consécutives dans L sont voisines.

Exemples : •

L = [ (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (4, 2), (4, 3), (4, 4) ] La liste L est un chemin dans la grille G.

•

T = [ (0, 0), (1, 1), (2, 1), (2, 2), (1, 2), (1, 1) ]. La liste T n’est pas un chemin dans la grille G.

Page 10 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q 6- Écrire la fonction chemin(L,G), qui reçoit en paramètres une liste L 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 : •

Cas d’une suite d’au moins 3 cases voisines, qui se trouvent sur la même ligne :

La suite des cases voisines : (2, 1), (2, 2), (2, 3), …, (2, 8), sera remplacée par : (2, 1), (2, 8)

La suite des cases voisines : (2, 8), (2, 7), (2, 6), …, (2, 1), sera remplacée par : (2, 8), (2, 1).

•

Cas d’une suite d’au moins 3 cases voisines, qui se trouvent sur la même colonne :

La suite des cases : (3, 5), (4, 5), (5, 5), …, (8, 5), sera remplacée par : (3, 5), (8, 5) ;

La suite des cases : (8, 5), (7, 5), (6, 5), …, (3, 5), sera remplacée par : (8, 5), (3, 5). Page 11 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 : •

L = [ (0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0), (9, 1), (9, 2) ] La fonction compresse_chemin(L) renvoie la liste : [ (0, 0), (9, 0), (9, 2) ]

•

L = [ (0, 0), (1, 0), (1, 1), (2, 1), (2, 0), (3, 0) ] 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) ] • •

Les cases (0, 0), (1, 0), (2, 0), (8, 0), (9, 1) appartiennent au chemin L ; La case (0, 2) n’appartient pas au chemin L.

II. 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 : • •

La longueur du chemin compressé [ (0, 0), (9, 0), (9, 2) ] est : 12 ; La longueur du chemin compressé [ (0, 0), (1, 0), (1, 1), (2, 1), (2, 0), (3, 0), (3, 1) ] est : 7.

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.

II. 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) : • • • • •

[ (0, 3), (0, 2), (1, 2), (1, 1), (0, 1), (0, 0), (3, 0), (3, 2), (4, 2), (4, 3), (6, 3), (6, 4), (4, 4) ] [ (0, 3), (0, 2), (1, 2), (1, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] [ (0, 3), (0, 2), (1, 2), (1, 1), (2, 1), (2, 0), (3, 0), (3, 2), (4, 2), (4, 4) ] [ (0, 3), (0, 0), (1, 0), (1, 1), (3, 1), (3, 2), (4, 2), (4, 3), (6, 3), (6, 4), (4, 4) ] … Page 12 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 : •

La fonction chemins (G, (0, 3), (4, 4), [ ]) renvoie la liste des chemins suivants :

[ [ (0, 3), (0, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (4, 3), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (0, 1), (0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (4, 2), (4, 3), (5, 3), (5, 4), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (4, 3), (5, 3), (5, 4), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (0, 1),

(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (4, 2), (4, 3), (4, 4) ] , … ] •

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 : •

La fonction list_chemins (G, (0, 3), (4, 4)) renvoie la liste des chemins suivants :

[ [ (0, 3), (0, 2), (1, 2), (1, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (0, 1), (0, 0), (2, 0), (2, 1), (3, 1), (3, 2), (4, 2), (4, 3), (5, 3), (5, 4), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (4, 3), (5, 3), (5, 4), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (0, 1), (0, 0), (3, 0), (3, 2),

(4, 2), (4, 4) ] , … ] •

La fonction list_chemins (G, (6, 0), (8, 1)) renvoie la liste : [ ]

II. 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. R = [ [ (0, 3), (0, 0), (3, 0), (3, 2), (4, 2), (4, 4) ] , [ (0, 3), (0, 2), (1, 2), (1, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] , [ (0, 3), (0, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] ] Après l’appel de la fonction tri_chemins (R), on obtient la liste triée suivante :

[ [ (0, 3), (0, 2), (1, 2), (1, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] , [ (0, 3), (0, 1), (3, 1), (3, 2), (4, 2), (4, 4) ] , [ (0, 3), (0, 0), (3, 0), (3, 2), (4, 2), (4, 4) ] ]

Page 13 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

II. 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 : •

La fonction plus_court_chemins (G, (0, 3), (4, 4)) renvoie la liste des deux chemins suivants : [ [(0, 3), (0, 2), (1, 2), (1, 1), (3, 1), (3, 2), (4, 2), (4, 4)] , [(0, 3), (0, 1), (3, 1), (3, 2), (4, 2), (4, 4)] ]

•

La fonction plus_court _chemins (G, (6, 0), (7, 2)) renvoie la liste : [ ]

II. 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 : •

La zone de la case (8, 2) est l’ensemble composé des cases suivantes : (8, 2) , (7, 3) , (8, 3) , (7, 1) , (8, 1) , (9, 3) , (7, 4) , (9, 4)

•

La zone de la case (9, 6) est l’ensemble composé des cases suivantes : (9, 6), (8, 6), (9, 5), (9, 7), (7, 6), (8, 5), (9, 8), (6, 6), (7, 5), (8, 4), (8, 8), (9, 9), (8, 9), (9, 10), (7, 9), (8, 10), (9, 11), (7, 10), (8, 11), (6, 10), (7, 11)

•

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 G, et qui renvoie le nombre de zones dans la grille binaire G. Exemple : La fonction compte_zone (G) renvoie le nombre : 10

≈≈≈≈≈≈≈≈

FIN DE l’ÉPREUVE ≈ ≈ ≈ ≈ ≈ ≈ ≈ ≈

Page 14 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2019 - Filière PSI Sommaire

Exercice : (4 points)

Somme et factoriel 1 pt

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 : • •

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

0.5 pt

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 : L = [ 5, 3, 0, 6, 1 ] La fonction som_fact (L) renvoie la valeur de la somme : 5! + 3! + 0! + 6! + 1!

1 pt

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

≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈

Page 15 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 16 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 0 ≤ i < n et 0 ≤ j < n, on a :

R[i,j]= R[j,i]=1, s’il existe une route qui relie entre la ville i et la ville j ; R[i,j]= R[j,i]=0, sinon.

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.

I. 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 17 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 =

[

[0,1,1,1,0,0,0,0],[1,0,1,0,1,0,0,0],[1,1,0,1,1,0,0,0], [1,0,1,0,1,0,1,1],[0,1,1,1,0,1,1,0],[0,0,0,0,1,0,1,1], [0,0,0,1,1,1,0,1],[0,0,0,1,0,1,1,0]

] R[i][j] est l’élément de R, à la ième ligne et la jème 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 [ 0 , 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 : R[4][2]

, R[1]

,

len(R[2])

,

len(R)

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 : • •

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

Q 2. b- Écrire la fonction list_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 : • • •

La fonction degre (3, R) renvoie le nombre : 5 La fonction degre (0, R) renvoie le nombre : 3 La fonction degre (2, R) renvoie le nombre : 4

(La ville 3 possède 5 villes voisines) (La ville 0 possède 3 villes voisines) (La ville 2 possède 4 villes voisines) Page 18 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

I. 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 R 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 : D = [ (0 , 3) , (1 , 3) , (2 , 4) , (3 , 5) , (4 , 5) , ( 5, 3) , (6 , 4) , (7 , 3) ]

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 : D = [ (0 , 3) , (1 , 3) , (2 , 4) , (3 , 5) , (4 , 5) , ( 5, 3) , (6 , 4) , (7 , 3) ] Après l’appel de la fonction tri_degres (D), on obtient la liste suivante : [ (3 , 5) , (4 , 5) , (2 , 4) , (6 , 4) , (0 , 3) , (5 , 3) , (1 , 3) , (7 , 3) ]

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 : [3,4,2,6,0,5,1,7]

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 : 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 C 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 19 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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

II. 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 L 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 : • • • •

La fonction couleurs_voisines (4, [ 0, 0, 0, 1, 0, 0, 0, 0 ], R) renvoie la liste : [0, 0, 1, 0, 0] La fonction couleurs_voisines (2, [ 0, 0, 0, 1, 2, 0, 0, 0 ], R) renvoie la liste: [0, 0, 1, 2] La fonction couleurs_voisines (6, [ 0, 0, 3, 1, 2, 0, 0, 0 ], R) renvoie la liste: [1, 2, 0, 0] La fonction couleurs_voisines (0, [ 0, 0, 3, 1, 2, 0, 3, 0 ], R) renvoie la liste: [0, 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 : • • •

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

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

Page 20 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie III : Chemins dans un réseau routier III. 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 : c1 : Le tuple T contient au moins deux villes du réseau routier ; c2 : Deux villes consécutives dans T sont voisines.

Exemples : • • •

Le tuple ( 2, 0, 1, 4, 3 ) est un chemin entre la ville 2 et la ville 3, composé de 4 routes ; Le tuple ( 7, 6, 4, 5, 6, 3, 4 ) est un chemin entre la ville 7 et la ville 4, composé de 6 routes ; Le tuple ( 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.

III. 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 : • •

Le chemin ( 2, 0, 1, 4, 3 ) est un chemin simple entre la ville 2 et la ville 3 ; 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 simple, sinon, la fonction renvoie False.

III. 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 :

[(1,0,2,3,4,5),(1,0,2,3,4,6,5),(1,0,2,3,4,6,7,5),(1,0,3,4,6,7,5), (1,0,3,6,4,5),(1,0,3,6,5),(1,0,3,6,7,5),(1,2,0,3,6,5),(1,2,0,3,6,7,5), (1,2,0,3,7,5),(1,2,0,3,7,6,4,5),(1,2,3,7,6,5),(1,4,2,0,3,7,5),(1,4,2,0, 3,7,6,5),(1,4,2,3,6,5),(1,4,2,3,6,7,5),(1,4,2,3,7,5),(1,4,2,3,7,6,5),( 1,4,3,6,5),(1,4,3,6,7,5),(1,4,3,7,5),(1,4,3,7,6,5),(1,4,5),(1,4,6,3,7, … ,(1,4,6,7,5)] 5),(1,4,6,5), Page 21 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 pc_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 : • •

La fonction pc_chemins (0, 7, R) renvoie la liste [ (0 , 3 , 7) ] ; La fonction pc_chemins (7, 1, R) renvoie la liste : [ (7 , 3 , 0 , 1) , (7 , 3 , 2 , 1) , (7 , 3 , 4 , 1) , (7 , 5 , 4 , 1) , (7 , 6 , 4 , 1) ].

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 :

R = array([ [0,1,1,1,0,0,0,0],[1,0,1,0,1,0,0,0],[1,1,0,1,1,0,0,0], [1,0,1,0,1,0,1,1],[0,1,1,1,0,1,1,0],[0,0,0,0,1,0,1,1], [0,0,0,1,1,1,0,1],[0,0,0,1,0,1,1,0]

])

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 :

(1,4,5,7,6,3) , (1,4,6,5,4,3) , (1,2,3,4,2,3) , (1,0,2,0,2,3), …

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

M = Rp (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 Calculer la matrice

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 22 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemples :

M = R2

M = R3

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

2

Il y a 0 chemins qui passent exactement par deux routes (dans la matrice M = R ) ; 3 Il y a 5 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 A 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 :

=

∗

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

IV. 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 n, le principe de l’exponentiation rapide est le suivant :

xn = x n 2 n/2 Si n est pair alors x = (x ) n 2 (n-1)/2 Si n est impair alors x = x . (x ) Si n = 1

alors

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 n

fonction calcule et renvoie la matrice R . Page 23 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie V : Base de données et langage SQL 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 : •

Le coût du chemin (1,0,3,6) est : 460 = 120+250+90

•

Le coût du chemin (4,6,5,7,3) est : 780 = 120+200+200+260

•

Le coû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

Chemins

code

(entier)

chemin

(texte)

nom

(texte)

nb_routes

(entier)

couleur

(entier)

cout

(réel)

ville_depart

(entier)

ville_arrivee

(entier)

Page 24 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 0 1 2 3 4 20 …

nom Agadir Essaouira Marrakech Ouarzazate Safi Tanger …

couleur 2 1 3 1 2 7 …

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-6' 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 0-1 1-0 2-4-1 1-4-2 1-0-3-6 4-6-5-7-3 0-1-2-3-4-5-6-7 1-4-5-7-6-3 5-7-6-4-1-0-2-3 …

nb_routes 1 1 2 2 3 4 7 5 7

cout 120 120 200 200 460 780 1040 720 950

…

…

ville_depart 0 1 2 1 1 4 0 1 5

ville_arrivee 1 0 1 2 6 3 7 3 3

… Page 25 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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.

≈≈≈≈≈≈

FIN DE L’ÉPREUVE

≈≈≈≈≈≈

Page 26 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2019 - Filière TSI Sommaire

Exercice : (4 points)

Somme et puissance 1 pt

Q1- Écrire la fonction somme (L) qui reçoit en paramètre une liste L de nombres entiers, et qui retourne la somme des éléments de L. Exemple : La fonction somme ([ 7, 0 , -1, 5 , -3 ]) renvoie la valeur 8 = 7 + 0 + (-1) + 5 + (-3)

0.5 pt

1 pt

Q2- Déterminer la complexité de la fonction somme (L), et justifier votre réponse.

Q3- Écrire la fonction list_puissances (L, p) qui reçoit en paramètres une liste L de nombres entiers, et un entier p strictement positif. La fonction renvoie une nouvelle liste qui contient les éléments de L élevés chacun à la puissance p. Exemple : La fonction list_puissances ([ 7, 0 , -1, 5 , -3 ] , 2) renvoie la liste [ 49 , 0 , 1 , 25 , 9 ]

1 pt

Q4- Écrire la fonction som_puiss (L, p) qui reçoit en paramètres une liste L de nombres entiers, et un entier p strictement positif. La fonction renvoie la somme des éléments de L élevés chacun à la puissance p. Exemple : La fonction som_puiss ([ 7, 0 , -1, 5 , -3 ], 2) renvoie le nombre 84 = 7² + 0² + (-1)² + 5² + (-3)²

0.5 pt

Q5- Déterminer la complexité de la fonction som_puiss (L, p), et justifier votre réponse.

Page 27 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie I :

Base de données et Langage SQL On considère la base de données relationnelle composée de deux tables : la table Pays et la table Villes.

Pays

Villes

code

(texte)

cod_ville

(texte)

nom_pays

(texte)

nom_ville

(texte)

superficie

(réel)

cod_pays

(texte)

continent

(texte)

Structure de la table ‘Pays’ : La table ‘Pays’ contient des informations sur les pays, elle est composée de 4 champs : Le champ code contient un code unique pour chaque pays ; Le champ nom_pays contient le nom de chaque pays ; Le champ superficie contient la superficie de chaque pays, exprimée en Km² ; Le champ continent contient le continent de chaque pays.

Exemples d’enregistrements dans la table ‘Pays’ : code nom_pays MAR DEU ITA ARG RUS …

Maroc Allemagne Italie Argentine Russie …

superficie continent 710 850 357 386 301 338 2 780 000 1 710 000

Afrique Europe Europe Amérique Asie

…

…

Structure de la table ‘Villes’ : La table ‘Villes’ contient des informations sur les villes des pays, elle est composée de 3 champs : Le champ cod_ville contient un code unique pour chaque ville ; Le champ nom_ville contient les noms des villes ; Le champ cod_pays contient le code du pays de chaque ville.

Page 28 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemples d’enregistrements dans la table ‘Villes’ : cod_ville nom_ville CIA CMN SVO RAK TXL …

cod_pays

Rome Casablanca Moscou Marrakech Berlin …

ITA MAR RUS MAR DEU …

I. 1- Déterminer les clés primaires et les clés étrangères dans les tables Pays et Villes. Justifier votre réponse.

I. 2- Écrire, en algèbre relationnelle, la requête qui donne le résultat suivant : Les noms et les superficies des pays du continent ‘Europe’.

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

I. 3- Les noms des villes, sans répétition, dans les quelles le caractère 'm' se trouve à la 2éme et à la dernière position. Exemple : Amsterdam.

I. 4- Les codes et les noms des villes du pays ‘Espagne’, triés dans l’ordre alphabétique des noms des villes.

I. 5- Les noms des pays, et le nombre de villes dans chaque pays, ayant le nombre de villes compris strictement entre 100 et 1000, triés dans l’ordre décroissant des nombres de villes.

I. 6- Dans certains pays, on peut trouver une ville ayant le même nom que celui de son pays. Donner les noms de ces pays. I. 7- Supprimer toutes les villes du pays ‘Belgique’.

≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈

Page 29 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie II : 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 tel réseau, on pourra s’intéresser, par exemple, à 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 ? …

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 :

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

Annales CNC – Informatique

OMAR ZEKRAOUI

Pour plus de clarté, tous les exemples de cette partie seront appliqués sur le réseau routier de la figure 2.

Représentation du réseau routier par une matrice 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 0 ≤ i < n et 0 ≤ j < n, on a :

R[i,j]= R[j,i]=1, s’il existe une route qui relie entre la ville i et la ville j ; R[i,j]= R[j,i]=0, sinon.

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

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

II. 1- Représentation de la matrice du réseau routier par une liste de listes Pour représenter la matrice symétrique R d’ordre n, on utilise une liste composée de n listes toutes de même longueur n. 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 =

[

[0,1,1,1,0,0,0,0], [1,0,1,0,1,0,0,0], [1,1,0,1,1,0,0,0], [1,0,1,0,1,0,1,1], [0,1,1,1,0,1,1,0], [0,0,0,0,1,0,1,1], [0,0,0,1,1,1,0,1], [0,0,0,1,0,1,1,0]

] Page 31 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

R[i][j] est l’élément de R, à la ième ligne et la jème 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 : [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 ], qui représente la ligne d’indice 0 dans R. Q 1- À partir de la matrice R, donner les résultats des expressions suivantes : R[4][2] , R[1] , len(R[2]) , len(R)

II. 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 une ville i 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 : • •

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

Q 2. b- Écrire la fonction list_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 : [ 0 , 2 , 4 , 6 , 7 ]

II. 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 : • • •

La fonction degre (3, R) renvoie le nombre : 5 La fonction degre (0, R) renvoie le nombre : 3 La fonction degre (2, R) renvoie le nombre : 4

(La ville 3 possède 5 villes voisines) (La ville 0 possède 3 villes voisines) (La ville 2 possède 4 villes voisines)

II. 4- Liste des degrés des villes Q 4- Écrire la fonction list_degres(R), qui reçoit en paramètres la matrice symétrique R qui représente un réseau routier. La fonction renvoie une liste D contenant des tuples. Chaque tuple est composé de deux éléments : une ville du réseau routier, et le degré de cette ville. Page 32 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemple : La fonction list_degres (R) renvoie la liste D suivante : D = [ (0, 3), (1, 3), (2, 4), (3, 5), (4, 5), (5, 3), (6, 4), (7, 3) ]

II. 5- Tri des villes Q 5- É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 : D = [ (0 , 3) , (1 , 3) , (2 , 4) , (3 , 5) , (4 , 5) , (5 , 3) , (6 , 4) , (7 , 3) ] Après l’appel de la fonction tri_degres (D), on obtient la liste suivante : [ (3 , 5) , (4 , 5) , (2 , 4) , (6 , 4) , (0 , 3) , (5 , 3) , (1 , 3) , (7 , 3) ]

II. 6- 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 : c1 : Le tuple T contient au moins deux villes du réseau routier ; c2 : Deux villes consécutives dans T sont voisines.

Exemples : • • •

Le tuple ( 2, 0, 1, 4, 3 ) est un chemin entre la ville 2 et la ville 3, composé de 4 routes ; Le tuple ( 7, 6, 4, 5, 6, 3, 4 ) est un chemin entre la ville 7 et la ville 4, composé de 6 routes ; Le tuple ( 3, 1, 4, 6 ) n’est pas un chemin.

Q 6- Écrire la fonction chemin_valide(T,R), qui reçoit en paramètre 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.

II. 7- 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 : • •

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

Q 7- É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 simple, sinon, la fonction renvoie False.

II. 8- Plus court chemin entre deux villes

Page 33 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 :

[(1,0,2,3,4,5),(1,0,2,3,4,6,5),(1,0,2,3,4,6,7,5),(1,0,3,4,6,7,5), (1,0,3,6,4,5),(1,0,3,6,5),(1,0,3,6,7,5),(1,2,0,3,6,5),(1,2,0,3,6,7,5), (1,2,0,3,7,5),(1,2,0,3,7,6,4,5),(1,2,3,7,6,5),(1,4,2,0,3,7,5),(1,4,2,0, 3,7,6,5),(1,4,2,3,6,5),(1,4,2,3,6,7,5),(1,4,2,3,7,5),(1,4,2,3,7,6,5),( 1,4,3,6,5),(1,4,3,6,7,5),(1,4,3,7,5),(1,4,3,7,6,5),(1,4,5),(1,4,6,3,7, 5),(1,4,6,5),

…

,(1,4,6,7,5)

]

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 8- Écrire la fonction pc_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 : •

La fonction pc_chemins (2, 6, R) renvoie la liste : [ ( 2 , 3 , 6 ) , ( 2 , 4 , 6 ) ]

•

La fonction pc_chemins (7, 1, R) renvoie la liste : [ (7 , 3 , 0 , 1) , (7 , 3 , 2 , 1) , (7 , 3 , 4 , 1) , (7 , 5 , 4 , 1) , (7 , 6 , 4 , 1) ]

•

La fonction pc_chemins (1, 4, R) renvoie la liste : [ ( 1 , 4 ) ]

II- 9. 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 :

R = array([ [0,1,1,1,0,0,0,0], [1,0,1,0,1,0,0,0], [1,1,0,1,1,0,0,0], [1,0,1,0,1,0,1,1], [0,1,1,1,0,1,1,0], [0,0,0,0,1,0,1,1], [0,0,0,1,1,1,0,1], [0,0,0,1,0,1,1,0]

])

Dans cette partie, on propose de résoudre le problème suivant : Page 34 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

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 ?

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 :

• • • • •

(1,4,5,7,6,3) (1,4,6,5,4,3) (1,2,3,4,2,3) (1,0,2,0,2,3) …

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

M = Rp (matrice symétrique R élevée à la puissance p) Chaque élément M[i][j] représente le nombre de chemins, qui partent de la ville i à la ville j, en Calculer la matrice

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.

Exemples :

M = R2

M = R3

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

2

Il y a 0 chemins qui passent exactement par deux routes (dans la matrice M = R ) ; 3 Il y a 5 chemins qui passent exactement par trois routes (dans la matrice M = R ).

Rappel : Le module numpy contient la méthode dot( ) qui calcule le produit matriciel.

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 d’une matrice carrée. n

Pour calculer x , le principe de l’exponentiation rapide est le suivant : Page 35 sur 109

Annales CNC – Informatique •

Si n = 1

alors

•

Si n est pair

alors

•

Si n est impair

alors

OMAR ZEKRAOUI

xn = x x n = (x2) n/2 x n = x . (x2) (n-1)/2

Q 9. a- Déterminer la complexité de l’algorithme de l’exponentiation rapide. Justifier votre réponse. Q 9. b- Écrire la fonction puissance(R,n), reçoit en paramètres la matrice symétrique R, qui représente un réseau routier, et un entier n strictement positif. La fonction calcule et renvoie la matrice

Rn (R puissance n), en utilisant le principe de l’exponentiation rapide.

≈≈≈≈≈≈

FIN DE L’ÉPREUVE

≈≈≈≈≈≈

Page 36 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2018 - Filière MP Sommaire

Partie I : Calcul numérique Résolution numérique d’équation différentielle Les méthodes d'Adams-Bashforth et d’Adams-Moulton

Dans cette partie, on suppose que les modules suivants sont importés : from numpy import * from matplotlib.pyplot import *

Les équations différentielles (ED) apparaissent très souvent dans la modélisation de la physique et des sciences de l'ingénieur. Trouver la solution d'une ED ou d'un système d'ED est ainsi un problème courant, souvent difficile ou impossible à résoudre de façon analytique. Il est alors nécessaire de recourir à des méthodes numériques pour les résoudre.

Le problème de Cauchy consiste à trouver une fonction y(t) définie sur l'intervalle [a, b] telle que : =

,

; =

∀ ∈[

, ]!

Pour obtenir une approximation numérique de la solution y(t) sur l'intervalle [a, b], nous allons estimer la valeur de cette fonction en un nombre fini de points ti, pour i = 0, 1, … , n, constituants les nœuds du maillage. La solution numérique obtenue aux points ti est notée yi = y(ti). L'écart entre deux abscisses, noté h, est appelé : le pas de discrétisation.

Page 37 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Les principales méthodes de résolution numérique des ED sont séparées en deux grandes catégories : les méthodes à un pas : Le calcul de la valeur yn+1 au nœud tn+1 fait intervenir la valeur yn obtenue à l'abscisse précédente. Les principales méthodes sont celles de : Euler, Runge-Kutta, CrankNicholson … les méthodes à multiples pas: Le calcul de la valeur yn+1 au nœud tn+1 fait intervenir plusieurs valeurs yn , yn-1 , yn-2 , … obtenues aux abscisses précédentes. Les principales méthodes sont celles de : Nyström, Adams-Bashforth, Adams-Moulton, Gear …

Les méthodes d'Adams-Bashforth et Adams-Moulton : Ce sont des méthodes basées sur des techniques d'intégration numérique, qui utilisent les polynômes interpolateurs de Lagrange. La formulation générale de ces méthodes est : "

=

%

+$∗

∗

&'

,

Dans la suite de cette partie, nous nous intéressons aux méthodes d'Adams-Bashforth et Adams-Moulton d’ordre 2.

Le schéma d'Adams-Bashforth à deux pas, explicite, d'ordre 2 :

y0 donné ; y1 calculé par la méthode Euler simple ; "

=

+

$ )∗ (

,

−

,

Le schéma d'Adams-Moulton à un pas, implicite, d'ordre 2 :

y0 donné ; "

=

+

$ (

,

−

"

,

"

En pratique, les schémas d’Adams-Moulton ne sont pas utilisés comme tels, car ils sont implicites. On utilise plutôt conjointement un schéma d’Adams-Moulton et un schéma d’Adams-Bashforth de même ordre, pour construire un schéma prédicteur-correcteur : Dans le schéma d’Adams-Moulton, on utilise la valeur de yn+1 prédite (calculée) par le schéma d’Adams-Bashforth. Le schéma prédicteur-correcteur d’ordre 2, d'Adams-Moulton et d'Adams-Bashford est :

y0 donné ; y1 calculé par la méthode d’Euler ; "

=

avec ∶

+ =

$ (

+

,

$ )∗ (

−

"

,

−

, , Page 38 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 1 : Écrire une fonction AMB2 (f, a, b, y0, h), qui reçoit en paramètres : f est la fonction qui représente une équation différentielle du premier ordre ; a et b sont les deux bornes de l’intervalle d’intégration ; y0 est la valeur initiale à l’instant a (y(a) = y0) ; h est le pas de discrétisation. En utilisant le schéma prédicteur-correcteur d'ordre 2, d'Adams-Moulton et d'Adams-Bashford, la fonction renvoie T et Y, qui peuvent être des listes ou des tableaux : T contient la subdivision de l’intervalle [a, b], en valeurs régulièrement espacée, utilisant le pas de discrétisation h ; Y contient les approximations des valeurs y(ti), à chaque instant ti de T.

Application à un oscillateur harmonique Un objet, de masse m, est suspendu à un ressort fixé à un support. 0 représente le point d’équilibre, et y(t) représente la position de l’objet par rapport au point d’équilibre, avec la direction positive vers le haut.

Si l’objet suspendu est tiré verticalement vers le bas, celui-ci effectue un mouvement harmonique. La forme générale de l’équation différentielle modélisant ce mouvement harmonique est :

(E)

0∗ 1

+

∗ 2

+

∗

=3

Les paramètres de cette équation différentielle sont : b : constante de proportionnalité de la force d’amortissement ; F(t) : force extérieure appliquée sur l’objet ; k : constante de rappel du ressort ; m : masse de l’objet. Page 39 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Si b = 0 et F(t) = 0, alors le mouvement harmonique est dit : simple. Si b ≠ 0 et F(t) = 0, alors mouvement harmonique est dit: amorti. Si F(t) ≠ 0, alors mouvement harmonique est dit : forcé.

Q. 2 : On suppose que les valeurs des paramètres de l’équation différentielle (E), sont : b=1

;

k = 12.5

;

m = 1.5 et

F(t) = 0

Écrire l’équation différentielle (E) sous la forme z' = G(t, z), avec G(t, z) une fonction à deux variables (t, z) dont z est un tableau de longueur 2.

Q. 3 : On suppose avoir tiré l’objet suspendu verticalement vers le bas, avant de le relâcher sans vitesse initiale. En utilisant le schéma prédicteur-correcteur d'Adams-Moulton et d'Adams-Bashford d'ordre 2, écrire le code Python qui permet de tracer la courbe ci-dessous, représentant la position y(t) de l’objet m suspendu, toutes les 10-3 secondes.

Q. 4 : Écrire la fonction racines (P), qui reçoit en paramètre la liste (ou le tableau) P des positions y(t) de l’objet suspendu, à intervalles de temps de 10-3 secondes. La fonction renvoie affiche les valeurs des zéros de la fonction y(t) : les valeurs des t tels que y(t) = 0, ou y(t) ≈ 0 avec la précision 10-3. Exemple : La fonction affiche les valeurs suivantes : 0.589 , 1.684 , 2.78 , 3.875 , 4.971 , 6.067 , 7.162

******************************* Page 40 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie II : Bioinformatique : Recherche d’un motif La bioinformatique, c'est quoi? Au cours des trente dernières années, la récolte de données en biologie a connu un boom quantitatif grâce notamment au développement de nouveaux moyens techniques servant à comprendre l'ADN et d’autres composants d’organismes vivants. Pour analyser ces données, plus nombreuses et plus complexes aussi, les scientifiques se sont tournés vers les nouvelles technologies de l’information. L'immense capacité de stockage et d’analyse des données qu'offre l'informatique leur a permis de gagner en puissance pour leurs recherches. La bioinformatique sert donc à stocker, traiter et analyser de grandes quantités de données de biologie. Le but est de mieux comprendre et mieux connaître les phénomènes et processus biologiques. Dans le domaine de la bioinformatique, la recherche de sous-chaîne de caractères, appelée motif, dans un texte de taille importante, était un composant important de beaucoup d’algorithmes. Puisqu’on travaille sur des textes de tailles très importantes, on a toujours cette obsession de l’efficacité des algorithmes : moins on a à faire de comparaisons, plus rapide sera l’exécution des algorithmes. Le motif à rechercher, ainsi que le texte dans lequel on effectue la recherche, sont écrits dans un alphabet composé de quatre caractères : 'A' , 'C' , 'G' et 'T'. Ces caractères représentent les quatre bases de l’ADN : Adénine, Cytosine, Guanine et Thymine.

Codage des caractères de l’alphabet L’alphabet est composé de quatre caractères seulement : 'A', 'C', 'G' et 'T'. Dans le but d’économiser la mémoire, on peut utiliser un codage binaire réduit pour ces quatre caractères.

Q. 1 : Quel est le nombre minimum de bits nécessaires pour coder quatre éléments ?

Q. 2 : Donner un exemple de code binaire pour chaque caractère de cet alphabet.

Préfixe d’une chaîne de caractères Un préfixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères entre la première position de S et une certaine position dans S. Exemple : S = 'TATCTAGCTA' La chaîne 'TAT' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTAGCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'T' est un préfixes de 'TATCTAGCTA' ; La chaîne 'CTAGC' n’est pas un préfixe de S.

Q. 3 : Écrire une fonction prefixe (M, S), qui reçoit en paramètres deux chaînes de caractères M et S non vides, et qui retourne True si la chaîne M est un préfixe de S, sinon, elle retourne False. Page 41 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 4 : Quel est le nombre de comparaisons élémentaires effectuées par la fonction prefixe (M, S), dans le pire cas ? Déduire la complexité de la fonction prefixe (M, S) dans le pire cas.

Suffixe d’une chaîne de caractères Un suffixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères, en partant d’une certaine position p dans S, jusqu’à la dernière position de S. L’entier p est appelée : position du suffixe. Exemple : S = 'TATCTAGCTA' La chaîne 'CTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 3 ; La chaîne 'GCTA' est un suffixe de 'TATCTAGCTA', sa position est : 6 ; La chaîne 'TATCTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 0 ; La chaîne 'CTAGC' n’est pas un suffixe de S.

Q. 5 : Écrire une fonction liste_suffixes (S), qui reçoit en paramètre une chaîne de caractères S non vide, et qui renvoie une liste de tuples. Chaque tuple de cette liste est composé de deux éléments : un suffixe de S, et la position p de ce suffixe dans S (0 ≤ p < taille(S)). Les tuples de cette liste sont ordonnés dans l’ordre croissant des positions des suffixes. Exemple : S = 'TATCTAGCTA' La fonction liste_suffixes (S) renvoie la liste : [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)]

Tri de la liste des suffixes Q. 6 : Écrire une fonction tri_liste (L), qui reçoit en paramètre la liste L des suffixes d’une chaîne de caractères non vide, créée selon le principe décrit dans la question 5. La fonction tri_liste, trie les éléments de L dans l’ordre alphabétique des suffixes. (Voir exemple suivant) NB : On ne doit pas utiliser la fonction sorted(), ou la méthode sort(). Exemple : L = [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)] Après l’appel de la fonction tri_liste (L), on obtient la liste suivante : [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ]

Recherche dichotomique d’un motif : La liste des suffixes L contient les tuples composés des suffixes d’une chaîne de caractères S non vide, et de leurs positions dans S. Si la liste L est triée dans l’ordre alphabétique des suffixes, alors, la recherche d’un motif M dans S, peut être réalisée par une simple recherche dichotomique dans la liste L.

Page 42 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 7 : Écrire une fonction recherche_dichotomique (M, L), qui utilise le principe de la recherche dichotomique, pour rechercher le motif M dans la liste des suffixes L triée dans l’ordre alphabétique des suffixes : Si M est un préfixe d’un suffixe dans un tuple de L, alors la fonction retourne la position de ce suffixe. Si la fonction ne trouve pas le motif M recherché, alors la fonction retourne None. Exemple : La liste des suffixes de 'TATCTAGCTA', triée dans l’ordre alphabétique des suffixes est : L = [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ] recherche_dichotomique ('CTA', L) renvoie la position 3 ; 'CTA' est préfixe de 'CTAGCTA' recherche_dichotomique ('TA', L) renvoie la position 0 ; 'TA' est un préfixe de 'TATCTAGCTA' recherche_dichotomique ('CAGT', L) renvoie None. 'CAGT' n’est préfixe d’aucun suffixe Q. 8 : On pose m et k les tailles respectives de la chaîne M et la liste L. Déterminer, en fonction de m et k, la complexité de la fonction recherche_dichotomique (M, L). Justifier votre réponse.

L’arbre des suffixes d’une chaîne de caractères : L'arbre des suffixes, d’une chaîne de caractères S non vide, est un arbre n-aire qui permet de représenter tous les suffixes de S. Cet arbre possède les propriétés suivantes : La racine de l’arbre est marquée par le caractère '#' ; Chaque nœuds de l’arbre contient une sous-chaîne de S, non vide ; Les premiers caractères, des sous-chaînes fils d’un même nœud, sont différents ; Chaque feuille de l'arbre contient un entier positif qui correspond à la position d’un suffixe dans la chaîne S. Exemple : S = 'TATCTAGCTA' La liste des suffixes de S, triée dans l’ordre alphabétique des suffixes est :

L = [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ] L’arbre des suffixes est crée à partir de la liste des suffixes triée :

Page 43 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

La racine de l’arbre '#' se trouve au niveau 0 de l’arbre, ses fils se trouvent au niveau 1, … . En parcourant une branche de l’arbre depuis le niveau 1, et en effectuant la concaténation des sous-chaînes des nœuds, on obtient un suffixe de la chaîne S ; et dans la feuille, on trouve la position de ce suffixe dans S. Exemples : En parcourant les nœuds de la première branche à droite de l’arbre 'T' + 'CTAGCTA', on obtient le suffixe 'TCTAGCTA'. La feuille contient la position 2 de ce suffixe ; En parcourant les nœuds de la troisième branche à partir de la droite de l’arbre 'T' + 'A' + 'GCTA', on obtient le suffixe 'TAGCTA'. La feuille contient la position 4 de ce suffixe. Pour représenter l’arbre des suffixes, on utilise une liste composée de deux éléments : Le nœud, et une liste contenant tous les fils de ce nœud : Un nœud N est représenté par la liste : [ N , [ f1 , f2 , … , fn ] ] ; Chaque fils fk est représenté par la liste : [ fk , [ tous les fils de fk ] ] ; Une feuille F est représentée par la liste : [ F , [ ] ].

On suppose que la fonction arbre_suffixes (S), reçoit en paramètre une chaîne de caractères S non vide, et construit et renvoie l’arbre des suffixes de S, représenté par une liste, selon le principe décrit ci-dessus. Exemple : arbre_suffixes ('TATCTAGCTA') renvoie la liste R suivante : R = [ '#', [ [ 'A', [ [ 9, [ ] ], [ 'GCTA', [ [ 5,[ ] ] ] ], [ 'TCTAGCTA', [ [ 1, [ ] ] ] ] ] ], [ 'CTA',[ [ 7, [ ] ], [ 'GCTA', [ [ 3, [ ] ] ] ] ] ], [ 'GCTA', [ [ 6, [ ] ] ] ], [ 'T', [ [ 'A', [ [ 8, [ ] ], [ 'GCTA', [ [ 4, [ ] ] ] ], [ 'TCTAGCTA', [ [ 0, [ ] ] ] ] ] ], [ 'CTAGCTA', [ [ 2, [ ] ] ] ] ] ] ] ]

Q. 9 : Écrire une fonction feuilles (R), qui reçoit en paramètre une liste R représentant l’arbre des suffixes d’une chaîne de caractères non vide, et qui retourne la liste contenant toutes les feuilles de l’arbre R. Exemple : feuilles (R) revoie la liste [ 9 , 5 , 1 , 7 , 3 , 6 , 8 , 4 , 0 , 2 ] L’intérêt, de l’arbre des suffixes, c’est qu’il permet d’effectuer une recherche de toutes les occurrences d’un motif dans un temps qui dépend uniquement de la longueur du motif, et non de la chaîne dans laquelle on effectue la recherche. En effet, la recherche d’un motif se réalise par la lecture du motif recherché et par le parcours simultané de l’arbre des suffixes. Trois cas peuvent survenir : On se retrouve sur un nœud, et le motif est un préfixe de ce nœud : Dans ce cas, les feuilles du sous arbre de ce nœud, correspondent aux positions de toutes les occurrences du motif dans la chaîne. On se retrouve sur un nœud, et ce nœud est un préfixe du motif : Dans ce cas, on continue la recherche parmi les fils de ce nœud. On ne peut plus descendre dans l’arbre : Dans ce cas, il n’y a pas d’occurrence du motif recherché dans la chaîne.

Q. 10 : Écrire une fonction recherche_arbre (M, R), qui reçoit en paramètres un motif M non vide, et une liste R représentant l’arbre des suffixes d’une chaîne de caractères non vide. La fonction retourne une liste contenant les positions de toutes les occurrences de M dans cette chaîne de caractères. Page 44 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemples : R est la liste qui représente l’arbre des suffixes de la chaîne S = 'TATCTAGCTA'. recherche_arbre ('TA', R) renvoie la liste : [ 8 , 4 , 0 ] recherche_arbre ('TCTAG', R) renvoie la liste : [ 2 ] recherche_arbre ('CTA', R) revoie la liste : [ 7 , 3 ] recherche_arbre ('TACG', R) renvoie la liste : [ ]

Base de données d’un arbre des suffixes Dans cette partie, on utilise une base de données pour stocker un arbre des suffixes d’une chaîne de caractères S non vide. Pour identifier les nœuds de l’arbre, on donne un code unique pour chaque nœud : Chaque nœud interne est identifié par un entier positif unique supérieur à la taille de S ; Les feuilles de l’arbre sont les différentes positions p dans la chaîne S (0 ≤ p < taille de S). Chaque feuille de l’arbre est identifiée par l’entier p qu’elle contient. Exemple : Codes des nœuds internes de l’arbre des suffixes de la chaîne S = 'TATCTAGCTA'

Dans cet exemple, la taille de S est 10. Chaque feuille est identifiée par un entier compris entre 0 et 9, et qui correspond à un indice dans S. Chaque nœud interne est identifié par un entier positif unique ≥ 10. Le choix et la répartition des codes des nœuds sont effectués de façon aléatoire.

La base de données de l’arbre des suffixes est composée de deux tables : Nœuds et Liens. a- Structure de la table Nœuds : Nœuds ( code (Entier) , nom (Texte), niveau (Entier) ) La table Nœuds contient les nœuds internes de l’arbre des suffixes, et elle est composée de trois champs : code, nom et niveau. Le champ code contient un entier positif unique pour chaque nœud interne ; Le champ nom contient le nom du nœud interne ; Le champ niveau contient un entier positif qui représente le niveau du nœud dans l’arbre. Page 45 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

b- Structure de la table Liens : Liens ( pere (Entier) , fils (Entier) ) La table liens contient les liaisons père-fils dans l’arbre, elle est composée des champs : pere et fils. Le champ pere contient les codes des nœuds pères ; Le champ fils contient les codes des nœuds fils ; c- Exemples de données des deux tables :

code 15 16 17 18 19 20 21 …

Table : Nœuds nom '#' 'A' 'CTA' 'GCTA' 'T' 'GCTA’ 'TCTAGCTA' …

niveau 0 1 1 1 1 2 2 …

Table : Liens pere 15 15 15 10 16 16 16 20 21 …

fils 16 17 18 19 9 20 21 5 1 …

Q. 11 : Déterminer la clé primaire de la table Nœuds, et la clé primaire de la table Liens. Justifier votre réponse.

Q. 12 : Écrire une requête SQL, qui renvoie Les noms des nœuds, sans répétition, tels que le motif 'GCTA' est un préfixe ou suffixe des noms de ces nœuds, triés dans l’ordre croissant du champ niveau.

Q. 13 : Écrire une requête SQL, qui renvoie La hauteur de l’arbre. Exemple : La hauteur de l’arbre exemple est 5.

Q. 14 : Le degré d'un nœud est égal au nombre de fils de ce nœuds. Exemple : Le degré de la racine de l’arbre exemple est 4. Écrire une requête SQL, qui renvoie Les noms et les niveaux des nœuds dont le degré est supérieur à 2, triés dans l’ordre croissant selon le degré.

Q. 15 : Le degré d'un arbre est égal au plus grand des degrés de ses nœuds. Écrire une requête SQL, qui renvoie Le degré de l’arbre.

Q. 16 : Écrire une requête SQL, qui renvoie Les feuilles de l’arbre et leurs niveaux.

Q. 17 : Écrire une requête, en algèbre relationnelle, qui renvoie Les feuilles de l’arbre. Page 46 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Plus long motif commun Le problème du plus long motif commun à deux chaînes de caractères P et Q non vides, consiste à déterminer le (ou les) plus long motif qui sont en même temps sous-chaîne de P et de Q. Ce problème se généralise à la recherche du plus long motif commun à plusieurs chaînes de caractères.

Pour rechercher le plus long motif commun à deux chaînes de caractères P et Q non vides, on commence par créer une matrice M remplie par des zéros, telle que le nombre de lignes de M est égal à la taille de P, et le nombre de colonnes de M est égal à la taille de Q. Ensuite, on compare les caractères de P avec ceux de Q, et on écrit, le nombre de caractères successifs identiques, dans la case correspondante de la matrice M. Exemple : P = 'GCTAGCATT' et Q = 'CATTGTAGCT' La matrice M, de comparaison des caractères de P avec ceux de Q, est la suivante :

À partir de cette matrice M, On peut extraire les plus longs motifs communs à P et Q : 'CATT' et 'TAGC'

Q-18 : Écrire une fonction : matrice (P, Q), qui reçoit en paramètres deux chaînes de caractères P et Q non vides, et qui retourne la matrice M de comparaison des caractères de P avec ceux de Q, selon le principe décrit dans l’exemple ci-dessus. Exemple : matrice ('GCTAGCATT', 'CATTGTAGCT') renvoie la matrice M suivante : [ [0, 0, 0, 0, 1, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 2, 0], [0, 0, 1, 1, 0, 1, 0, 0, 0, 3], […] , … ]

Q-19 : Écrire une fonction plus_long_mc (P, M), qui reçoit en paramètres une chaîne de caractères P non vide, et la matrice M de comparaison des caractères de la chaîne P avec ceux d’une autre chaîne Q non vide aussi, selon le principe décrit dans l’exemple ci-dessus. La fonction renvoie la liste, sans doublons, de tous les plus longs motifs communs à P et Q. Exemple : P = 'GCTAGCATT' et M est la matrice de comparaison des caractères de P avec ceux de la chaîne 'CATTGTAGCT'. plus_long_mc (P, M) retourne la liste des plus longs motifs communs : [ 'TAGC' , 'CATT' ] Page 47 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Plus long motif commun dans un fichier On considère le fichier texte dont le chemin absolu est : 'C:\génomes.txt'. On suppose que ce fichier contient au moins deux lignes.

Q-20 : Écrire le code python qui permet d’afficher les plus longs motifs communs, à toutes les lignes de ce fichier texte, sans doublons. Exemple : On suppose que le fichier 'C:\génomes.txt' est composé des lignes suivantes :

GATTCGAGGCTAAACTAGCTAA GATTCGAGGCTCTAGCTATTCGAGGG CTAGCTATAGGCTAGCTACCATTATTCGAG CGCTAGCTACATTCGAGGCTAAAC ATTCGAGAGGGCTAACTAGCTAAGCCA

Le programme affiche les plus longs motifs communs à toutes les lignes de ce fichier : 'ATTCGAG' , 'CTAGCTA'

~~~~~~~~~~~~

FIN

~~~~~~~~~~~~

Page 48 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2018 - Filière PSI Sommaire

Partie I : Base de données d’un pendule simple Un pendule simple est constitué d’un solide de masse m, suspendu à une tige rigide de longueur L et de masse négligeable devant m. Ecarté de sa position initiale d’un angle θ et lâché sans vitesse initiale, le pendule effectue des oscillations périodiques autour de sa position d’équilibre définie par : θ = 0.

On considère une base de données, dans laquelle on a enregistré les mesures réalisées sur plusieurs pendules simples. Cette base de données est composée de deux tables : la table Pendules et la table Mesures.

Pendules

Mesures

code

cod_pendule

longueur

T

masse

theta

coef_frottement

Page 49 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

a- Structure de la table Pendules : La table Pendules est composée de 4 champs : Pendules ( code , longueur , masse , coef_frottement ) Le champ code, de type texte, contient un code unique pour chaque pendule ; Le champ longueur, de type réel, contient la longueur de la tige du pendule, exprimée en mètre ; Le champ masse, de type réel, contient la masse de l’objet suspendu, exprimée en kilogramme ; Le champ coef_frott, de type réel, contient le coefficient du frottement.

b- Structure de la table mesures : La table Mesures est composée de 3 champs : Mesures ( cod_pendule , T , theta ) Le champ cod_pendule, de type texte, contient les codes des pendules ; Le champ T, de type réel, contient les temps de mesure de l’angle thêta, exprimé en seconde. NB : Les mesures de l’angle thêta sont prises à un même intervalle de temps, pour chaque pendule. Le champ theta, de type réel, contient la mesure de l’angle θ correspondante à chaque instant de T, exprimée en radian.

c- Exemples de données dans les deux tables : Table : Pendules

Table : Mesures

code

longueur

masse

coef_frott

P1 P2 P3 P4 P5

0.5 0.4 1.0 1.5 1.0

1.0 0.5 0.5 2.0 0.5

0.2 0.0 0.4 0.3 1.0

…

…

…

…

cod_pendule

T

theta

P1 P1 P1 P1 P1

0 0.001 0.002 0.003 0.004

1.047198 1.047164 1.04713 1.047062 1.046994

…

…

…

P1

10

0.120292

P2

0

1.570796

P2

0.02

1.551176

P2

0.04

1.531556

P2

0.06

1.492324

… … P2

…

P3 P3

0 0.005

- 0.387401 2.356194 2.355848

P3

…

…

25

Page 50 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q.1- Déterminer la clé primaire de la table Pendules, et la clé primaire de la table Mesures. Justifier votre réponse.

Q.2- Convertir la requête suivante, en langage SQL : R = π T, theta ( σ cod_pendule = 'P1' (Mesures) )

Q.3- Écrire une requête SQL, qui donne pour résultat Les codes, les masses et les longueurs des pendules dont la masse est comprise entre 500 g et 1500 g, et dont le code ne contient pas le chiffre 5.

Q.4- Écrire une requête SQL, qui donne pour résultat Les codes des pendules et les mesures de l’angle thêta en degré, à l’instant 0, triés par ordre décroissant selon les codes.

Q.5- Écrire une requête SQL qui donne pour résultat Les codes des pendules et le nombre de mesures prises pour chaque pendule, triés dans l’ordre croissant du nombre de mesures.

Q.6- Pour chaque pendule, les mesures de l’angle thêta ont été prises à un même intervalle de temps, appelé : pas. Écrire une requête SQL qui donne pour résultat Le code et le pas des mesures de chaque pendule, ayant pour pas 10-1.

Q.7- Écrire une requête SQL, qui crée la nouvelle table 'Pendules_1', ayant la structure suivante : Pendules_1 ( code texte , longueur réel , masse réel , coef_frott réel , Tmax réel , pas réel , N entier )

Q.8- Écrire une requête SQL, qui copie, dans la table Pendules_1, le code, la longueur, la masse, le coefficient de frottement, le max des T, le pas, et le nombre de mesures prises pour chaque pendule de la table Pendules.

Exemple : code

longueur

masse

coef_frott

Tmax

pas

N

P1 P2 P3

0.5 0.4 1.0

1.0 0.5 0.5

0.2 0.0 0.4

10 25 8

0.001 0.02 0.005

1000 1250 1600

…

…

…

…

…

…

…

****************************** Page 51 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie II : Calcul numérique Résolution numérique d’équation différentielle La méthode de Nyström (ou saute-mouton) Dans cette partie, on suppose que les modules suivants sont importés : from numpy import * from matplotlib.pyplot import *

Les équations différentielles (ED) apparaissent très souvent dans la modélisation de la physique et des sciences de l'ingénieur. Trouver la solution d'une ED ou d'un système d'ED est ainsi un problème courant, souvent difficile ou impossible à résoudre de façon analytique. Il est alors nécessaire de recourir à des méthodes numériques pour les résoudre.

Le problème de Cauchy consiste à trouver une fonction y(t) définie sur l'intervalle [a, b] telle que : =

,

; =

∀ ∈[

, ]!

Pour obtenir une approximation numérique de la solution y(t) sur l'intervalle [a, b], nous allons estimer la valeur de cette fonction en un nombre fini de points ti, pour i = 0, 1, … , n, constituants les nœuds du maillage. La solution numérique obtenue aux points ti est notée yi = y(ti). L'écart entre deux abscisses, noté h, est appelé : le pas de discrétisation.

Les principales méthodes de résolution numérique des ED sont séparées en deux grandes catégories : les méthodes à un pas : Le calcul de la valeur yn+1 au nœud tn+1 fait intervenir la valeur yn obtenue à l'abscisse précédente. Les principales méthodes sont celles de : Euler, Runge-Kutta, CrankNicholson … les méthodes à multiples pas: Le calcul de la valeur yn+1 au nœud tn+1 fait intervenir plusieurs valeurs yn , yn-1 , yn-2 , … obtenues aux abscisses précédentes. Les principales méthodes sont celles de : Nyström, Adams-Bashforth, Adams-Moulton, Gear …

La méthode de Nyström :

Le schéma de la méthode de Nyström à deux pas est :

y0 donné ; y1 calculé par la méthode Euler ; "

=

+(∗$∗

,

Géométriquement : on considère la droite de pente f(yn , tn) passant par le point (yn-1 , tn-1) parallèle à la tangente passant par (yn , tn). La valeur yn+1 est l'ordonnée du point de cette droite d'abscisse tn+1. Page 52 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 1 : Écrire une fonction : nystrom (f, a, b, y0, h), qui reçoit en paramètres : f est la fonction qui représente une équation différentielle du premier ordre ; a et b sont les deux bornes de l’intervalle d’intégration ; y0 est la valeur de la condition initiale à l’instant a (y(a)=y0) ; h est le pas de discrétisation. En utilisant le schéma de Nyström, la fonction renvoie T et Y, qui peuvent être des listes ou des tableaux : T contient la subdivision de l’intervalle [a, b], en valeurs régulièrement espacée, utilisant le pas de discrétisation h ; Y contient les approximations des valeurs y(ti), à chaque instant ti de T.

Application au pendule simple

On considère une masse m suspendue par une tige rigide de longueur L et de masse négligeable. On désigne par θ l’angle entre la verticale passant par le point de suspension et la direction de la tige. On considère que le pendule est également soumis à un frottement fluide de coefficient k. Si l’objet m est écarté de façon à ce que l’angle entre la verticale et la tige soit θ0, et ensuite relâché sans vitesse initiale, alors l’objet m effectue un mouvement harmonique amorti. La forme générale de l’équation différentielle modélisant ce mouvement harmonique est :

(E)

4 ∗ 51

+

0∗4

∗ 52

+6∗7

5

=

Les paramètres de cette équation différentielle sont : k : le coefficient du frottement fluide ; g : la pesanteur ; L : la longueur de la tige ; m : la masse de l’objet suspendu. NB : Cette équation n'a pas de solution analytique, sa solution est numérique. Page 53 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 2 : On suppose que les valeurs des paramètres de l’équation différentielle (E), sont : m = 1 kg ;

g = 9.81 m/s2

;

L = 0.50 m

et

k = 0.2 kg/s

Écrire l’équation différentielle (E) sous la forme z’ = F(t, z), avec F(t, z) une fonction à deux variables (t, z) avec z un tableau de longueur 2.

Q. 3 : On suppose avoir écarté l’objet, de façon à ce que l’angle entre la verticale et la tige, soit de π/3, avant de le relâcher sans vitesse initiale. a- En utilisant la fonction de Nyström, écrire le code python qui, permet de tracer le graphe ci-dessous, qui représente la valeur de l’angle 8, toutes les 10-3 secondes.

b- Écrire le code python qui permet de tracer le graphe ci-dessous, qui représente le portrait de phase du pendule : les valeurs de 52 (axe des ordonnées) en fonction des valeurs de 8 (axe des abscisses).

~~~~~~ ~~~~~~~~~~~~~~ ~~~ ~ Page 54 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie III : Bioinformatique : Recherche d’un motif La bioinformatique, c'est quoi? Au cours des trente dernières années, la récolte de données en biologie a connu un boom quantitatif grâce notamment au développement de nouveaux moyens techniques servant à comprendre l'ADN et d’autres composants d’organismes vivants. Pour analyser ces données, plus nombreuses et plus complexes aussi, les scientifiques se sont tournés vers les nouvelles technologies de l’information. L'immense capacité de stockage et d’analyse des données qu'offre l'informatique leur a permis de gagner en puissance pour leurs recherches. La bioinformatique sert donc à stocker, traiter et analyser de grandes quantités de données de biologie. Le but est de mieux comprendre et mieux connaître les phénomènes et processus biologiques. Dans le domaine de la bioinformatique, la recherche de sous-chaîne de caractères, appelée motif, dans un texte de taille importante, était un composant important de beaucoup d’algorithmes. Puisqu’on travaille sur des textes de tailles très importantes, on a toujours cette obsession de l’efficacité des algorithmes : moins on a à faire de comparaisons, plus rapide sera l’exécution des algorithmes. Le motif à rechercher, ainsi que le texte dans lequel on effectue la recherche, sont écrits dans un alphabet composé de quatre caractères : 'A' , 'C' , 'G' et 'T'. Ces caractères représentent les quatre bases de l’ADN : Adénine, Cytosine, Guanine et Thymine.

Codage des caractères de l’alphabet L’alphabet est composé de quatre caractères seulement : 'A', 'C', 'G' et 'T'. Dans le but d’économiser la mémoire, on peut utiliser un codage binaire réduit pour ces quatre caractères.

Q. 1 : Quel est le nombre minimum de bits nécessaires pour coder quatre éléments ?

Q. 2 : Donner un exemple de code binaire pour chaque caractère de cet alphabet.

Préfixe d’une chaîne de caractères Un préfixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères entre la première position de S et une certaine position dans S. Exemple : S = 'TATCTAGCTA' La chaîne 'TAT' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTAGCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'T' est un préfixes de 'TATCTAGCTA' ; La chaîne 'CTAGC' n’est pas un préfixe de S.

Q. 3 : Écrire une fonction prefixe (M, S), qui reçoit en paramètres deux chaînes de caractères M et S non vides, et qui retourne True si la chaîne M est un préfixe de S, sinon, elle retourne False. Page 55 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 4 : Quel est le nombre de comparaisons élémentaires effectuées par la fonction prefixe (M, S), dans le pire cas ? Déduire la complexité de la fonction prefixe (M, S) dans le pire cas.

Suffixe d’une chaîne de caractères Un suffixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères, en partant d’une certaine position p dans S, jusqu’à la dernière position de S. L’entier p est appelée : position du suffixe. Exemple : S = 'TATCTAGCTA' La chaîne 'CTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 3 ; La chaîne 'GCTA' est un suffixe de 'TATCTAGCTA', sa position est : 6 ; La chaîne 'TATCTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 0 ; La chaîne 'CTAGC' n’est pas un suffixe de S.

Q. 5 : Écrire une fonction liste_suffixes (S), qui reçoit en paramètre une chaîne de caractères S non vide, et qui renvoie une liste de tuples. Chaque tuple de cette liste est composé de deux éléments : un suffixe de S, et la position p de ce suffixe dans S (0 ≤ p < taille(S)). Les tuples de cette liste sont ordonnés dans l’ordre croissant des positions des suffixes. Exemple : S = 'TATCTAGCTA' La fonction liste_suffixes (S) renvoie la liste : [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)]

Recherche séquentielle d’un motif La recherche séquentielle, d’un motif M dans une chaîne de caractères S non vide, consiste à parcourir la liste L des suffixes de S (voir Question. 5), en cherchant si le motif M est un préfixe du suffixe d’un tuple de la liste L. Si oui, la fonction retourne la position de ce suffixe. Le parcours, de la liste L, ne doit considérer que les positions possibles pour le motif M, c’est-à-dire les positions p tels que : 0 ≤ p ≤ (taille de L – taille de M).

Q. 6 : Écrire une fonction : recherche_sequentielle (M, L), qui, en utilisant le principe de la recherche séquentielle dans L, renvoie la position du premier tuple, tel que M est un préfixe du suffixe de ce tuple, s’il existe ; sinon, la fonction renvoie None. NB : Dans cette fonction, on ne doit pas utiliser la méthode index(). Exemples : La liste des suffixes de la chaîne 'TATCTAGCTA' est : L = [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)] recherche_sequentielle ('CTA', L) renvoie la position 3 ; 'CTA' est préfixe de 'CTAGCTA' recherche_sequentielle ('TA', L) renvoie la position 0 ; 'TA' est préfixe de 'TATCTAGCTA' recherche_sequentielle ('CAGTA', L) renvoie None. 'CAGT' n’est préfixe d’aucun suffixe

Page 56 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 7 : On pose m et k les tailles respectives de la chaîne M et la liste L. Déterminer, en fonction de m et k, la complexité de la fonction recherche_sequentielle (M, L), dans le pire cas. Et, donner un exemple, de chaînes M et S, qui atteigne cette complexité.

Tri de la liste des suffixes Q. 8 : Écrire une fonction tri_liste (L), qui reçoit en paramètre la liste L des suffixes d’une chaîne de caractères non vide, créée selon le principe décrit dans la question 5. La fonction tri_liste, trie les éléments de L dans l’ordre alphabétique des suffixes. (Voir exemple suivant) NB : On ne doit pas utiliser la fonction sorted(), ou la méthode sort(). Exemple : L = [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)] Après l’appel de la fonction tri_liste (L), on obtient la liste suivante : [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ]

Recherche dichotomique d’un motif : La liste des suffixes L contient les tuples composés des suffixes d’une chaîne de caractères S non vide, et de leurs positions dans S. Si la liste L est triée dans l’ordre alphabétique des suffixes, alors, la recherche d’un motif M dans S, peut être réalisée par une simple recherche dichotomique dans la liste L.

Q. 9 : Écrire une fonction recherche_dichotomique (M, L), qui utilise le principe de la recherche dichotomique, pour rechercher le motif M dans la liste des suffixes L triée dans l’ordre alphabétique des suffixes : Si M est un préfixe d’un suffixe dans un tuple de L, alors la fonction retourne la position de ce suffixe. Si la fonction ne trouve pas le motif M recherché, alors la fonction retourne None. Exemple : La liste des suffixes de 'TATCTAGCTA', triée dans l’ordre alphabétique des suffixes est : L = [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ] recherche_dichotomique ('CTA', L) renvoie la position 3 ; 'CTA' est préfixe de 'CTAGCTA' recherche_dichotomique ('TA', L) renvoie la position 0 ; 'TA' est un préfixe de 'TATCTAGCTA' recherche_dichotomique ('CAGT', L) renvoie None. 'CAGT' n’est préfixe d’aucun suffixe Q. 10 : On pose m et k les tailles respectives de la chaîne M et la liste L. Déterminer, en fonction de m et k, la complexité de la fonction recherche_dichotomique (M, L), dans le pire cas. Justifier votre réponse.

L’arbre des suffixes d’une chaîne de caractères : L'arbre des suffixes, d’une chaîne de caractères S non vide, est un arbre n-aire qui permet de représenter tous les suffixes de S. Cet arbre possède les propriétés suivantes : Page 57 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

La racine de l’arbre est marquée par le caractère '#' ; Chaque nœuds de l’arbre contient une sous-chaîne de S, non vide ; Les premiers caractères, des sous-chaînes fils d’un même nœud, sont différents ; Chaque feuille de l'arbre contient un entier positif qui correspond à la position d’un suffixe dans la chaîne S.

Exemple : S = 'TATCTAGCTA' La liste des suffixes de S, triée dans l’ordre alphabétique des suffixes est :

L = [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ] L’arbre des suffixes est crée à partir de la liste des suffixes triée :

La racine de l’arbre '#' se trouve au niveau 0 de l’arbre, ses fils se trouvent au niveau 1, … . En parcourant une branche de l’arbre depuis le niveau 1, et en effectuant la concaténation des sous-chaînes des nœuds, on obtient un suffixe de la chaîne S ; et dans la feuille, on trouve la position de ce suffixe dans S. Exemples : En parcourant les nœuds de la première branche à droite de l’arbre 'T' + 'CTAGCTA', on obtient le suffixe 'TCTAGCTA'. La feuille contient la position 2 de ce suffixe ; En parcourant les nœuds de la troisième branche à partir de la droite de l’arbre 'T' + 'A' + 'GCTA', on obtient le suffixe 'TAGCTA'. La feuille contient la position 4 de ce suffixe. Pour représenter l’arbre des suffixes, on utilise une liste composée de deux éléments : Le nœud, et une liste contenant tous les fils de ce nœud : Un nœud N est représenté par la liste : [ N , [ f1 , f2 , … , fn ] ] ; Chaque fils fk est représenté par la liste : [ fk , [ tous les fils de fk ] ] ; Une feuille F est représentée par la liste : [ F , [ ] ].

On suppose que la fonction arbre_suffixes (S) reçoit en paramètre une chaîne de caractères S non vide, et construit et renvoie l’arbre des suffixes de S, représenté par une liste, selon le principe décrit ci-dessus. Page 58 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemple : arbre_suffixes ('TATCTAGCTA') renvoie la liste R suivante : R = [ '#', [ [ 'A', [ [ 9, [ ] ], [ 'GCTA', [ [ 5,[ ] ] ] ], [ 'TCTAGCTA', [ [ 1, [ ] ] ] ] ] ], [ 'CTA',[ [ 7, [ ] ], [ 'GCTA', [ [ 3, [ ] ] ] ] ] ], [ 'GCTA', [ [ 6, [ ] ] ] ], [ 'T', [ [ 'A', [ [ 8, [ ] ], [ 'GCTA', [ [ 4, [ ] ] ] ], [ 'TCTAGCTA', [ [ 0, [ ] ] ] ] ] ], [ 'CTAGCTA', [ [ 2, [ ] ] ] ] ] ] ] ]

Q. 11 : Écrire une fonction feuilles (R), qui reçoit en paramètre une liste R représentant l’arbre des suffixes d’une chaîne de caractères non vide, et qui retourne la liste contenant toutes les feuilles de l’arbre R. Exemple : feuilles (R) revoie la liste [ 9 , 5 , 1 , 7 , 3 , 6 , 8 , 4 , 0 , 2 ] L’intérêt, de l’arbre des suffixes, c’est qu’il permet d’effectuer une recherche de toutes les occurrences d’un motif dans un temps qui dépend uniquement de la longueur du motif, et non de la chaîne dans laquelle on effectue la recherche. En effet, la recherche d’un motif se réalise par la lecture du motif recherché et par le parcours simultané de l’arbre des suffixes. Trois cas peuvent survenir : On se retrouve sur un nœud, et le motif est un préfixe de ce nœud : Dans ce cas, les feuilles du sous arbre de ce nœud, correspondent aux positions de toutes les occurrences du motif dans la chaîne. On se retrouve sur un nœud, et ce nœud est un préfixe du motif : Dans ce cas, on continue la recherche parmi les fils de ce nœud. On ne peut plus descendre dans l’arbre : Dans ce cas, il n’y a pas d’occurrence du motif recherché dans la chaîne.

Q. 12 : Écrire une fonction recherche_arbre (M, R), qui reçoit en paramètres un motif M non vide, et une liste R représentant l’arbre des suffixes d’une chaîne de caractères non vide. La fonction retourne une liste contenant les positions de toutes les occurrences de M dans cette chaîne de caractères. Exemples : R est la liste qui représente l’arbre des suffixes de la chaîne S = 'TATCTAGCTA'. recherche_arbre ('TA', R) renvoie la liste : [ 8 , 4 , 0 ] recherche_arbre ('CTA', R) revoie la liste : [ 7 , 3 ] recherche_arbre ('TACG', R) renvoie la liste : [ ]

~~~~~~~~~~~~

FIN

~~~~~~~~~~~~

Page 59 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2018 - Filière TSI Sommaire

Partie I : Bases de donnée

Arbre généalogique

Dans cette partie, le but est de modéliser une structure qui représente un arbre généalogique par une base de données. On commence par représenter l’arbre généalogique sous forme d’un arbre n-aire descendant : En haut de l’arbre se situe l’ancêtre commun à tous les membres de l’arbre généalogique. Et chaque membre de l’arbre est relié vers le bas à chacun de ses enfants. À l’exception de l’ancêtre commun, chaque membre de l’arbre est relié vers le haut à une unique personne : son parent. Pour plus de clarté, nous prendrons l’arbre généalogique suivant comme exemple dans toute cette partie :

Page 60 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Cet arbre généalogique est composé de plusieurs générations. Le plus grand ancêtre est 'Mohamed', il appartient à la génération 0. Le plus grand ancêtre est appelé : racine de l’arbre. Ce dernier possède trois enfants : 'Ahmed', 'Maryem' et 'Khalid'. Ces trois enfants appartiennent à la génération 1. 'Khalid' n’a pas d’enfant, 'Ahmed' a un enfant, et 'Maryem' en a deux. Les enfants de 'Ahmed' et de 'Maryem' appartiennent à la génération 2, ... etc. Le nombre total de générations dans l’arbre est appelé : hauteur de l’arbre. On peut calculer la hauteur de l’arbre en ajoutant le nombre 1 à la plus grande génération dans l’arbre. Exemple : La hauteur de l’arbre de l’exemple précédent est 4.

Dans ce qui suit, on propose de représenter l’arbre généalogique par une base de données composée de deux tables : la table : membres et la table : liens.

Membres

Liens

id

(Entier)

id_parent

(Entier)

prenom

(Texte)

id_enfant

(Entier)

genre

(Texte)

generation

(Entier)

a- Structure de la table Membres : La table Membres contient tous les membres de l’arbre généalogique. Elle est composée de quatre champs : id, prenom, genre et generation : Le champ id contient un entier positif unique, qui permet d’identifier, chaque membre dans la table ; Le champ prenom contient le prénom d’un membre de l’arbre généalogique ; Le champ genre contient le caractère 'M' pour les masculins, ou 'F' pour les féminins : Le champ generation contient un entier positif qui représente le niveau du membre dans l’arbre généalogique.

b- La structure de la table Liens : La table Liens contient tous les liens de parenté parent-enfant entre les membres de l’arbre généalogique. Elle est composée de deux champs : id_parent et id_enfant : Le champ id_parent contient les identifiants des membres parents ; Le champ id_enfant contient les identifiants des membres enfants.

Page 61 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

c- Exemples d’enregistrements dans les tables Membres et Liens: Table : Membres id 1 2 3 4 5 6 7 8

prenom Mohamed Ahmed Maryem Khalid Manal Sara Ahmed Jinane

… …

genre M M F M F F M F

…

Table : Liens generation 0 1 1 1 2 2 2 3

id_parent 1 1 1 2 3 3 7

id_enfant 2 3 4 5 6 7 8

…

…

…

Q.1- Déterminer la clé primaire de la table Membres, et la clé primaire de la table Liens. Justifier votre réponse. Q.2- Écrire une requête SQL, qui donne pour résultat le prénom et le genre du plus grand ancêtre des membres.

Q.3- Écrire une requête SQL, qui donne pour résultat les prénoms et les générations, sans répétition, des membres masculins, dont le prénom commence par 'A', et se termine par 'D', et contient 'E'.

Q.4- Écrire une requête SQL, qui donne pour résultat la hauteur de l’arbre.

Q.5- Écrire une requête SQL, qui donne pour résultat les prénoms et les genres des enfants du parent dont l’id_parent = 15, triés dans l’ordre alphabétique des prénoms.

Q.6- Écrire une requête SQL qui donne pour résultat les identifiants, les prénoms et les générations des membres ayant un nombre d’enfants supérieur ou égal à 3, triés dans l’ordre décroissant du nombre d’enfants.

Q.7- Écrire une requête SQL qui crée une nouvelle table nommée Membres_1, ayant la même structure que la table Membres.

Q.8- Écrire une requête SQL qui copie dans la table Membres_1, tous les membres de la table Membres, qui possèdent le même prénom que celui du plus grand ancêtre.

*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* Page 62 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie II : Bioinformatique : Recherche d’un motif La bioinformatique, c'est quoi? Au cours des trente dernières années, la récolte de données en biologie a connu un boom quantitatif grâce notamment au développement de nouveaux moyens techniques servant à comprendre l'ADN et d’autres composants d’organismes vivants. Pour analyser ces données, plus nombreuses et plus complexes aussi, les scientifiques se sont tournés vers les nouvelles technologies de l’information. L'immense capacité de stockage et d’analyse des données qu'offre l'informatique leur a permis de gagner en puissance pour leurs recherches. La bioinformatique sert donc à stocker, traiter et analyser de grandes quantités de données de biologie. Le but est de mieux comprendre et mieux connaître les phénomènes et processus biologiques. Dans le domaine de la bioinformatique, la recherche de sous-chaîne de caractères, appelée motif, dans un texte de taille importante, était un composant important dans beaucoup d’algorithmes. Puisqu’on travaille sur des textes de tailles très grandes, on a toujours cette obsession de l’efficacité des algorithmes : moins on a à faire de comparaisons, plus rapide sera l’exécution des algorithmes. Le motif à rechercher, ainsi que le texte dans lequel on effectue la recherche, sont écrits dans un alphabet composé de quatre caractères : 'A' , 'C' , 'G' et 'T'. Ces caractères représentent les quatre bases de l’ADN : Adénine, Cytosine, Guanine et Thymine.

Codage des caractères de l’alphabet L’alphabet est composé de quatre caractères seulement : 'A', 'C', 'G' et 'T'. Dans le but d’économiser la mémoire, on peut utiliser un codage binaire réduit pour ces quatre caractères.

Q. 1 : Quel est le nombre minimum de bits nécessaires pour coder quatre éléments ?

Q. 2 : Donner un exemple de code binaire pour chaque caractère de cet alphabet.

Préfixe d’une chaîne de caractères Un préfixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères entre la première position de S et une certaine position dans S. Exemple : S = 'TATCTAGCTA' La chaîne 'TAT' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'TATCTAGCTA' est un préfixes de 'TATCTAGCTA' ; La chaîne 'T' est un préfixes de 'TATCTAGCTA' ; La chaîne 'CTAGC' n’est pas un préfixe de S.

Q. 3 : Écrire une fonction prefixe (M, S), qui reçoit en paramètres deux chaînes de caractères M et S non vides, et qui retourne True si la chaîne M est un préfixe de S, sinon, elle retourne False. Page 63 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 4 : Quel est le nombre de comparaisons élémentaires effectuées par la fonction prefixe (M, S), dans le pire cas ? Déduire la complexité de la fonction prefixe (M, S) dans le pire cas.

Suffixe d’une chaîne de caractères Un suffixe d’une chaîne de caractères S non vide, est une sous-chaîne non vide de S, composée de la suite des caractères, en partant d’une certaine position p dans S, jusqu’à la dernière position de S. L’entier p est appelée : position du suffixe. Exemple : S = 'TATCTAGCTA' La chaîne 'CTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 3 ; La chaîne 'GCTA' est un suffixe de 'TATCTAGCTA', sa position est : 6 ; La chaîne 'TATCTAGCTA' est un suffixe de 'TATCTAGCTA', sa position est : 0 ; La chaîne 'CTAGC' n’est pas un suffixe de S.

Q. 5 : Écrire une fonction liste_suffixes (S), qui reçoit en paramètre une chaîne de caractères S non vide, et qui renvoie une liste de tuples. Chaque tuple de cette liste est composé de deux éléments : un suffixe de S, et la position p de ce suffixe dans S (0 ≤ p < taille(S)). Les tuples de cette liste sont ordonnés dans l’ordre croissant des positions des suffixes. Exemple : S = 'TATCTAGCTA' La fonction liste_suffixes (S) renvoie la liste : [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)]

Recherche séquentielle d’un motif La recherche séquentielle, d’un motif M dans une chaîne de caractères S non vide, consiste à parcourir la liste L des suffixes de S (voir Question. 5), en cherchant si le motif M est un préfixe du suffixe d’un tuple de la liste L. Si oui, la fonction retourne la position de ce suffixe. Le parcours, de la liste L, ne doit considérer que les positions possibles pour le motif M, c’est-à-dire les positions p tels que : 0 ≤ p ≤ (taille de L – taille de M).

Q. 6 : Écrire une fonction : recherche_sequentielle (M, L), qui, en utilisant le principe de la recherche séquentielle dans L, renvoie la position du premier tuple, tel que M est un préfixe du suffixe de ce tuple, s’il existe ; sinon, la fonction renvoie None. NB : Dans cette fonction, on ne doit pas utiliser la méthode index(). Exemples : La liste des suffixes de la chaîne 'TATCTAGCTA' est : L = [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)] recherche_sequentielle ('CTA', L) renvoie la position 3 ; 'CTA' est préfixe de 'CTAGCTA' recherche_sequentielle ('TA', L) renvoie la position 0 ; 'TA' est préfixe de 'TATCTAGCTA' recherche_sequentielle ('CAGTA', L) renvoie None. 'CAGT' n’est préfixe d’aucun suffixe

Page 64 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Q. 7 : On pose m et k les tailles respectives de la chaîne M et la liste L. Déterminer, en fonction de m et k, la complexité de la fonction recherche_sequentielle (M, L), dans le pire cas. Et, donner un exemple, de chaînes M et S, qui atteigne cette complexité.

Tri de la liste des suffixes Q. 8 : Écrire une fonction tri_liste (L), qui reçoit en paramètre la liste L des suffixes d’une chaîne de caractères non vide, créée selon le principe décrit dans la question 5. La fonction tri_liste, trie les éléments de L dans l’ordre alphabétique des suffixes. (Voir exemple suivant) NB : On ne doit pas utiliser la fonction sorted(), ou la méthode sort(). Exemple : L = [('TATCTAGCTA', 0), ( 'ATCTAGCTA', 1), ( 'TCTAGCTA', 2), ('CTAGCTA', 3), ('TAGCTA', 4), ('AGCTA', 5), ('GCTA', 6), ('CTA', 7), ('TA', 8), ('A', 9)] Après l’appel de la fonction tri_liste (L), on obtient la liste suivante : [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ]

Recherche dichotomique d’un motif : La liste des suffixes L contient les tuples composés des suffixes d’une chaîne de caractères S non vide, et de leurs positions dans S. Si la liste L est triée dans l’ordre alphabétique des suffixes, alors, la recherche d’un motif M dans S, peut être réalisée par une simple recherche dichotomique dans la liste L.

Q. 9 : Écrire une fonction recherche_dichotomique (M, L), qui utilise le principe de la recherche dichotomique, pour rechercher le motif M dans la liste des suffixes L triée dans l’ordre alphabétique des suffixes : Si M est un préfixe d’un suffixe dans un tuple de L, alors la fonction retourne la position de ce suffixe. Si la fonction ne trouve pas le motif M recherché, alors la fonction retourne None. Exemple : La liste des suffixes de 'TATCTAGCTA', triée dans l’ordre alphabétique des suffixes est : L = [ ('A', 9) , ('AGCTA', 5) , ('ATCTAGCTA', 1) , ('CTA', 7) , ('CTAGCTA', 3) , ('GCTA', 6) , ('TA', 8) , ('TAGCTA', 4) , ('TATCTAGCTA', 0) , ('TCTAGCTA', 2) ] recherche_dichotomique ('CTA', L) renvoie la position 3 ; 'CTA' est préfixe de 'CTAGCTA' recherche_dichotomique ('TA', L) renvoie la position 0 ; 'TA' est un préfixe de 'TATCTAGCTA' recherche_dichotomique ('CAGT', L) renvoie None. 'CAGT' n’est préfixe d’aucun suffixe Q. 10 : On pose m et k les tailles respectives de la chaîne M et la liste L. Déterminer, en fonction de m et k, la complexité de la fonction recherche_dichotomique (M, L), dans le pire cas. Justifier votre réponse.

*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Page 65 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie III : Calcul numérique Calcule de la racine nième par la méthode de 'Newton' De nombreux problèmes d'économie, de mathématiques ou de physique se concluent par la résolution d'une équation f(x) = 0. Bien souvent, il n'est pas possible de résoudre exactement cette équation, et on cherche une valeur approchée de la solution (ou des solutions). Newton a proposé une méthode générale pour obtenir une telle approximation. L'idée est de remplacer la courbe représentative de la fonction par sa tangente.

On part d'un point x0 de l'intervalle de définition de f, et on considère la tangente à la courbe représentative de f en (x0 , f(x0)). On suppose que cette tangente coupe l’axe des abscisses (c.à.d. f '(x0) non nul). Soit x1 l'abscisse de l'intersection de la tangente avec l'axe des abscisses :

9 =9 −

9

9

Puisque la tangente est proche de la courbe, on peut espérer que x1 donne une meilleure estimation d'une solution de l'équation f(x) = 0 que x0.

9( = 9 −

On recommence alors le procédé à partir de x1, on obtient x2 :

9

9

… Ainsi, on construit par récurrence une suite (xn) définie par :

9

"

=9 −

9

9

Sous de bonnes hypothèses sur f, assez restrictives, (xn) converge vers la solution de l’équation f(x) = 0, et la convergence est très rapide. Page 66 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

A- Approximation de la dérivée par la moyenne des taux d’accroissement à gauche et à droite : Si f est une fonction dérivable en xi, on peut toutefois obtenir une approximation de f '(xi) par la moyenne des taux d’accroissement à gauche et à droite de xi : Pour un réel h > 0 (très proche de 0) : ′ 9 ≈

Q.1- Montrer que :

9

"

= 9 − ($

9 "$

9 +$ − 9 −$ ($

9

9

$

Q.2- Écrire une fonction : newton ( f, x0, eps, h) qui reçoit en paramètres : La fonction f ; Le premier terme x0 de la suite (xn) ; Le réel h strictement positif très proche de 0 ; Le réel eps strictement positif qui représente la précision. La fonction renvoie le premier terme xk de la suite (xn) tel que : | 9 − 9

| ≤ =%7

B- Calcul de la racine n-ème positive d’un réel positif Pour calculer la racine n-ème positive d’un réel positif a, il suffit de trouver la solution positive de l’équation : 9 – = , par la méthode de Newton. Dans ce qui suit, on suppose que a et n sont deux variables globales déclarées et initialisées : a est un réel positif, et n un entier strictement positif. Q. 3- Définir la fonction g (x), qui reçoit en paramètre un réel positif x et qui renvoie : 9 –

.

Q. 4- On suppose que les modules suivant sont importé : from numpy import * from matplotlib.pyplot import *

Écrire le code du programme Python qui permet de tracer la courbe de la fonction g, dans l’intervalle [0 , a]. Le nombre de points générés dans la courbe est : 500

Page 67 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemple : Pour a=2.0 et n=7, on obtient la courbe suivante :

Représentation graphique de la fonction : g(x) = x7 - 2

Q. 5- Écrire le code du programme Python qui utilise la fonction newton (), et qui affiche la valeur approximative de la racine n-ème positive de a :

√ , avec la précision : 10-12 et

h= 0.00001.

Exemple : Pour n=7 et a=2.0, le programme affiche la racine 7ème positive de 2 :

~~~~~~

FIN

1.1040895136738123

~~~~~~

Page 68 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

CNC 2017 - Filières MP-PSI-TSI Sommaire

Partie I : Base de données et langage SQL La compression des fichiers est une pratique aussi courante qu'indispensable en informatique. Elle consiste à stocker les données dans un nouveau format moins encombrant que l'original. Ce gain de place induit d'autres bénéfices dont le principal est l'accélération des transferts entre ordinateurs. Faire circuler moins de bits sur les réseaux diminue le temps de connexion, encombre moins les lignes de communication et limite les dépenses télématiques. La décompression rétablit le fichier dans son état initial. De nombreux algorithmes de compressions existent, chacun ayant sa particularité et surtout un type de données cible. Car toutes les données ne se compressent pas de la même manière. Un algorithme de compression de texte travaillera sur les répétitions du nombre de caractères ou de parties de phrases. Un algorithme de compression d’images travaillera quant à lui sur d’autres domaines comme la différence entre un pixel et un autre. On imagine cependant mal le second algorithme en train de compresser un texte. Néanmoins, tous les algorithmes de compression ont un point commun : leur objectif est de récupérer les données initiales partiellement, voire totalement. La décompression consiste à rétablir les données d’origine à l’aide du fichier compressé. Elle consiste souvent à appliquer l’algorithme de compression en sens inverse.

Types de compressions : Il y a deux types majeurs de compressions : la compression sans perte et la compression avec perte. a- La compression sans perte : Une compression est dite sans perte si les données après décompression sont identiques aux données originelles. Ces compression se basent toutes sur le même principe : la répétition d’une donnée est une répétition de trop. L’objectif va être de supprimer le maximum de répétition pour obtenir une compression plus importante tout en étant capable de retrouver les répétitions retirées. En somme, ces compressions écrivent exactement les mêmes données mais de façon plus concise. Elles sont appliquées à tous types de données et les formats compressés sont très nombreux. Pour ne citer que les plus connus, nous retrouvons les formats : zip, rar, 7z, bz2, gz, ... Les algorithmes, moins connu du grand public, sont aussi très nombreux. Nous retrouvons par exemple le codage de Huffman, les codages de Lempel-Ziv, …

b- La compression avec perte : Une compression est dite avec perte si les données après décompression sont différentes des données originelles.

Page 69 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Elles sont appliquées à des données perceptibles, c'est-à-dire à des images, des sons ou des vidéos. Le principe va consister à supprimer les informations là où les sens de la vue et de l’ouïe ne les perçoivent que très peu. Par exemple, l’œil humain ne distingue que très peu les zones de contraste. Aussi, nous pouvons retirer des détails à ces zones sans trop impacter sur la qualité de l’image. Le nom de format représente directement le type de compression employé : jpeg, mpeg, mp3, divx, ...

Taux de compression : Le taux de compression est une mesure de la performance d'un algorithme de compression. Il est exprimé en pourcentage. Le taux de compression est le gain en volume rapporté au volume initial des données. Plus le taux de compression est élevé, plus la taille du fichier compressé résultant est faible. La formule correspondante s'écrit : @ABC =

−

DAEFFG HB IEJKEGL JMNOLGPPé ∗ DAEFFG EQEDEAFG HB IEJKEGL

On dispose d’une base de données de chemin absolu : "C:\BDcompressions.sql", composée de trois tables : la table Algorithme, la table Fichier et la table Compression, dont les structures sont les suivantes :

Algorithme ( format (texte), type (entier) ) La table Algorithme contient différents formats d’algorithmes de compressions. Le champ format est la clé primaire. Le champ type contient la valeur 1, si l’algorithme de compression est du type avec perte de données, ou 0 sinon. Exemples de données de la table Algorithme : format 7z bz2 gz jpeg rar zip mp3 huffman …

type 0 0 0 1 0 0 1 0 …

Fichier ( numeroF (entier), nomF (texte), tailleF (entier) ) La table Fichier contient des fichiers de différents types : texte, image, son, vidéo … . Le champ numeroF est la clé primaire. Le champ nomF contient le nom complet de chaque fichier. Le champ tailleF contient la taille originale du fichier, exprimée en Octet. Exemples de données de la table Fichier : numeroF 1 2 3 4 …

nomF Cours Python.pdf Nature.bmp Langage SQL.doc Chanson.wav …

tailleF 6 420 768 5 760 054 345 600 47 185 920 … Page 70 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Compression (numeroF (entier), format (texte), tailleC (entier) ) La table Compression contient les compressions de certains fichiers de la table Fichier. Les champs numeroF et format sont des clés étrangères. Le champ tailleC contient la taille du fichier compressé, exprimée en octet. Un fichier de la table Fichiers peut être compressé plusieurs fois, par différents algorithmes de compressions. Exemples de données de la table Compression : numeroF 2 2 2 1 1 4 3 3 …

format jpeg png zip cab zip mp3 zip 7z …

tailleC 291 441 2 622 545 2 160 937 5 768 938 5 818 538 11 364 145 366 133 396 …

I. 1- Écrire, en algèbre relationnelle, une requête qui donne pour résultat : Les noms des fichiers dont la taille originale est comprise entre 1 Kilo-octet et 1 Méga-octet. I. 2- Écrire une requête SQL, qui donne pour résultat : Les noms et les tailles des fichiers textes, dont le nom se termine par : .doc ou .docx, triés dans l’ordre alphabétique des noms des fichiers. I. 3- Écrire une requête SQL qui donne pour résultat : Les noms des fichiers compressés, les formats de compression, les types de compression, et le taux de compression de chaque fichier, dont le taux de compression dépasse 40%, triés dans l’ordre des numéros des fichiers. I. 4- Écrire une requête SQL qui donne pour résultat : Les algorithmes sans perte de données et le compte des fichiers compressés par chacun de ces algorithmes, dont ce compte est égal à 3, 5 ou 8. I. 5- Écrire une requête SQL qui donne pour résultat : Les 3 premiers grands taux de compressions, triés dans l’ordre croissant. I. 6- Écrire un programme Python qui saisi un format de compression, et qui affiche le taux moyen des taux des compressions de ce format, si le format saisi existe dans la base de données. Si le format saisi n’existe pas, le programme doit afficher le message : « Le format saisi n’existe pas dans la BD ». On suppose que le module sqlite3 est importé. Ce module contient les fonctions et permettant de manipuler les bases de données : Connexion à une base de données : connect() Créer un curseur : cursor()

les méthodes

Exécuter une requête : execute() Récupérer le résultat d’une requête :

fetchone(), fetchall()

Page 71 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie II : Programmation Python La compression de HUFFMAN La compression de Huffman est une méthode de compression de données sans perte proposé par « David Huffman » en 1952. C’est un processus qui permet de compresser des données informatiques afin de libérer de la place dans la mémoire d'un ordinateur. Or tout fichier informatique (qu'il s'agisse d'un fichier texte, d'une image ou d'une musique …) est formé d'une suite de caractères. Chacun de ces caractères étant luimême code par une suite de 0 et de 1. L'idée du codage de Huffman est de repérer les caractères les plus fréquents et de leur attribuer des codes courts (c'est-a-dire nécessitant moins de 0 et de 1) alors que les caractères les moins fréquents auront des codes longs. Pour déterminer le code de chaque caractère on utilise un arbre binaire. Cet arbre est également utilisé pour le décodage. Dans cette partie, on s’intéressera à appliquer la compression de Huffman pour compresser une liste de nombres entiers, contenant des éléments en répétition. Exemple : L = [12,29,55,29,31,8,12,46,29,8,12,29,31,29,8,29,8] NB : Dans toute cette partie, on suppose que la liste L contient au moins deux éléments différents.

II. 1- L’espace mémoire occupé par un entier positif Quel est le plus grand nombre entier positif, avec bit de signe, qu’on peut coder sur 12 bits ? Justifier votre réponse.

II. 2- Écriture binaire d’un nombre entier II. 2- a) Écrire la fonction : binaire(N), qui reçoit en paramètre un entiers naturel N, et qui retourne une chaine de caractères qui contient la représentation binaire de N. Le bit du poids le plus fort se trouve à la fin de la chaine. Ne pas utiliser la fonction prédéfinie bin( ) de Python. Exemple : binaire (23) retourne la chaine : "11101"

II. 2- b) Déterminer la complexité de la fonction binaire (N). II. 2- c) La méthode dite de Horner (William George Horner : 1786-1837) est une méthode très pratique, utilisée pour améliorer le calcule de la valeur d’un polynôme, en réduisant le nombre de multiplications. Soit le polynôme P à coefficients réels suivant :

P(x) = an*xn + an-1*xn-1 + … + a2*x2 + a1*x + a0 Pour calculer P(k), la méthode de Horner effectue le calcul comme suit :

P(k) = (( … ((an*k+an-1)*k+an-2)*k+ … +a2)*k+a1)*k+a0 En utilisant le principe de la méthode de Horner, écrire la fonction de complexité linéaire : entier(B), qui reçoit en paramètre une chaine de caractères B contenant la représentation binaire d’un entier naturel, dont le premier bit est celui du poids le plus faible, et qui calcule et retourne la valeur décimale de cet entier. 0

1

2

3

4

Exemple : entier ("11101") retourne le nombre entier : 23 (23 = 1*2 + 1*2 + 1*2 + 0*2 + 1*2 ) Page 72 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

II. 3- Liste des fréquences : La première étape de la méthode de compression de Huffman consiste à compter le nombre d’occurrences de chaque élément de la liste des entiers. Écrire une fonction : frequences(L), qui reçoit en paramètre une liste d’entiers L, et qui retourne une liste de tuples : Chaque tuple est composé d’un élément de L et de son occurrence (répétition) dans L. Les premiers éléments des tuples de la liste des fréquences doivent être tous différents (sans doublon). Exemple : L= [ 12, 29, 46, 29, 31, 8, 12, 55, 29, 8, 12, 29, 31, 29, 8, 29, 8 ] La fonction frequences (L) retourne la liste F = [ (8, 4), (12, 3), (46, 1), (55, 1), (29, 6), (31, 2) ]

II. 4- Tri de la liste des fréquences : La liste F des fréquences, des différents éléments de la liste des entiers, étant créée. L’étape suivante èmes est de trier cette liste F dans l’ordre croissant des occurrences (les 2 éléments des tuples). Écrire la fonction: tri(F), qui reçoit en paramètre la liste F des fréquences, et qui trie les éléments de la liste F dans l’ordre croissant des occurrences. Cette fonction doit être de complexité quasi-linéaire O(nlog(n)). Ne pas utiliser ni la fonction sorted( ), ni la méthode sort( ) de Python. Exemple : F = [ (12, 3), (29, 6), (55, 1), (31, 2), (8, 4), (46, 1) ] La fonction tri (F) retourne la liste : [ (46, 1), (55, 1), (31, 2), (12, 3), (8, 4), (29, 6) ]

II. 5- Création de l’arbre binaire de HUFFMAN : Pour représenter un arbre binaire, on va utiliser une liste composée de trois éléments : Chaque nœud est représenté par la liste : [ Père , [ Fils gauche ] , [ Fils droit ] ] Chaque feuille est représentée par la liste : [ Feuille , [ ] , [ ] ]

Exemple : L’arbre binaire suivant, sera représenté par la liste :

A = [24,[17,[],[]],[9,[12,[],[]],[]]]

L’arbre binaire de Huffman est crée à partir de la liste des fréquences, selon le procédé suivant : Trier la liste des fréquences dans l’ordre croissant des occurrences ; Tant que la liste des fréquences contient au moins deux éléments, on répète les opérations : •

ème

Retirer les deux premiers éléments dont les poids (2

élément de chaque tuple) sont les plus

faibles, et créer un tuple dont le poids est la somme des poids de ces deux éléments ; •

Insérer le tuple obtenu dans la liste des fréquences, de façon à ce qu’elle reste croissante.

Les feuilles de l’arbre binaire obtenu sont les différents éléments de la liste à compresser. Page 73 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Exemple : La liste F des fréquences suivante, est triée dans l’ordre croissant des occurrences. F = [ (46, 1), (55, 1), (31, 2), (12, 3), (8, 4), (29, 6) ]

1ère étape

A

F = [ (46, 1), (55, 1), (31, 2), (12, 3), (8, 4), (29, 6) ] Retirer : (46, 1) et (55, 1) Insérer le tuple (A , 2) dans la liste F La liste F triée devient : F = [ (31, 2), (A , 2), (12, 3), (8, 4), (29, 6) ]

2ème étape

A

F = [ (31 , 2), (A , 2), (12, 3), (8, 4), (29, 6) ] Retirer : (31 , 2) et (A , 2) Insérer le tuple (A , 4) dans la liste F La liste F triée devient : F = [ (12, 3), (8, 4), (A , 4), (29, 6) ]

3ème étape

B

F = [ (12, 3), (8, 4), (A , 4), (29, 6) ] Retirer : (12 , 3) et (8 , 4) Insérer le tuple (B , 7) dans la liste F La liste Ftriée devient : F = [ (A, 4), (29, 6), (B , 7) ]

A 4ème étape F = [ (A, 4), (29, 6), (B , 7) ] Retirer : (A , 4) et (29 , 6) Insérer le tuple (A , 10) dans la liste F La liste F triée devient : F = [ (B , 7), (A , 10) ]

A 5ème étape F = [ (B , 7), (A , 10) ] Retirer : (B , 7 ) et (A , 10) Insérer le tuple (A , 17) dans la liste F La liste F triée devient : F = [ (A , 17) ]

La liste F ne compte plus qu’un seul élément, le procédé est arrêté.

Page 74 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

II. 5- a) Écrire la fonction de complexité linéaire : insere(F,T), qui reçoit en paramètre la liste F des fréquences triée dans l’ordre croissant des occurrences, et un tuple T, de même nature que les éléments de F. La fonction insère le tuple T dans F de façon à ce que la liste F reste triée dans l’ordre croissant des occurrences. Exemple : F = [ (46, 1), (55, 1), (31, 2), (12, 3), (8, 4), (29, 6) ] et T = (17, 5). Après l’appel de la fonction : insere (F, T), la liste F devient : F = [ (46, 1), (55, 1), (31, 2), (12, 3), (8, 4), (17, 5), (29, 6) ]

II. 5- b) Écrire la fonction : arbre_Huffman(F), qui reçoit en paramètre la liste des fréquences F, composée des tuples formés des différents éléments de la liste à compresser, et de leurs occurrences. La fonction retourne un arbre binaire de Huffman, crée selon le principe décrit ci-dessus.

II. 6- Construction du dictionnaire des codes de HUFFMAN : On suppose que l’arbre binaire de Huffman est crée selon le principe de la question précédente. L’étape suivante est de construire un dictionnaire où les clés sont les différents éléments de la liste à compresser (les feuilles de l’arbre de Huffman), et les valeurs sont les codes binaires de Huffman correspondants.

Parcours de l’arbre binaire de HUFFMAN : On associe le code 0 à chaque branche de gauche et le code 1 à chaque branche de droite. Pour obtenir le code binaire de chaque feuille, on parcourt l'arbre à partir de la racine jusqu'aux feuilles en rajoutant à chaque fois au code 0 ou 1 selon la branche suivie :

Ainsi, en parcourant l’arbre, on obtient les codes suivants : Feuilles 12 8 31 46 55 29

Codes "00" "01" "100" "1010" "1011" "11"

Page 75 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Écrire la fonction : codes_Huffman(A,code,codesH), qui reçoit trois paramètres : A : est un arbre binaire de Huffman, crée selon le principe de la question précédente. code : est une chaine de caractère initialisée par la chaine vide. codesH : est un dictionnaire initialisé par le dictionnaire vide La fonction effectue un parcours de l’arbre, en ajoutant dans le dictionnaire codesH, les feuilles de l’arbre comme clés et les codes binaires correspondants comme valeurs des clés. Exemple : codesH = { } # codesH est un dictionnaire vide. code = " "

# code est une chaine de caractères vide.

Après l’appel de la fonction : codes_Huffman (Arbre, code, codesH), Le contenu du dictionnaire codesH est : { 55 : '1011' , 8 : '01' , 12 : '00' , 29 : '11' , 46 : '1010' , 31 : '100' }

II. 7- Compression de la liste des entiers : Le dictionnaire des codes binaires contient les différents éléments de la liste à compresser, et leurs codes Huffman binaires correspondants. On peut maintenant procéder à la compression de la liste des entiers. Écrire la fonction : compresse(L,codesH), qui reçoit en paramètres la liste L des entiers, et le dictionnaire codesH des codes binaires Huffman. La fonction retourne une chaine de caractères contenant la concaténation des codes binaires Huffman correspondants à chaque élément de L. Exemple : L= [ 12 , 29 , 46 , 29 , 31 , 8 , 12 , 55 , 29 , 8, 12, 29, 31, 29, 8, 29, 8 ] codesH = { 55: '1011' , 8: '01' , 12: '00' , 29: '11' , 46: '1010' , 31: '100' } La fonction compresse (L, codesH) retourne la chaine : "0011101011100010010111101001110011011101"

II. 8- Décompression de la chaine de caractères binaires : L’opération de décompression consiste à retrouver la liste initiale des nombres entiers, à partir de la chaine binaire et du dictionnaire des codes. Écrire la fonction : decompresse(codesH, B), qui reçoit en paramètres le dictionnaire codesH des codes de Huffman, et la chaine de caractères binaires B. La fonction construit et retourne la liste initiale. Exemple : B = "0011101011100010010111101001110011011101" codesH = { 55: '1011', 8: '01', 12: '00', 29: '11', 46: '1010', 31: '100' } La fonction decompresse (codesH , B) retourne la liste initiale : [ 12, 29, 46, 29, 31, 8, 12, 55, 29 , 8, 12, 29, 31, 29, 8, 29, 8 ]

Page 76 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Partie III : Calcul scientifique Calcul de la matrice inverse d’une matrice carrée inversible

Méthode : Élimination de ‘Gauss-Jordan’ En mathématiques, l'élimination de « Gauss-Jordan », aussi appelée pivot de Gauss, nommée en hommage à Carl Friedrich Gauss et Wilhelm Jordan, est un algorithme de l'algèbre linéaire pour déterminer les solutions d'un système d'équations linéaires, pour calculer l'inverse d'une matrice carrée inversible ou pour déterminer le rang d'une matrice… Pour calculer la matrice inverse d’une matrice carrée M inversible, la méthode de l’élimination de « GaussJordan » consiste à effectuer des transformations, simultanément sur les deux matrices : la matrice M, et la matrice identité E de même dimension que M. Le but de la méthode de l’élimination de « Gauss-Jordan » est de transformer la matrice M en matrice identité, tout en effectuant simultanément les mêmes opérations (effectuer les mêmes échanges, utiliser les mêmes valeurs des pivots …), sur les deux matrices M et E. La matrice E contient, alors, la matrice inverse de la matrice M initiale. Exemple : Matrice carrée inversible M :

Matrice identité E, de même dimension que M :

Après les transformations, les deux matrices M et E deviennent ainsi : Matrice M transformée en identité:

E contient l’inverse de la matrice M initiale :

On suppose que le module numpy est importé :

import numpy as np Le module numpy contient les méthodes et les fonctions permettant de manipuler les matrices. On rappelle que les indices des listes et tableaux en Python commencent à 0. Exemple : M = np.array( [ [ 1, -1, 2, -2 ] , [ 3, 2, 1, -1 ] , [ 2, -3, -2, 1 ] , [ -1, -2, 3, -3 ] ] , float )

Cette instruction permet de créer la matrice M suivante :

Page 77 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

III. 1- Matrice inversible : Une matrice carrée est inversible, si son déterminant est différent de 0. Le module numpy contient un sous-module appelé : linalg. Ce dernier contient la méthode : det () qui reçoit en paramètre une matrice, et qui retourne la valeur du déterminant de cette matrice. Écrire la fonction : inversible(M), qui reçoit en paramètre une matrice carrée M, et qui retourne True si la matrice M est inversible, sinon, elle retourne False.

III. 2- Matrice identité : Écrire la fonction : identite(n), qui reçoit en paramètre un entier strictement positif n, et qui crée et retourne la matrice identité d’ordre n (n lignes et n colonnes), de nombres réels. Exemple : La fonction identite (4) retourne la matrice identité E d’ordre 4 suivante :

III. 3- Opération de transvection : Écrire une fonction : transvection(M,p,q,r), qui reçoit en paramètres une matrice M, deux entiers p et q représentant les indices de deux lignes dans la matrice M, et un nombre réel r. Dans la matrice M, la fonction remplace la ligne p par la ligne résultat de la combinaison linéaire des deux lignes p et q, suivante : Mp+r*Mq. Exemple : Matrice M :

Après l’appel : transvection (M, 2, 0, -3.), la matrice M devient :

III. 4- Échanger deux lignes dans une matrice : Écrire la fonction : echange_lignes(M,p,q), qui reçoit en paramètres une matrice M, et deux entiers p et q représentant respectivement deux indices de deux lignes dans la matrice M. la fonction échange les lignes p et q dans la matrice M. Exemple : Matrice M :

Après l’appel : echanger _lignes (M, 1, 3), les lignes 1 et 3 de la matrice M sont échangées :

Page 78 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

III. 5- Recherche de la ligne du pivot dans une colonne de la matrice : Écrire la fonction : ligne_pivot(M,c), qui reçoit en paramètres une matrice M, et un entier c représentant une colonne dans la matrice M. La fonction retourne l’indice p tel que : | M[p, c] | = max { | M[i, c] | / 0 ≤ i ≤ c } Exemple : Si la matrice M est la suivante :

La fonction ligne_pivot (M, 2) retourne l’indice : 1, car, dans la colonne 2, l’élément -6.0 est le plus grand en valeur absolue, parmi les éléments des lignes 0, 1 et 2.

III. 6- Transformer la matrice M en matrice triangulaire inférieure : Écrire la fonction : triangulaire_inf(M,E), qui reçoit en paramètre une matrice carrée inversible M, et une matrice identité E de même dimension que M. La fonction transforme la matrice M en matrice triangulaire inférieure. Les transformations effectuées sur la matrice M, doivent être effectuées simultanément sur la matrice E. Exemple : Après l’appel de la fonction triangulaire_inf (M, E), les matrices M et E deviennent ainsi : Matrice M triangulaire inférieure

Matrice E

III. 7- Transformer la matrice triangulaire inférieure M en matrice diagonale : Les deux matrices M et E sont les résultats de la fonction triangulaire_inf (M, E). La matrice M est devenue triangulaire inférieure. Écrire la fonction : diagonale(M,E), qui transforme la matrice M en matrice diagonale. Les transformations effectuées sur la matrice M, doivent être aussi effectuées simultanément sur la matrice E. Exemple : Après l’appel de la fonction diagonale (M, E), les matrices M et E deviennent ainsi : Matrice M diagonale

Matrice E

Page 79 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

III. 8- Calcul de la matrice inverse par élimination de « Gauss-Jordan » : Écrire la fonction : inverse(M), qui reçoit en paramètre une matrice carrée inversible M, et qui calcule et renvoie la matrice inverse de M. (Ne pas utiliser la méthode prédéfinie inv( ) de Python) Exemple : M matrice carrée inversible :

La fonction inverse (M) renvoie la matrice inverse de M :

III. 9- Matrice stockée dans un fichier texte : On suppose avoir créé un fichier texte contenant une matrice carrée. Chaque ligne du fichier contient une ligne de la matrice, et les éléments de chaque ligne du fichier sont séparés par le caractère espace. Exemple :

Matrice carrée inversible d’ordre 6, stockée dans un fichier texte

Écrire la fonction : matrice_fichier(ch), qui reçoit en paramètre une chaîne de caractère ch, qui contient le chemin absolu du fichier texte, contenant une matrice carrée : Si cette matrice est inversible, la fonction renvoie sa matrice inverse ; Si cette matrice n’est pas inversible, la fonction affiche le message « Matrice non inversible » ; Si le fichier texte ne se trouve pas à l’emplacement spécifié dans la chaine ch, l’exception FileNotFoundError sera levée. La fonction affiche le message : « Fichier texte inexistant »

------- FIN DE l’ÉPREUVE ------

Page 80 sur 109

Annales CNC – Informatique

OMAR ZEKRAOUI

Correction CNC 2019 – MP Sommaire Exercice : Q1 : def grands(L, x) : c=0 for e in L : if e>x: c=c+1 return c Q2 : Complexité linéaire O(n) avec n=len(L) Q3 : def petits(L,x): c=0 for e in L : if e