Top piège du sujet
Récurrence sur les sommets mal biaisée (Q2-Q3)
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).
Calculateur
Où je me situe sur ce sujet ?
Entrez votre note brute. Le percentile et la position se mettent à jour en temps réel.
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
Bosse chaque chapitre sur d'autres sujets de concours qui le couvrent.
Source : Rapport du jury Centrale-Supélec · Info MP, session 2024 · PDF officiel ↗
Contexte
L'épreuve en quelques chiffres
L'épreuve Option Informatique Centrale-Supélec MP 2024 s'est déroulée fin avril 2024, en 4 heures, coefficient 10. Épreuve d'option choisie par environ 32% des effectifs MP (1519 sur 4735), l'autre choix étant l'Option S2I.
Sujet en quatre parties autour des arbres de Steiner : un sous-graphe contenant les sommets d'un ensemble X et qui soit un arbre. Partie I : résultats classiques sur les graphes + programmation d'un tri-fusion sur listes. Partie II : algorithme de Kruskal inversé (arbre couvrant de poids minimal). Partie III : réduction logique de la satisfiabilité d'une formule vers la recherche d'arbre de Steiner. Partie IV : Floyd-Warshall puis construction polynomiale d'un arbre de Steiner approché.
La moyenne brute s'est établie à 9.27/20, écart-type 3.97. Médiane 9.20, premier quartile 6.30, troisième quartile 12.10. 1519 présents sur 1612 inscrits (taux d'absents 5.7%). Le sujet contenait plusieurs coquilles (Q4, Q9, Q17 graphe G1 mal représenté) que le jury a traitées avec souplesse.
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 2024 confirme : « pour avoir une bonne note, il était important de s'intéresser aux quatre parties, qui contenaient toutes des questions abordables ». La partie programmation est plus facile et bien traitée ; les questions théoriques sur les graphes (parties I-II) sont mal rédigées par beaucoup de candidats. Stratégie clé : réserver du temps pour balayer les quatre parties et soigner les codes OCaml (cas de base, noms de variables, présentation).
Si tu vises 9-12/20 (médiane à top 25%)
Capitalise sur les questions de programmation : Q7 (fusion de listes triées, récursif simple non terminal), Q8 (tri-fusion principal, n'oublie pas les cas de base liste vide et liste à un élément), Q9 (rappel Kruskal classique). Sur Q13, utilise impérativement connectes g i j p au lieu de tester la connexité de tous les sommets au sommet 0.
Si tu vises 14+ (top ~12%)
Il faut traiter Q12 (parcours de graphe avec tableau de marquage), la partie III complète (réduction satisfiabilité-Steiner) et Q24 en évoquant explicitement la polynomialité de la construction de G_φ et G'_φ. La partie IV-B (Q33-Q35) demande un investissement conséquent.
Gestion des 4h : 1h sur la partie I (Q1-Q8), 1h sur la partie II (Q9-Q16, Kruskal inversé), 50 min sur la partie III (Q17-Q26, après avoir lu la « bonne » figure G1), 50 min sur la partie IV-A (Q27-Q32, Floyd-Warshall), 20 min de relecture. Le jury insiste sur la présentation : copies aérées, codes avec begin/end, noms de variables explicites, pas de aux1, aux2, l, m, n sans description.
Conseils du jury
Cinq conseils transversaux
- S'imposer un entraînement régulier sur machine : seul moyen d'acquérir de bons réflexes en programmation et de s'habituer à rédiger en détail des questions théoriques.
- Toujours traiter les cas de base dans un programme récursif (liste vide, liste à un élément), première chose à écrire pour éviter les oublis.
- Utiliser les fonctions du module List autorisées (notamment List.rev) au lieu de les réécrire, gain de temps, code plus lisible.
- Présentation aérée des codes avec begin/end (l'indentation OCaml ne délimite pas les blocs), noms de variables représentatifs, résultats encadrés.
- Récurrence sur les graphes : descendre de n+1 à n, pas l'inverse. Considérer un graphe G de n+1 sommets et le ramener à un graphe G' de n sommets, pas l'inverse.
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