comment évaluer/mesurer la complexité ?

[mh34]

Est-ce que quelqu'un pourrait me dire ce qu'on cherche en essayant de comparer la complexité de deux organismes éloignés l'un de l'autre, comme le corail et le chat, pour poursuivre l'exemple de noir_écaille?
-----

[invite6754323456711]

Est-ce que quelqu'un pourrait me dire ce qu'on cherche en essayant de comparer la complexité de deux organismes éloignés l'un de l'autre, comme le corail et le chat, pour poursuivre l'exemple de noir_écaille?

En mon sens, si on ne cherche pas une ontologie qui se cacherait derrière le mot "complexité" et fonction bien entendu d'un objectif donnée, ce cadre bâti sur la théorie de la complexité de Kolmogorov offre un référentiel/un langage commun permettant de faire des classifications dans le domaine de la génétique.

Patrick

[invite6754323456711]

Bonjour,

Une présentation qui fait la synthèse des notions de complexité aléatoire (Kolmogorov) et de complexité organisée (Bennett) dans le cadre auquel ils sont définis.

Patrick

[pesdecoa]

Ces définitions mathématiques de la complexité ne donne pas la raison d'être de la complexité.

Prenons le cas de la turbulence : Les structures complexes de la turbulence ne sont pas aléatoires. Elles sont "optimisées" pour transférer l'énergie des grands tourbillons aux petits tourbillons.
Lorsque l'énergie est transférée aux petites échelles, alors une autre forme de structure apparait, le mouvement brownien, dont le but est de dissiper l'énergie.

En biologie, c'est le même principe: Les alvéoles pulmonaires ou les vaisseaux sanguins ont des structure optimisées pour échanger l'oxygène.

[invite6754323456711]

Ces définitions mathématiques de la complexité ne donne pas la raison d'être de la complexité.

En a-t'elle une ? C'est en mon sens une erreur de vouloir chercher une ontologie à un désigné car ne peut s’avérer très fécond. On se construit des référentiels relativement à des objectifs données qui nous aides à structurer nos discours. Les probabilités, les statistiques, les groupes et leurs représentation on été de tel référentiel. Aujourd'hui un nouveau référentiel semble émergé basé sur la théorie algorithmique de l'information; Il est encore jeune mais les résultats déjà obtenue semble encourageant de par leur fécondité.

Patrick

[JPL]

Est-ce que quelqu'un pourrait me dire ce qu'on cherche en essayant de comparer la complexité de deux organismes éloignés l'un de l'autre, comme le corail et le chat, pour poursuivre l'exemple de noir_écaille?

À faire durer la discussion pour le plaisir de la rhétorique.

[invite3816b51f]

Bonjour,

je pense que l'étude des atomes a montré qu'il sont bien aussi complexes que tout autre phénomène réel
On ne peut pas mesurer la complexité car c'est le propre de la réalité c'est comme mesurer la quantité de réalité d'un objet il me semble.

[invite3816b51f]

le hasard le plus fiable est en mécanique quantique donc à la base de la réalité

Selon l'interprétation classique de la théorie quantique, les meilleurs générateurs aléatoires (c'est-à-dire ceux qui produiraient de vrais nombres aléatoires), seraient ceux qui utilisent les phénomènes quantiques. Par exemple, le choix d'un photon de traverser ou non une lame semi-réfléchissante constitue un tel générateur.

http://fr.wikipedia.org/wiki/G%C3%A9...l%C3%A9atoires

[pesdecoa]

L'intuition que j'ai de la complexité, c'est que la complexité n'est surtout pas linéaire.
Prenons le cas des transitions de phases solide/liquide. Le désordre est paramétré par la température.
Dans la phase solide, le désordre a beau augmenté, la complexité ne bronche pas d'un iota.
Au dela d'un certain niveau de désordre, alors la complexité fait un "saut" pour changer de phase -liquide en l'occurence-

La complexité semble être une quantité globale et pas locale.
Qu'est ce qui fait dire aux atomes d'un cristal de s'ordonner telle une parade militaire en Corée du Nord? Car un cristal a une complexité basse.

[invite6754323456711]

Car un cristal a une complexité basse.

Dixit wikipédia - En cristallographie, un groupe ponctuel contient les opérations de symétrie qui laissent invariants la morphologie d’un cristal et ses propriétés physiques (la symétrie de la structure atomique d’un cristal est décrite par les groupes d’espace). Donc possède une organisation.

Deux des principales applications de la complexité de Kolmogorov sont l’aléatoirité et la classification. Une application récente de la complexité de Kolmogorov : la classification par compression, qui met en œuvre une implémentation audacieuse de la complexité de Kolmogorov, par des auteurs comme Bennett, Vitanyi et Cilibrasi. Ce qui permet de dégager, entre autre, en quoi la complexité de Kolmogorov est liée à la classification.


