Complexité - Complexity

La complexité caractérise le comportement d'un système ou d'un modèle dont les composants interagissent de multiples façons et suivent des règles locales, ce qui signifie qu'il n'y a pas d'instruction supérieure raisonnable pour définir les diverses interactions possibles.

Le terme est généralement utilisé pour caractériser quelque chose avec de nombreuses parties où ces parties interagissent les unes avec les autres de plusieurs manières, aboutissant à un ordre d' émergence supérieur à la somme de ses parties. L'étude de ces liens complexes à différentes échelles est l'objectif principal de la théorie des systèmes complexes .

La science à partir de 2010 adopte un certain nombre d'approches pour caractériser la complexité; Zayed et al. reflètent beaucoup d'entre eux. Neil Johnson déclare que "même parmi les scientifiques, il n'y a pas de définition unique de la complexité - et la notion scientifique a traditionnellement été véhiculée à l'aide d'exemples particuliers..." En fin de compte, Johnson adopte la définition de "science de la complexité" comme "l'étude des phénomènes qui émergent d'une collection d'objets en interaction".

Aperçu

Les définitions de la complexité dépendent souvent du concept de " système " - un ensemble de parties ou d'éléments qui ont des relations entre eux différenciées des relations avec d'autres éléments en dehors du régime relationnel. De nombreuses définitions tendent à postuler ou à supposer que la complexité exprime une condition de nombreux éléments dans un système et de nombreuses formes de relations entre les éléments. Cependant, ce que l'on voit comme complexe et ce que l'on voit comme simple est relatif et évolue avec le temps.

Warren Weaver a posé en 1948 deux formes de complexité : la complexité désorganisée et la complexité organisée. Les phénomènes de « complexité désorganisée » sont traités à l'aide de la théorie des probabilités et de la mécanique statistique, tandis que la « complexité organisée » traite des phénomènes qui échappent à de telles approches et confrontent « traiter simultanément un nombre important de facteurs qui sont interreliés en un tout organique ». L'article de Weaver de 1948 a influencé la réflexion ultérieure sur la complexité.

Les approches qui incarnent les concepts de systèmes, d'éléments multiples, de régimes relationnels multiples et d'espaces d'états pourraient être résumées comme impliquant que la complexité découle du nombre de régimes relationnels distincts (et de leurs espaces d'états associés) dans un système défini.

Certaines définitions se rapportent à la base algorithmique de l'expression d'un phénomène ou d'un modèle complexe ou d'une expression mathématique, comme indiqué plus loin dans les présentes.

Désorganisé vs organisé

L'un des problèmes rencontrés dans la résolution des problèmes de complexité a été de formaliser la distinction conceptuelle intuitive entre le grand nombre de variances dans les relations existant dans les collections aléatoires, et le nombre parfois grand, mais plus petit, de relations entre les éléments dans les systèmes où les contraintes (liées à la corrélation de des éléments par ailleurs indépendants) réduisent simultanément les variations par rapport à l'indépendance des éléments et créent des régimes distincts de relations ou d'interactions plus uniformes ou corrélées.

Weaver a perçu et abordé ce problème, au moins de manière préliminaire, en faisant une distinction entre la « complexité désorganisée » et la « complexité organisée ».

Du point de vue de Weaver, la complexité désorganisée résulte du système particulier ayant un très grand nombre de pièces, disons des millions de pièces, voire beaucoup plus. Bien que les interactions des parties dans une situation de « complexité désorganisée » puissent être considérées comme largement aléatoires, les propriétés du système dans son ensemble peuvent être comprises en utilisant des méthodes probabilistes et statistiques.

Un excellent exemple de complexité désorganisée est un gaz dans un conteneur, avec les molécules de gaz comme pièces. Certains suggèrent qu'un système de complexité désorganisée peut être comparé à la simplicité (relative) des orbites planétaires – cette dernière peut être prédite en appliquant les lois du mouvement de Newton . Bien sûr, la plupart des systèmes du monde réel, y compris les orbites planétaires, finissent par devenir théoriquement imprévisibles, même en utilisant la dynamique newtonienne ; comme découvert par la théorie moderne du chaos .

