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

ةرود

Concours Mathématique et Physique, Physique et Chimie et Technologie

Corrigé épreuve d’informatique

PROBLEME 1

Partie 1 : Représentation de la structure d’arbre binaire

1. la méthode isLeaf

def isLeaf(self):

return self.left == None and self.right == None

#ou bien return self.left is self.right is None

2. la méthode __len__

def __len__(self):

if self.isLeaf():

return 1

elif self.left == None:

return 1 + len(self.right)

elif self.right == None:

return 1 + len(self.left)

else:

return 1 + len(self.left) + len(self.right)

3. la méthode __str__

def __str__(self):

if self.isLeaf():

return "Node("+self.label+")"

else:

return "Node("+self.label+","+str(self.left)+

","+str(self.right)+ ")"

Partie 2 : Représentation du modèle de décision

1. l’entête de la classe DecisionNode

class DecisionNode(Node):

2. la méthode __init__

def __init__(self,label,distr,S,left,right):

Node.__init__(self,label,left,right)

self.seuil = S

self.distr = distr

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 1/7

3. la méthode outcome

def outcome(self,val):

try:

assert not self.isLeaf()

if val >= self.seuil:

return self.left

else:

return self.right

except:

print("le noeud est une feuille")

4. la méthode __str__

def __str__(self):

L = self.linearize()

ch=""

for e in L:

ch+="IF"

for i in range(1,len(e)):

if e[i] == e[i-1].left:

ch+=e[i-1].label+">="+str(e[i-1].seuil)+ "AND"

else:

ch+=e[i-1].label+"<"+str(e[i-1].seuil)+ "AND"

ch = ch[:len(ch)-4]+"THEN"+

e[len(e)-1].label+"="+str(e[len(e)-1].distr)+ "\n"

return ch

5. la méthode predict

def predict (self,dicobs):

currentNode = self

while not(currentNode.isLeaf())and currentNode.label in dicobs:

curvalue = dicobs[currentNode.label]

currentNode = currentNode.outcome(curvalue)

return currentNode.distr

6. la méthode __init__

def __init__(self):

self. listNodes = []

7. la méthode add

def add(self,dt):

self. listNodes.append(dt)

8. la méthode predict

def predict(self, dicobs):

if len(self.listNodes) == 0:

distr = {0:0.5, 1:0.5}

else:

p0 = 0

for e in self.listNodes:

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 2/7

d = e.predict(dicobs)

p0+=d[0]

p0 = p0/len(self.listNodes)

distr = {0:p0, 1:1-p0}

return distr

Partie 3 : Apprentissage

1. la fonction CountValues

def CountValues(DSET,ind):

e = set()

for i in range(DSET.shape[0]):

e.add(DSET[i,ind])

return len(e)

2. la fonction EvalDistr

def EvalDistr(DSET):

n,m = np.shape(DSET)

if (n,m) == (0,0):

d = {0:0.5,1:0.5}

else:

d={0:0,1:0}

for i in range(n):

if DSET[i,m-1] == 0:

d[0]+=1/n

else:

d[1]+=1/n

return d

3. la fonction IsPure

def IsPure(DSET):

d = EvalDistr(DSET)

if d[0] == 1 or d[1] == 1:

return True

else:

return False

4. la fonction IsQualitative

def IsQualitative(DSET):

n,m = np.shape(DSET)

L = [True]*m

for j in range(m):

i = 0

while 1:

if DSET[i,j] not in [0,1]:

L[j] = False

break

i+=1

if i = n:

break

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 3/7

return L

5. la fonction Cut

def Cut(DSET, Lcol, obs, S = 0.5):

indice = Lcol.index(obs)

n,m = np.shape(DSET)

n1,n2 = 0,0

for i in range(n):

if DSET[i,indice] >= S:

n1+=1

else:

n2+=1

ds1=np.empty((n1,m-1))

ds2=np.empty((n2,m-1))

k11,k21 = 0,0

for i in range (n):

if DSET[i,indice] >= S:

k2=0

for j in range(indice):

ds1[k11,k2]=DSET[i,j]

k2+=1

for j in range(indice+1,m):

ds1[k11,k2]=DSET[i,j]

k2+=1

k11+=1

else:

k2=0

for j in range(indice):

ds2[k21,k2]=DSET[i,j]

k2+=1

for j in range(indice+1,m):

ds2[k21,k2]=DSET[i,j]

k2+=1

k21+=1

L1 = Lcol[:indice] + Lcol[indice+1:]

L2 = [ds1,ds2]

L3 = [n1/n,n2/n]

return L1 , L2 , L3

6. la fonction Impurity

def Impurity(DSET, Lcol, obs, S = 0.5):

t = Cut(DSET, col, obs, S)

p1 = t[2][0]

p2 = t[2][1]

ds1 = t[1][0]

ds2 = t[1][1]

d1 = EvalDistr(ds1)

d2 = EvalDistr(ds2)

