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