Développement : Théorie des matroïdes et une application

Détails/Enoncé :

On prouve grâce aux propriétés de certains ensemble, appelés matroïdes, l'optimalité des algorithmes gloutons sur ces ensembles.
On applique ensuite cette théorie pour prouver l'optimalité des solutions renvoyées par l'algorithme de Kruskall (calcul d'arbres couvrants de poids minimal)

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :