Mines-Ponts 2023 MP Informatique option MP : sujet en PDF

Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2023, filière MP, en 3 heures. Thème : Résolution du hanjie : logique, retour sur trace et automates.

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

Ce que traite le sujet, partie par partie

• Section 1 : hanjie et calcul de vérité. Unicité de la solution d'une petite grille, tables de vérité et formes normales conjonctives des contraintes d'une ligne et d'une colonne, arbres de preuve en déduction naturelle et absence de preuve pour une formule.
  À revoir : Logique, ensembles et applications
• Section 2 : cadre de résolution systématique. Présolutions représentées par une matrice de couleurs manipulée de façon immuable, accès par numéro de case, traces des rangées et admissibilité, puis recherche d'une solution par retour sur trace à l'aide d'un extenseur.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Récursivité
• Section 3 : résolution autonome des lignes et extenseur. Plus grande extension commune d'une rangée, dénombrement des complétions, expression régulière, automate déterministe et automate de Glushkov du langage d'une indication, déploiement d'un automate le long d'un mot, états accessibles et co-accessibles, mot projeté et extenseur qui propage les déductions, avec une comparaison des complexités par la formule de Stirling.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Dictionnaires et principes du hachage, Complexité des algorithmes itératifs et récursifs

Chapitres à revoir avant de traiter ce sujet

• Logique, ensembles et applications
• Langage OCaml : expressions, types, filtrage, récursivité
• Récursivité
• Dictionnaires et principes du hachage
• 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.