La complexité organisée, selon Weaver, ne réside dans rien d'autre que l'interaction non aléatoire ou corrélée entre les parties. Ces relations corrélées créent une structure différenciée qui peut, en tant que système, interagir avec d'autres systèmes. Le système coordonné manifeste des propriétés non portées ou dictées par des parties individuelles. On peut dire que l'aspect organisé de cette forme de complexité vis-à-vis d'autres systèmes que le système sujet « émerge », sans aucune « main directrice ».

Le nombre de pièces n'a pas besoin d'être très grand pour qu'un système particulier ait des propriétés émergentes. Un système de complexité organisée peut être appréhendé dans ses propriétés (comportement parmi les propriétés) à travers la modélisation et la simulation , en particulier la modélisation et la simulation avec des ordinateurs . Un exemple de complexité organisée est un quartier de la ville en tant que mécanisme vivant, avec les habitants du quartier parmi les parties du système.

Sources et facteurs

Il existe généralement des règles qui peuvent être invoquées pour expliquer l'origine de la complexité dans un système donné.

La source de complexité désorganisée est le grand nombre de parties dans le système d'intérêt et le manque de corrélation entre les éléments du système.

Dans le cas des systèmes vivants auto-organisés, la complexité utilement organisée vient du fait que des organismes ayant subi une mutation bénéfique sont sélectionnés pour survivre par leur environnement pour leur capacité de reproduction différentielle ou au moins leur succès sur la matière inanimée ou des organismes complexes moins organisés. Voir par exemple le traitement des écosystèmes de Robert Ulanowicz .

La complexité d'un objet ou d'un système est une propriété relative. Par exemple, pour de nombreuses fonctions (problèmes), une complexité de calcul telle que le temps de calcul est plus petite lorsque des machines de Turing à plusieurs bandes sont utilisées que lorsque des machines de Turing avec une seule bande sont utilisées. Les machines à accès aléatoire permettent de réduire encore plus la complexité temporelle (Greenlaw et Hoover 1998 : 226), tandis que les machines de Turing inductives peuvent même réduire la classe de complexité d'une fonction, d'un langage ou d'un ensemble (Burgin 2005). Ceci montre que les outils d'activité peuvent être un facteur important de complexité.

Des significations variées

Dans plusieurs domaines scientifiques, la « complexité » a un sens précis :

