Top piège du sujet
Calculs de complexité erronés
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Problème unique de 32 questions sur les automates d'arbres et les langages associés. Construction et parcours d'automates d'arbres descendants et ascendants. Le sujet est codé en Caml (autres langages exclus). Préliminaires sur listes (contient, union, fusion), modélisation d'une structure d'arbre, complexité asymptotique exigée à chaque fonction. L'ensemble permet de bien évaluer l'acquisition du programme des deux années de classe préparatoire.
Structure de l'épreuve
- Partie I — Préliminaires et fonctions sur listes (Q1-Q4)(Q1-Q4)Abordable
Coder en Caml les fonctions utilitaires sur listes : `contient`, `union` (sans doublon), `fusion`. Le jury note des confusions avec les tableaux et l'utilisation abusive de la notation L(i) sur les listes. Donner la complexité de chaque fonction.
- Partie II — Structures d'arbres et premières propriétés (Q5-Q11)(Q5-Q11)Niveau attendu
Définition Caml d'une structure d'arbre, calculs sur taille et profondeur. Q5-Q6 : confusion fréquente entre taille et profondeur d'un arbre. Q8 contre-exemples souvent erronés. Q10-Q11 rarement traitées, l'exemple fourni par les candidats est rarement compris.
- Partie III — Automates d'arbres descendants (Q12-Q18)(Q12-Q18)Difficile
Q12-Q13 bien formulées quand traitées. Q14 : traitement de la réciproque souvent oublié. Q15-Q18 rarement traitées. Q16 : la notion de boucle dans l'automate est repérée mais souvent mal utilisée pour aboutir à une contradiction. Q17 : une inclusion souvent oubliée.
- Partie IV — Automates ascendants et identifiants (Q19-Q32)(Q19-Q32)Très difficile
Q19-Q20 bien traitées (rares îlots de réussite). Q21-Q23 rarement traitées. Q22 : confusion entre états initiaux et états finaux. Q24 : confusion dans la liste retournée par `partie_identifiant`, alors que `identifiant_partie` est bien traitée. Q25-Q32 peu abordées par les candidats.
Analyse globale du jury
« La majorité des candidats traitent les questions 1 à 13, ils évitent les questions 10 et 11. Puis ils abordent les questions 19, 20 et 24. Quelques copies seulement ont traité les questions 26 à 31. Les calculs de complexité sont souvent erronés. La présentation des copies est globalement satisfaisante. Pour cette épreuve, plusieurs copies « blanches » dans lesquelles aucune composition n'est présentée ont été notées. »
Top pièges sanctionnés
Calculs de complexité erronés-2 pts
« Les calculs de complexité sont souvent erronés. »
Confusion taille / profondeur d'un arbre (Q5-Q6)-1 pts
« Plusieurs copies confondent la taille d'un arbre avec la profondeur d'un arbre. »
Confusion liste / tableau, notation L(i) sur les listes (Q1-Q4)-1 pts
« On trouve parfois une confusion avec les tableaux, avec l'utilisation de la notation L(i) sur les listes. »
Boucle dans l'automate mal exploitée pour la contradiction (Q16)-2 pts
« La notion de boucle dans l'automate est souvent bien repérée mais parfois, elle est mal utilisée pour obtenir une contradiction. »
Recherche d'états initiaux au lieu d'états finaux (Q22)-2 pts
« Les candidats recherchent souvent des états initiaux plutôt que des états finaux. »
Réciproque oubliée (Q14)-1 pts
« Le traitement de la réciproque est souvent oublié. »
Copies blanches anormalement nombreuses-3 pts
« Pour cette épreuve, nous avons noté plusieurs copies « blanches » dans lesquelles aucune composition n'est présentée. »
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 2015 · PDF officiel ↗
Contexte
L'épreuve Informatique 2015
L'épreuve Informatique Mines-Ponts MP 2015 s'est déroulée début mai 2015, durée 3h, coefficient 2. Calculatrice autorisée. Langage imposé : Caml (tout autre langage exclu).
Le sujet est un problème unique de 32 questions sur les automates d'arbres et les langages associés. Construction et parcours d'automates d'arbres descendants et ascendants sont étudiés. Préliminaires Caml sur listes (Q1-Q4 : contient, union, fusion), puis modélisation d'une structure d'arbre adaptée, propriétés (taille, profondeur), automates descendants (Q12-Q18) puis ascendants (Q19-Q32) avec questions sur les identifiants de parties.
Le jury indique que la majorité des candidats traitent « les questions 1 à 13, ils évitent les questions 10 et 11. Puis ils abordent les questions 19, 20 et 24 ». Quelques copies seulement ont traité les questions 26 à 31. Anomalie cette session : « plusieurs copies "blanches" dans lesquelles aucune composition n'est présenté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 : « les calculs de complexité sont souvent erronés ». Stratégie clé : justifier chaque complexité avec rigueur (récurrence, sommation), pas juste annoncer un O(·) au feeling. Et distinguer taille et profondeur d'un arbre dès Q5-Q6, confusion fréquente qui plombe toute la suite.
Si tu vises 9-12/20
Sécurise Q1-Q9 (préliminaires listes + structure d'arbre) sans confondre liste et tableau (pas de notation L(i) sur les listes). Saute Q10-Q11 (jury : « rarement traitées ») et reviens dessus en fin. Capitalise sur Q12-Q13 (« en général bien formulées »). En Q14, ne pas oublier la réciproque.
Si tu vises 14+ (top 10%)
Q16 boucle dans l'automate bien exploitée pour la contradiction (souvent repérée mais mal utilisée). Q17 ne pas oublier la seconde inclusion. Q19-Q20 bien traitées par les candidats, assurer 100%. Q22 chercher les états finaux (pas initiaux). Q24 attention à partie_identifiant (souvent bugguée alors que identifiant_partie passe).
Caml et arbres récursifs : pattern matching propre, fonctions auxiliaires nommées, complexité justifiée par récurrence T(n) = a·T(n/b) + f(n) ou par sommation explicite. Ne pas laisser de copie blanche : même Q1-Q3 traitées proprement valent mieux que zéro. Les fonctions auxiliaires définies en cours de problème peuvent être réutilisées dans les questions suivantes.
Conseils du jury
Conseils transversaux
- Justifier les complexités rigoureusement, récurrence ou sommation explicite, pas un O(·) annoncé sans raisonnement.
- Distinguer taille et profondeur d'un arbre, confusion fréquente Q5-Q6 qui plombe toutes les questions suivantes.
- Caml strict, pas la notation tableau : pas de L(i) sur les listes ; pattern matching head::tail ou fonction d'accès
nth. - Réciproque obligatoire en Q14 : prouver les deux sens de l'équivalence, sans en oublier un.
- Boucle dans l'automate ⇒ contradiction explicite en Q16 : repérer la boucle suffit pas, il faut en tirer la contradiction proprement.
- États finaux, pas initiaux en Q22, confusion classique.
- Ne pas rendre copie blanche : même les préliminaires Q1-Q3 rapportent des points.
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