Patrick

[invite6754323456711]

L'intuition que j'ai de la complexité, c'est que la complexité n'est surtout pas linéaire.

La complexité semble être une quantité globale et pas locale.

L'autre intuition est que la complexité n'est pas une réalité en soi. Pour en parler il nous faut construire des référentiels qui capturent chacun un regard relativement à un objectif fixé. La complexité de Kolmogorov en est un.

Patrick

[pesdecoa]

Ce qui permet de dégager, entre autre, en quoi la complexité de Kolmogorov est liée à la classification.

L'information et la complexité sont mis sur le même plan: l'information serait equivalent à la complexité.
Or il semble plutôt y avoir une relation de causalité entre les deux.
L'information traduit la méconnaissance du système localisé au point (x,y,z) et au temps t.
A partir de cette information locale, le système s'arrange dans sa globalité d'une certaine manière. Cet arrangement est mesuré alors par la complexité.
La complexité serait un paramètre global et macroscopique.
L'information serait un paramètre local et microscopique.

La complexité présenterait alors une stabilité plus forte que l'information car la loi des grands nombres pourrait jouer pleinement son rôle.

La complexité serait une émergence macroscopique de l'information microscopique.

Je me demande si l'information ne pourrait pas se traduire aussi par un couplage/une interaction statistique entre des composants.

[invite3816b51f]

Bonjour,

Merci ù100fil

La classification par compression a des résultats encouragent mais qui seront toujours imparfaits

Hélas, les méthodes parfaites de compression (mentionnées par la théorie) sont des méthodes idéales dont on démontre qu’elles ne sont pas programmables : aucun algorithme ne permettra jamais de calculer les compressions optimales de la théorie algorithmique de l’information ! Le recours à des méthodes de compression particulières et imparfaites est donc inévitable. La distance de similarité définie en s’appuyant sur un compresseur particulier C n’est qu’une version approchée d’un concept mathématique définitivement inaccessible.

Car un cristal a une complexité basse

Quel est le plus petit programme pour reproduire un diamant naturel avec ses défauts ?
En compressant l'algorithme qui produit un diamant artificiel et ce programme on pourrait trouver sa classification par compression.

[invite3816b51f]

Bonjour

La complexité serait un paramètre global et macroscopique.
L'information serait un paramètre local et microscopique.

la dualité de la lumière et le fait qu'un photon et une lame semi-réfléchissante soit le plus parfait aléatoire que nous connaissons me semble assez complexe et microscopique pour vous contredire.

[invite6754323456711]

L'information et la complexité sont mis sur le même plan: l'information serait equivalent à la complexité.

En mon sens et celui de bien d'autre (d'après ce que je peux lire) il faut prendre conscience que nous avons des degrés de liberté pour associer du sens à des étiquettes information, complexité, ... Il n'y a pas d'information en soi, ni de complexité en soi. Relativement à des objectifs donnés on construit un cadre conceptuel pour ensuite l'appliquer afin de vérifier sa pertinence et son utilité. Plusieurs regard complémentaires peuvent être possible.

Henri Poincaré disait : « On fait la science avec des faits comme une maison avec des pierres ; mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. »

Patrick

[pesdecoa]

En mon sens et celui de bien d'autre (d'après ce que je peux lire) il faut prendre conscience que nous avons des degrés de liberté pour associer du sens à des étiquettes information, complexité, ... Il n'y a pas d'information en soi, ni de complexité en soi. Relativement à des objectifs donnés on construit un cadre conceptuel pour ensuite l'appliquer afin de vérifier sa pertinence et son utilité. Plusieurs regard complémentaires peuvent être possible.

Le risque est peut-être de rendre "complémentaires" des concepts qui ne le sont pas...

Henri Poincaré disait : « On fait la science avec des faits comme une maison avec des pierres ; mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. »

Très belle image! La maison et le tas de pierres sont deux structures différentes bien que constituées des mêmes "briques".

Et donc justement, comment quantifier le rôle du maçon? Car après tout, c'est lui qui en fonction de l'information qu'il a à un intant t, va positionner la brique suivante. Au final on obtient une structure globale qui aura une certaine complexitée suivant d'une part l'information qu'aura eu au cours de la construction le maçon mais aussi de la manière dont il a traité cette information.

La complexité est l'aboutissement d'un processus dynamique élémentaire.

[invite6754323456711]

La complexité est l'aboutissement d'un processus dynamique élémentaire.

Pouquoi pas, comme je l'ai dit nous avons bon nombre de degré de liberté, mais il te faut pousser plus loin sa construction en proposent un concept permettant des mesures. Tout comme il est fait dans le cadre de la théorie algorithmique de l’information qui propose une notion de distance basé sur la compression afin de pouvoir comparer, classifier, ...

