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

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.

Problème 1 - Partie 1 : Représentation de la structure d’arbre binaire

Cette partie étudie la classe Node qui représente un arbre binaire à l'aide de méthodes récursives.

Question 1 : Méthodes isLeaf et linearise

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 :

• Si le nœud est une feuille, elle retourne une liste contenant une seule branche constituée du nœud courant : [[self]].
• Sinon, elle appelle récursivement 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.

Question 2 : Calcul de la taille de l'arbre

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

Question 3 : Représentation textuelle récursive

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)

Problème 1 - Partie 2 : Représentation du modèle de décision

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.

Question 1 : Déclaration de la classe

Définir la classe DecisionNode héritant de Node.

La syntaxe de déclaration est : class DecisionNode(Node):.

Question 2 : Constructeur de DecisionNode

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.

Question 3 : Évaluation du franchissement d'un nœud

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 :

• Si val >= seuil, la méthode retourne self.left.
• Sinon, elle retourne self.right.

Question 4 : Génération des règles de décision

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

Question 5 : Algorithme de prédiction sur un nœud

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 :

• Si le nœud courant est une feuille ou si son attribut label n’est pas présent dans dicobs, la méthode retourne l'attribut distr.
• Sinon, elle extrait la valeur observée et poursuit le parcours sur le sous-arbre désigné par outcome.

Question 6 : Structure de la forêt de décision

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.

Question 7 : Ajout d'un arbre à la forêt

Définir la méthode add(newinstance) qui insère un nouvel arbre de décision dans la liste listNodes.

Question 8 : Prédiction par agrégation dans la forêt

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}.

Problème 1 - Partie 3 : Apprentissage

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.

Question 1 : Importation de la bibliothèque

L'importation de la bibliothèque d'analyse numérique s'effectue via l'instruction : import numpy as np.

Question 2 : Décompte des valeurs distinctes

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.

Question 3 : Évaluation de la distribution des classes

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}.

Question 4 : Test de pureté d'un jeu de données

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().

Question 5 : Identification des variables qualitatives

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}.

Question 6 : Partitionnement du jeu de données

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.

Question 7 : Mesure de l'impureté d'une coupure

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

Question 8 : Tri des observations

Définir SortObs(DSET, colonnes, obs) pour ordonner les couples (valeur de l'attribut obs, classe) par valeur croissante.

Question 9 : Recherche du meilleur seuil de coupure

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.

Question 10 : Algorithme de construction de l'arbre de décision

Définir la fonction récursive BuildTree(DSET, colonnes, qual) qui assemble l'arbre de décision :

• Calcule la distribution courante des classes.
• Si DSET est vide, pure, ou s'il ne reste qu'une seule colonne, renvoie un nœud feuille DecisionNode avec la distribution associée.
• Sinon, recherche la variable et le seuil optimaux en minimisant l'impureté globale.
• Instancie un nœud DecisionNode muni de ces paramètres.
• Découpe DSET en deux sous-ensembles et effectue les appels récursifs pour construire les sous-arbres gauche et droit.
• Retourne la racine de l'arbre construit.

Problème 2 - Partie 1 : Algèbre relationnelle

Cette section détaille les expressions formelles en algèbre relationnelle pour interroger la base de données.

1. Sélection des jeux de données au format CSV avec projection des attributs d'identification :

   Π ds_id, ds_name, ds_description (σ format='csv' (DataSet))

2. Extraction des descriptions de classifieurs implémentés en Python utilisant l'algorithme KNN :

   Π cls_description (σ language='Python' et category='KNN' (Classifieur ⋈ cls_id Combine ⋈ m_name Method))

Problème 2 - Partie 2 : SQL

Cette partie présente la formulation des requêtes en langage SQL.

Question 1 : Sélection sous condition simple

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;

Question 2 : Utilisation d'une différence d'ensembles

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

Question 3 : Agrégation et décompte distinct

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;

Question 4 : Mise à jour conditionnelle avec sous-requête

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

Problème 2 - Partie 3 : Utilisation de sqlite3 en 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 :

• Établissement d'une connexion vers la base de données CMP.db via sqlite3.connect.
• Création de la table Method (comportant les champs m_name en clé primaire, category et m_description) à l'aide de la méthode execute.
• Lecture du fichier texte DataMeth.txt et découpage de chaque ligne selon le séparateur #.
• Insertion groupée des données dans la base de données via executemany, suivie de la validation de la transaction avec commit().
• Exécution d'une requête de regroupement pour calculer le taux d'erreur moyen par jeu de données.
• Extraction des résultats sous forme de séries de données x (identifiants) et y (moyennes d'erreurs) grâce à l'instruction zip(*cur.fetchall()).
• Génération et affichage de la courbe d'erreur au moyen du module matplotlib.pyplot.
• Fermeture explicite de la connexion à la base de données.

Méthode - Techniques récompensées et erreurs à éviter

L'évaluation des candidats repose sur les critères d'excellence suivants :

• La maîtrise des principes de programmation orientée objet et du traitement récursif des arbres binaires.
• La rigueur dans l'implémentation algorithmique des modèles de décision et du calcul d'impureté.
• La précision de la syntaxe en algèbre relationnelle et en langage SQL pour l'expression de requêtes complexes.
• L'utilisation adéquate des fonctions de l'interface sqlite3 et du traitement des structures de données en Python.

Principales erreurs à éviter lors de l'épreuve :

• L'omission de la condition d'arrêt dans les algorithmes récursifs.
• Les erreurs d'indexation lors du découpage des tableaux de données NumPy.
• L'absence d'appel à la méthode commit() après l'exécution de requêtes de modification (INSERT, UPDATE).
• L'oubli de la fermeture de la connexion SQLite en fin de traitement.