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