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

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2021, filière MP, en 4 heures. Thème : Arbres couvrants et pavages : partitions par forêts, algorithme de Wilson, bijection de Temperley et graphe dual.

Ce que traite le sujet, partie par partie

• Partie I : quelques fonctions auxiliaires. En Caml, graphes en listes d'adjacence et tableaux d'adjacence, conversion en O(m + n) justifiée, rang d'une arête du graphe quadrillage G_p,q, fonction réciproque et construction de ce graphe.
• Partie II : caractérisation des arbres. Composantes connexes comme partition des sommets, plus courts chemins, équivalence entre arbre, connexité avec m = n - 1 et absence de cycle avec m = n - 1. Partitions représentées par une forêt : recherche du représentant et réunion selon la hauteur en Caml, minoration |X| >= 2^h(s), complexités et test qu'un graphe est un arbre.
• Partie III : algorithme de Wilson, arbre couvrant aléatoire. Construction d'un arbre couvrant aléatoire enraciné : chemin aléatoire sans boucle codé par un enregistrement à champ mutable et un tableau suivant, question sur la terminaison, puis fonctions marche_aleatoire, greffe et wilson en Caml avec Random.int.
• Partie IV : arbres couvrants et pavages par des dominos. Échiquier à 2p - 1 colonnes et 2q - 1 lignes privé d'un coin, bijection de Temperley entre ses pavages et les arbres couvrants de G_p,q : exemples graphiques dans les deux sens, procédé de calcul du père d'un sommet, fonctions coord_noire, sommet_direction et phi en Caml.
• Partie V : utilisation du dual pour la construction d'un pavage. Graphe dual de G_p,q et sa construction en Caml, dual du dual, cycle et non-connexité, dual d'un arbre couvrant. Conversions entre tableau parent et couple (racine, tableau de booléens) avec leurs complexités, calcul de l'arbre dual, construction du pavage associé à un arbre, pavage aléatoire et adaptation à d'autres tailles d'échiquier.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Logique, ensembles et applications

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.