CCINP 2020 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2020, filière MP, en 4 heures. Thème : Connecteur de Sheffer, problème de Freudenthal, mots de Lyndon et de de Bruijn.

Ce que traite le sujet, partie par partie

• Partie I : logique et calcul des propositions. Mintermes et maxtermes, connecteur de Sheffer, table de vérité, formes normales conjonctive et disjonctive, et expression de tous les connecteurs à partir de ce seul connecteur.
• Partie II : le problème de Freudenthal. Résolution en Python de l'énigme où deux personnes retrouvent deux entiers à partir de leur somme et de leur produit, par des fonctions successives qui filtrent les candidats.
• Partie III.1 : mots de Lyndon. En Caml, mots, conjugués et colliers, test d'un mot de Lyndon, algorithme de génération et sa complexité, factorisation de Lyndon.
• Partie III.2 : mots de de Bruijn. Graphe de de Bruijn, degrés et nombre d'arcs, construction par circuit eulérien, algorithme Prefer One et lien avec les mots de Lyndon, puis application à la recherche d'un code de digicode.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Bases de Python : expressions, types, instructions, fonctions
• Logique, ensembles et applications

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.