X-ENS 2025 MP Informatique A : sujet en PDF
Sujet de l'épreuve de Informatique A du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2025, filière MP, en 4 heures. Thème : Arbres de décision pour l'identification des plantes : raisonnement bayésien, entropie et recherche d'un arbre optimal.
Ce que traite le sujet, partie par partie
- Partie I : Description probabiliste des plantes. Distributions sur les espèces, probabilité d'observer une valeur d'un caractère, mise à jour bayésienne de l'état après une observation et commutation de deux observations, avec leur programmation sur des listes de mesures.
- Partie II : Arbre optimal. Arbres de décision et hauteur moyenne, énumération des arbres sur un exemple, produit cartésien de listes, génération de tous les arbres et choix d'un arbre de hauteur moyenne minimale.
- Partie III : Algorithme glouton. Entropie de Shannon, extremums sur un ensemble fini, entropie moyenne d'un caractère, construction gloutonne de l'arbre et contre-exemple montrant que le glouton n'est pas optimal.
- Partie IV : Optimisation de l'algorithme naïf. Fonction de recherche à récursion ouverte avec un oracle : préconditions, preuve par invariant de boucle, version récursive et élagage des arbres dont le score dépasse le meilleur courant.
- Partie V : Observations complexes et formules logiques. Observations décrites par des formules propositionnelles sur les caractères, équivalence et probabilité d'une formule, calcul pour une clause, implication entre clauses et mise sous forme conjonctive pour une formule quelconque.
Chapitres à revoir avant de traiter ce sujet
- Espaces probabilisés
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Dérivabilité et convexité
- Spécifier, tester, prouver : terminaison et correction
- Logique, ensembles et applications
Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.