Concours Nationale Commun Session 2017
Épreuve d'informatique
Filière MP/PSI/TSI
Durée : 2H
Correction
Partie I : Bae de données et langage SQL
I. 1 : Ecrire 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.
πnomF(σ(tailleF≥1024∧tailleF≤1000000) (Fichier))
I. 2 : Ecrire 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.
SELECT nomF, tailleF
FROM Fichier
WHERE nomF like "%.doc" OR nomF like "%.docx"
ORDER BY nomF;
I. 3: Ecrire 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.
SELECT nomF, [Link], type,(1-tailleC/tailleF)*100 AS taux
FROM Algorithme A JOIN Fichier F JOIN Compression C ON
[Link]=[Link] AND [Link]=[Link]
WHERE taux>=40
ORDER BY [Link];
I. 4 : Ecrire 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.
SELECT [Link], COUNT(*)
FROM Algorithme A JOIN Compression C ON [Link]=[Link]
WHERE type=0
GROUP BY [Link]
HAVING COUNT(*) IN (3,5,8);
CNC INFO MP-PSI-TSI : 2017 1 [Link]
I. 5 : Ecrire une requête SQL qui donne pour résultat: Les 3 premiers grands taux de compressions, triés
dans l'ordre croissant.
SELECT taux
FROM (SELECT (1-tailleC/tailleF) * 100 AS taux
FROM Compression C JOIN Fichier F ON [Link]=[Link]
ORDER BY taux DESC
Limit 0,3)
ORDER BY taux ASC
I. 6 : Ecrire 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".
import sqlite3 as s3
db=[Link]("C:/[Link]")
cur=[Link]()
req=" SELECT format FROM Algorithme "
[Link](req)
L=[Link]()
L=[L[i][0] for i in range(len(L))]
format=input("saisir le format de compression: ")
if format in L:
req="SELECT AVG(1-(tailleC/tailleF)*100)
FROM Compression C JOIN Fichier F ON [Link]=[Link]
WHERE [Link]=?"
[Link](req,[format])
moy=[Link]()[0]
print("Le taux moyen de compression du format %c est: %.2f"
%(format,moy))
[Link]()
[Link]()
else:
print("Le format saisi n'existe pas dans la BD")
CNC INFO MP-PSI-TSI : 2017 2 [Link]
Partie 2 : Programmation pyton
II. 1- 'espace mémoire occupé par un entier posotif
Quel est le plus grand nombre entier positif, avec bit de signe, qu'on peut coder sur 12 bits? Justifier
votre réponse.
Sur 12bits, après avoir réservé un bit pour le signe, il reste 11 bits, s'ils sont tous à 1 la valeur
représentée est : 211 − 1
II. 2 - Ecriture binaire d'un nombre entier
II. 2. a) Ecrire la fonction : binaire(N), qui reçoit en paramètre un entier 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.
def binaire(N):
if N==0:return("0")
ch=""
while N!=0:
ch=str(N%2)+ch
N=N//2
return(ch)
II. 2.b) Déterminer la complexité de la fonction binaire(N).
Le coût de la fonction binaire(N) est celui de la boucle while, celle-ci itérera autant de fois que le
nombre de bits de la représentation binaire de N, or le nombre de bits de N correspond à log2(N)+1.
A chaque itération de la boucle while un bloc constant s'exécute composé de deux affectations, une
concaténation, un calcul de quotient, un calcul de reste et un appel à la fonction str dont le cout est c
considéré comme étant constant indépendant de N, s'ajoute à ce coût un test et une affectation avant la
boucle, donc en considérant N la taille du problème, la complexité dans le pire des cas est:
T(N)=1+1+log2(N)∗(c+1+1+1+1+)=O(log2(N))
II. 2. c) 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ère 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.
def entier(B):
N=len(B)
n=0
for i in range(-1,-N-1,-1):
n=n*2+int(B[i])
return(n)
def entier(B):
n=0
while B!="":
n=n*2+int(B[-1])
B=B[:-1]
return(n)
CNC INFO MP-PSI-TSI : 2017 3 [Link]
II.3 - Liste des fréquences
Ecrire une fonction: frequence(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).
def frequence(L):
L2=[]
E=set(L)
for e in E:
[Link]((e, [Link](e)))
return(L2)
II. 4 Tri de la liste des fréquences
Ecrire la fonction: tri(F), qui reçoit en paramètre la liste F des fréquences, et qui trie les éléments de
liste F dans l'ordre croissant des occurrences. Cette fonction doit être de complexité quasi-linéaire
O(nlog(n)). Ne pas utiliser la fonction sorted() ou la méthode sort() de Python.
#le tri fusion est un tri de complexité O([Link](n))
def fusion(L1, L2):
res = [ ]
i, j= 0, 0
while i< len(L1) and j< len(L2):
if L1[i][1] <= L2[j][1]:
[Link](L1[i])
i += 1
else:
[Link](L2[j])
j += 1
return res+L1[i:]+L2[j:]
def triFusion(L):
if len(L) <= 1: return L
m = len(L) // 2
return fusion( triFusion(L[:m]),triFusion(L[m:]))
II. 5 Création de l'arbre binaire de HUFFMAN
II.5-a) Ecrire 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.
def insere(F,T):
[Link](T)
i=len(F)-1
while i>0 and T[1]<F[i-1][1]:
F[i]=F[i-1]
i-=1
F[i]=T
CNC INFO MP-PSI-TSI : 2017 4 [Link]
II.5-b) Ecrire 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.
def arbre_Huffman(F):
while len(F)>1:
t1=[Link](0)
t2=[Link](0)
if type(t1[0])!=list:
if type(t2[0])!=list:
t3=([t1[1]+t2[1],[t1[0],[],[]],[t2[0],[],[]]],t1[1]+t2[1])
else:
t3=([t1[1]+t2[1],[t1[0],[],[]],t2[0]],t1[1]+t2[1])
else:
if type(t2[0])!=list:
t3=([t1[1]+t2[1],t1[0],[t2[0],[],[]]],t1[1]+t2[1])
else:
t3=([t1[1]+t2[1],t1[0],t2[0]],t1[1]+t2[1])
insere(F,t3)
return(F[0][0])
II. 6 Construction du dictionnaire des codes HUFFMAN
Ecrire la fonction: codes_Huffman(A,code,codesH), qui reçoit trois paramètres:
A: est un arbre binnaire de Huffman, crée selon le principe de la question précédente.
code: est une chaine de caractères 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.
##définition de quelques fonctions de base pour manipuler un arbre binaire
#Fonction qui détermine si un arbre a est vide ou non.
def vide(a): return a==[]
#Fonction qui retourne la valeur de la racine d’un arbre (étiquette).
def val(a): if a!=[]: return a[0]
#Fonction qui retourne le fils gauche de l’arbre a .
def FG(a):
if not vide(a): return a[1]
else: return []
#Fonction qui retourne le fils Droit de l’arbre a .
def FD(a):
if not vide(a): return a[2]
else: return []
CNC INFO MP-PSI-TSI : 2017 5 [Link]
#déterminer si un nœud est une feuille
def estFeuille(a):
if vide(a) : return False
return vide(FG(a)) and vide(FD(a))
def code_Huffman(A,code,codesH):
if vide(A): return
if estFeuille(A) : codesH[val(A)]=code
if not vide(FG(A)): code_Huffman(FG(A),code+'0',codesH)
if not vide(FD(A)): code_Huffman(FD(A),code+'1',codesH)
II. 7- Compression de la liste des entiers
Ecrire 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.
def compresse(L,codesH):
ch=""
for e in L:
ch+=codesH[e]
return ch
II. 8- Décompression de la chaine de caractères binaires
Ecrire 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.
def decompresse(codesH,B):
L=[]
K=list([Link]())
V=list([Link]())
ch=""
for i in range(len(B)):
ch=ch+B[i]
if ch in V:
[Link](K[[Link](ch)])
ch=""
return L
CNC INFO MP-PSI-TSI : 2017 6 [Link]
Partie 3 : Calcul scientifique
Calcul de la matrice inverse d'une matrice carré inversible
Méthode : Elimination de 'Gauss-Jordan'
III. 1- Matrice inversible
Ecrire 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.
import numpy as np
from [Link] import det
def inversible(M):
return det(M)!=0
III. 2- Matrice identité
Ecrire 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.
def identite(n):
M=[Link]([n*[0.] for i in range(n)])
for i in range(n):
M[i][i]=1.
return(M)
III.3- Opération de transvection
Ecrire 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.
def transvection(M, p, q, r):
M[p]=M[p]+r*M[q]
III.4- Echanger deux lignes dans une matrice
Ecrire 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.
def echange_lignes(M,p,q):
for i in range(len(M)):
M[p][i],M[q][i]=M[q][i],M[p][i]
CNC INFO MP-PSI-TSI : 2017 7 [Link]
III.5- Recherche de la ligne du pivotdans une colonne de la matrice
Ecrire 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}
def ligne_pivot(M,c):
imax=0
for i in range(1,c+1):
if abs(M[imax][c])<abs(M[i][c]):
imax=i
return(imax)
III.6- Transformer la matrice M en matrice triangulaire inférieure:
Ecrire 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.
def triangulaire_inf(M,E):
for i in range(len(M)-1,0,-1):
p=ligne_pivot(M,i)
echange_lignes(M,i,p)
echange_lignes(E,i,p)
for k in range(i):
r=-M[k][i]/M[i][i]
transvection(M,k,i,r)
transvection(E,k,i,r)
III.7- Transformer la matrice triangulaire inférieure 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. Ecrire 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.
def diagonale(M,E):
for i in range(len(M)-1):
for k in range(i+1,len(M)):
c=-M[k][i]/M[i][i]
transvection(M,k,i,c)
transvection(E,k,i,c)
CNC INFO MP-PSI-TSI : 2017 8 [Link]
III.8 – Calcul de la matrice inverse par élimination de 'Gauss-Jordan'
Ecrire 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)
def inverse(M):
if not inversible(M):
return(None)
else:
E=identite(len(M))
triangulaire_inf(M,E)
diagonale(M,E)
for i in range(len(M)):
c=1/M[i][i]
M[i]*=c
E[i]*=c
return(E)
III.9- Matrice stockée dans un fichier texte
Ecrire la fonction: matrice_fichier(ch), qui reçoit en paramètre une chaine de caractère
ch, qui contient le chemin absolu du fichier texte, contenant une matrice carrée:
def matrice_fichier(ch):
try:
f=open(ch,'r')
except FileNotFoundError:
print("Fichier texte inexistant")
else:
L=[]
M=[]
for l in f:
l=[Link]()
l=[float(x) for x in l]
[Link](l)
[Link]()
M=[Link](M)
inv=inverse(M)
if inv!=None:
return(inv)
else:
print("Matrice non inversible")
CNC INFO MP-PSI-TSI : 2017 9 [Link]
