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