P=np ( question de démonstration ..)

[Marc aurele]

Bonjour à tous ...

Comment pensez vous que l on puisse démontrer qu un algorithme produit bien le résultat escompté autrement qu'en multipliant le nombre de bon résultats en sortie et ainsi de fait l'improbable té qu'il soit faux ..
Merci d'avance pour vos réponses .

[Monsieur23]

Aloha,

Je suis pas sûr de comprendre la question…

Il est possible de prouver qu'un algorithme donne bien le bon résultat, c'est ce qu'on appelle … la preuve d'algorithme.
Notamment, on prouve qu'il termine bien, et qu'il renvoie bien le résultat voulu.

[mathelot]

bonjour,

je connais deux techniques pour étudier les algorithmes



- invariant de boucle (WHILE, LOOP,etc)

0 STO n
0 STO j

WHILE j<6
n+2 STO n
j+1 STO j
ENDWHILE
DISP n


i) l'invariant de boucle est "n pair". ça assure que le résultat est pair.
ii) que le WHILE (toto)
que le programme progresse vers NON toto.
on vérifie qu'il ne boucle pas (ad vitam)

[Marc aurele]

Bonjour et merci pour vos réponses ..

En fait, il s'agit d'un algorithme d'optimisation pour le problème du sac à dos 0/1 ..
L'algorithme en question m'a toujours renvoyé le résultat optimal mais je ne vois pas comment démontrer que ce sera toujours le cas ..

[Marc aurele]

Aloha,

Je suis pas sûr de comprendre la question…

Il est possible de prouver qu'un algorithme donne bien le bon résultat, c'est ce qu'on appelle … la preuve d'algorithme.
Notamment, on prouve qu'il termine bien, et qu'il renvoie bien le résultat voulu.

Je ne connais pas la preuve d'algorithmes.
En quoi cela consiste t il .?

[Monsieur23]

Je ne connais pas la preuve d'algorithmes.
En quoi cela consiste t il .?

Ben justement, à montrer que ton algorithme renvoie bien ce que tu veux.