e3a-Polytech 2020 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours e3a-Polytech, 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.

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

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