Dans cet article, nous vous présentons le sujet d’info option tombé au concours Centrale-Supélec pour les filières MP et MPI du 3 mai 2024.
Le sujet
Le titre du sujet est « Optimisation de réseau ».
Il est découpé en 4 parties :
- La première partie étudie des généralités sur les arbres couvrants et une fonction de tri
- La seconde partie présente l’algorithme de Kruskal inversé, ce qui permet de trouver un arbre couvrant de poids minimal dans un graphe connexe
- La troisième partie montre la complexité du problème d’optimisation du réseau en se ramenant au problème de satisfiabilité
- Enfin, la quatrième et dernière partie présente comment approcher une solution au problème d’optimisation en utilisant des arbres couvrant.
Un papier de recherche de 2010 est utilisé en illustration du sujet. Sujet que voici :
