Top piège du sujet
Complexités annoncées « curieuses » pour un tri général : O(ln n), O(n), O(n!)
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet constitué de deux problèmes. (1) Programmation : graphe du Web, mettre en œuvre un algorithme de calcul du pageRank d'un ensemble de pages, avec préliminaires Caml (concaténation, tri fusion), structure de dictionnaire imposée, parcours BFS/DFS, calcul de norme indice 1 et itération. (2) Automates : la notion d'automate est étendue à celle d'automate probabiliste entièrement définie dans le sujet, déterminisation et calculs.
Structure de l'épreuve
- Partie I — Préliminaires Caml (Q1-Q2)(Q1-Q2)Niveau attendu
Q1 : concaténation/aplatissement de listes, confusions entre liste et tableau, et entre ajout en tête (::) et concaténation (@). Q2 tri fusion : erreurs très surprenantes, parfois confondu avec d'autres tris ; complexités annoncées très curieuses pour un tri général : O(ln n), O(n) ou même O(n!).
- Partie II — Dictionnaire et complexité (Q3-Q4)(Q3-Q4)Niveau attendu
Q3 : il faut comprendre l'intérêt de la structure de dictionnaire imposée, certains candidats ne le perçoivent pas et se contentent d'une fonction d'appartenance à une liste. Q4 : beaucoup d'erreurs dans le calcul de la complexité, le rôle de m mal compris.
- Partie III — Crawler, BFS/DFS et pageRank (Q5-Q11)(Q5-Q11)Difficile
Q5-Q6 BFS/DFS : nombreux candidats semblent les découvrir (oubli des sommets visités, absence de gestion des sommets en attente, confusion BFS/DFS). Q7 peu traitée. Q10 puissances de matrice recalculées, norme indice 1 souvent inconnue. Q11 synthèse en général juste.
- Partie IV — Automate probabiliste (Q13-Q22)(Q13-Q22)Très difficile
Q13 rédaction fine, rares aboutissent. Q14 mot vide souvent mal placé. Q16-Q18 idées rarement vues, justifications superficielles. Q17 déterminisation rarement maîtrisée, méthode du tableau d'états peu utilisée. Q19-Q21 beaucoup d'erreurs de calculs. Q22 difficile.
Analyse globale du jury
« Les candidats abordent les deux parties 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. Le jury constate cette année un nombre anormalement élevé de copies difficiles à lire : par multiplications des ratures, renvois, mauvaise indentation des codes. Peu d'efforts de rédaction des questions théoriques, beaucoup de candidats ne donnent pas d'arguments ou se contentent d'arguments superficiels. Des candidats traitent les questions relativement faciles en grappillant des points, attitude peu productive. »
Top pièges sanctionnés
Complexités annoncées « curieuses » pour un tri général : O(ln n), O(n), O(n!)-2 pts
« Des complexités annoncées très curieuses pour un algorithme général de tri : on trouve O(ln n), O(n) mais aussi O(n!). »
BFS/DFS : oubli de mémorisation des sommets visités-3 pts
« De nombreux candidats semblent découvrir le BFS ou le DFS : oubli de mémorisation des sommets visités, absence de gestion des sommets en attente. Certains ne voient pas la différence entre ces deux algorithmes. »
Dictionnaire remplacé par appartenance à une liste-2 pts
« Il faut bien comprendre l'intérêt de la structure de dictionnaire imposée ici. Certains candidats ne perçoivent pas son intérêt et se contentent d'une fonction d'appartenance à une liste. »
Confusion :: (ajout en tête) et @ (concaténation)-1 pts
« Des confusions entre liste et tableau. Ainsi qu'entre ajout en tête de liste (opération ::) et concaténation de listes (opération @). »
Norme indice 1 inconnue, puissances de matrice recalculées-2 pts
« Certains candidats font du calcul de puissances de matrice à chaque tour de boucle. D'autres font de la soustraction de tableaux sans écrire une fonction associée. La définition de la norme indice 1 semble très souvent non connue. »
Déterminisation par déterminisation « de tête » au lieu du tableau d'états-2 pts
« Beaucoup d'erreurs dans la déterminisation de l'automate. Cette technique semble rarement maitrisée. Peu de candidats appliquent la méthode (pourtant efficace) du tableau d'états et semblent déterminiser de tête. »
Conversions liste ↔ tableau abusives-1 pts
« Beaucoup de candidats abusent des conversions de listes en tableaux et réciproquement. Ceci est inutile dans le sujet. »
Grappillage des questions faciles-2 pts
« Des candidats traitent les questions qui sont relativement faciles en grappillant des points. Attitude peu productive. »
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 2016 · PDF officiel ↗
Contexte
L'épreuve Informatique 2016
L'épreuve Informatique Mines-Ponts MP 2016 s'est déroulée début mai 2016, durée 3h, coefficient 2. Calculatrice autorisée. Langage imposé : Caml. Sujet en deux problèmes qui, selon le jury, « permet de bien évaluer l'acquisition du programme des deux années de classe préparatoire ».
Problème 1 : graphe du Web et pageRank. Mettre en œuvre un algorithme de calcul du pageRank d'un ensemble de pages du Web. Préliminaires Caml (concaténation, tri fusion), structure de dictionnaire imposée, parcours BFS/DFS du graphe, itération matricielle avec norme indice 1. Problème 2 : automate probabiliste. La notion d'automate est étendue à celle d'automate probabiliste, entièrement définie dans le sujet, déterminisation et calculs de probabilités.
Le jury indique que « les candidats abordent les deux parties dans leur grande majorité » et finissent parfois le sujet en passant les questions difficiles. Particularité 2016 : « un nombre anormalement élevé de copies difficiles à lire : par multiplications des ratures, renvois, mauvaise indentation des codes ». 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 déplore « des complexités annoncées très curieuses pour un algorithme général de tri : on trouve O(ln n), O(n) mais aussi O(n!) ». Stratégie clé : connaître par cœur la complexité du tri fusion (O(n log n)) et la justifier par la récurrence T(n) = 2T(n/2) + O(n). Et maîtriser BFS/DFS : beaucoup de candidats semblent les découvrir le jour J.
Si tu vises 9-12/20
Q1 : distinguer :: (ajout en tête) et @ (concaténation), pas de conversion liste/tableau abusive. Q2 tri fusion classique avec complexité O(n log n) justifiée. Q3 utiliser vraiment le dictionnaire imposé (pas une simple liste). Q11 question de synthèse, souvent juste quand abordée, à viser même si Q5-Q10 résistent.
Si tu vises 14+ (top 10%)
Q5-Q6 BFS/DFS rigoureux avec mémorisation des sommets visités et gestion explicite de la pile/file. Q10 norme indice 1 connue (||x||₁ = Σ|xᵢ|), pas de recalcul de puissance matricielle à chaque itération. Q13 rédaction fine sur les automates probabilistes. Q17 déterminisation par tableau d'états, pas « de tête ».
Présentation : le jury insiste cette année sur la lisibilité, « indentation des codes », pas de renvois, pas de ratures multipliées. Les questions théoriques sur les automates probabilistes (Q19-Q21) cumulent « beaucoup d'erreurs de calculs » : poser les calculs proprement, traiter avec soin les exemples de l'énoncé. Pas de grappillage : « attitude peu productive » selon le jury, mieux vaut traiter en profondeur Q1-Q11 que survoler tout le sujet.
Conseils du jury
Conseils transversaux
- Tri fusion = O(n log n), justifié par récurrence T(n) = 2T(n/2) + O(n). Pas de O(ln n), O(n) ou O(n!) annoncés au feeling.
- BFS/DFS rigoureux : mémoriser les sommets visités, gérer la file (BFS) ou la pile (DFS) explicitement, savoir distinguer les deux.
- Utiliser la structure de dictionnaire imposée : pas une simple fonction d'appartenance à une liste.
- :: vs @ : ajout en tête vs concaténation, confusion à éviter. Pas de conversions liste/tableau inutiles.
- Norme indice 1 connue : ||x||₁ = Σ|xᵢ|. Soustraction vectorielle dans une fonction dédiée.
- Déterminisation = tableau d'états, méthode systématique. Pas « de tête ».
- Indentation, pas de ratures multipliées : codes lisibles. Le jury l'a souligné spécifiquement cette année.
- Pas de grappillage : approfondir un problème vaut mieux que survoler les deux.
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