Complexité

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden), en physique, en biologie (par exemple par Henri Atlan), en sociologie (par exemple par Edgar Morin), en informatique ou en sciences de l’information. La définition connaît des nuances importantes selon ces différents domaines.

Sommaire

1 La complexité du point de vue de la théorie de l’information
- 1.1 Complexité de Kolmogorov
- 1.2 Autres complexités
2 La complexité du point de vue de la physique
- 2.1 Le nombre et l’indépendance des parties
- 2.2 La complexité du réel
3 Voir aussi
- 3.1 Liens externes

[modifier] La complexité du point de vue de la théorie de l’information

Une notion de complexité est définie en théorie de l'information.

[modifier] Complexité de Kolmogorov

La théorie de la complexité de Kolmogorov définit la complexité d’un objet fini par la taille du plus petit programme informatique (au sens théorique) qui permet de produire cet objet. Ainsi, un texte compressible a une faible complexité et contient peu d’information. C’est d’ailleurs pourquoi les utilitaires de compression généralistes ne peuvent pas comprimer des fichiers totalement aléatoires (opération par nature impossible), mais uniquement des fichiers dont on sait à l’avance qu’ils comportent une certaine redondance qui se traduit par des corrélations.

La complexité de Kolmogorov est un sujet discuté. On peut en effet toujours donner à un ordinateur une construction telle qu’une opération très particulière (par exemple le calcul de pi ou l’impression de l’intégrale des œuvres de Victor Hugo)) y sera codée par un bit. On retrouve ici la notion connue qu’une information n’est jamais contenue dans un message seul, mais toujours dans le couple message + décodeur pris de façon indissociable. Aussi la notion de « plus petit programme théorique » ne peut-elle être définie opérationnellement de façon rigoureuse et univoque qu'avec la référence à une machine. On pourrait objecter qu’il suffit de prendre comme référence la machine la plus simple. C’est oublier que ce que nous nommerons simple dépend justement de notre vécu et de notre langage, tous deux arbitraires. Voir les articles Rasoir d'Occam et Paradoxe du compresseur : The library is the language ( « La bibliothèque est le langage »).

Une difficulté supplémentaire réside dans le fait que la complexité de Kolmogorov n'est pas décidable : on peut donner un algorithme produisant l'objet voulu, ce qui prouve que la complexité de cet objet est au plus la taille de cet algorithme. Mais on ne peut pas écrire de programme qui donne la complexité de Kolmogorov de tout objet que l'on voudrait lui donner en entrée.

La notion, manipulée avec précaution, se révèle néanmoins à l'origine de nombreux résultats théoriques.

Par exemple, on appelle nombre incompressible au sens de Kolmogorov un réel dont le développement p-adique (binaire pour plus de commodité) est comparable à la taille de l'algorithme qui permet de le calculer. En ce sens, tous les rationnels et certains irrationnels sont compressibles, en particulier les nombres transcendants comme $π$ , e ou 0,12345678910111213… dont le développement binaire est infini mais la suite des décimales parfaitement calculable. En revanche, le nombre dit Oméga de Gregory Chaitin ne l'est pas : ce nombre mesure la probabilité qu'une machine, alimenté par un programme composé de bits aléatoires, s'arrête. La topologie des nombres incompressibles est intéressante : on conçoit intuitivement que cet ensemble est dense dans R, mais il est impossible d'exhiber un réel incompressible, puisque cela reviendrait à en donner une méthode de calcul efficace. 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.

[modifier] Autres complexités

Voir complexité algorithmique, complexité descriptive, système complexe.
Complexité P : La classe P est l'ensemble des problèmes de décisons qui sont résolubles par un algorithme à temps polynomial.

[modifier] La complexité du point de vue de la physique

Intuitivement, un système est complexe lorsque beaucoup de ramifications le composent (donc il n'est pas forcément compliqué, puisqu'en le décomposant il peut être simple à comprendre). Deux critères permettent de caractériser plus finement cette notion : le nombre et l’indépendance des parties.

[modifier] Le nombre et l’indépendance des parties

Un système complexe est composé d’un grand nombre de parties. Avec ce seul critère tous les systèmes matériels seraient complexes sauf les particules, les atomes, les petits ions et les petites molécules. Mais un système peut avoir un grand nombre de parties sans avoir un mouvement très compliqué, si toutes les parties bougent de la même façon par exemple. Le critère de l’indépendance des parties est destiné à exclure ces cas. Mais il est difficile à définir précisément.

