Théorie des matroïdes et une application
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)
| Qualité | Numéro | Titre |
|---|
Utilisateur : Devevey
La preuve est légèrement modifiée par rapport à celle du livre pour utiliser un invariant de boucle, ce qui permet le recasage dans la leçon 927 et rend la preuve plus formelle.'
Références :
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis - Anne Benoît, Yves Robert, Frédéric Vivien