Discussion:Complexité

Remarques de 2003

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)

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)

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 :

1. une complexité compliquée
2. 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)

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)

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)

Nombre incompressible et nombre normal

J'ai une petite interrogation sur la phrase "On peut donc conjecturer que tous les nombres incompressibles sont normaux, la suite de leurs décimales doit être aléatoire au sens fort, au moins à partir d'un certain rang". Un exemple: soit un nombre réel tel que chaque décimale de rang pair vaut "1" et chaque décimale de rang impair est le résultat de tirages aléatoires successifs. Ce nombre n'est pas un nombre normal, mais il me semble bien qu'il réponde à la définition de nombre incompressible. Non ? Prokofiev (d) 9 février 2010 à 11:25 (CET)

Non. Il est même très compressible. Si tu fait passer par "pkzip" une telle chaine, elle sera comprimée à environ 50% (tu peux faire l'essai) Jean-Christophe BENOIST (d) 9 février 2010 à 13:54 (CET)

Je comprends bien, mais 50% d'une taille infinie donne toujours une taille infinie...(J'ai oublié de préciser que le nombre en question a un nombre de décimales infini). Ca doit bien faire de lui un nombre incompressible, me semble-t-il. Si on comprime très simplement les décimales de rang pair, on ne peut rien comprimer de l'infinité des décimales de rang impair. Peut-on appeler compressible un nombre dont le résultat de la compression reste infini ?Prokofiev (d) 9 février 2010 à 14:17 (CET)

Voir dans suite aléatoire : pour une suite infinie, l'incompressibilité est caractérisée par "Il existe une constante C, telle que pour tout entier n, la taille du plus petit programme engendrant les n premiers octets de la suite est >= à n+C octets." Ici, C est clairement négatif, pour presque tous les n en plus. Cordialement Jean-Christophe BENOIST (d) 9 février 2010 à 14:31 (CET).

Très clair. J'avais mal interprêté la notion de compressibilité, pour moi elle nécessitait un programme de taille finie, j'ai confondu avec la calculabilité, il me semble. Merci ! Prokofiev (d) 9 février 2010 à 14:43 (CET)

Bonjour, plusieurs remarques. La citation n'est pas une conjecture mais un théorème, on peut démontrer que les réels dont le développement est incompressible (au sens que je précise ensuite) sont normaux). Deuxième remarque(plus grave)il n'existe aucun réel ayant cette propriété ("Il existe une constante C, telle que pour tout entier n, la taille du plus petit programme engendrant les n premiers octets de la suite est >= à n+C octets"), on peut montrer que toute suite il existe une infinité de n tel que le tronqué au rang n a une complexité inférieur à n-log(n)+c. En faite pour trouver des réels ayant cette propriété il faut prendre une définition de la complexité de Kolmogorov un peu différente (comme par exemple la complexité préfixe). Cordialement Antoinetav (d) 9 février 2010 à 21:46 (CET)

D'ailleurs il semble qu'il y ai un bug à ce sujet sur la page suite aléatoire. Quelqu'un s'en charge ? Antoinetav (d) 9 février 2010 à 21:48 (CET)

Je ne sais pas si c'est aussi "grave" que cela. Dans la citation, on ne précise pas s'il s'agit d'un programme auto-délimité ou délimité par des blancs, et toute la différence est là, et je ne pense pas qu'il soit nécessaire de descendre dans cette subtilité dans ce paragraphe de suite aléatoire (dont je ne suis pas l'auteur d'ailleurs). Je crois que "par défaut", on n'utilise plus que les programmes auto-délimités concernant la complexité aléatoire. Pour la compréhension du "principe" du passage de la définition de la compressibilité d'une suite finie à celle d'une suite infinie, cela ne change rien (et c'était l'objet de cette discussion). En revanche, dans un paragraphe sur l'incompressibilité dans complexité de Kolmogorov, là il faudrait effectivement descendre à ce niveau de détails. Cordialement Jean-Christophe BENOIST (d) 10 février 2010 à 09:39 (CET)

