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

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2024, filière MP, en 4 heures. Thème : Optimisation de réseau : arbres couvrants de poids minimal, algorithme de Kruskal inversé, arbre de Steiner et approximation.

Ce que traite le sujet, partie par partie

• Partie I : généralités. Arbre couvrant de poids minimal sur un exemple, nombre d'arêtes et équivalences caractérisant un arbre, unicité de l'arbre minimal quand les poids sont distincts, arête de poids maximal dans un cycle, puis séparation, fusion et tri fusion de listes en OCaml avec sa complexité.
• Partie II : algorithme de Kruskal inversé. Rappel de l'algorithme de Kruskal et de sa complexité, exécution de la variante inversée sur un exemple, implémentation en OCaml sur des listes d'adjacence pondérées (tri des arêtes, test de connexion en temps linéaire), preuve que le résultat est un arbre couvrant de poids minimal, complexité commentée.
• Partie III : difficulté du calcul de l'arbre optimal. Problème de l'arbre de Steiner dans un graphe non pondéré. Formule en 3-FNC et graphe associé : équivalence entre satisfaisabilité et existence d'un stable de taille m, construction d'un graphe G' qui relie les stables aux arbres de Steiner, conséquence sur le calcul d'un arbre ayant un nombre minimal de sommets de Steiner.
• Partie IV : approximation du problème. Algorithme de Floyd-Warshall : matrice d'adjacence, relation de récurrence, distances et prédécesseurs en OCaml, complexité, reconstruction d'une chaîne de poids minimal. Algorithme approché de l'arbre de Steiner pondéré, majoration f(T) <= 2 f(T*), renumérotation des sommets, fonction steiner_approche et sa complexité.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Tri par fusion et tri rapide
• 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.