Mines-Ponts 2019 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2019, filière MP, en 3 heures. Thème : Morphismes d'automates et réduction des automates déterministes.
Ce que traite le sujet, partie par partie
- 1 Premiers exemples et 2 États accessibles d'un automate. Description des langages reconnus par quelques automates déterministes complets, tableau des positions d'une liste, états accessibles par un parcours en profondeur depuis l'état initial avec sa complexité et construction de la partie accessible en Caml.
- 3 Morphismes d'automates. Exemples et absence de morphisme entre automates donnés, conservation du langage reconnu, isomorphismes entre automates de même taille, composition, puis test en Caml de l'existence d'un morphisme entre deux automates accessibles.
- 4 Constructions de morphismes d'automates. Automate produit et sa partie accessible, morphisme vers chacun des facteurs quand les langages coïncident, relation d'équivalence engendrée par deux morphismes, automate quotient et morphismes vers lui, renumérotation des classes et calcul de la relation en Caml.
- 5 Réduction d'automates. Existence et unicité à isomorphisme près de l'automate accessible minimal d'un langage rationnel, fusion d'états sur un exemple, table des paires d'états distinguables par un parcours du graphe des paires en O(n²) et construction de l'automate réduit.
Chapitres à revoir avant de traiter ce sujet
- Graphes : représentations et parcours
- Langage OCaml : expressions, types, filtrage, récursivité
- 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.