Mines-Ponts 2018 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2018, filière MP, en 3 heures. Thème : Recherche de motifs dans un texte : recherche naïve, automates à repli et algorithme de Knuth-Morris-Pratt.
Ce que traite le sujet, partie par partie
- 1 Recherche naïve d'un motif. Chevauchement de deux occurrences et nombre maximal d'occurrences d'un motif, longueur d'une liste et test de préfixe en Caml, recherche naïve des occurrences et sa complexité.
- 2 Automates finis déterministes à repli. Existence d'une transition après un nombre fini de replis, automate complet équivalent et langage reconnu sur un exemple, copie d'un automate et suppression des replis en O(kλ), puis calcul en temps linéaire des préfixes d'un mot acceptés par l'automate.
- 3 Automate de Knuth-Morris-Pratt. Automate KMP associé à un motif et langage reconnu, caractérisation récursive de la fonction de repli, construction en Caml et preuve de sa complexité linéaire par un argument d'amortissement, recherche de toutes les occurrences et comparaison avec la recherche naïve.
- 4 Ensemble de motifs et automates à repli arborescents. Langage d'un automate à repli arborescent, automate pour un ensemble de suffixes, recherche d'un dictionnaire de motifs par appels successifs à KMP et sa complexité, puis principe d'un automate unique pour tous les motifs et gain attendu.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Chaînes de caractères et algorithmes sur les textes
- Complexité des algorithmes itératifs et récursifs
- Arbres binaires, arbres binaires de recherche et tas
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.