CCINP 2015 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2015, filière MP, en 4 heures. Thème : Test d'un programme de dialogue, racine carrée d'un automate, tri à bulles et tri par tas.
Ce que traite le sujet, partie par partie
- Partie I : logique et calcul des propositions. Vérification des réponses d'un programme qui doit donner trois affirmations dont une seule est vraie : traduction en formules propositionnelles et résolution par les lois de De Morgan puis par tables de vérité.
- Partie II : automates et langages. Opérateur racine carrée d'un langage et d'un automate fini complet déterministe : expressions régulières de quelques langages, construction de l'automate racine et preuve qu'il reconnaît la racine du langage.
- Partie III : algorithmique et programmation. En Python et en CaML, tri à bulles avec trace d'exécution, correction, terminaison et cas de complexité ; puis arbres binaires, hauteur, arbres complets et parfaits numérotés dans un tableau, construction d'un tas et tri par tas.
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
- Spécifier, tester, prouver : terminaison et correction
- 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.