Mines-Ponts 2014 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2014, filière MP, en 3 heures. Thème : Automates et langages ; implications logiques, fermeture transitive et axiomatique minimale.
Ce que traite le sujet, partie par partie
- Première partie : automates et langages. Langages des mots dont le nombre de a est fonction du nombre de b : automate pour une fonction constante, expression rationnelle et automate non déterministe pour une fonction de parité, déterminisation, puis non-rationalité lorsque la fonction n'est pas majorée et étude des langages à autant ou plus de a que de b.
- Seconde partie : implications et fermeture transitive. Preuves de longueur k entre propositions et borne n - 1, produit de matrices booléennes, puissances de la matrice d'adjacence et fermeture transitive, puis déduction récursive en O(n²) par un parcours et calcul de la fermeture en O(n³), en Caml ou en Pascal.
- Seconde partie : axiomes et axiomatique minimale. Axiomes des exemples et test d'un axiome à partir de la fermeture transitive, suites unidirectionnelles, existence d'un axiome au-dessus de toute proposition, classes d'équivalence et classes sources, construction d'une axiomatique de cardinal minimum.
Chapitres à revoir avant de traiter ce sujet
- Graphes : représentations et parcours
- Plus courts chemins et applications : Dijkstra, A*, Floyd-Warshall, coloration
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- 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.