Patrick

[Ryuujin]

Peut-on compresser l’information qui définit le vivant ?

La complexité ne se résume pas à l'information.
Si je prends un bottin, c'est une grosse masse d'information, mais ça n'est pas complexe.

[invite6754323456711]

Si je prends un bottin, c'est une grosse masse d'information, mais ça n'est pas complexe.

L'information ne se résume pas à la complexité. Il se compresse bien. Dans un référentiel donner nous avons un outils de mesure. Nulle part il est mentionné la définition, mais une définition.

La définition objective (au sens dur) de la complexité ne peut être au mieux qu'une croyance de la vérité absolu.

Patrick




Patrick

[pesdecoa]

Tout comme il est fait dans le cadre de la théorie algorithmique de l’information qui propose une notion de distance basé sur la compression afin de pouvoir comparer, classifier, ...

Veux tu dire que la complexité doit nécessairement reposer sur une valeur étalon (la notion de distance ici)? Une autre quantité qui fait sens pour nous?

En partant de ce principe, j'ai cherché quels étaient des objets mathématiques complexes qui on un sens.

En premier, j'ai pensé au mouvement Brownien. Bien que très complexe (le plus complexe?), nous possédons des outils mathématiques pour sa description. Du coup, le mouvement Brownien pourrait être une sorte de repère, de jalon à partir duquel on peut comparer d'autre objets complexes.

Ensuite j'ai pensé aussi aux attracteurs étranges. Ce sont des objets complexes dont on (re)connait leurs formes caractéristiques (attracteur de Hénon, Lorenz). On pourrait aussi les utiliser comme valeurs étalons.

[invite6754323456711]

Veux tu dire que la complexité doit nécessairement reposer sur une valeur étalon (la notion de distance ici)? Une autre quantité qui fait sens pour nous?

Je veux dire qu'il n'y à rien de nouveau il faut pouvoir mesurer, comparer, classifier quel que soit le concept.

Dans le cadre qui repose sur la complexité de Kolmogorov l’idée de base est de mesurer le contenu en information commun à deux mots binaires représentant des objets d’une famille pour laquelle on désire une classification.

Une première tentative de cette nature remonte aux années 90, Bennett et coll. définissent une notion de distance informationnelle entre deux mots x,y comme étant la taille du plus court programme qui transforme le mot x en y et le mot y en x. Cette distance satisfait les axiomes d’une distance définit en mathématique.

Patrick

[pesdecoa]

Une première tentative de cette nature remonte aux années 90, Bennett et coll. définissent une notion de distance informationnelle entre deux mots x,y comme étant la taille du plus court programme qui transforme le mot x en y et le mot y en x. Cette distance satisfait les axiomes d’une distance définit en mathématique.

Ce qui est assez original avec cette approche, c'est qu'on a l'impression d'être dans un espace des programmes!

[Ryuujin]

Ce qui est gênant avec cette approche, ù100fil, c'est qu'elle suppose que la complexité d'un programme se résume à sa longueur après optimisation.
Est-ce vraiment le cas ?

[invite6754323456711]

Ce qui est gênant avec cette approche, ù100fil, c'est qu'elle suppose que la complexité d'un programme se résume à sa longueur après optimisation.
Est-ce vraiment le cas ?

Il y a deux définitions qui sont donnée de la complexité :

G. Chaitin et Kolmogorof avaient indépendamment donné une définition de la complexité aléatoire : est complexe ce qui est long à décrire ...
Par exemple d'une suite de chiffres, 947659923710740 ..., chaque chiffre étant obtenu par le lancer d'un dé à dix faces (sur chaque face du dé est inscrit un chiffre). Il n'est pas possible de décrire la suite de ces chiffres par une formule plus courte que la liste elle-même, et cette liste est aléatoire.

En revanche, la suite 01010101010 .... constituée de mille paires successives de O et de 1, est descriptible par : La suite de mille paires de 01, phrase plus courte que la liste exhaustive.

La définition de Chaitin-Kolmogorof laissait dans l'ombre un autre type de complexité. Par exemple la définition de PI est très succincte : Le quotient de la circonférence du cercle par son diamètre.,, De cette définition, on peut tirer de courts algorithmes de calcul de Pi.

Il fallait donc caractériser cette autre forme de complexité, liée à la fois au caractère très organisé de pi et à la difficulté de son calcul. Le physicien mathématicien Charles Bennett, du Centre de recherche IBM donner une définition de ce qui est complexe car très organisé afin de la distinguer de ce qui est complexe car aléatoire.

Ainsi, dans ce cadre, complexe peut signifier : "difficile à décrire totalement" ou "difficile à décrire pour ce qui est organisé ".

