CCINP 2021 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2021, filière MP, en 4 heures. Thème : Partitions non croisées, problème Horn-Sat et classes sylvestres.

Ce que traite le sujet, partie par partie

• Partie I : étude des partitions non croisées. En Python, représentation et test d'une partition non croisée ; dénombrement par les nombres C_n, relation de récurrence et fonction de calcul.
• Partie II : logique et étude du problème Horn-Sat. Satisfiabilité de formules, formules de Horn, propagation unitaire itérée (transformation Pi) qui conserve la satisfiabilité d'une forme normale conjonctive, et critère de non-satisfiabilité par l'apparition de la clause vide.
• Partie III : étude des classes sylvestres. En OCaml, insertion dans un arbre binaire de recherche et lecture préfixe, S-équivalence des mots qui donnent le même arbre, puis construction des classes sylvestres par le produit de mélange.

Chapitres à revoir avant de traiter ce sujet

• Arbres binaires, arbres binaires de recherche et tas
• 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.