Centrale-Supélec 2023 MP Option informatique : sujet en PDF

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2023, filière MP, en 4 heures. Thème : Transformations de langages réguliers, structures pour des ensembles d'entiers denses et arbres de van Emde Boas.

Ce que traite le sujet, partie par partie

• Partie I : langages et automates. Langage obtenu en insérant un mot de L dans un mot de K : exemples, formules avec la réunion, la concaténation et l'étoile, stabilité de la régularité, automate à epsilon-transitions. Transformation sigma qui place la dernière lettre en tête, images itérées d'un langage, expression à l'aide des langages L_q,q', régularité et étude de la réciproque.
• Partie II : représentations classiques d'ensembles. En OCaml, successeur dans une liste triée, tableau trié avec recherche dichotomique et union, arbres binaires de recherche : minimum, partition autour d'un entier, insertion à la racine, union, avec les complexités dans le pire cas.
• Partie III : représentation par arbres binaires complets. Numérotation en largeur des nœuds, partie de [0, 2^p - 1] codée par un tableau de booléens où chaque nœud interne porte le ou logique de ses fils. En OCaml : appartenance, construction en O(2^p), insertion, suppression, minimum d'un sous-arbre, successeur avec preuve de l'algorithme et majoration de son coût, cardinal et sa complexité à l'aide de la concavité de log2, intérêts de la structure.
• Partie IV : arbres de van Emde Boas. Parties de [0, 2^(2^p) - 1] codées récursivement par un enregistrement à champs mutables : codage d'un exemple, création, récurrence C(q) = C(sqrt(q)) + O(1), appartenance, successeur, insertion en O(log2(log2(N))) en OCaml, puis relation de récurrence et ordre de grandeur de l'espace mémoire.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Récursivité
• Tri par fusion et tri rapide
• Logique, ensembles et applications
• Dérivabilité et convexité

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.