Utilisateur : Emile
Développements
Développement : Universalité d'un langage rationnel
On peut se contenter du côté PSPACE-difficile, tant qu'on a l'idée pour le reste de la preuve.
Références :
Le Langage des machines - Floyd, Beigel
Développement : Correction des algorithmes de Prim et Kruskal
On utilise la preuve du Cormen qui traite le cas général de ce type d'algorithmes.
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest