Top piège du sujet
Q12 : tableau trié sans dichotomie, seulement 15% des candidats y ont pensé
Statistiques jury
Comment les candidats s'en sont sortis
Notes brutes officielles publiées par le jury — non harmonisées.
Moyenne
9.33
Médiane
9.2
Écart-type
4.06
Q1 (25%)
6.4
Q3 (75%)
12.1
Candidats présents
1 557
sur 1 659 inscrits · 6.1% d'absents
Comparaison
Comment ce sujet se compare aux autres
Moyenne stable par rapport à 2022 (9.33 vs 9.45). Écart-type stable (σ=4.06). Difficulté globale comparable à la session précédente. Effectif -8% (1689 → 1557 présents).
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
Quatre parties dont les trois dernières sont reliées par un même thème : structures de données pour modéliser un ensemble d'entiers positifs. Partie I indépendante sur les langages réguliers (raisonnement inductif, lemme de l'étoile, automates par blocs). Parties II-IV : représentations classiques (liste triée, vecteur trié, ABR), arbre binaire complet étiqueté par booléens, puis arbres de van Emde Boas, efficaces pour les ensembles denses.
Structure de l'épreuve
- Partie I — Langages et automates (partie indépendante)(Q1-Q11)Difficile
Transformation de langages réguliers, raisonnement inductif, lemme de l'étoile, construction d'automates par blocs. « À peine abordée alors qu'elle représentait un gros quart de l'épreuve. »
- Partie II — Structures classiques d'ensembles d'entiers(Q12-Q23)Niveau attendu
Liste triée, vecteur trié (dichotomie attendue), arbre binaire de recherche. Légères variantes d'algorithmes vus en cours en première et deuxième année.
- Partie III — Arbre binaire complet étiqueté par booléens(Q24-Q33)Difficile
Test d'appartenance, insertion/suppression, calcul du minimum, parcours, étude de complexité à chaque fois.
- Partie IV — Arbres de van Emde Boas pour gros ensembles denses(Q34-Q40)Très difficile
Structure d'arbre plus complexe. « Abordée seulement dans les meilleures copies. » La fin de l'épreuve (question 37 et au-delà) n'a quasiment jamais été abordée.
Analyse globale du jury
« Le sujet est relativement long et la fin de l'épreuve (question 37 et au-delà) n'a quasiment jamais été abordée. L'épreuve comporte cette année une proportion plus importante de questions de programmation que de questions théoriques. La partie programmation a été traitée plutôt convenablement par la plupart des copies, avec des algorithmes qui « marchent » mais dont l'efficacité n'est pas toujours optimale. Les réponses apportées aux questions théoriques (tant sur les langages que dans la partie III) ont été, par contre, souvent trop confuses ou sans véritable justification. Sur un nombre non négligeable de copies, la partie I a été à peine abordée alors qu'elle représentait un gros quart de l'épreuve. »
Top pièges sanctionnés
Q12 : tableau trié sans dichotomie, seulement 15% des candidats y ont pensé-2 pts
« Le jury a été un peu déçu de constater que sur un tableau d'entiers trié dans l'ordre croissant, seuls 15% des candidats proposent de faire une dichotomie pour tester la présence d'un élément dans le tableau. »
Confusion langages vs ensembles de mots (Q1, Q7)-2 pts
« Confusion entre a*ba* qui est un langage (ici l'ensemble des mots {a^n b a^p, (n,p) ∈ ℕ²}) et {a*ba^p, p ∈ ℕ} qui est un ensemble de langages (dont l'union vaut a*ba*). »
Lemme de l'étoile mal appliqué (Q4)-2 pts
« L'utilité du lemme de l'étoile est bien comprise mais la mise en pratique est souvent confuse. Dire qu'un automate « ne sait pas compter » n'est en aucun cas une preuve pour justifier qu'un langage tel que {a^n b a^n, n ∈ ℕ} n'est pas régulier. »
Confusions OCaml/Python (// vs /, 2**p, indentation)-2 pts
« On rencontre encore trop souvent des confusions avec Python sur les opérateurs (/ et non // pour la division entière, 2**p qui ne permet pas de calculer 2^p en OCaml) ou sur les délimiteurs (indenter rend un code OCaml plus lisible mais ne permet absolument pas de délimiter des blocs, il faut utiliser par exemple begin/end). »
Présentation et orthographe sanctionnées-1 pts
« Le jury rappelle qu'il apporte une grande attention à la présentation de la copie (une copie aérée avec des résultats encadrés est bien plus facile à lire, ce qui ne peut que profiter au candidat) et a pénalisé les écritures illisibles, en recrudescence. On rencontre aussi encore trop de fautes d'orthographe grossières (« on parcours… » « les languages rationels… »). »
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 2023 · PDF officiel ↗
Contexte
L'épreuve en quelques chiffres
L'épreuve Option Informatique Centrale-Supélec MP 2023 s'est déroulée fin avril 2023, en 4 heures, coefficient 10. Cette option est choisie par les candidats MP ayant suivi le programme d'informatique de deuxième année (alternative à S2I).
Sujet en quatre parties dont les trois dernières sont reliées par un même thème : l'étude de structures de données permettant de modéliser un ensemble d'entiers positifs. La partie I est totalement indépendante (langages réguliers, lemme de l'étoile, construction d'automates par blocs). Les parties II à IV explorent successivement les structures classiques (liste/vecteur trié, ABR), un arbre binaire complet étiqueté par booléens, puis les arbres de van Emde Boas, efficaces pour les ensembles denses.
La moyenne brute s'est établie à 9.33/20, écart-type 4.06. Médiane 9.20, premier quartile 6.40, troisième quartile 12.10. 1557 candidats présents sur 1659 inscrits (6.1% d'absents). Distribution très proche des autres épreuves de la session 2023, l'écart Q1–Q3 est de 5.7 points, ce qui rend l'épreuve discriminante.
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 2023 note que « la partie I a été à peine abordée alors qu'elle représentait un gros quart de l'épreuve ». Stratégie clé : ne pas zapper les langages sous prétexte qu'ils paraissent abstraits, c'est là que se font les écarts entre une copie médiane et une bonne copie. Et inversement, ne pas perdre de temps sur les arbres vEB de la partie IV sauf si le reste est bouclé.
Si tu vises 9-12/20 (médiane à top 25%)
Concentre-toi sur la partie II (structures classiques). Q12, tableau trié, appelle une dichotomie (seulement 15% des candidats y ont pensé), c'est un point facile à 2 pts. Donne systématiquement les complexités demandées (Q23, Q24 ont sanctionné les oublis). En partie I, traite au moins Q1 et Q3 (raisonnement inductif).
Si tu vises 14+ (top 10%)
Il faut traiter rigoureusement la partie I (lemme de l'étoile bien appliqué, construction d'automates avec états initial et final explicites) et bien attaquer la partie III. Pour Q24 (insertion dans arbre III), privilégier la fonction optimisée (recalcul de l'étiquette des ascendants jusqu'à un nœud déjà étiqueté true) plutôt qu'une approche fonctionnelle naïve.
Gestion des 4h : 1h sur la partie I (Q1-Q11, langages, ne PAS sauter), 1h15 sur la partie II (Q12-Q23, structures classiques avec dichotomie soignée), 1h sur la partie III (Q24-Q33, arbre binaire complet), 30 min sur ce qui est faisable de la partie IV (vEB), 15 min de relecture orthographe. Code OCaml strict : pas de // pour la division entière (c'est /), pas de 2**p pour 2^p, et begin/end pour les blocs (l'indentation Python ne fait rien).
Conseils du jury
Cinq conseils transversaux
- Ne pas zapper la théorie des langages. La partie I représente un gros quart de l'épreuve mais a été « à peine abordée » par beaucoup. Maîtriser raisonnement inductif, lemme de l'étoile, automates par blocs.
- Penser dichotomie sur tableau trié. Q12 : seuls 15% des candidats l'ont fait, c'est pourtant l'algorithme classique attendu. Et la dichotomie de Q13 doit être écrite avec une fonction auxiliaire récursive prenant deux indices début/fin.
- OCaml strict, pas Python. Division entière : / et non // ; puissance : pas 2**p mais une fonction puissance ou une astuce ; blocs : begin/end et pas indentation. Connaître List.length et List.mem (inutile de les reprogrammer).
- Indiquer les complexités quand demandées et donner la complexité correcte (Q23, Q24 ont été sanctionnées). Justifier les propriétés d'algorithmes par un invariant de boucle en partie III, pas par paraphrase.
- Soigner la présentation et l'orthographe. Le jury sanctionne les écritures illisibles « en recrudescence » et les fautes grossières (« on parcours… » « les languages rationels… »).
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