• En théorie de la complexité computationnelle , les quantités de ressources nécessaires à l'exécution d' algorithmes sont étudiées. Les types de complexité de calcul les plus courants sont la complexité temporelle d'un problème égale au nombre d'étapes nécessaires pour résoudre une instance du problème en fonction de la taille de l'entrée (généralement mesurée en bits), en utilisant la méthode la plus efficace. algorithme, et la complexité spatiale d'un problème égale au volume de la mémoire utilisée par l'algorithme (par exemple, les cellules de la bande) qu'il faut pour résoudre une instance du problème en fonction de la taille de l'entrée (généralement mesurée en bits), en utilisant l'algorithme le plus efficace. Cela permet de classer les problèmes de calcul par classe de complexité (comme P , NP , etc.). Une approche axiomatique de la complexité computationnelle a été développée par Manuel Blum . Il permet de déduire de nombreuses propriétés des mesures concrètes de complexité computationnelle, telles que la complexité temporelle ou spatiale, à partir des propriétés de mesures définies axiomatiquement.
• En théorie algorithmique de l' information , la complexité de Kolmogorov (également appelé la complexité descriptive , complexité algorithmique ou entropie algorithmique ) d'une chaîne est la longueur de la plus courte binaire programme que les sorties de cette chaîne. La longueur minimale des messages est une application pratique de cette approche. Différents types de complexité de Kolmogorov sont étudiés : la complexité uniforme, la complexité de préfixe, la complexité monotone, la complexité de Kolmogorov limitée dans le temps et la complexité de Kolmogorov limitée dans l'espace. Une approche axiomatique de la complexité de Kolmogorov basée sur les axiomes de Blum (Blum 1967) a été introduite par Mark Burgin dans l'article présenté pour publication par Andrey Kolmogorov . L'approche axiomatique englobe d'autres approches de la complexité de Kolmogorov. Il est possible de traiter différents types de complexité de Kolmogorov comme des cas particuliers de complexité de Kolmogorov généralisée définie axiomatiquement. Au lieu de prouver des théorèmes similaires, tels que le théorème d'invariance de base, pour chaque mesure particulière, il est possible de déduire facilement tous ces résultats d'un théorème correspondant prouvé dans le cadre axiomatique. C'est un avantage général de l'approche axiomatique en mathématiques. L'approche axiomatique de la complexité de Kolmogorov a été développée plus avant dans le livre (Burgin 2005) et appliquée aux métriques logicielles (Burgin et Debnath, 2003 ; Debnath et Burgin, 2003).
• En théorie de l'information , la complexité de fluctuation de l'information est la fluctuation de l'information sur l' entropie de l'information . Il est dérivé des fluctuations de la prédominance de l'ordre et du chaos dans un système dynamique et a été utilisé comme mesure de la complexité dans de nombreux domaines divers.
• En traitement de l'information , la complexité est une mesure du nombre total de propriétés transmises par un objet et détectées par un observateur . Un tel ensemble de propriétés est souvent appelé état .
• Dans les systèmes physiques , la complexité est une mesure de la probabilité du vecteur d'état du système. Cela ne doit pas être confondu avec l' entropie ; c'est une mesure mathématique distincte, dans laquelle deux états distincts ne sont jamais confondus et considérés comme égaux, comme cela se fait pour la notion d'entropie en mécanique statistique .
• Dans les systèmes dynamiques , la complexité statistique mesure la taille du programme minimum capable de reproduire statistiquement les motifs (configurations) contenus dans l'ensemble de données (séquence). Alors que la complexité algorithmique implique une description déterministe d'un objet (elle mesure le contenu informationnel d'une séquence individuelle), la complexité statistique, comme la complexité prévisionnelle , implique une description statistique, et fait référence à un ensemble de séquences générées par une certaine source. Formellement, la complexité statistique reconstruit un modèle minimal comprenant la collection de toutes les histoires partageant un futur probabiliste similaire, et mesure l' entropie de la distribution de probabilité des états au sein de ce modèle. C'est une mesure calculable et indépendante de l'observateur basée uniquement sur la dynamique interne du système, et a été utilisée dans des études sur l' émergence et l' auto-organisation .
• En mathématiques , la complexité de Krohn-Rhodes est un sujet important dans l'étude des semi - groupes finis et des automates .
• En théorie des réseaux, la complexité est le produit de la richesse des connexions entre les composants d'un système, et définie par une distribution très inégale de certaines mesures (certains éléments étant fortement connectés et d'autres très peu, voir réseau complexe ).
• En génie logiciel , la complexité de programmation est une mesure des interactions des différents éléments du logiciel. Cela diffère de la complexité de calcul décrite ci-dessus en ce qu'il s'agit d'une mesure de la conception du logiciel.
• Au sens abstrait - Complexité abstraite, basée sur la perception des structures visuelles. C'est la complexité d'une chaîne binaire définie comme un carré de nombre de caractéristiques divisé par le nombre d'éléments (0 et 1). Les caractéristiques comprennent ici tous les arrangements distinctifs de 0 et de 1. Bien que le nombre de caractéristiques doive toujours être approximatif, la définition est précise et répond à des critères intuitifs.

D'autres domaines introduisent des notions de complexité moins précisément définies :

• Un système adaptatif complexe possède tout ou partie des attributs suivants :
  • Le nombre de pièces (et les types de pièces) dans le système et le nombre de relations entre les pièces n'est pas trivial – cependant, il n'y a pas de règle générale pour séparer « trivial » de « non trivial » ;
  • Le système a de la mémoire ou inclut un retour d'informations ;
  • Le système peut s'adapter en fonction de son historique ou de son retour d'expérience ;
  • Les relations entre le système et son environnement sont non triviales ou non linéaires ;
  • Le système peut être influencé par, ou peut s'adapter à, son environnement ;
  • Le système est très sensible aux conditions initiales.

Étudier

La complexité a toujours fait partie de notre environnement et, par conséquent, de nombreux domaines scientifiques ont traité des systèmes et des phénomènes complexes. D'un certain point de vue, ce qui est en quelque sorte complexe – afficher des variations sans être aléatoire – est le plus digne d'intérêt étant donné les récompenses trouvées dans les profondeurs de l'exploration.

