Prepa HelpMines-Ponts 2025 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2025, filière MP, en 3 heures. Thème : Apprentissage d'un langage régulier par requêtes et arbre discriminant.
Ce que traite le sujet, partie par partie
- Section 1 : alphabets, mots et automates. Comparaison lexicographique de mots sur {a, b}, dictionnaire immuable à clés mots, automate déterministe complet décrit par une fonction de transition, langage reconnu, expression régulière et automate de Glushkov, fonctions de lecture d'un mot et d'acceptation.
- Section 2 : relation de séparabilité. Oracle à requêtes d'appartenance et d'équivalence, mots séparés par un discriminant, inséparabilité comme relation d'équivalence et finitude du nombre de classes pour un langage régulier grâce au lien avec les automates.
- Section 3 : arbre discriminant. Arbre de décision binaire dont les nœuds internes portent des discriminants et les feuilles des états : liste des feuilles en temps linéaire, criblage d'un mot et sa complexité, propriétés des criblats et borne sur le nombre de feuilles d'un arbre accessible.
- Section 4 : automate tiré d'un arbre discriminant. Automate associé à un crible, crible initial, traitement d'un contre-exemple pour ajouter un état, algorithme complet d'apprentissage avec un variant de boucle et minimalité du nombre d'états de l'automate obtenu.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Dictionnaires et principes du hachage
- Logique, ensembles et applications
- Complexité des algorithmes itératifs et récursifs
- Spécifier, tester, prouver : terminaison et correction
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.