REPUBLIQUE TUNISIENNE
Ministère de l'Enseignement Supérieur,
de la Recherche Scientifique
Concours Nationaux d’Entrée
aux Cycles de Formation d’Ingénieurs
Session 2019
يملعلا
ةيسنوتلا ةيروهمجلا
ثحبلاو
يلاعلا
ميلعتلا
ةرازو
لوخدلل ةينطولا تارظانملا
نيسدنهملا
نيوكت لحارم ىلإ
2019
ةرود
Altérative de Correction
Concours Mathématique et Physique, Physique et Chimie et Technologie
Epreuve d’Informatique
PROBLEME 1
Partie 1 : Représentation de la structure d’arbre binaire
class Node :
def __init__ (self, val, leftNode = None, rightNode = None):
self.label = val # chaine de caractèr
self.left = leftNode # instance de la classe Node ou None
self.right= rightNode # instance de la classe Node ou None
question 1
def isLeaf(self) :
return self.left is self.right is None
def __repr__(self) :
return self.label
def linearise(self) : #méthode récursive retournant la liste des branches
if self.isLeaf() : # traitement si le nœud est une feuille
return [[self]]
else :
if self.left != None :
L1 = self.left.linearise() # traitement récursif du nœud fils gauche
else :
L1=[]
if self.right != None :
L2 = self.right.linearise() # traitement récursif du nœud fils gauche
else :
L2=[]
return [[self]+e for e in L1]+[[self]+e for e in L2]
question 2
def __len__(self): # méthode récursive
if self.isLeaf():
return 1
else:
n = len(self.left) if self.left is not None else 0
n += len(self.right) if self.right is not None else 0
return n + 1
question 3
Publicité
def __str__(self): # méthode récursive
return "Node({},{},{})".format(repr(self.label), self.left, self.right)
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 1/
6
Partie 2 : Représentation du modèle de décision
question 1
class DecisionNode(Node):
question 2
def __init__(self, label, distr, seuil = 0.5, left= None, right = None):
super().__init__(label, left, right)
self.distr = distr
self.seuil = seuil
question 3
def outcome(self, val):
assert not self.isLeaf()
if val >= self.seuil:
return self.left
return self.right
question 4
def __str__(self):
paths = self.linearise()
lstrules = []
for path in paths:
rule = ["{}{}{}".format(cn.label,
">=" if cn.left == nn else "<",
cn.seuil)
for cn, nn in zip(path, path[1:])]
lstrules.append("IF {} THEN décision = {}".format(
" AND ".join(rule), path[-1].distr))
return "\n".join(lstrules)
question 5
def predict(self, dicobs):
currentNode = self
while True:
if currentNode.isLeaf() or currentNode.label not in dicobs:
return currentNode.distr
currentvalue = dicobs[currentNode.label]
currentNode = currentNode.outcome(currentvalue)
class DecisionForest:
question 6
def __init__(self):
self.listNodes = []
question 7
def add(self, newinstance):
self.listNodes.append(newinstance)
question 8
def predict(self, dictobs):
if len(self.listNodes) == 0:
return {0:0.5, 1:0.5}
else:
p0 = 0
for dn in self.listNodes:
distr = dn.predict(dictobs)
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 2/
Publicité
6
p0 += distr[0]
p0 /= len(self.listNodes)
return {0:p0, 1:1-p0}
Partie 3 : Apprentissage
1.
import numpy as np
2.
def CountValues(DSET, index):
return len(set(DSET[:,index]))
3.
def EvalDistr(DSET):
if DSET.size == 0:
return {0:0.5, 1:0.5}
else:
p1 = (DSET[:,-1]).sum()/len(DSET)
return {0:1-p1, 1:p1}
4.
def IsPure(DSET):
return 1 in EvalDistr(DSET).values()
5.
def IsQualitative(DSET):
return [set(DSET[:,i]) <= {0,1} for i in range(DSET.shape[-1])]
6.
def Cut(DSET, colonnes, obs, S = 0.5):
robs = colonnes[:]
robs.remove(obs)
cindex = colonnes.index(obs)
lst1 = []
lst2 = []
for row in DSET:
vals = row.tolist()
vals.pop(cindex)
if row[cindex] >= S:
lst1.append(vals)
else:
lst2.append(vals)
p1 = len(lst1)/len(DSET)
p2 = 1 - p1
return robs, [np.array(lst1), np.array(lst2)], [p1, p2]
7.
def Impurity(DSET, colonnes, obs, S = 0.5):
_, [d1, d2], [p1, p2] = Cut(DSET, colonnes, obs, S)
return p1 min(EvalDistr(d1).values()) + p2 min(EvalDistr(d2).values())
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 3/
6
8.
def SortObs(DSET, colonnes, obs):
col_index = colonnes.index(obs)
Lc = [(v,d) for v, d in zip(DSET[:,col_index], DSET[:,-1])]
return sorted(Lc)
9.
def BestCut(DSET, colonnes, obs, qual):
col_index = colonnes.index(obs)
Publicité
if qual[col_index]:
return (0.5, Impurity(DSET, colonnes, obs))
Lc = SortObs(DSET, colonnes, obs)
Lseuil = []
if IsPure(DSET):
Lseuil.append(max(Lc)[0])
else:
for (vc,dc),(vn,dn) in zip(Lc, Lc[1:]):
if dc != dn:
Lseuil.append((vc+vn)/2)
impurities = [Impurity(DSET, colonnes, obs, s) for s in Lseuil]
best_index = impurities.index(min(impurities))
return (Lseuil[best_index], impurities[best_index])
10.
def BuildTree(DSET, colonnes, qual):
distr = EvalDistr(DSET)
if len(DSET) == 0 or IsPure(DSET) or len(colonnes) == 1:
return DecisionNode(colonnes[-1], distr)
bestImp = np.inf
for obs in colonnes[:-1]:
sBest, vBest = BestCut(DSET, colonnes, obs, qual)
if bestImp > vBest:
bestObs = obs
bestImp = vBest
bestT = sBest
root = DecisionNode(bestObs, distr, bestT)
cols, [ds1, ds2], [p1, p2] = Cut(DSET, colonnes, bestObs, bestT)
rqual = qual[:]
rqual.pop(colonnes.index(bestObs))
root.left = BuildTree(ds1, cols, rqual)
root.right = BuildTree(ds2, cols, rqual)
return root
PROBLEME 2
Partie 1 : algèbre relationnelle
1. Π
𝑑𝑠_𝑖𝑑,𝑑𝑠_𝑛𝑎𝑚𝑒,𝑑𝑠_𝑑𝑒𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 (𝜎𝑓𝑜𝑟𝑚𝑎𝑡=′𝑐𝑠𝑣′(𝐷𝑎𝑡𝑎𝑆𝑒𝑡))
2. Π𝑐𝑙𝑠_𝑑𝑒𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛( 𝜎𝑙𝑎𝑛𝑔𝑢𝑎𝑔𝑒=′𝑃𝑦𝑡ℎ𝑜𝑛′𝑒𝑡 𝑐𝑎𝑡𝑒𝑔𝑜𝑟𝑦=′𝐾𝑁𝑁′(𝐶𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑒𝑢𝑟 ⋈𝑐𝑙𝑠_𝑖𝑑 𝐶𝑜𝑚𝑏𝑖𝑛𝑒⋈𝑚_𝑛𝑎𝑚𝑒 𝑀𝑒𝑡ℎ𝑜𝑑)
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 4/
6
Partie 2 : SQL
1.
SELECT ds_id
FROM Classifieur
WHERE error_rate < 0.3 ;
2.
SELECT D.ds_id, ds_name
FROM DataSet AS D, Classifieur AS C
WHERE (D.ds_id = C.ds_id)
EXCEPT
SELECT D.ds_id, ds_name
FROM DataSet AS D, Classifieur AS
WHERE (D.ds_id = C.ds_id) AND (language <> 'Python');
3.
SELECT D.ds_id, COUNT(DISTINCT M.m_name) AS NB_M
Publicité
FROM DataSet AS D,
Classifieur AS C,
Combine AS CM,
Method AS M
WHERE (D.ds_id = C.ds_id) AND
(C.cls_id = CM.cls_id) AND
(CM.m_name = M.m_name)
GROUP BY C.cls_id;
4.
UPDATE DataSet
Set nb_instances = nb_instances + 100
WHERE ds_id IN
(SELECT ds_id
FROM Classifieur
WHERE language ='Python');
Partie 3 : sqlite3
5.
import sqlite3
cnx = sqlite3.connect("CMP.db")
cur = cnx.cursor()
sql_tbl = """
CREATE TABLE Method
(
m_name TEXT PRIMARY KEY,
category TEXT,
m_description TEXT
);
"""
cur.execute(sql_tbl)
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 5/
6
with open("DataMeth.txt") as f:
ldata = [l.strip().split('#') for l in f]
sql_ins = """
INSERT INTO Method VALUES(?,?,?);
"""
cur.executemany(sql_ins, ldata)
cnx.commit()
sql_sel = """
SELECT ds_id, AVG(error_rate) AS M_erreur
FROM Classifieur
GROUP BY ds_id
ORDER BY ds_id
"""
cur.execute(sql_sel)
x, y = zip(*cur.fetchall())
import matplotlib.pyplot as plt
plt.plot(x,y)
plt.show()
cnx.close()
Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 6/
6