|
Le terme de complexité est
souvent utilisé dans notre langage quotidien. Monde
complexe, situation complexe, film complexe, oeuvre
complexe...
Nous essaierons de cerner le concept de complexité
à travers ses diverses acceptions, informatique,
mathématique, biologique, artistique. Nous verrons en
quoi l'oeuvre humaine est tentative de maîtrise de ces
complexités, et comment se situe l'informatique dans
cette démarche, avec ses différents domaines,
de l'algotithmique à ce que certains appellent
l'intelligence artificielle, terme sur lequel nous
reviendrons.
C'est avec l'apparition de l'informatique
en tant que science (1936) et les travaux d'Alan Mathison
Turing (1912-1954) que le concept de complexité a
commencé à émerger scientifiquement.
Par la suite, une autre façon, plus
mathématique (1950 env.), due à Alexis
Nikolaevitch Kolmogorov (1903-1987), le père de la
théorie moderne des probabilités
(Théorie de la mesure...) est apparue basée
sur des aspects probabilistes (et de théorie de
l'information) et sur la théorie des
automates.
La complexité « à
la Turing », dite aussi complexité algorithmique
est donnée pour un programme par le temps de calcul
nécessaire à celui-ci pour résoudre un
représentant de la classe de problèmes pour
laquelle il a été conçu, dans le pire
des cas (1).
Ce qui est important c'est de savoir alors exprimer le temps
de calcul d'un programme en fonction de la taille (i. e. le
nombre de paramètres) du problème à
résoudre, lorsqu'on fait tendre cette taille vers
l'infini.
Ainsi on a des algorithmes dont le
temps de calcul s'exprime en logarithme du nombre de
variables, d'autres en fonction polynomiale, d'autres encore
en fonction exponentielle.
C'est la complexité
asymptotique qui est intéressante,
c'est-à-dire l'expression de la variation du temps en
fonction (ou plutôt son terme de degré plus
élevé) de la taille des variables (la taille
de l'instance) lorsqu'on fait tendre cette taille vers
l'infini. La complexité d'une classe de
problèmes est alors donnée par la
complexité du meilleur algorithme résolvant
tous les problèmes de la classe.
La complexité « à
la Kolmogorov » pourrait être qualifiée de
complexité descriptionnelle ou informationnelle. La
complexité d'un objet est alors donnée par la
longueur du plus petit énoncé qu'on peut
donner pour décrire cet objet, ce qui suppose que
tout le monde soit d'accord sur l'alphabet utilisé.
En d'autres termes, c'est la quantité d'information
inhérente à l'objet. Ainsi, une
séquence aléatoire est de complexité
maximale puisque réductible à aucune autre
description qu'elle-même. Ainsi, une séquence
aléatoire est de complexité maximale puisque
réductible à aucune autre description
qu'elle-même. Par exemple, la suite définie par
: un suivi de trente milliards de zéros et
terminée par un a-t-elle une complexité
moindre que la suite :
vbhqihhvvevsacvsacvsGQSghHNNNWjjjkjgbxiatzyhgbx 321°)
&,;,q, ? h.
Le pont entre ces deux théories
est assez facile à faire, mais il sort du
présent cadre (c'est tout de même assez
complexe).
Ainsi, on a là les bases d'une
théorie générale de la
complexité. Le problème dans la théorie
de l'évolution et dans le propos de S. J. Gould c'est
précisément ce manque de définition
rigoureuse de la complexité des organismes vivants et
surtout de lien avec la théorie mathématique
de la complexité. Ce problème se pose tout au
long des pages de l'Eventail du vivant où S. J. Gould
parle plusieurs fois de descriptions des vertèbres
(P. 250)et description de telle ou telle partie d'un
organisme. La collection de vertèbres d'un poisson
peut avoir une complexité moindre que celle des
mammifères, en quoi cela implique-t-il qu'ils soient
moins complexes ? De plus, il est intéressant de
remarquer la méthode. S. J. Gould dit : j'ai besoin
d'un énoncé plus long pour décrire la
colonne vertébrale des mammifères que pour
décrire celle des poissons, donc la colonne
vertébrale des mammifères est plus complexe
que celle des poissons. Là on n'est pas vraiment loin
de Kolmogorov! La vision peut toutefois sembler parcellaire.
Est-ce la description des caractéristiques de tel ou
tel individu, ou de telle ou telle collection d'individus
qui est importante, ou plutôt la description de ce qui
fait la généricité de l'espèce
dans son ensemble et non tel ou tel individu ?Par exemple,
pour les organismes possédant un ADN, on pourrait
peut-être prendre comme mesure de complexité ,
la longueur de la séquence de codons minimale
permettant de générer l'individu(2).
A quel niveau place-t-on
l'étude de la complexité ? Pourquoi se limiter
aux organismes vivants ? Depuis la soupe originelle vue par
Ilya Prigogine à l'homo sapiens sapiens, en passant
par le Big Bang, n'y a-t-il pas augmentation de la
complexité. Qu'est-ce qui fait cette augmentation ?
Le temps ! Sur les grandes périodes des temps
cosmiques se produisent des phénomènes
chaotiques qui introduisent l'aléatoire dans la
construction. La réponse au problème de
l'accroissement ou non de la complexité n'est-elle
pas conditionnée aussi par les frontières de
l'ensemble des événements
étudiés ? On peut se trouver, comme dans le
cas de l'entropie, dans des situations de dégradation
locale de la complexité de presque tous les objets
étudiés, avec une augmentation globale de la
dite complexité. La tendance naturelle de toute vie ,
c'est la mort, et pourtant il y a la vie et apparaissent des
organismes plus complexes les uns que les autres. Ça
ne signifie pas évidemment qu'il y ait une tendance
d'ensemble des organismes vers la complexité, mais il
existe une tendance certaine au cours du temps à
l'apparition de nouveaux organismes de plus en plus
complexes, ne serait-ce que par le jeu de
l'aléatoirité. L'apparition des
bactéries elle-même marque un saut dans
l'accroissement de complexité du mouvement de la
matière. Ce qui caractérise la matière
c'est le mouvement, il n'y a pas de matière sans
mouvement et dès qu'il y a mouvement, il y a temps
(le temps du mouvement) et donc passage d'un état
à un autre de la matière. C'est durant ce
passage que joue l'aléatoirité mais elle joue
avec des lois propres à l'état dans lequel
était la matière à
«l'instant» d'avant. Dans cette situation, la
croissance globale n'est pas le résultat d'une
accumulation des croissances locales. C'est une situation
bien connue en mathématiques non convexes (principe
de Pontriaguine). La limitation du propos à une
catégorie risque là d'affaiblir la
portée de la démonstration. Toutefois pour une
complexité globale donnée, dès
qu'apparaît un objet de complexité
supérieure à celle de tous les autres, la
complexité globale elle-même augmente, elle
devient égale à la complexité maximale
des objets étudiés. En effet, l'ensemble des
objets étudiés contient, par
définition, tous les objets étudiés,
donc aussi chacun d'eux. L'objet de complxité
maximale ne saurait se réduire à aucun des
autres objets de l'ensemble (sinon il ne serait pas de
complexité maximale). Lorsqu'on donne une description
minimale de l'ensemble étudié, il faut que
cettedescription décrive aussi
l'élément de complexité maximale. La
complexité de l'ensemble ne saurait donc être
de complexité inférieure à celle de
l'élément de complexité maximale. La
conséquence en est que quelque soit la
prégnance du règne bactérien sur le
monde vivant, si l'homo sapiens sapiens en est
l'élément le plus complexe, la
complexité du vivant est alors au moins égale
à celle-ci, ce qui marque un accroissement de
complexité par rapport au temps où
n'existaient QUE des bactéries.
|
Spécial
web -
L'événement