Statistiques jury
Comment les candidats s'en sont sortis
Notes brutes officielles publiées par le jury — non harmonisées.
Moyenne
9.27
Médiane
9.2
Écart-type
3.97
Q1 (25%)
6.3
Q3 (75%)
12.1
Candidats présents
1 519
sur 1 612 inscrits · 5.7% d'absents
Comparaison
Comment ce sujet se compare aux autres
Moyenne 9.27/20 en option Info 2024 — quasi-identique à Option S2I 2024 (9.38) sur le tronc commun « S2I ou info » à 9.34. Médiane 9.20, écart-type 3.97. 1519 présents (32% des effectifs MP). Niveau cohérent avec les épreuves de maths de la session (Maths I et II à 9.19).
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet en quatre parties autour de la construction d'un arbre de Steiner pour un ensemble X dans un graphe connexe G. Partie I : résultats classiques sur les graphes + tri-fusion sur listes. Partie II : algorithme de Kruskal inversé (arbre couvrant minimal) en OCaml. Partie III : réduction satisfiabilité d'une formule logique ↔ recherche d'arbre de Steiner. Partie IV : Floyd-Warshall puis construction polynomiale d'un arbre de Steiner approché.
Structure de l'épreuve
- Partie I — Préliminaires sur les graphes et tri-fusion(Q1-Q8)Niveau attendu
Démonstrations sur les graphes (récurrences sur sommets ou arêtes), fonctions auxiliaires de fusion de listes triées, fonction principale du tri-fusion. Coquilles signalées (Q4 hypothèse de connexité implicite, Q17 graphe G1 mal représenté).
- Partie II — Algorithme de Kruskal inversé(Q9-Q16)Difficile
Programmation OCaml : pour chaque arête (i,j) de poids p, tester si retirer l'arête maintient la connexité via connectes g i j p. Q9 (rappel de Kruskal classique) bien traitée, Q12 (parcours avec table de sommets visités) plus délicate.
- Partie III — Réduction satisfiabilité ↔ arbre de Steiner(Q17-Q26)Très difficile
Logique élémentaire, correspondances entre stable d'un graphe G_φ associé à φ et arbre de Steiner d'un graphe G'_φ. Q22-Q23 connaissent moins de succès. Q24 oublie souvent que la construction de G_φ et G'_φ doit aussi être polynomiale.
- Partie IV — Floyd-Warshall et construction polynomiale(Q27-Q35)Difficile
Algorithme classique des plus courts chemins entre tous sommets, puis construction d'arbre de Steiner approché. Partie IV-A bien traitée, Q33 et Q35 demandent un investissement plus conséquent.
Analyse globale du jury
« Le sujet était de longueur raisonnable mais comportait quelques questions difficiles. Pour avoir une bonne note, il était important de s'intéresser aux quatre parties, qui contenaient toutes des questions abordables. Il y avait cette année une proportion un peu plus importante de questions théoriques que de programmation. La partie programmation, plus facile, a été traitée convenablement. Les réponses aux questions théoriques, en particulier sur les graphes dans les parties I et II, ont été souvent trop confuses, illogiques ou s'appuyaient sur des cas trop particuliers. Le jury rappelle qu'il apporte une grande attention à la présentation des codes. »
Top pièges sanctionnés
Récurrence sur les sommets mal biaisée (Q2-Q3)-2 pts
« La très grande majorité des candidats a choisi de faire des récurrences sur le nombre de sommets des graphes mais certains raisonnent mal. En admettant P(n), pour montrer P(n+1), il s'agit de considérer un graphe G ayant n+1 sommets et de se ramener à un graphe G' ayant un sommet de moins afin de pouvoir, le cas échéant, lui appliquer l'hypothèse de récurrence (et non de partir d'un graphe à n sommets vérifiant la propriété voulue et de lui rajouter un sommet et des arêtes d'une manière biaisée afin d'avoir facilement la propriété au rang n+1). »
Réécriture de fonctions du module List (List.rev) au lieu d'utiliser celles autorisées-1 pts
« Trop de candidats réécrivent les fonctions du module List comme List.rev alors qu'ils les ont sans doute rencontrées dans leur formation et que le sujet disait explicitement qu'on pouvait les utiliser. »
Cas de base oubliés en récursivité (Q8)-2 pts
« Sur la question 8 qui demande d'écrire la fonction principale du tri fusion, nombreux sont ceux qui oublient le cas de la liste vide ou plus subtil, celui de la liste à un élément. Commencez toujours, lors d'un programme récursif, par traiter les cas de base afin de ne pas les oublier ! »
Test de connexité incorrect dans Kruskal inversé (Q13)-2 pts
« La question 13 demandait d'écrire le programme principal de l'algorithme de Kruskal. De nombreux candidats n'ont pas vu qu'à chaque étape, lorsqu'on veut tester si l'arête (ij) de poids p peut être retirée du graphe B en cours, il suffit d'appeler connectes g i j p pour voir si le graphe reste connexe sans cette arête : ils ont testé à la place si tous les sommets restaient connectés au sommet 0 (ou pire si tous les sommets restaient connectés deux à deux) ce qui affecte bien sûr fortement la complexité de l'algorithme. »
Construction de G_φ et G'_φ non polynomiale oubliée (Q24)-2 pts
« Les questions 22 et 23 ont par contre connus moins de succès et dans la question 24, la quasi-totalité des réponses oublient d'évoquer la construction des graphes G_φ et G'_φ qui doit aussi être faite en temps polynomial pour avoir le résultat. »
Chapitres clés à maîtriser
Source : Rapport du jury Centrale-Supélec · Info MP, session 2024 · PDF officiel ↗
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
