NP-Complet

[ee94]

Bonjour à tous et à toutes
J'ai pas bien compris la phrase suivante: ordonnancement des instructions NP-Complet.
Pourriez vous m'expliquer cette phrase ?
merci d'avance
-----

[kwariz]

Bonjour,

ça ressemble plus à un titre qu'à une phrase, mais en substance l'ordonnancement des exécutions est une technique qui permet de tirer partie de l'architecture parallèle de certains processeurs pour augmenter la vitesse d'exécution d'un programme en modifiant l'ordre des instructions.
NP-complet indique que c'est un problème qui a été prouvé difficile à résoudre mais qu'on dispose d'une procédure simple en temps polynomial pour vérifier une si une proposition de solution est bien une solution. Difficile à résoudre signifie qu'il n'existe aucun algorithme connu en temps polynomial pour trouver une solution, certains conjecturent qu'il n'en n'existe aucun : c'est la conjecture P≠NP.
Voilà, mais peut-être pourrais-tu nous donner un contexte pour mieux t'aider ?

[ee94]

merci
il s'agit d'un cours de DSP, pour comparer VLIW et RISC/CISC. ils ont précisé ce problème mais vu de mon bagage j'ai rien compris
Que signifie NP ?? c'est un acronyme de quoi ??

[kwariz]

NP est un acronyme pour Non deterministic Polynomial.
En très gros on mesure l'efficacité des algorithmes en comparant le temps (ici pris au sens large) pris pour finir l'exécution à la taille des données fournies à l'algorithme. Par exemple, il y a un algorithme d'addition qui si on lui donne deux nombres de n chiffres donne le bon résultat en un temps proportionnel aux nombre de chiffres, i.e. additionner deux nombres de 10 chiffres prendra 2 fois plus de temps qu'additionner deux nombres de 5 chiffres : le temps est proportionnel à n qui est un polynome, on dit cet algorithme polynomial. De la même manière il existe un algorithme de multiplication dont le temps d'exécution sera proportionnel au carré du nombre de chiffres des nombres à multiplier, cet algorithme est toujours polynomial car proportionnel à n², on dit qu'il est en O(n²). Multiplier est doncen ce sens plus «compliqué» qu'additionner. Il existe aussi bien des problèmes plus facile à résoudre qu'une addition (par exemple déterminer si un certain nombre se trouve dans un tableau trié) que des problèmes plus compliqués qu'une addition mais moins qu'une multiplication (trier un tableau) et d'autres beaucoup plus compliqués (déterminer si on peut tracer une figure sans lever le crayon en ne passant qu'une fois par chaque point).
Si on s'intéresse aux problèmes dont la réponse est oui ou non, comme dans «peut-on tracer cette figure sans lever le crayon en ne passant qu'une fois par chaque point?» on peut regrouper les algorithmes en classes. La classe P est la classe des algorithmes polynomiaux : on trouve la réponse en temps polynomial. La classe NP est définie comme la classe des problèmes pour lesquels il existe un algorithme qui vérifié si une proposition est une solution, pour le problème de la figure c'est relativement simple : si tu me donnes la liste des points par lesquels tu passes je peux facilement vérifier que tu passes par tout les points une et une seule fois sans lever le crayon. On appelle cette classe Non Deterministic Polynomial car si on disposait d'une machine magique (on appelle ça un oracle dans le jargon) qui te donne la solution alors tu pourrais répondre en temps polynomial à la question. Le non deterministic vient de l'intervention d'un oracle qui choisit miraculeusement la bonne solution.
On dir d'un problème qu'il est NP-difficile s'il est au moins aussi difficile à résoudre que les problèmes les plus difficiles de NP (ceux dont les solutions sont difficiles à trouver mais faciles à vérifier). Si un problème est à la fois dans NP et est NP-difficile (on dit aussi NP-dur) alors c'est un problème NP-complet.
Normalement cela concerne les problèmes de décision (ceux dont le résultat est oui ou non), mais on peut étendre la notion de NP-dur à tous les problèmes et par abus de langage on les dira aussi NP-Complets.

Bon je t'ai fait une tartine juste pour dire qu'un problème dit NP-complet est simplement un problème considéré comme très (mais très) difficile à résoudre, et que si on veut une réponse rapidement il va falloir se contenter d'une approximation qui pourra ne pas être la solution optimale.

[A voir en vidéo sur Futura]

[ee94]

Merci beaucoup
votre réponse est très claire