D'ailleurs, il semble y avoir le même "bug" (et même pire) sur en:Algorithmically_random_sequence An infinite sequence S is Martin-Löf random if and only if there is a constant c such that all of S's finite prefixes are c-incompressible. C'est pire, car la "c-incompressibilité" y est définie explicitement à partir de la complexité de Kolmogorov K(s), qui se calcule avec des programmes délimités par des blancs, et là ta remarque s'applique à plein. C'est H(s), nommée aussi "complexité de Levin-Chaitin", qui est la complexité de Kolmogorov, mais relative à des programmes auto-délimités, qui devrait être associée à la c-incompressibilité (mais dans suite aléatoire, on est moins précis, donc à l'abri de ta remarque). Mais tout cela me fait dire que cela ne ferait effectivement pas de mal d'être plus précis. Jean-Christophe BENOIST (d) 10 février 2010 à 14:57 (CET)

Bonjour, comme tu veux. Tel que c'est présenté je maintient que c'est inexacte (si on avais dit que la complexité de kolmo doit être supérieur à n-c (ou n+c, c'est exactement pareil)on pourrai admettre l'ellipse mais la le lecteur non avertie crois quelque chose de faut. Enfin bon je ne veux pas me battre la dessus. Il faudrait que je prenne le temps de relire sérieusement toute cette série d'article. Bonne journée Antoinetav (d) 10 février 2010 à 18:51 (CET)

Sans se battre aucunement (d'ailleurs je t'incite à modifier l'article), il y a qqchose que je ne comprends pas dans ta réponse. Tu dis que on aurait pu admettre l'ellipse si on parlait de complexité de Kolmogorov, mais justement la complexité de K est calculée relativement à des programmes non auto-délimités, et la formule > n-c est sujette à ta remarque, et est donc fausse, justement dans ce cas (où les programmes de sont pas auto-délimités) ! Voir par exemple ici où Chaitin explique cela. Je crois que nous somme d'accord, mais qu'il y a quiproquo quelque-part. Cordialement Jean-Christophe BENOIST (d) 10 février 2010 à 20:52 (CET)

Bonjour, oui oui ne nous battons pas et on discute d'un détaille. Je dit juste que si on disait "complexité de Kolmogorov" au lieu de "la taille du plus petit programme engendrant les n premiers octets" l'ellipse serait plus acceptable (mais surement moins compréhensible pour le non initié) car par complexité de Kolmogorov au sens large on peu inclure la complexité classique, préfixe, monotone, a priori (et d'autres). Donc en interprétant un peu cela deviens moins faux alors que en disant "la taille du plus petit programme engendrant les n premiers octets" on se place forcement dans le cas de la complexité classique. Bon bref ne pinaillons pas trop. Pour tout dire, je commence une thèse en complexité de Kolmogorov et donc je pense que je vais essayer de travailler sur ces articles dans les mois à venir et si tu veux le faire avec moi tu est plus que bienvenue. A bientôt Antoinetav (d) 10 février 2010 à 21:10 (CET)

Et réciproquement ! Je pensais être tout seul sur la théorie algorithmique de l'information, et je suis ravi de te voir arriver sur le sujet. Je pense que notre quiproquo était que tu pensais (comme tu viens de le dire) à la complexité de K "au sens large", et pour ma part à la complexité de K telle qu'imaginée par K, avec des programmes terminés par des blancs. D'ailleurs (et notre quiproquo vient en partie de là) je pense qu'il y a confusion et pas de terme bien défini pour désigner la complexité de Levin-Chatin (c'est Delahaye qui l'appelle comme cela) : on la désigne aussi souvent comme étant la "complexité de Kolmogorov" alors que ce n'est pas rigoureusement le cas. Ce sera un point à traiter dans l'article sur la complexité de K. Cordialement Jean-Christophe BENOIST (d) 10 février 2010 à 22:06 (CET)

Ouh la ! C'est un débat infini entre Chaitin (et d'autres) et les russes. Je n'ai pas vraiment envi de rentrer dans ce débat (en tout cas pas de façon écrite et publique et sans avoir fait une généalogie précise par moi même). Il semble que les choses ne soit pas clair et dépende des auteurs mais on discute ici un problème de notation. Je vois Delahay la semaine prochaine, je lui en parlerai. Antoinetav (d) 10 février 2010 à 22:37 (CET)

Gros veinard !! Même si ce n'est pas tout à fait le sujet d'ici, as-tu un avis sur Discussion:Nombre_définissable/Suppression, et éventuellement demander à Delahaye ce qu'il en pense ? Jean-Christophe BENOIST (d) 10 février 2010 à 23:09 (CET)

La Complexité est trans-disciplinaire

Bonjour, Je m'intéresse à la systémique et aux notions de Complexité et d'émergence. J'ai lu Edgar Morin et il ne place clairement pas la complexité uniquement dans le domaine de la physique mais bien comme un sujet trans-disciplinaire lié aux systèmes (eux-mêmes trans ou plutôt a-disciplinaires). Par ailleurs, son introduction à la complexité éclaire au moins sur un point: on ne peut pas expliquer simplement la Complexité (autrement qu'en disant que ce n'est pas "simple", ce qui, finalement, ne veut rien dire ;)

Bref, je ne sais pas trop comment contribuer, mais l'article me semble aujourd'hui un peu light. Je vais aller lire les "systèmes complexes" ça me donnera peut-être des idées... --Nicolas STAMPF (d) 26 août 2011 à 15:03 (CEST)

Oui c'est vrai, l'article est un peu "light". Je ne pense pas qu'il donne l'impression que la complexité est liée spécialement à la physique, on voit bien tout de même l'aspect transdisciplinaire, il me semble. Morin reste une bonne source, mais il aborde la complexité sous un angle certes transdisciplinaire, mais très liée à la théorie générale des systèmes qui était très à la mode au moment de la rédaction de ses livres, qui a donné lieu aussi au Macroscope de JdR à la même époque, mais qui est maintenant en perte de vitesse et ne couvre pas tous les aspects du problème (même si les aspects couverts restent plutôt pertinents). Il y a des n° spéciaux de "La Recherche" sur la Complexité (et l'Emergence aussi) qui sont des bons points de départ, plus globaux que la systémique et Morin; c'est à partir de là que je comptais (un jour..) reprendre éventuellement l'article. Mais n'hésites pas : tout enrichissement et travail sur cet article est bon à prendre ! Cordialement --Jean-Christophe BENOIST (d) 26 août 2011 à 16:13 (CEST)

Etude de la complexité : quels objectifs ?

L'objectif de l'article encyclopédique sur la complexité pourrait être la simplicité (ce serait exemplaire) et l'interdisciplinarité.

• Par rapport à la version anglophone, les objets mathématiques, dans la version francophone d'aujourd'hui, me semblent un peu faibles : théorie du chaos et autres exemples. Qu'en pensez-vous ?
• Si l'article devenait trop compliqué à lire, il deviendrait un épouvantail, il y a un dosage à trouver.

... Par ailleurs, c'est intéressant de voir les motivations/méthodes/objectifs de ceux qui étudient la complexité : en fait, il n'est pas certain que les chercheurs soient tous intéressés dans une méthode caractérisée par la simplification : Catégoriser, sectoriser, hiérachiser, pacifier, enregistrer, ordonner, identifier, rechercher des motifs(patterns), etc. Bon courage. --GéGé twin (d) 20 octobre 2011 à 16:02 (CEST)

Compliqué versus complexe

Bonjour, J'ai lu Edgar Morin, fait des études en physique et m'entretiens en Prosophia (la pratique de la Sagesse : la philosophie pratique que l'on peut mettre en œuvre dans tous les actes de la vie !)...

Ce que je ne retrouve pas dans l'ébauche proposée qui tente de positionner le compliqué par rapport au complexe est le thème suivant : Complexe s'applique au système regardé (l'objet) / Compliqué s'applique au sujet qui regarde.... Je m'explique :

Un système est complexe lorsqu'il y a une multitude d'entrées, une architecture non modulaire, un foisonnement de boucles de retour (asservissements), des interrelations de circuits, des non linéarités, une absence de documentation, des astuces de génie d'un concepteur, des plugg-ins informatiques, des impondérables, du hasard, du bruit,... et qu'en plus, ce système est objectivement lié avec le monde extérieur (système ouvert, alors qu'on s'efforce de travailler avec un système fermé en mécanique ou en thermodynamique).

Un observateur trouve l'analyse du système compliquée parce qu'il n'a pas le temps, les compétences, le discernement, la mémoire, le raisonnement, les moyens, ni le don d'ubiquité lui permettant d'atteindre toutes les subtilités d'un système complexe...

L'observateur fait donc une erreur de vocabulaire et une projection lorsqu'il dit que le système est compliqué... Il devrait dire l'analyse de ce système complexe est compliquée pour moi seul aujourd'hui...

N'y a-t-il pas lieu à mettre cette distinction en lumière... Merci --Guy6631 (discuter) 27 février 2014 à 23:53 (CET)