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 :

Références utilisées dans les versions de ce développement :

A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis, Anne Benoît, Yves Robert, Frédéric Vivien (utilisée dans 5 versions au total)