Prepa HelpMines-Ponts 2021 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2021, filière MP, en 3 heures. Thème : Jeu du solitaire : parcours en largeur et automates.
Ce que traite le sujet, partie par partie
- Parties 1.1 et 1.2 : numérotation du tablier et motifs. Choix du parcours adapté à un chemin de longueur minimale, numérotation des 37 encoches du tablier européen, puis représentation d'un motif par les bits d'un entier, avec les opérateurs bit à bit pour tester un motif ponctuel ou une inclusion et décaler une encoche.
- Parties 1.3 et 1.4 : coups et partie de longueur minimale. Listes des coups simples et composés depuis un motif, puis nombre minimal de coups composés entre deux motifs par une exploration en strates appuyée sur un dictionnaire, et lien avec le parcours en largeur d'un graphe des motifs.
- Parties 2.1 et 2.2 : motifs ponctuels et bascules d'une encoche. Sur le tablier n x 1 codé par des mots binaires : expression rationnelle, automate et caractère local du langage des motifs ponctuels, puis variant pondéré par les puissances de (racine de 5 - 1)/2 qui borne le nombre de changements d'état d'une encoche au cours d'une partie.
- Partie 2.3 : trace d'une partie et motifs résolubles. Construction de la trace d'une partie colonne par colonne, alphabet fini des colonnes, langage local des traces et automate fini qui reconnaît les motifs résolubles, d'où un algorithme de décision de complexité optimale.
Chapitres à revoir avant de traiter ce sujet
- Architecture de l'ordinateur et représentation des nombres
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- 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.