Pulsars
Log inSign up
Competitive examComputer scienceFranceCPGEMP2026

Centrale-Supélec 2026 — Option informatique (MP)

Sujet officiel de Option informatique du Concours Centrale-Supélec 2026, filière MP. Le document est consulté depuis le site du concours.

Paper from the education system of France

9 exercises 18 views 12 downloadsDownloaded by 1 peopleOpen the official paper

Official exam paper

Source: Concours Centrale-Supélec

Official paper published by Concours Centrale-Supélec. Displayed from the exam board's own website — Pulsars hosts no copy of it.

Open the official paper
Download the solutions (PDF)

Independent solutions, written by Pulsars. Neither official nor affiliated with Concours Centrale-Supélec.

  1. Exercise 1 — Partie A · I — Automates et analyse lexicale (Q1 à Q6)

    An OCaml source is analysed lexically in order to highlight its syntax.

    • Q1, Q2 — regular expression for the binary representations of integers, then a deterministic automaton; adapt it to base 10.
    • Q3 — the language recognised by the automaton of figure 1, and an equivalent deterministic one.
    • Q4 — why a deterministic automaton recognises the set of lexemes.
    • Q5 — an automaton for in, let and variable names.
    • Q6 — the complexity of the lexical analysis phase.

  2. Exercise 2 — Partie A · II — Un langage non régulier (Q7, Q8)

    L is the set of words containing as many opening parentheses as closing ones.

    • Q7 — L is not regular.
    • Q8 — recognise a well-parenthesised list of tokens in linear time.

  3. Exercise 3 — Partie B · I.1 — Graphes bipartis (Q9 à Q11)

    • Q9 — a graph is 2-colourable if and only if it is bipartite.
    • Q10 — an odd cycle prevents 2-colouring.
    • Q11 — conversely, the absence of an odd cycle guarantees it.

  4. Exercise 4 — Partie B · I.2 — Une solution naïve (Q12 à Q15)

    A 2-colouring is viewed as an integer written in base 2 in an array.

    • Q12 — the function suivante, which moves to the next 2-colouring.
    • Q13 — the function valide.
    • Q14 — the exhaustive search bicolnaif.
    • Q15 — its worst-case complexity.

  5. Exercise 5 — Partie B · I.3 — Une file avec deux piles (Q16 à Q21)

    • Q16 — the OCaml list as a stack structure.
    • Q17 — the four queue operations: initFile, estVideFile, enfile, defile.
    • Q18, Q19 — the output order, and the worst-case cost of a defile.
    • Q20, Q21 — the amortised cost, by a counting argument.

  6. Exercise 6 — Partie B · I.4 — Bicoloration par parcours (Q22 à Q27)

    • Q22 — the function bicol, by breadth-first traversal.
    • Q23 to Q25 — termination, complexity, correctness.
    • Q26 — adapting it to disconnected graphs.
    • Q27 — the depth-first variant.

  7. Exercise 7 — Partie B · II — La 3-coloration par retour sur trace (Q28 à Q30)

    • Q28 — the partial validation partial.
    • Q29 — the function backtracking.
    • Q30 — its worst-case complexity.

  8. Exercise 8 — Partie B · III.1 — La formule d'Euler (Q31 à Q36)

    • Q31 — the sum of the degrees of the vertices and that of the degrees of the faces.
    • Q32, Q33 — Euler's formula, first for trees, then in general.
    • Q34, Q35 — the bound |A| ⩽ 3|S| − 6, the non-planarity of K_5, and the existence of a vertex of small degree.
    • Q36 — the bipartite case and K_{3,3}.

  9. Exercise 9 — Partie B · III.2 à III.4 — Planar-k-COL et les cinq couleurs (Q37 à Q43)

    • Q37 — solve Planar-2-COL in linear time.
    • Q38, Q39 — the graphs of figure 5, then three examples to construct.
    • Q40 to Q43 — the induction for the five colour theorem, by swapping colours along Kempe chains.
Generated solutions must be checked against the original exam paper. Open the official paper.