L'utilisation du terme complexe est souvent confondue avec le terme compliqué. Dans les systèmes d'aujourd'hui, c'est la différence entre une myriade de « tuyaux de poêle » et des solutions « intégrées » efficaces. Cela signifie que complexe est le contraire d'indépendant, tandis que compliqué est le contraire de simple.

Bien que cela ait conduit certains domaines à proposer des définitions spécifiques de la complexité, il existe un mouvement plus récent pour regrouper les observations de différents domaines pour étudier la complexité en elle-même, qu'elle apparaisse dans les fourmilières , les cerveaux humains ou les marchés boursiers , les systèmes sociaux. L'un de ces groupes interdisciplinaires de domaines est celui des théories de l'ordre relationnel .

Les sujets

Comportement

On dit souvent que le comportement d'un système complexe est dû à l'émergence et à l' auto-organisation . La théorie du chaos a étudié la sensibilité des systèmes aux variations des conditions initiales en tant que cause d'un comportement complexe.

Mécanismes

Les développements récents de la vie artificielle , du calcul évolutif et des algorithmes génétiques ont conduit à mettre de plus en plus l' accent sur la complexité et les systèmes adaptatifs complexes .

Simulation

En sciences sociales , l'étude sur l'émergence des macro-propriétés à partir des micro-propriétés, aussi appelée macro-micro vue en sociologie . Le sujet est communément reconnu comme une complexité sociale qui est souvent liée à l'utilisation de la simulation informatique en sciences sociales, c'est-à-dire : la sociologie computationnelle .

Systèmes

La théorie des systèmes s'intéresse depuis longtemps à l'étude des systèmes complexes (ces derniers temps, la théorie de la complexité et les systèmes complexes ont également été utilisés comme noms du domaine). Ces systèmes sont présents dans la recherche d'une variété de disciplines, y compris la biologie , l' économie , les études sociales et la technologie . Récemment, la complexité est devenue un domaine d'intérêt naturel des systèmes socio-cognitifs du monde réel et de la recherche systémique émergente . Les systèmes complexes ont tendance à être de grande dimension , non linéaires et difficiles à modéliser. Dans des circonstances spécifiques, ils peuvent présenter un comportement de faible dimension.

Données

En théorie de l'information, la théorie algorithmique de l'information s'intéresse à la complexité des chaînes de données.

Les chaînes complexes sont plus difficiles à compresser. Alors que l'intuition nous dit que cela peut dépendre du codec utilisé pour compresser une chaîne (un codec pourrait théoriquement être créé dans n'importe quel langage arbitraire, y compris un dans lequel la toute petite commande "X" pourrait amener l'ordinateur à produire une chaîne très compliquée comme "18995316"), deux langues Turing-complètes quelconques peuvent être implémentées l'une dans l'autre, ce qui signifie que la longueur de deux encodages dans des langues différentes variera au maximum de la longueur de la langue de "traduction" - qui finira par être négligeable pour suffisamment grandes chaînes de données.

Ces mesures algorithmiques de complexité tendent à attribuer des valeurs élevées au bruit aléatoire . Cependant, ceux qui étudient les systèmes complexes ne considéreraient pas le hasard comme une complexité.

L'entropie de l'information est également parfois utilisée dans la théorie de l'information comme indicateur de complexité, mais l'entropie est également élevée pour le caractère aléatoire. La complexité de la fluctuation de l'information, les fluctuations de l'information sur l'entropie, ne considère pas le hasard comme complexe et a été utile dans de nombreuses applications.

Des travaux récents en apprentissage automatique ont examiné la complexité des données car elle affecte les performances des algorithmes de classification supervisée . Ho et Basu présentent un ensemble de mesures de complexité pour les problèmes de classification binaire .

Les mesures de complexité couvrent globalement :

• les chevauchements de valeurs de caractéristiques de classes différentes.
• la séparabilité des classes.
• mesures de la géométrie, de la topologie et de la densité des variétés . La dureté d'instance est une autre approche qui cherche à caractériser la complexité des données dans le but de déterminer à quel point un ensemble de données est difficile à classer correctement et ne se limite pas aux problèmes binaires.

