comment évaluer/mesurer la complexité ?

[JPL]

En fait "complexité algorithmique" est une traduction un peu malheureuse de "Computational Complexity Theory"... complexité computationnelle serait àmha un meilleur choix, ou complexité calculatoire si on préfère le laid à l'anglicisme.

Un peu hors sujet, mais c'est la minute de maître Capello : comput (au sens de calendrier ecclésiastique) existe dans la langue française bien que d'emploi très restreint ou désuet. Computation existe aussi avec le sens de calcul des dates. Il n'était donc pas nécessaire de créer en français le mot ordinateur ; computeur aurait été parfaitement correct et le sens de computation aurait pu être étendu sans problème. D'autant que dans la religion catholique l'ordinateur est celui qui confère les ordre à un postulant (diaconat, prêtrise, etc.) lors d'une cérémonie.
-----

[inviteccac9361]

D'autant que dans la religion catholique l'ordinateur est celui qui confère les ordre à un postulant (diaconat, prêtrise, etc.) lors d'une cérémonie.

L'ordinateur en tant que machine est plutôt censé (du moins à notre époque...) faire l'inverse, recevoir des ordres, les executer.
Bien que des fois, avec certains systèmes on se demande.

J'admet néanmoins que la limite du conversationnel est assez floue à ce niveau.
http://fr.wikipedia.org/wiki/Conversationnel

[invite4492c379]

Oui c'est vrai que c'est un autre sens possible, mais ce nom suggère une interprétation fausse àmha. Ce qui est complexe en théorie de la complexité ce ne sont pas les algorithmes mais les problèmes: par exemple l'algorithme de pesdecoa prend un temps infini actuel (donc hors Turing!) alors qu'en fait le résultat peut s'obtenir beaucoup plus rapidement. Il n'y a donc pas de sens (ou pas de sens utile*) à classifier la complexité en fonction du comportement des algorithmes. En classifiant en fonction des problèmes (et des ressources) on aboutit directement à classifier la complexité en fonction du meilleur algorithme donnant le même résultat, ce qui est plus intéressant.

En fait "complexité algorithmique" est une traduction un peu malheureuse de "Computational Complexity Theory"... complexité computationnelle serait àmha un meilleur choix, ou complexité calculatoire si on préfère le laid à l'anglicisme.


* quoique... on pourrait peut-être obtenir des classes intéressantes en fonction de la facilité à trouver un algorithme qui résout les problèmes de cette classe plutôt que de l'algorithme le plus efficace... je ne sais pas si cela à vraiment un sens mais ce serait peut-être intéressant d'y réfléchir. Merci pour cette piste de réflexion suscitée!

Tu soulèves deux aspects.
D'un côté on étudie le comportement des algorithmes. Ce comportement est déterminé non seulement en fonction d'une métrique sur les données, on considère non seulement certains attributs des données comme leur nombre, ou leur taille (en chiffres en bits en caractères) ou dans le cas d'un graphe le nombre de sommets et/ou d'arêtes, mais également d'une autre métrique qui sera spécifique à un but : nombre de comparaisons pour les tris par comparaisons, nombre de multiplications pour les algo de multiplications de matrices, espace mémoire nécessaire, .... On parlera, peut-être abusivement, de la complexité en temps ou en espace d'un algorithme.

D'un autre côté on étudie les problèmes de décision. Pour un problème de décision pour lequel nous disposons d'algorithmes de résolution, nous pouvons comparer leur complexité computationnelle (le terme ne me choque pas). Celui qui aura la plus petite complexité dans le pire cas donnera une borne supérieure de la complexité computationnelle du problème (parfois il s'agit plus que d'une simple borne). Les problèmes dont on connaît un algorithme de résolution en temps polynomial seront regroupés dans une classe nommée P (assimilés aux problèmes facilement résolubles), ceux dont on peut seulement vérifier en temps polynomial qu'un candidat est une solution seront regroupés dans une classe nommée NP (assimilés aux problèmes difficiles à résoudre). Ici je cite les deux les plus connues, mais il y en a beaucoup d'autres.
Il existe des problèmes dont on ne sait pas s'ils sont dans P ou dans NP, mais on sait qu'il sont au moins aussi compliqué à résoudre que ceux dans NP, d'autres dont on ne sait rien du tout. Il y a aussi des résultats «surprenant» comme PRIMES (le problème de savoir si un entier n donné est premier) est dans P : savoir si un nombre est premier ou non est donc simple.

Maintenant je ne vois pas comment définir «la facilité de trouver un algorithme».

Une remarque : quelle que soit la complexité considérée (Kolmogorov ou computationnelle) on travaille toujours avec des objets finis mais de longueur quelconque. On ne peut donc pas utiliser la complexité Kolmogorov d'une suite infinie, tout comme on ne peut pas parler de la complexité d'un algorithme qui ne finit jamais.

[invite73192618]

computeur aurait été parfaitement correct

Merci pour l'info.

D'un côté on étudie le comportement des algorithmes. (...) D'un autre côté on étudie les problèmes de décision.

C'est kif kif en fait, de même que cela ne fait pas de différence de travailler avec des nombres en base 2 ou en base 10 ou n'importe quelle autre.

Maintenant je ne vois pas comment définir «la facilité de trouver un algorithme».

Trouver une définition n'est pas en soit pas bien difficile, par exemple cela pourrait être la longueur d'une preuve que tel ou tel algorithme résout tel ou tel problème de décision. Par contre ce qui est délicat est de trouver une définition utile. Par exemple il est douteux que la longueur d'une preuve dépende de la taille des données traités par un algorithme, alors qu'elle va inévitablement dépendre du formalisme pour un facteur constant. Dans ce cas la longueur d'une preuve ne dit probablement rien de profond puisqu'elle varie selon le formalisme. Si au contraire il existe des problèmes qui ne peuvent être résolu que par une série d'algorithmes différents en fonction de la taille des inputs, alors la longueur d'une preuve d'équivalence peut varier en fonction de la taille selon une loi valable indépendamment des détails du formalisme. Dans ce cas là la définition pourrait être utile voir profonde.

Une remarque : quelle que soit la complexité considérée (Kolmogorov ou computationnelle) on travaille toujours avec des objets finis mais de longueur quelconque. On ne peut donc pas utiliser la complexité Kolmogorov d'une suite infinie, tout comme on ne peut pas parler de la complexité d'un algorithme qui ne finit jamais.

Voir contre-exemple plus haut...

PS: presque indisponible dans les prochaines semaines, merci pour la discussion et A+