Exercice 3 - Partie B : Arbres de décision binaire · Bac Numérique et Sciences Informatiques Asie 2025 (jour 2)

EXERCICE 3 (8 points)

Cet exercice porte sur la programmation Python (dictionnaire, récursivité, spécification), la programmation orientée objet, les bases de données relationnelles, les requêtes SQL et les arbres binaires.

Cet exercice est composé de 3 parties indépendantes.

Partie A

Dans cette partie, on s'intéresse à la gestion de la base de données d'un hôpital. On pourra utiliser les mots-clés SQL suivants: AND, FROM, INSERT, INTO, JOIN, ON, SELECT, SET, UPDATE, VALUES, WHERE. On utilisera également la fonction d'agrégation COUNT qui renvoie le nombre d'enregistrements correspondant à une requête.

La table Patient possède les attributs suivants:

nom_patient de type TEXT (clé primaire);

prenom de type TEXT;

numero_secu de type INT;

age de type INT.

La table Symptome possède les attributs suivants:

nom_patient de type TEXT (clé primaire et clé étrangère);

toux de type TEXT;

fievre de type TEXT;

nausee de type TEXT;

anosmie de type TEXT.

Partie B: Arbres de décision binaire

On s'intéresse maintenant à l'automatisation du diagnostic à partir des symptômes. Cette automatisation se fait à l'aide d'un arbre de décision binaire, tel que celui illustré sur la figure 1.

Chaque nœud interne de l'arbre est étiqueté par un symptôme, et chaque feuille est étiquetée par un diagnostic. Pour établir un diagnostic, on se place à la racine et on parcourt l'arbre de la manière suivante:

si on arrive à une feuille, le diagnostic est l'étiquette de cette feuille;

sinon, on regarde si l'étiquette du nœud est un des symptômes du patient. Si oui, on continue le parcours dans le sous-arbre droit, sinon, on continue le parcours dans le sous-arbre gauche.

L'arbre de la figure 1 donne un diagnostic pour la Covid-19. Par exemple, un patient qui ne tousse pas et n'a pas d'anosmie, mais a de la fièvre et des nausées est diagnostiqué négatif si on suit cet arbre de décision.

6.

Donner le diagnostic pour un patient qui tousse et qui a de la fièvre, mais n'a pas de nausée ni d'anosmie, d'après l'arbre de la figure 1.

On décide d'implémenter les arbres binaires à l'aide de la classe Noeud ci-dessous:

class Noeud:

def __init__(self, valeur, gauche = None, droit = None):

"""valeur correspond au symptome si le noeud est

interne ou au diagnostic si le noeud est une feuille"""

self.valeur = valeur

self.gauche = gauche

self.droit = droit

def est_feuille(self):

"""renvoie vrai si le noeud est une feuille faux sinon"""

return self.gauche == None and self.droit == None

def symptome(self):

assert not self.est_feuille()

return self.valeur

def diagnostic(self):

assert self.est_feuille()

return self.valeur

7.

Préciser la signification de l'assertion de la méthode symptome.

8.

Nommer un attribut et une méthode de la classe Noeud.

On représente les symptômes d'un patient en Python par un dictionnaire dont les clés sont les symptômes possibles, et les valeurs sont True si le patient présente ce symptôme et False sinon.

Par exemple, les symptômes du patient de la question 6 sont représentés par le dictionnaire suivant:

patient = {'toux': True, 'fievre': True, 'nausee': False, 'anosmie': False}

9.

Compléter la fonction applique suivante, définie récursivement, qui renvoie le diagnostic établi en utilisant un arbre de décision binaire implémenté à l'aide de la classe Noeud précédente.

def applique(arbre, patient):

10.

Donner la taille de l'arbre représenté en figure 1. On considère que la taille d'un arbre constitué d'une unique feuille est 1.

On souhaite réduire la taille de cet arbre en utilisant l'observation suivante: un nœud dont les deux sous-arbres sont des feuilles correspondant au même diagnostic peut être remplacé par une feuille correspondant à ce diagnostic, comme illustré en figure 2.

11.

Appliquer cette règle à l'arbre de la figure 1 pour le réduire et dessiner le nouvel arbre.

12.

Compléter la méthode reduire qui permet d'appliquer cette règle récursivement pour réduire la taille d'un arbre de décision binaire.

def reduire(self):