Centrale-Supélec 2019 MP Option informatique : sujet en PDF
Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2019, filière MP, en 4 heures. Thème : Code binaire de Gray et énumération des combinaisons : fonctions Caml, circuits logiques, système de numération combinatoire et problème du sac.
Ce que traite le sujet, partie par partie
- Partie I : code binaire de Gray. Énumération des n-uplets binaires dans l'ordre lexicographique puis dans l'ordre de Gray par deux fonctions mutuellement récursives, complexité et amélioration, expression de la bijection de Gray à l'aide du ou exclusif et de sa réciproque, circuits logiques réalisant ces conversions.
- Partie II : énumération des combinaisons. Combinaisons de p éléments parmi n dans l'ordre lexicographique et fonction donnant la suivante, nombre de combinaisons, existence et unicité de la décomposition d'un entier en somme de coefficients binomiaux, recherche exhaustive pour remplir un sac de capacité donnée et nombre d'additions, puis passage d'une combinaison à la suivante en deux modifications grâce au code de Gray et remplissage optimal du sac.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Architecture de l'ordinateur et représentation des nombres
- Complexité des algorithmes itératifs et récursifs
- Calcul algébrique : sommes, produits, binôme et systèmes linéaires
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.