INFORMATIQUE A
Arbres de classification d’arbres
Ce sujet porte sur la réalisation d’arbres d’identification des plantes basés sur des observations morphologiques. A partir d’une base de connaissance botaniste, il s’agit de réaliser un arbre dont les feuilles sont des diagnostics (typiquement des noms d’espèce) et les nœuds des caractères morphologiques (par exemple la couleur des fleurs). Un nœud a autant de fils que le caractère a de valeurs possibles (jaune, bleue, etc.).
Etant donnée une base de connaissance, il s’agit de construire un arbre dont la hauteur moyenne est la plus petite possible, ce qui revient à minimiser le nombre moyen d’observations nécessaires pour identifier une plante. La difficulté revient donc à choisir à chaque étape le caractère le plus discriminant,
c’est-à-dire celui qui va le mieux séparer l’espace de recherche.
Pour tenir compte de la diversité au sein d’une espèce, nous adoptons une approche probabiliste basée sur un raisonnement bayésien : la valeur d’un caractère morphologique pour une espèce donnée sera probabiliste. Par exemple, la couleur des fleurs d’une certaine espèce pourra être bleue ou jaune, avec certaines probabilités.
La partie I introduit les éléments de raisonnement bayésien nécessaires à la construction des arbres.
La partie II propose une approche par énumération pour générer un arbre qui minimise la hauteur moyenne.
La partie III propose une heuristique basée sur l’entropie de Shannon pour éviter la construction de tous les arbres.
La partie IV revient sur le calcul exact en proposant une optimisation permettant de réduire l’espace de recherche.
Les parties III et IV sont indépendantes l’une de l’autre.
Enfin, la partie V propose une approche logique pour étendre la notion de caractère. Cette dernière partie ne dépend que de la première.
Rappels de probabilités
Rappels d’OCaml
Partie I : Description probabiliste des plantes
Partie II : Arbre optimal
Partie III : Algorithme glouton
Partie IV : Optimisation de l’algorithme naïf
Partie V : Observations complexes et formules logiques
INFORMATIQUE B
Le jeu de Röckse
Partie I : Sauts et chemins
Partie II : Recherche exhaustive
Partie III : Recherche gloutonne
Partie IV : Recherche par programmation dynamique
Le sujet et le corrigé de cette épreuve sont également disponibles sur le site de l’UPSTI (Union des Professeurs de Sciences et Techniques Industrielles) :
https://www.upsti.fr/espace-etudiants/annales-de-concours
