Prepa HelpMines-Ponts 2022 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2022, filière MP, en 3 heures. Thème : Correction orthographique : distance d'édition, tries et systèmes de transitions.
Ce que traite le sujet, partie par partie
- Partie 1.1 : une fonction mystère. Fonction récursive sur une liste d'entiers : signature, terminaison et nombre d'appels, propriété qui caractérise la valeur renvoyée et sa preuve, complexité en espace.
- Partie 1.2 : distance d'édition de Levenshtein. Relation de récurrence entre les distances des préfixes de deux mots, calcul par mémoïsation dans une matrice, complexité et filtrage d'une liste de mots proches, puis décomposition des deux mots autour de symboles communs.
- Partie 2 : fouille dans un trie. Corpus de mots stocké dans un trie persistant fondé sur un dictionnaire de caractères : appartenance, ajout, élagage et partage de la mémoire, nombre de mots à distance au plus k, puis systèmes de transitions déterministes et filtrage d'un trie avec sa complexité.
- Partie 3 : système de transitions des voisins d'un mot brouillé. Scripts de transformation et leur coût, caractérisation des mots à distance au plus k d'un mot brouillé, puis système de transitions non déterministe qui accepte les préfixes de ces mots et adaptation du filtrage du trie sans déterminiser.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Spécifier, tester, prouver : terminaison et correction
- Complexité des algorithmes itératifs et récursifs
- Chaînes de caractères et algorithmes sur les textes
- Dictionnaires et principes du hachage
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.