Mines-Ponts 2015 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2015, filière MP, en 3 heures. Thème : Automates d'arbres : arbres binaires étiquetés, automates descendants et ascendants.
Ce que traite le sujet, partie par partie
- Fonctions utilitaires et arbres binaires étiquetés. Fonctions Caml sur les listes (appartenance, union sans doublon, produit cartésien) avec leur complexité, type Caml des arbres binaires étiquetés, constructeur et taille d'un arbre.
- Langages d'arbres. Arbres contenant une étiquette donnée, arbres complets, arbres-chaînes et arbres impartiaux : exemples et contre-exemples, tout arbre complet est impartial sans réciproque, un arbre impartial non vide a un nombre impair de nœuds.
- Automates d'arbres descendants déterministes. Automate reconnaissant les arbres-chaînes, impossibilité de reconnaître les arbres contenant α0, évaluation récursive d'un automate sur un arbre en Caml, lien avec les automates de mots et les langages rationnels et cas du langage à autant de α0 que de α1.
- Automates d'arbres ascendants. Langage reconnu par un automate ascendant non déterministe, passage d'un automate descendant à un automate ascendant, calcul en Caml des états accessibles à la racine, déterminisation par codage des parties en entiers, clôture par complémentaire, union et intersection avec leurs constructions, et non-rationalité du langage des arbres impartiaux.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Arbres binaires, arbres binaires de recherche et tas
- 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.