Top piège du sujet
Lemme de l'étoile mal énoncé ou versions exotiques
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet en deux parties indépendantes. (1) Exercice sur les automates : prouver le caractère rationnel ou non d'un langage particulier, manipulation d'automates, lemme de l'étoile, déterminisation. (2) Problème de programmation : notions de logique propositionnelle (ensemble Π de propositions, ensemble I d'implications, dérivation P ⇒_1 Q) avec représentation à base de matrices de booléens. L'ensemble permet de bien évaluer l'acquisition du programme des deux années.
Structure de l'épreuve
- Partie I — Exercice, Automates et lemme de l'étoile(Q1-Q8)Niveau attendu
Prouver le caractère rationnel ou non d'un langage. Q2 double inclusion (souvent une seule faite). Q5 déterminisation maîtrisée mais oublis des deux états finaux. Q6 lemme de l'étoile mal énoncé. Q8 piège : « inclus dans non-rationnel ⇒ non-rationnel » est faux.
- Partie II — Problème, Logique et matrices booléennes(Q9-Q22)Difficile
Logique avec représentation matricielle. Q13 introduit boucles dans preuve (preuves rigoureuses lues). Q16 double implication incontournable. Q17 calcul de puissances par multiplications (sans contrainte de complexité). Q18 parcours profondeur/largeur avec marquage.
- Partie III — Questions de synthèse, axiomes et classes(Q23-Q26)Très difficile
Q23 piège : « Qi ≠ Q(i+1) pour tout i » ne signifie pas Qi distincts deux à deux (suite 1,2,1,2…). Q24 difficile, à appuyer sur Q23. Q26 rédaction précise sur axiomes et classes attendue, beaucoup de preuves « qualitatives » lues.
Analyse globale du jury
« Les candidats abordent les deux parties dans leur grande majorité et finissent le sujet en passant les trois questions difficiles. Quelques (rares) excellentes copies (tout juste !) ont pu être lues. La présentation des copies est globalement satisfaisante. Le jury constate une nette amélioration de la qualité de rédaction des questions théoriques. Cependant, de gros écarts sont à déplorer quant aux connaissances mathématiques de base, certains candidats sont défaillants sur des notions élémentaires de calculs matriciels, ce qui est surprenant à ce niveau. Une grande majorité de candidats maîtrisent les notions de logique abordées. »
Top pièges sanctionnés
Lemme de l'étoile mal énoncé ou versions exotiques-2 pts
« Le lemme de l'étoile est trop rarement bien énoncé ou, alors, mal utilisé. Certaines versions « exotiques » ont pu être lues. »
Abus de transitions instantanées (ε-transitions) parfaitement inutiles-1 pts
« Nous avons pu constater un abus des transitions instantanées (parfaitement inutiles ici) : nous ne pouvons que déconseiller leur usage, surtout lorsqu'il s'agit ensuite de déterminiser l'automate. »
Une seule inclusion faite, la seconde oubliée (Q2)-1 pts
« Une preuve par double inclusion était attendue. Une seule inclusion est faite généralement. La seconde est oubliée. »
« Inclus dans un non rationnel ⇒ non rationnel » (Q8)-2 pts
« Une faute que nous avons eue dans beaucoup trop de copies : un langage inclus dans un langage non rationnel est non rationnel. Nous invitons les candidats à méditer le cas du langage vide (par exemple). »
Confusion fonction non majorée / fonction surjective (Q6)-1 pts
« Certains candidats pensent qu'une fonction non majorée est surjective. »
Récursivité abusive (produit matriciel notamment)-1 pts
« On constate parfois un usage abusif de la récursivité (pour le produit de deux matrices par exemple). Cela conduit parfois à des programmes lourds, là où une simple boucle faisait l'affaire. »
Équivalences alignées sans justification (Q16)-1 pts
« Une preuve par double implication était assez incontournable ici. Beaucoup trop de candidats se contentent d'aligner des équivalences, sans les justifier. »
Chapitres clés à maîtriser
Bosse chaque chapitre sur d'autres sujets de concours qui le couvrent.
Source : Rapport du jury Mines-Ponts · Info MP, session 2014 · PDF officiel ↗
Contexte
L'épreuve Informatique 2014
L'épreuve Informatique Mines-Ponts MP 2014 s'est déroulée fin avril 2014, durée 3h, coefficient 2. Sujet en deux parties indépendantes, un exercice sur les automates et un problème de programmation, qui, selon le jury, « permet de bien évaluer l'acquisition du programme des deux années de classe préparatoire ».
Première partie : automates et lemme de l'étoile. Le but est de prouver le caractère rationnel ou non d'un langage particulier, bonne manipulation des automates indispensable, énoncé rigoureux du lemme de l'étoile, déterminisation par l'algorithme du cours. Seconde partie : logique propositionnelle. Étude d'un ensemble Π de propositions et d'un ensemble I d'implications, avec représentation à base de matrices de booléens, calcul de puissances, parcours d'implications dérivables.
Le jury indique que « les candidats abordent les deux parties dans leur grande majorité » et « finissent le sujet en passant les trois questions difficiles » (Q18 sur le parcours de graphe, Q24 et Q26 sur les axiomes/classes). Le rapport ne publie pas les statistiques détaillées de cette épreuve.
Accompagnement personnalisé
Travaillez ce sujet avec un prof de l'équipe
Nos professeurs anciens taupins (Polytechnique, ENS, Centrale) reprennent ce sujet avec toi en cours particulier — corrigé ligne par ligne, méthode, pièges évités.
Trouvez le prof qu'il vous faut
Échangez avec notre équipe pour trouver le professeur idéal selon vos besoins.
Stratégie
Notre approche pour ce sujet
Le jury déplore « un abus des transitions instantanées (parfaitement inutiles ici) » et un « lemme de l'étoile trop rarement bien énoncé ». Stratégie clé : énoncer le lemme de l'étoile correctement avant de l'appliquer, et éviter les ε-transitions qui compliquent inutilement la déterminisation. Une grande majorité des candidats maîtrisent les notions de logique de la partie 2, c'est le terrain où marquer.
Si tu vises 9-12/20
Sécurise Q1-Q5 (constructions et déterminisation), la déterminisation est globalement maîtrisée, attention juste à préciser les états finaux (deux ici). En Q2, fais bien la double inclusion. En logique : Q12-Q13 et Q17 (calcul simple de puissances par boucles, pas de récursivité abusive sur le produit matriciel).
Si tu vises 14+ (top 10%)
Q6 lemme de l'étoile rigoureux (sans confondre « non majorée » et « surjective »). Q8 attention au piège « un langage inclus dans un langage non rationnel n'est pas forcément non rationnel » (cas du langage vide). Q16 double implication explicite, pas d'équivalences alignées. Q18 parcours en profondeur ou largeur avec marquage, peu de bonnes réponses.
Connaissances mathématiques de base : le jury déplore que « certains candidats sont défaillants sur des notions élémentaires de calculs matriciels ». Avant de coder, vérifie que produit matriciel et puissances n'ont pas de zone d'ombre. Présentation : indentation propre du code, pas de récursivité gratuite (boucle simple suffit pour le produit), traiter avec soin les exemples proposés dans l'énoncé, « c'est un passage parfois incontournable pour être en mesure de trouver ensuite les algorithmes appropriés ».
Conseils du jury
Conseils transversaux
- Énoncer correctement le lemme de l'étoile avant de l'appliquer, pas de version « exotique ». Et ne pas confondre « non majorée » et « surjective ».
- Éviter les transitions instantanées (ε-transitions), inutiles ici et compliquent la déterminisation. Méthode du tableau d'états privilégiée.
- Double inclusion / double implication : Q2, Q16 : ne pas se contenter d'une seule inclusion ni d'équivalences alignées sans justification.
- Pas de récursivité abusive pour le produit matriciel ou le calcul de puissances, boucle simple suffit, sans contrainte de complexité imposée en Q17.
- Parcours de graphe avec marquage (Q18) : DFS ou BFS sur les implications, marquage des propositions visitées pour éviter de boucler.
- Méditer les exemples de l'énoncé, passage incontournable pour trouver les algorithmes appropriés.
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