m1 = min(d1[0],d1[1])

m2 = min(d2[0],d2[1])

return(p1m1+p2m2)

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 4/7

7. la fonction SortObs

def SortObs(DSET,Lcol,obs):

n,m = np.shape(DSET)

indice = Lcol.index(obs)

Lc = []

for i in range(n):

Lc.append((DSET[i,indice],DSET[i,m-1]))

Lc.sort()

return Lc

8. la fonction BestCut

def BestCut(DSET, Lcol, obs, qual):

i = Lcol.index(obs)

if qual[i]:

return Impurity(DSET,Lcol,obs,0.5))

else:

Lc = SortObs(DSET,Lcol,obs)

if IsPure(DSET):

LSeuil = [max(Lc)]

else:

LSeuil = []

for i in range(len(Lc)-1):

if Lc[i][1]!=Lc[i+1][1]:

LSeuil.append((Lc[i][0]+Lc[i+1][0])/2)

sBest = LSeuil[0]

vbest = Impurity(DSET,Lcol,obs,sBest)

for s in LSeuil:

imp = Impurity(DSET,Lcol,obs,s)

if imp<vBest:

vBest = imp

sBest = s

return vBest,sBest

9. la fonction BuildTree

def BuildTree(DSET, Lcol, qual):

distr = EvalDistr(DSET)

if DSET.shape == (0,0) or IsPure(DSET) or len(Lcol) == 1:

return DecisionNode(Lcol[0], distr)

else:

LvBest = []

LsBest=[]

for obs in Lcol[:len(Lcol)-1]:

sBest, vBest = BestCut(DSET, colonnes, obs, qual)

LvBest.append(vBest)

LsBest.append(sBest)

indice=LvBest(min(LvBest))

sBest=LsBest[indice]

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 5/7

oBest=Lcol[indice]

L=Cut(DSET, Lcol, oBest, sBest)

DSET1=L[1][0]

DSET2=L[1][1]

Lcol= L[0]

rqual = qual[:]

rqual.pop(Lcol.index(oBest))

root=DecisionNode(oBest,distr,BuildTree(DSET1,Lcol,rqual),

BuildTree(DSET2, Lcol, rqual),sBest)

return root

PROBLEME 2

Partie 1 : algèbre relationnelle

1. Π

𝑑𝑠 _𝑖𝑑 ,𝑑𝑠 _𝑛𝑎𝑚𝑒 ,𝑑𝑠 _𝑑𝑒𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 𝜎𝑓𝑜𝑟𝑚𝑎𝑡 =′ 𝑐𝑠 𝑣′ 𝐷𝑎𝑡𝑎𝑆𝑒𝑡

2. Π𝑐𝑙𝑠 _𝑑𝑒𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 ( 𝜎𝑙𝑎𝑛𝑔𝑢𝑎𝑔𝑒 =′ 𝑃𝑦𝑡 𝑕 𝑜𝑛 ′ 𝑒𝑡 𝑐𝑎𝑡𝑒𝑔𝑜𝑟𝑦 =′ 𝐾𝑁 𝑁′ (𝐶𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑒𝑢𝑟 ⋈𝑐𝑙𝑠 _𝑖𝑑 𝐶𝑜𝑚𝑏𝑖𝑛𝑒 ⋈𝑚 _𝑛𝑎𝑚𝑒 𝑀𝑒𝑡 𝑕𝑜𝑑 )

Partie 2 : SQL

SELECT ds_id FROM Classifieur WHERE error_rate < 0.3

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')

SELECT D.ds_id , COUNT(DISTINCT M.m_name) AS NB_M

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 D.ds_id

UPDATE DataSet SET nb_instances = nb_instances + 100

WHERE ds_id IN (SELECT ds_id FROM Classifieur WHERE language ='Python')

Partie 3 : sqlite3

import sqlite3

cnx = sqlite3.connect("classifieur.db")

cur = cnx.cursor()

cur.execute("CREATE TABLE Method (m_name TEXT PRIMARY KEY,

category TEXT, m_description TEXT ) ")

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 6/7

f = open("DataMeth.txt",’r’)

L = f.readlines()

Ldata = [ l.strip().split('#') for l in L]

ou bien

ldata =

[l.strip().split('

#') for l in f]

cur.executemany("INSERT INTO Method VALUES(?,?,?) ", ldata)

cur.execute("SELECT ds_id , AVG(error_rate) AS M_erreur FROM Classifieur

GROUP BY ds_id ORDER BY ds_id")

L=cur.fetchall()

x=[i[0] for i in L]

y=[i[1] for i in L]

ou bien

x, y =

zip(*cur.f

etchall())

import matplotlib.pyplot as plt

plt.plot(x,y)

plt.show()

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 7/7

Concours Nationaux d’Entrée aux Cycles de Formation d’Ingénieurs - Session 2019

Concours Nationaux d’Entrée aux Cycles de Formation d’Ingénieurs - Session 2019

ou bien

ou bien