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
Source : Rapport du jury Mines-Ponts · Info MP, session 2014 · PDF officiel ↗
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
