Top piège du sujet
Recouvrement des positions du motif manqué (Q1-Q2)
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Le sujet traite de la recherche des positions d'un motif dans un texte. Il fait appel à la notion formelle d'automate et à des structures informatiques complexes que le candidat doit manipuler. Première partie : recherche naïve. Deuxième partie : automates finis déterministes à repli. Suite du sujet : écriture en binaire, calculs de puissances, applications. Caml exclusivement. L'ensemble permet de bien évaluer l'acquisition du programme des deux années.
Structure de l'épreuve
- Partie I — Recherche naïve dans un texte (Q1-Q6)(Q1-Q6)Niveau attendu
Q1-Q2 font découvrir le recouvrement des positions du motif, beaucoup passent à côté et sont pénalisés ensuite. Q3-Q4 fonction préfixe avec mauvaise gestion des cas d'arrêt ; `longueur(texte)` à éviter (complexité linéaire en taille texte au lieu du motif). Q5 listes. Q6 conclusion en O(·).
- Partie II — Automates finis déterministes à repli (Q7-Q11)(Q7-Q11)Difficile
Q7 arguments théoriques précis, justifications peu rigoureuses (« strictement décroissante… donc constante à partir d'un certain rang »). Q8-Q9 construction de l'automate. Q10-Q11 type automate imposé, manipulation des champs ; finesse de complexité rarement vue.
- Partie III — Écriture en binaire et puissances (Q18-Q19)(Q18-Q19)Difficile
Q18 médiocre qualité des codes, candidats semblent découvrir l'écriture en binaire et abusent des manipulations de puissances de 2. Quelques lignes suffisent avec des divisions euclidiennes par 2. Q19 rarement traitée, quelques candidats en ont vu toutes les finesses.
- Partie IV — Puissances de a et applications (Q20-Q25)(Q20-Q25)Très difficile
Q20-Q23 lien rarement fait entre puissance de 3 présentée et puissance de a associée, incompréhension, exemples parfois erronés. Q25 codes très compliqués, récursivité inadaptée, complexité imposée souvent non respectée, les candidats ne s'en aperçoivent pas.
Analyse globale du jury
« Les candidats abordent l'ensemble des questions dans leur grande majorité. Ils finissent parfois le sujet en passant les questions difficiles. Quelques (rares) excellentes copies ont pu être lues. La présentation des copies est globalement satisfaisante. Pour ce qui est de la manipulation des objets de type élaboré, une certaine aisance a pu être globalement appréciée. Cependant, peu d'efforts de rédaction des quelques questions théoriques, beaucoup de candidats ne donnent pas d'arguments ou se contentent d'arguments superficiels. Certains codes sont parfois bien trop compliqués ou difficiles à comprendre. »
Top pièges sanctionnés
Recouvrement des positions du motif manqué (Q1-Q2)-3 pts
« Le but de ces deux questions est de faire découvrir la possibilité du recouvrement des positions du motif dans le texte. Beaucoup de candidats passent à côté de cette finesse et se trouvent ensuite pénalisés dans l'écriture des codes. »
Usage de longueur(texte) au lieu de longueur(motif)-2 pts
« L'usage de la fonction longueur (pour le texte) est inutile et à déconseiller : elle induit une complexité linéaire en la taille du texte alors que l'on peut obtenir une complexité linéaire en la taille du motif. »
Justifications théoriques superficielles en Q7-2 pts
« On rencontre bien trop souvent des justifications peu rigoureuses du type : « La suite est strictement décroissante… » « … donc constante à partir d'un certain rang » dans la même phrase. »
Complexité imposée non vue, résultat annoncé conforme à l'énoncé mais faux (Q10-Q11)-2 pts
« Une complexité était imposée : peu de candidats ont vu la finesse sous-jacente et se contentent d'annoncer un résultat en accord avec celle annoncée par l'énoncé (et fausse au regard de leur propre code). »
Écriture binaire, codes compliqués au lieu de divisions par 2 (Q18)-2 pts
« Nous avons pu lire des codes particulièrement compliqués, abusant des manipulations de puissances de deux. Quelques lignes de code suffisent en s'appuyant sur de simples divisions euclidiennes par deux. »
Récursivité inadaptée, complexité imposée non respectée (Q25)-3 pts
« De nombreux codes très compliqués ont pu être lus. La récursivité n'est pas bien adaptée ici. Bien souvent, la complexité imposée n'est pas respectée. Les candidats ne semblent pas s'en apercevoir. »
Fonction préfixe, mauvaise gestion des cas d'arrêt-1 pts
« La fonction préfixe pose parfois des difficultés cependant (mauvaise gestion des cas d'arrêt). »
Lien puissance de 3 / puissance de a non fait (Q20-Q23)-2 pts
« Le lien est rarement fait entre le calcul de la puissance de 3 présenté et celui de la puissance de a associée. Cela traduit une incompréhension. Les exemples donnés sont parfois erronés. »
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 2018 · PDF officiel ↗
Contexte
L'épreuve Informatique 2018
L'épreuve Informatique Mines-Ponts MP 2018 s'est déroulée fin avril 2018, durée 3h, coefficient 2. Programmation en Caml exclusivement. Sujet qui, selon le jury, « permet de bien évaluer l'acquisition du programme des deux années de classe préparatoire ».
Le sujet traite de la recherche des positions d'un motif dans un texte. Il fait appel à la notion formelle d'automate et à des structures informatiques complexes. Première partie : recherche naïve dans un texte avec la subtilité du recouvrement des positions. Deuxième partie : automates finis déterministes à repli (esprit KMP), type automate imposé, fonction préfixe, complexité imposée. Suite : écriture en binaire (Q18), calcul de puissances (Q19-Q23), applications (Q25).
Le jury indique que « les candidats abordent l'ensemble des questions dans leur grande majorité » et finissent parfois le sujet en passant les questions difficiles. « Pour ce qui est de la manipulation des objets de type élaboré, une certaine aisance a pu être globalement appréciée. » 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 insiste : « le but de Q1-Q2 est de faire découvrir la possibilité du recouvrement des positions du motif », beaucoup passent à côté et sont « pénalisés ensuite dans l'écriture des codes ». Stratégie clé : traiter avec soin les exemples Q1-Q2 pour intérioriser le recouvrement, sinon toute la suite tombe.
Si tu vises 9-12/20
Q1-Q2 : intérioriser le recouvrement via les exemples. Q3-Q4 fonction préfixe avec cas d'arrêt propres, complexité linéaire en taille du motif (pas du texte, pas de longueur(texte)). Q5 listes Caml avec pattern matching propre. Q6 conclusion en O(·) cohérente avec le code.
Si tu vises 14+ (top 10%)
Q7 argument théorique rigoureux (suite d'entiers strictement décroissante minorée ⇒ stationnaire, proprement justifié). Q10-Q11 manipulation des champs du type automate, complexité imposée vraiment respectée (pas juste annoncée). Q18 écriture binaire par divisions par 2, pas par puissances. Q25 itératif, pas récursif, avec complexité imposée respectée.
Rédaction théorique : le jury déplore « peu d'efforts de rédaction des quelques questions théoriques ». Argumenter, pas affirmer. Codes clairs : « utiliser l'indentation est un excellent moyen d'y parvenir ». Et, leçon Q25, toujours vérifier que ton propre code respecte la complexité demandée par l'énoncé : beaucoup l'annoncent sans la satisfaire et ne s'en aperçoivent pas.
Conseils du jury
Conseils transversaux
- Recouvrement des positions du motif : Q1-Q2 le font découvrir, ne pas passer à côté sous peine de pénalité sur tous les codes suivants.
- Complexité linéaire en la taille du motif, pas du texte, éviter
longueur(texte)qui dégrade la borne. - Justifications théoriques rigoureuses : « strictement décroissante » + « stationnaire » sans expliciter le minorant entier = sanction.
- Type automate imposé en Q10-Q11 : manipuler les champs, vérifier que le code respecte vraiment la complexité imposée.
- Écriture binaire par divisions euclidiennes par 2 en Q18, quelques lignes suffisent, pas de manipulation de puissances de 2.
- Pas de récursivité inadaptée en Q25, itératif. Et vérifier sa propre complexité avant de l'annoncer.
- Indentation et lisibilité du code, codes clairs, pas trop compliqués.
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