CCINP 2019 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2019, filière MP, en 4 heures. Thème : Inversions de permutations, racine carrée d'un langage et mots sans facteur carré.
Ce que traite le sujet, partie par partie
- Partie I : inversions de permutations (Informatique pour tous). Inversions d'une permutation et nombre d'échanges du tri à bulles en Python, table d'inversions et preuve que l'application qui y mène est bijective, avec les fonctions de passage dans les deux sens.
- Partie II : théorie des automates et des langages rationnels. Racine carrée d'un langage, automate de Glushkov d'une expression rationnelle et déterminisation, puis preuve que la racine d'un langage rationnel est rationnelle.
- Partie III : algorithmique des mots sans facteur carré. Fonctions CaML sur les listes, détection naïve d'une répétition et sa complexité, puis algorithme de Main-Lorentz fondé sur les tableaux de préfixes et de suffixes pour détecter un carré centré.
Chapitres à revoir avant de traiter ce sujet
- Tris par sélection, à bulles, par insertion et par comptage
- Bases de Python : expressions, types, instructions, fonctions
- Logique, ensembles et applications
- Langage OCaml : expressions, types, filtrage, récursivité
- Complexité des algorithmes itératifs et récursifs
- Chaînes de caractères et algorithmes sur les textes
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.