La dureté d'instance est une approche ascendante qui cherche d'abord à identifier les instances susceptibles d'être mal classées (ou, en d'autres termes, quelles instances sont les plus complexes). Les caractéristiques des instances susceptibles d'être mal classées sont ensuite mesurées sur la base de la sortie d'un ensemble de mesures de dureté. Les mesures de dureté sont basées sur plusieurs techniques d'apprentissage supervisé telles que la mesure du nombre de voisins en désaccord ou la probabilité de l'étiquette de classe attribuée compte tenu des caractéristiques d'entrée. Les informations fournies par les mesures de complexité ont été examinées pour être utilisées dans le méta-apprentissage afin de déterminer pour quels ensembles de données le filtrage (ou la suppression des instances suspectes de bruit de l'ensemble d'apprentissage) est le plus bénéfique et pourrait être étendu à d'autres domaines.

En reconnaissance moléculaire

Une étude récente basée sur des simulations moléculaires et des constantes de conformité décrit la reconnaissance moléculaire comme un phénomène d'organisation. Même pour les petites molécules comme les glucides , le processus de reconnaissance ne peut pas être prédit ou conçu, même en supposant que la force de chaque liaison hydrogène individuelle est exactement connue.

La loi de la complexité requise

S'inspirant de la loi de la variété requise , Boisot et McKelvey ont formulé la « loi de la complexité requise », selon laquelle, pour être efficacement adaptative, la complexité interne d'un système doit correspondre à la complexité externe à laquelle il est confronté. L'application en gestion de projet de la loi de la complexité requise est l'analyse de la complexité positive, appropriée et positive .

En gestion de projet

La complexité d'un projet est la propriété d'un projet qui rend difficile la compréhension, la prévision et le contrôle de son comportement global, même lorsque l'on dispose d'informations raisonnablement complètes sur le système du projet.

Applications

La théorie de la complexité computationnelle est l'étude de la complexité des problèmes, c'est-à-dire de la difficulté de les résoudre . Les problèmes peuvent être classés par classe de complexité selon le temps qu'il faut à un algorithme – généralement un programme informatique – pour les résoudre en fonction de la taille du problème. Certains problèmes sont difficiles à résoudre, tandis que d'autres sont faciles. Par exemple, certains problèmes difficiles nécessitent des algorithmes qui prennent un temps exponentiel en termes de taille du problème à résoudre. Prenez le problème du voyageur de commerce , par exemple. Il peut être résolu dans le temps (où n est la taille du réseau à visiter – le nombre de villes que le voyageur de commerce doit visiter exactement une fois). À mesure que la taille du réseau de villes augmente, le temps nécessaire pour trouver l'itinéraire augmente (plus que) de façon exponentielle. ${\displaystyle O(n^{2}2^{n})}$

Même si un problème peut en principe être résolu par le calcul, dans la pratique, cela peut ne pas être aussi simple. Ces problèmes peuvent nécessiter beaucoup de temps ou une quantité excessive d'espace. La complexité informatique peut être abordée sous de nombreux aspects différents. La complexité informatique peut être étudiée sur la base du temps, de la mémoire ou d'autres ressources utilisées pour résoudre le problème. Le temps et l'espace sont deux des considérations les plus importantes et les plus populaires lorsque des problèmes de complexité sont analysés.

Il existe une certaine classe de problèmes qui, bien qu'ils soient en principe résolvables, nécessitent tellement de temps ou d'espace qu'il n'est pas pratique de tenter de les résoudre. Ces problèmes sont appelés insolubles .

Il existe une autre forme de complexité appelée complexité hiérarchique . Elle est orthogonale aux formes de complexité discutées jusqu'ici, qui sont appelées complexité horizontale.

Voir également

Les références

Lectures complémentaires

Liens externes

• Mesures de complexité – un article sur l'abondance de mesures de complexité pas très utiles.
• Exploring Complexity in Science and Technology Archivé 2011-03-05 à la Wayback Machine – Cours d'introduction aux systèmes complexes par Melanie Mitchell
• Institut de Santa Fe axé sur l'étude de la science de la complexité : vidéos de conférence
• Vidéoconférences UC Four Campus Complexity – Sciences humaines et complexité