Centrale-Supélec 2017 MP Option informatique : sujet en PDF
Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2017, filière MP, en 4 heures. Thème : Mots synchronisants d'un automate déterministe complet : parcours en largeur, réduction depuis SAT et existence par l'automate des parties.
Ce que traite le sujet, partie par partie
- Partie I : considérations générales. Mots synchronisants sur de petites machines, fonctions Caml qui calculent l'état atteint après lecture d'un mot et testent si un mot est synchronisant, condition nécessaire d'existence, langage des mots synchronisants et lien entre problème d'existence et calcul d'un mot.
- Partie II : algorithmes classiques. File d'attente implantée par un vecteur circulaire, terminaison, complexité et invariant d'un parcours en largeur depuis un ensemble de sommets, distances obtenues, fonctions Caml qui calculent les sommets accessibles et reconstruisent un chemin.
- Partie III : réduction SAT. Machine associée à une formule sous forme normale conjonctive, preuve que la formule est satisfiable si et seulement si la machine a un mot synchronisant de longueur au plus égale au nombre de variables, conséquence sur la difficulté du problème du plus court mot synchronisant.
- Partie IV : existence. Évolution du cardinal des images successives de l'ensemble des états, critère d'existence par paires d'états, machine dont les états sont les parties à un ou deux éléments, nombre de ses états et codage par des entiers, fonction Caml qui décide l'existence d'un mot synchronisant par un parcours.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Piles, files et deques
- Spécifier, tester, prouver : terminaison et correction
- Complexité des algorithmes itératifs et récursifs
- 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.