CCINP 2017 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2017, filière MP, en 4 heures. Thème : Énigme de logique, recherche dichotomique et produit synchronisé d'automates.
Ce que traite le sujet, partie par partie
- Partie I : logique et calcul des propositions. Interlocuteurs qui disent tous la vérité ou tous mentir sur un même sujet : traduction des indications en formules et recherche du bon chemin par les propriétés des opérateurs booléens puis par tables de vérité.
- Partie II : algorithmique et programmation (Informatique pour tous). Recherche dichotomique de la position d'une valeur dans une séquence croissante en Python : trace d'exécution, correction, terminaison et cas de complexité.
- Partie III : automates et langages. Mots, langages et automates en CaML et en Python, préfixage et acceptation d'un mot avec leur complexité, puis produit synchronisé de deux mots, de deux langages et de deux automates, et preuve que l'automate produit reconnaît le produit des langages.
Chapitres à revoir avant de traiter ce sujet
- Logique, ensembles et applications
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Spécifier, tester, prouver : terminaison et correction
- Complexité des algorithmes itératifs et récursifs
- Langage OCaml : expressions, types, filtrage, récursivité
- Bases de Python : expressions, types, instructions, fonctions
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.