Disons qu'il me semble là qu'on parle de la complexité d'un algorithme donné et pas de la complexité du problème. Alors effectivement, si on ne s'intéresse qu'a la complexité de l'algo, ça va.
Si le programmeur se rend compte que la complexité de son algo est exponentielle il est tout de même très intéressant de savoir dans quelle classe se trouve le problème. S'il est dans P, alors faudra sans doute se creuser la tête pour trouver un algo polynomial. S'il est NP-complet soit on se dit "tant pis" soit faut se tourner vers une bonne approximation. Classer les problèmes ne me parait pas si évident. Bon, on ne lui demandera peut être pas d'en faire la preuve, mais même intuitivement ça nécessite bien souvent une bonne expérience des "réductions" (si on ne veut pas être à côté de la plaque, l'intuition est parfois trompeuse).
Tous les programmeurs ne sont pas confrontés à ces problème et bon nombre d'informaticiens n'ont qu'une connaissance assez vague de ces notions (moi aussi). Je pense cependant que dans certains besoins pratique de l'informatique cela peut arriver. Et quand ça arrive, qu'est-ce qu'on fait ?
[^] # Re: sonntag
Posté par Dr BG . En réponse à la dépêche Lisaac 0.12 en GPL v3. Évalué à 3.
Si le programmeur se rend compte que la complexité de son algo est exponentielle il est tout de même très intéressant de savoir dans quelle classe se trouve le problème. S'il est dans P, alors faudra sans doute se creuser la tête pour trouver un algo polynomial. S'il est NP-complet soit on se dit "tant pis" soit faut se tourner vers une bonne approximation. Classer les problèmes ne me parait pas si évident. Bon, on ne lui demandera peut être pas d'en faire la preuve, mais même intuitivement ça nécessite bien souvent une bonne expérience des "réductions" (si on ne veut pas être à côté de la plaque, l'intuition est parfois trompeuse).
Tous les programmeurs ne sont pas confrontés à ces problème et bon nombre d'informaticiens n'ont qu'une connaissance assez vague de ces notions (moi aussi). Je pense cependant que dans certains besoins pratique de l'informatique cela peut arriver. Et quand ça arrive, qu'est-ce qu'on fait ?