Centrale-Supélec 2026 MP Option informatique : sujet en PDF

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2026, filière MP, en 4 heures. Thème : Analyse lexicale par automates, coloration de graphes, file à deux piles et graphes planaires.

Ce que traite le sujet, partie par partie

• Partie A, exercice : coloration syntaxique. Analyse lexicale d'un code OCaml : expression régulière et automate des écritures d'entiers, automate déterministe équivalent à un automate donné, automate des lexèmes avec les constructeurs du type token, complexité de l'analyse, langage des mots ayant autant de parenthèses ouvrantes que fermantes et vérification du parenthésage en temps linéaire.
• Partie B, I : cas de la 2-COLORATION. Graphes bipartis, cycles impairs et 2-coloration. En OCaml, recherche exhaustive en parcourant les colorations comme des entiers en base 2, file implémentée par deux piles et complexité amortie, fonction bicol par parcours en largeur : terminaison, complexité, correction, cas d'un graphe non connexe et parcours en profondeur.
• Partie B, II : cas de la 3-COLORATION. En OCaml, validation partielle d'une coloration, stratégie par retour sur trace pour trouver une 3-coloration, complexité dans le pire cas.
• Partie B, III : graphes planaires. Faces et degrés, formule d'Euler pour les arbres puis les graphes planaires connexes, majorations |A| <= 3|S| - 6 et |A| <= 2|S| - 4, non-planarité de K5 et K3,3, sommet de degré au plus 5. Problèmes Planar-k-COL, résolution de Planar-2-COL en temps linéaire, exemples de graphes colorables, preuve par récurrence et échange de couleurs qu'un graphe planaire est 5-colorable.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Récursivité
• Architecture de l'ordinateur et représentation des nombres
• Logique, ensembles et applications

Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.