Par exemple, une allée de cailloux peut être difficile à décrire totalement, car il faut y indiquer l'emplacement de chaque caillou, mais elle est facile à décrire pour ce qui est, en elle, organisée : sa forme géométrique.

....

http://www2.lifl.fr/~delahaye/pls/005.pdf

Patrick

[invite6754323456711]

Ce qui est gênant avec cette approche, ù100fil, c'est qu'elle suppose que la complexité d'un programme se résume à sa longueur après optimisation.
Est-ce vraiment le cas ?

Pour répondre plus précisément à ta question. Ce n'est pas n'importe quel programme. ils visent à codifier la dualité aléatoire/organiser.

Je le répète c'est un référentiel et non des définitions dans l'absolu. On peut certainement en construire d'autre, mais il faut dépasser le verbiage pour les rendre crédible.

Patrick

[pesdecoa]

Ce qui est gênant avec cette approche, ù100fil, c'est qu'elle suppose que la complexité d'un programme se résume à sa longueur après optimisation.
Est-ce vraiment le cas ?

L'optimisation est je crois définie par rapport à un temps polynomial.
Un algorithme à temps polynomial est considéré comme efficient.
On voit donc que dans ce monde des algorithmes (ou des programmes), on a aussi défini ce qu'était le temps!

Est-ce une fausse image que je me fais ou Kolmogorov, Chaitin et les autres ont créés un monde virtuel, le monde des programmes où les programmes sont des entités capables d'interagir entre elles comme des particules physiques entre elles?

[invite6754323456711]

On voit donc que dans ce monde des algorithmes (ou des programmes), on a aussi défini ce qu'était le temps!

Ce que l'on peut lire : L'idée de C. Bennett est de rattacher la complexité organisée au temps de calcul qu'il faut pour produire une description d'un objet. Un objet aléatoire ne nécessite aucun calcul, car il n'a aucune régularité et l'on ne peut donc rien faire de mieux que le copier, éléments par élément, dans le programme charger dans donner la description. A l'inverse un objet fortement organisé contient en lui la trace d'un processus d'élaboration ou d'évolution qui correspond à une forme de calcul.

Maintenant d'un point de vue épistémologique cela peut interpeller, mais c'est un autre débat.

Patrick

[invite4492c379]

Hello,

je vais prendre un peu de temps pour clarifier deux ou trois choses (enfin à mon sens) :

* il n'y pas de lien entre complexité d'un objet décrit par un algorithme (= programme sur une MT) et complexité de ce même algorithme. En effet si on considère la longueur de cet algorithme par exemple pour décrire un objet alors la notion de compléxité algorithmique ne peut s'appliquer (hors champs d'application), si on considère le temps d'exécution alors il faudra évidemment prendre celui qui s'exécute le plus rapidement, prouver qu'il n'en existe pas de plus rapide ....

* pi n'est pas un objet difficile à calculer, dans le sens des algorithmes simples et rapides existent non seulement pour lister les décimales aussi loin qu'on peut, et même au delà dans certaines bases

* la complexité algorithmique ne concerne pas uniquement le temps d'exécution, mais peut aussi étudier l'espace utilisé, ou certaine particularités (nombre de multiplication pour comparer des algos de multiplication de matrices, nombre de comparaison ou d'échange pour les algos de tris utilisant l'un, respectivement l'autre)

[invite6754323456711]

Bonsoir,

Une video

Patrick

[Xoxopixo]

G. Chaitin et Kolmogorof avaient indépendamment donné une définition de la complexité aléatoire : est complexe ce qui est long à décrire ...
Par exemple d'une suite de chiffres, 947659923710740 ..., chaque chiffre étant obtenu par le lancer d'un dé à dix faces (sur chaque face du dé est inscrit un chiffre). Il n'est pas possible de décrire la suite de ces chiffres par une formule plus courte que la liste elle-même, et cette liste est aléatoire.

Si la suite de chiffre est infinie, peut-être....il s'agit là d'un point de vue mathématique.
Mais concretement aucune liste n'est infinie.

Dans le cas d'une suite finie, obtenue aleatoirement, il est tout à fait possible de faire le tirage suivant :
999999555556666666, qui est particulière certes, mais qui résulte d'un processus aléatoire.
Cette suite peut être décrite par exemple par 6x9,5x5,7x6, qui est une description plus courte que la liste originale.

Dire que l'on exclue la sequence 999999555556666666 d'une liste plus longue, enlève une possibilité à la liste aléatoire, et donc la liste n'est plus aleatoire.
Qu'une séquence de ce type (ou possedant une logique) apparaisse au sein d'une liste de taille très grande, est une quasi certitude.
Or ces séquences, et celles-ci pour le moins, sont compressibles...