Tant qu’on considère un solide comme un corps parfaitement rigide, ses parties ne sont pas indépendantes les unes des autres. Quelques nombres, quelques variables d’état suffisent pour caractériser complètement l’état de mouvement du solide : position du centre d’inertie, vitesse de translation, vitesse de rotation. Le mouvement de chacune des parties est complètement déterminé par ces nombres. En revanche, si on étudie les vibrations du solide, les mouvements peuvent être beaucoup plus compliqués, parce que chaque partie peut avoir un mouvement différent des autres. Il en va de même pour un fluide. Pour décrire ces mouvements il faut beaucoup plus de variables d’état, un nombre infini en théorie. Dire ici que les parties sont indépendantes, ce n’est pas dire qu’elles n’interagissent pas avec les autres mais seulement que la connaissance de l’état d’une partie ne fournit pas ou peu d’informations sur l’état des autres parties.

Il y a une part de subjectivité et d'ambiguité dans l’appréciation de l’indépendance des parties : un système mal connu peut sembler tout aussi bien complexe, car inexplicable, que très simple, en se contentant d'explications superficielles.

[modifier] La complexité du réel

Les systèmes simples sont des objets d’études privilégiés. Pendant longtemps ils ont été les seuls systèmes pour lesquels on pouvait faire des calculs, mais ce n’est plus vrai maintenant, grâce aux ordinateurs. Ce sont aussi les seuls systèmes que l’on peut bien caractériser lors d’une expérience et c’est un point important pour la reproductibilité (le fait que l’on peut reproduire la même expérience plusieurs fois et obtenir toujours le même résultat). Cet intérêt de la simplicité explique en partie pourquoi on trouve dans tous les livres et les laboratoires de physique les mêmes géométries simples (cercle, sphère, cylindre, ...).

Les exemples étudiés dans les livres sont souvent simples mais la réalité l’est beaucoup moins. On peut dire qu’en première approximation les systèmes complexes sont tous les systèmes. La complexité est la règle, la simplicité l’exception. La complexité est un défi pour les mathématiques appliquées : utiliser les mathématiques pour comprendre tout ce qui est sous nos yeux, ne pas se limiter à ce qu’on peut tracer à la règle et au compas.

Tous les systèmes réels sont complexes, ou presque tous. Mais plus un système est complexe, plus il est difficile de le connaître avec précision. Le nombre des combinaisons possibles par exemple pose problème. Comme les parties sont indépendantes, les états envisageables a priori sont toutes les combinaisons d’états des partie. L’explosion combinatoire conduit à des nombres gigantesques de cas possibles, souvent plus que le nombre de particules dans l’univers connu, même pour des systèmes relativement peu complexes. La connaissance précise de l’état présent d’un système complexe pose également problème. Il y a beaucoup trop de variables d’état à mesurer. Les systèmes complexes sont souvent mal connus et ils réservent beaucoup de surprises (émergence de propriétés collectives, auto-organisation, nombres de Feigenbaum dans les systèmes chaotiques). L’Institut de Santa Fe, créé par plusieurs physiciens dont Murray Gell-Mann et dont le nom officiel est Institute for complexity, fait de l’étude de ce type de questions son activité à plein temps.

La théorie générale des systèmes est parfois appelée systémique.

La redondance n'est pas la répétition à l'identique, mais le déploiement d'une multitude de versions différentes d'un même schéma ou motif (en anglais pattern).

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.

1 - La redondance structurelle désigne des structures différentes pour exécuter une même fonction, comme le double circuit de freinage d'une voiture automobile ou plusieurs ateliers différents ou usines différentes pour fabriquer une même pièce ou un même engin. La redondance structurelle caractérise la « complication ». La redondance structurelle s'illustre avec le double circuit de freinage pour plus de sécurité dans des véhicules automobiles modernes et avec les multiples circuits de commande électrique, hydraulique et pneumatique des engins de guerre pour les ramener au bercail avec leur équiage après des dégats du combat.

2 - La redondance fonctionnelle est celle de la multiplicité de fonctions différentes exécutées en un point d'une structure, comme un atelier d'artisan qui exécute différentes opérations sur différents matériaux. La redondance fonctionnelle caractérise la « complexité » et condition de l'auto-organisation chez Henri Atlan. C'est la « variété » chez le neuropsychiatre Ross W. Ashby passé à la cybernétique.

La complication est de l’ordre de la redondance structurelle d’une configuration avec (cum) beaucoup de plis (latin : plico, are, atum : plier). La complication, multiplication, duplication et replication sont de la même série des plis et plissements. C'est la multiplicité des circuits de commande pour effectuer une même fonction.

La complexité est une configuration avec (cum) un nœud (plexus) d’entrelacents d’enchevêtrements. Alors, la complexité est de l’ordre de la redondance fonctionnelle, comme un restaurant qui présente un menu de 40 plats différents. Une machine à bois combinée d'artisan qui scie, rabote perce et tutti quanti est représentative de cette complexité, comme une perceuse électrique d'amateur avec une multiplicité d'accessoires pour différentes fonctions.