Complexité des algorithmes

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
momento85
Messages: 1
Enregistré le: 15 Sep 2009, 11:18

complexité des algorithmes

par momento85 » 15 Sep 2009, 11:23

Bonjour!! Tu es nouveau sur le forum. Je te prie d'aller lire le réglement du forum avant de poster, et de le respecter!

Considérons le problème du sac à dos sous la forme suivante:

(P):"étant donné n+1 entiers positifs c1,c2,...,cn et K ,existe -il un vecteur x de {0,1}^n tel que : somme (Cj Xj) =K avec j=1...n ? "

Montrer que le problème (P) appartient à la classe NP.Pour cela on décrira soigneusement un codage des données du problème ,on évaluera la taille de ce codage et on exhibera un algorithme non déterministe.



Clembou
Membre Complexe
Messages: 2732
Enregistré le: 03 Aoû 2006, 13:00

par Clembou » 15 Sep 2009, 13:34

Oui, et alors ? :hein:

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 15 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite