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

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2022, filière MP, en 4 heures. Thème : Automates et expressions rationnelles : miroir, déterminisation, algorithmes de Brzozowski et de Conway, dérivées d'Antimirov.

Ce que traite le sujet, partie par partie

• Partie I : mots et automates. Langage miroir et automate transposé, palindromes et rationalité, reconnaissabilité des langages D(L) et R(L). Déterminisation à la main puis en Caml, ensembles d'états codés par des entiers, table de transition et renumérotation, complexités, puis algorithme de Brzozowski, langages u^(-1) L et fonction minimal.
• Partie II : expression rationnelle associée à un automate. Type exprat en Caml : nombre de lettres, test du langage vide, simplification selon des règles données. Matrices d'expressions rationnelles : somme, produit, étoile définie par blocs, complexités des découpages C(n) = 2C(n - 1) + O(n^2) et C(n) = 4C(n/2) + O(n^3), fonction etoile, puis algorithme de Conway pour écrire le langage d'un automate.
• Partie III : automate des dérivées d'Antimirov. Dérivées partielles d'une expression rationnelle par une lettre puis par un mot, calcul et dessin de l'automate sur un exemple, preuve que l'automate d'Antimirov reconnaît le langage de l'expression, majoration du cardinal de Q(E) par le nombre de lettres de E et conséquence sur l'automate.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Tri par fusion et tri rapide
• Récursivité
• Logique, ensembles et applications
• Architecture de l'ordinateur et représentation des nombres
• Arithmétique dans l'ensemble des entiers relatifs

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.