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

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)

   On analyse lexicalement un source OCaml pour en colorer la syntaxe.

   • Q1, Q2 — expression régulière des écritures binaires d'entiers, puis un automate déterministe ; l'adapter à la base 10.
   • Q3 — le langage reconnu par l'automate de la figure 1, et un déterministe équivalent.
   • Q4 — pourquoi un automate déterministe reconnaît l'ensemble des lexèmes.
   • Q5 — un automate pour in, let et les noms de variables.
   • Q6 — la complexité de la phase d'analyse lexicale.
   View solution

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

   L est l'ensemble des mots comportant autant de parenthèses ouvrantes que de fermantes.

   • Q7 — L n'est pas régulier.
   • Q8 — reconnaître en temps linéaire une liste de tokens bien parenthésée.
   View solution

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

   • Q9 — un graphe est 2-colorable si et seulement s'il est biparti.
   • Q10 — un cycle impair empêche la 2-coloration.
   • Q11 — réciproquement, l'absence de cycle impair la garantit.
   View solution

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

   Une bicoloration est vue comme un entier écrit en base 2 dans un tableau.

   • Q12 — la fonction suivante, qui passe à la bicoloration suivante.
   • Q13 — la fonction valide.
   • Q14 — la recherche exhaustive bicolnaif.
   • Q15 — sa complexité dans le pire cas.
   View solution

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

   • Q16 — la liste OCaml comme structure de pile.
   • Q17 — les quatre opérations de la file : initFile, estVideFile, enfile, defile.
   • Q18, Q19 — l'ordre de sortie, et le coût d'un defile dans le pire cas.
   • Q20, Q21 — le coût amorti, par un argument de comptage.
   View solution

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

   • Q22 — la fonction bicol, par parcours en largeur.
   • Q23 à Q25 — terminaison, complexité, correction.
   • Q26 — l'adapter aux graphes non connexes.
   • Q27 — la variante en profondeur.
   View solution

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

   • Q28 — la validation partielle partial.
   • Q29 — la fonction backtracking.
   • Q30 — sa complexité dans le pire cas.
   View solution

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

   • Q31 — la somme des degrés des sommets et celle des degrés des faces.
   • Q32, Q33 — la formule d'Euler, d'abord pour les arbres, puis en général.
   • Q34, Q35 — la majoration |A| ⩽ 3|S| − 6, la non-planarité de K_5, et l'existence d'un sommet de petit degré.
   • Q36 — le cas biparti et K_{3,3}.
   View solution

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

   • Q37 — résoudre Planar-2-COL en temps linéaire.
   • Q38, Q39 — les graphes de la figure 5, puis trois exemples à construire.
   • Q40 à Q43 — la récurrence du théorème des cinq couleurs, par échange de couleurs le long des chaînes de Kempe.
   View solution