CCINP 2018 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2018, filière MP, en 4 heures. Thème : Énigmes de boîtes, automate minimal, transformation de Burrows-Wheeler et codage RLE.
Ce que traite le sujet, partie par partie
- Partie I : logique et calcul des propositions. Trois épreuves d'un jeu où il faut choisir une boîte à partir d'inscriptions vraies ou fausses : formules propositionnelles, simplification et raisonnement par l'absurde.
- Partie II : automates. Résiduels d'un langage, relation d'équivalence de Nerode et automate minimal, puis algorithme de recherche des états équivalents appliqué à un exemple pour construire l'automate minimal.
- Partie III : algorithmique et programmation. Transformation de Burrows-Wheeler en CaML : permutations circulaires, tri par insertion récursif et complexité, codage puis reconstruction de la matrice pour le décodage ; codage et décodage par plages RLE en Python.
Chapitres à revoir avant de traiter ce sujet
- Logique, ensembles et applications
- Langage OCaml : expressions, types, filtrage, récursivité
- Tris par sélection, à bulles, par insertion et par comptage
- Chaînes de caractères et algorithmes sur les textes
- Complexité des algorithmes itératifs et récursifs
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.