CCINP 2024 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2024, filière MP, en 4 heures. Thème : Coloration de graphes, satisfiabilité et reconnaissance de motifs par automates.

Ce que traite le sujet, partie par partie

• Partie I : coloration de graphes. Nombre chromatique, encadrement entre la taille de la plus grande clique et le nombre de sommets, puis heuristique de Welsh-Powell en Python sur des dictionnaires d'adjacence, et modélisation de groupes de travail par une coloration.
• Partie II : satisfiabilité d'une formule propositionnelle. En OCaml, problème CNF-SAT : évaluation d'une forme normale conjonctive, énumération des valuations et complexité, stratégie de retour sur trace, conséquence logique et arbre de preuve en déduction naturelle.
• Partie III : automates et reconnaissance de motifs. En OCaml, recherche naïve d'un motif et sa complexité, période et bords d'un mot, automate de recherche, élimination des états et localisation des occurrences avec preuve de correction.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Bases de Python : expressions, types, instructions, fonctions
• 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.