Discussion :

[debalgo]

Salut,

y a til qq'un qui peut m'expliquer que signifie ces deux phrases :
les problème de flow shop sont NPcomplets.
Un algorithme n'est considéré efficace si et seulement si il est polynomial.

Merci d'avance !

[CedricMocquillon]

Il existe un FAQ Algorithmes http://algo.developpez.com/faq/?page=complexe mais elle est un peu sommaire pour ce qui est de la complexité. Sinon tu peux aller voir sur wikipédia. Après pour tes phrases, elles sont un peu étranges: les problèmes de flow-shop ne sont pas tous NP-Difficiles, cela dépend de ce que tu cherches à optimiser, des contraintes à prendre en compte, du nombre de machines,... Pour la seconde c'est pareil c'est un peu vite dit, cela dépend de ce que tu cherches à obtenir: si tu as prouvé que ton problème est NP-Difficile, tu as deux options devant toi: soit tu veux une solution rapidement (en terme de temps de calcul) mais qui ne sera pas optimale (là effectivement, il est préférable d'avoir un algorithme polynomial), soit tu veux absolument avoir la solution optimale (et là l'algorithme le plus efficace ne sera pas polynomial).
Un autre exemple est si tu as démontré que ton problème est polynomial mais que le meilleur algorithme est en O(n^100), pour de petites instances il sera tout de même préférable de faire une énumération des solutions possibles.
Tout ça pour dire qu'en science rien n'est jamais tout à fait blanc ou noir, cela dépend fortement du contexte