Concours Nationaux d’Entrée aux Cycles de Formation d’Ingénieurs
Concours Nationaux d’Entrée aux Cycles de Formation d’Ingénieurs
Programming, Mathematics, Computer Science · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente la correction de l’épreuve d’informatique du Concours National d’Entrée aux Cycles de Formation d’Ingénieurs (session 2019). Il détaille les solutions aux exercices de programmation orientée objet, de structures de données (arbres binaires), de modélisation de décision, d’apprentissage automatique simple, d’algèbre relationnelle, de langage SQL et d’interaction avec SQLite en Python.
Cette partie étudie la classe Node qui représente un arbre binaire à l'aide de méthodes récursives.
Définir la méthode isLeaf qui indique si un nœud est une feuille (sans fils gauche ni droit) et la méthode linearise qui retourne la liste des branches (chemins) de l’arbre sous forme de listes de nœuds.
La méthode isLeaf vérifie si self.left et self.right sont tous deux None.
La méthode linearise applique le principe de récursion suivant :
[[self]].linearise sur les fils gauche et droit (s’ils existent) pour obtenir les listes de branches L1 et L2. Pour chaque branche e de L1 et L2, elle ajoute le nœud courant en tête avec [self] + e.Définir la méthode récursive __len__ qui retourne le nombre total de nœuds contenus dans l’arbre.
Si le nœud est une feuille, la méthode retourne 1. Sinon, elle évalue récursivement la taille des sous-arbres gauche et droit (0 en cas d'absence), puis ajoute 1 pour comptabiliser le nœud courant :
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
Définir la méthode récursive __str__ qui retourne une chaîne de caractères décrivant le nœud ainsi que ses sous-arbres.
La méthode s’appuie sur la méthode d'enseigne format pour afficher le libellé du nœud et la représentation récursive des sous-arbres gauche et droit :
return "Node({},{},{})".format(repr(self.label), self.left, self.right)
Cette partie porte sur la classe DecisionNode, dérivée de Node, qui modélise un nœud de décision associé à un seuil et à une distribution de probabilités.
Définir la classe DecisionNode héritant de Node.
La syntaxe de déclaration est : class DecisionNode(Node):.
Définir le constructeur __init__ de DecisionNode acceptant les attributs label, distr (distribution), seuil (valeur par défaut 0.5), left et right.
Le constructeur réutilise l'initialisation de la classe mère via super().__init__(label, left, right) puis affecte les attributs distr et seuil.
Définir la méthode outcome(val) qui compare la valeur val au seuil pour aiguiller vers le fils gauche ou le fils droit.
Après avoir vérifié que le nœud n’est pas une feuille :
val >= seuil, la méthode retourne self.left.self.right.Définir la méthode __str__ pour afficher l’ensemble des règles de décision sous forme textuelle.
La méthode extrait tous les chemins via linearise(). Pour chaque parcours, elle évalue la transition entre nœuds consécutifs pour déterminer l'opérateur de comparaison (>= ou <) appliqué au seuil. Elle met en forme chaque règle selon le modèle :
IF condition1 AND condition2 AND ... THEN décision = distribution
Définir la méthode predict(dicobs) qui parcourt l’arbre à partir d’un dictionnaire d’observations jusqu’à atteindre une feuille ou un attribut non renseigné.
L’évaluation s'effectue en boucle :
label n’est pas présent dans dicobs, la méthode retourne l'attribut distr.outcome.Définir la classe DecisionForest représentant un ensemble d'arbres de décision.
Son constructeur initialise un attribut listNodes sous la forme d'une liste vide.
Définir la méthode add(newinstance) qui insère un nouvel arbre de décision dans la liste listNodes.
Définir la méthode predict(dictobs) qui calcule la distribution moyenne prédite par l'ensemble des arbres de la forêt.
Si la forêt ne contient aucun arbre, la méthode renvoie la distribution uniforme {0: 0.5, 1: 0.5}.
Dans le cas contraire, elle calcule la moyenne des probabilités associées à la classe 0 sur tous les arbres, puis renvoie la distribution agrégée {0: p0_moyen, 1: 1 - p0_moyen}.
Cette section présente les fonctions permettant de construire un arbre de décision à partir d’un jeu de données DSET représenté par un tableau NumPy.
L'importation de la bibliothèque d'analyse numérique s'effectue via l'instruction : import numpy as np.
Définir CountValues(DSET, index) qui renvoie le nombre de valeurs distinctes présentes dans la colonne index de DSET.
La fonction s'appuie sur la structure d'ensemble set(DSET[:, index]) pour déterminer le nombre d'éléments uniques.
Définir EvalDistr(DSET) qui calcule la proportion de chaque classe au sein du jeu de données.
Si le tableau DSET est vide, la fonction renvoie {0: 0.5, 1: 0.5}. Sinon, elle calcule la proportion de la classe 1 (somme des éléments de la dernière colonne rapportée au nombre total de lignes) et retourne {0: 1 - p1, 1: p1}.
Définir IsPure(DSET) pour déterminer si le jeu de données contient une seule classe.
La fonction vérifie si la valeur 1 est présente parmi les valeurs renvoyées par EvalDistr(DSET).values().
Définir IsQualitative(DSET) qui renvoie une liste de booléens indiquant si les valeurs de chaque colonne sont exclusivement contenues dans l'ensemble {0, 1}.
Définir Cut(DSET, colonnes, obs, S=0.5) qui sépare le jeu de données selon les valeurs de l'attribut obs par rapport au seuil S.
Les lignes sont réparties en deux listes :
lst1 : sous-ensemble des observations dont la valeur pour obs est supérieure ou égale à S.lst2 : sous-ensemble des observations dont la valeur pour obs est inférieure à S.La fonction retourne la liste des colonnes privée de obs, les deux sous-ensembles sous forme de tableaux NumPy, ainsi que leurs proportions respectives p1 et p2.
Définir Impurity(DSET, colonnes, obs, S=0.5) pour évaluer la qualité d'une séparation.
La fonction sépare les données via Cut, puis calcule l'impureté pondérée :
impureté = p1 * min(EvalDistr(d1).values()) + p2 * min(EvalDistr(d2).values())
Définir SortObs(DSET, colonnes, obs) pour ordonner les couples (valeur de l'attribut obs, classe) par valeur croissante.
Définir BestCut(DSET, colonnes, obs, qual) pour identifier le seuil minimisant l'impureté sur une colonne donnée.
Pour un attribut qualitative, la fonction renvoie directement le seuil 0.5 et son impureté associées. Pour un attribut continu, elle évalue les seuils intermédiaires situés entre deux valeurs consécutives de classes différentes, puis sélectionne le seuil offrant l'impureté minimale.
Définir la fonction récursive BuildTree(DSET, colonnes, qual) qui assemble l'arbre de décision :
DSET est vide, pure, ou s'il ne reste qu'une seule colonne, renvoie un nœud feuille DecisionNode avec la distribution associée.DecisionNode muni de ces paramètres.DSET en deux sous-ensembles et effectue les appels récursifs pour construire les sous-arbres gauche et droit.Cette section détaille les expressions formelles en algèbre relationnelle pour interroger la base de données.
Π ds_id, ds_name, ds_description (σ format='csv' (DataSet))
Π cls_description (σ language='Python' et category='KNN' (Classifieur ⋈ cls_id Combine ⋈ m_name Method))
Cette partie présente la formulation des requêtes en langage SQL.
Obtenir la liste des identifiants ds_id des classifieurs dont le taux d’erreur est strictement inférieur à 0.3 :
SELECT ds_id
FROM Classifieur
WHERE error_rate < 0.3;
Identifier les jeux de données associés exclusivement à des classifieurs développés en Python :
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 C
WHERE (D.ds_id = C.ds_id) AND (language <> 'Python');
Déterminer le nombre de méthodes distinctes mobilisées par chaque classifieur :
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 C.cls_id;
Augmenter de 100 le nombre d'instances des jeux de données associés à au moins un classifieur écrit en Python :
UPDATE DataSet
SET nb_instances = nb_instances + 100
WHERE ds_id IN
(SELECT ds_id
FROM Classifieur
WHERE language = 'Python');
Cette section étudie la manipulation d'une base de données SQLite et la représentation graphique des résultats d'une requête à l'aide des bibliothèques sqlite3 et matplotlib.
L'exécution du script suit la séquence suivante :
CMP.db via sqlite3.connect.Method (comportant les champs m_name en clé primaire, category et m_description) à l'aide de la méthode execute.DataMeth.txt et découpage de chaque ligne selon le séparateur #.executemany, suivie de la validation de la transaction avec commit().x (identifiants) et y (moyennes d'erreurs) grâce à l'instruction zip(*cur.fetchall()).matplotlib.pyplot.L'évaluation des candidats repose sur les critères d'excellence suivants :
sqlite3 et du traitement des structures de données en Python.Principales erreurs à éviter lors de l'épreuve :
commit() après l'exécution de requêtes de modification (INSERT, UPDATE).