e3a-Polytech 2024 MP Informatique : sujet en PDF

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

Lire le sujet 8 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,4 Mo)

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.
  À revoir : Bases de Python : expressions, types, instructions, fonctions
• 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.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Logique, ensembles et applications, Complexité des algorithmes itératifs et récursifs
• 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.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Complexité des algorithmes itératifs et récursifs

Chapitres à revoir avant de traiter ce sujet

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