Discuter:Complexité
Un article de Wikipédia, l'encyclopédie libre.
Salut, ce serait bien de définir dans cet article les différents niveaux de complexité et les notations associées :
- O(n)
- O(n<exp>2</exp>)
- O(n<exp>x</exp>)
- O(log n)
. . .
-- AlNo 13 oct 2003 à 10:39 (CEST)
Merci à Looxix pour avoir ajouté le lien vers complexité algorithmique... :)
-- AlNo 14 oct 2003 à 19:39 (CEST)
Sommaire |
[modifier] Entropie
Est-ce qu'ici Complexité ne serait-il un synonyme d'Entropie ? (ou sens théorie de l'information, bien sûr). Ne faudrait-il pas ajouter un lien ? Ou alors expliquer la différence, si ce n'est pas le cas ?
--
Je n'ai jamais entendu parler de cette notion dans les cours que j'ai eu en théorie de la complexité. Il ne me semble pas qu'il y ai de rapport, si?.--as4 12 jul 2004 à 09:51 (CEST)
--
En fait, il y a deux « théories de l'information ». Ce qu'on appelle habituellement théorie de l'information, c'est la théorie de l'information de Shannon, qui parle de quantité d'information, de codages, de canaux de communication, de codes correcteurs, tout ça. Les problèmes sont qu'est-ce qu'on peut faire passer dans un canal vérifiant telle propriété, quand est-ce qu'un codage est optimal (en place), quand est-ce qu'il est suffisamment redondant pour limiter les erreurs, et de combien. On veut chiffrer la notion de redondance, pouvoir calculer la probabilité d'une erreur de transmission. C'est à ça que sert la notion d'entropie.
Ensuite, il y a la théorie de la complexité de Kolmogorov, alias théorie algorithmique de l'information. Celle-là, comme esquissé (n'importe comment, j'en ai peur) dans l'article, définit la complexité d'un mot comme la longueur du plus court programme capable de l'imprimer. (Évidemment, la complexité d'un mot n'est définie que pour une machine fixée, mais on s'en moque puisque c'est la même à O(1) près pour deux machines différentes, et il suffit de se restreindre à des suites dont la complexité tend vers l'infini pour que la notion de complexité ait un sens.) Il se trouve que l'on peut plus ou moins (je ne sais pas trop comment) retrouver la théorie de Shannon comme un cas particulier.
Enfin, la théorie de la complexité tout court, ce serait plutôt l'étude des classes de complexité algorithmique : P, NP, PSPACE, EXPTIME, et compagnie.
Mais j'ai l'impression que cet article, en essayant de parler de complexité en général, mélange toutes ces notions au lieu justement de les distinguer et de renvoyer vers les articles appropriés. Il faudrait que quelqu'un de compétent dans ces domaines (ce que je ne suis pas, malheureusement) le réécrive...
MM 25 oct 2004 à 16:54 (CEST)
MM 25 oct 2004 à 16:54 (CEST)
[modifier] Suggestion de plan
J'ai essayé de faire une intro assez générale, mais je connais pas trop la plupart des domaines cités. Ce que j'ai compris de la complexité c'est que c'est un terme qui peut recouvrir la notion de compliqué et celle de complexe. Compliqué c'est ce qui est "plié ensemble" et peut donc être "déplié" par l'analyse. Ce qui est complexe serait plutôt tissé et ne peut pas être "déplié" par l'analyse sans perdre tout sens. Je sais pas si c'est clair. J'aurai tendance à faire le plan suivant :
- une complexité compliquée
- une complexité complexe
Quelqu'un en pense quelque chose ? Quelqu'un pense ? Fred.th 3 jan 2005 à 15:08 (CET)
- oui. Actuellement l'article ne présente comme complexe (en physique) que des truc compliqué, ce qui est une faute grave. Des truc très, très simples peuvent être très, très complexe, l'archétype étant le problème des trois corps en gravitation, ou l'itération de la fonction logistique (y= a x(1-x)). gem 14 jun 2005 à 18:18 (CEST)
[modifier] Compliqué contre complexe
Compliqué ne signifie pas complexe. Un programme informatique peut être compliqué tout en restant explicable donc "prouvable"; il n'est pas complexe, son comportement peut être déduit de son écriture.
Un problème n'est pas complexe parce que la somme des parties est moins que le tout. Une automobile est plus que la somme de ses parties sans être complexe.
Un système est complexe quand la seule façon de connaitre son état futur est de le regarder fonctionner.
- Tu parle de quel domaine, ou de quel partie de l'article ? car la complexité en théorie de l'information, n'a rien à voir avec l'exemple que tu donne de la voiture. La complexité en informatique est « transmissible ». Puis tu peut signer tes message en placant à la fin ~~~~ (4 tild), les trois premier place ton nom, le dernier place la date et l'heure. ~ þayo ♫♪♫♪ 21 septembre 2005 à 22:04 (CEST)
- D'autre par, pour réduire la complexité d'un algorithme, il est très souvant necessaire de le rendre compliqué (par rapport à un algorithme naïf) :) la complexité est alors une notion qui caractérise le temps de calcule, l'encombrement mémoire... grace a un coéficiant. ~ þayo ♫♪♫♪ 21 septembre 2005 à 22:09 (CEST)
[modifier] Complexité-complication
L'un n'est pas contre l'autre en dehors de l'idéologie desoppositions binaires. C'est simplement deux formes différentes.
Un restaurant chinois qui présente un menu de 40 plats différents est beaucoup plus complexe qu'une usine qui sort 40 000 unités toutes identiques à l'heure.
En définissant la "variété" de William Ross Ashby comme le dénombrement de comportements et d'agencements différents exhibés par un système, cette variété peut se décomposer en "redondance structurelle" d'agencements différents et en "redondance fonctionnelle" le déploiement d'une multitude de comportements différents.
Alors, il est possible de modéliser la complexité en termes de redondance fonctionnelle, comme le restaurant chinois où plusieurs fonctions sont effectuées en un même endroit d'une structure.
Pour la complication, le modèle serait la redondance structurelle d'une usine où une même fonction est exécutée en plusieurs endroits différents d'une structure.
J'ai déjà présenté ce point de vue au Congrès des sociologues de langue française à Genève en 1986
Takima 28 mars 2006 à 02:23 (CEST)
