Une question un peu triviale:
Supposons une série convergente possédant une infinité de termes.
Chaque terme est parfaitement déterministe ou calculable.Le manque d'information sur chaque terme est donc nul.
Or sommer une infinité de termes prend un temps infini. Donc la complexité est infinie, non ?
Salut,
En principe la complexité n'est pas liée au temps.Envoyé par pesdecoa
Mais tout dépend aussi de la définition donnée à "complexité" (d'où la longueur de ce fil de discussion). Et aussi ce à quoi il s'applique.
Au sens de Kolmogorov :
Si on parle de la complexité de la série ou du nombre qu'elle définit, effectivement la complexité peut être assez faible (en gros la complexité de l'algorithme permettant de calcul des termes).
Mais si on parle de la complexité du calcul lui-même, le calcul de la somme des termes, et qu'on désire inclure dedans le temps, alors oui ça diverge (en fait, pour le calcul lui-même j'appliquerais la même méthode que ci-dessus : complexité de l'algorithme, la complexité serait à peine plus grande que pour la série. Et en incluant le temps je parlerais plutôt de '"difficulté").
Mais il y a encore d'autres définitions. Par exemple, si j'utilise la notion de complexité calculatoire des algorithmes :
http://fr.wikipedia.org/wiki/Th%C3%A...es_algorithmes
Dans ce cas la complexité de la série est celle de l'algorithme de calcul des termes et ça peut être P, NC, NP, NPSPACE, EXPTIME, etc....
Dans le cas où cet algorithme serait NP (le calcul des termes devenant de plus en plus difficile), alors le calcul de la somme peut être extrêmement ardu même si on ne prend que quelques termes.
Bref, la définition de la complexité est.... complexe
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Dans le cadre de la théorie algorithmique de l'information deux dimensions ont été formalisées permettant de définir la complexité aléatoire et la complexité organisée dont l'une fait intervenir le temps.
Justement il en existe au moins une basé sur la théorie algorithmique de l’information, ce qui permet d'éviter d'en parler dans l'absolu.
Patrick
@Deedee81 : +1, exactement, il ne faut pas confondre ce qu'on appelle la complexité algorithmique qui permet la comparaison de deux algos en considérant le temps de résolution, l'espace utilisé, ou d'autres métriques comme le nombre de multiplication ou de comparaisons mais où ma connaissance la longueur même de l'algorithme en tant que texte n'est jamais prise en compte (sauf dans la définition de l'algorithme où on stipule qu'un algorithme est une suite finie d'instructions)
/
Les algorithmes généraux de compression de données
et
la complexité de Kolmogorov qui est aussi appelée complexité algorithmique (malheureusement) et qui concerne un autre champs d'étude, la théorie de l'information. Dans ce cadre la notion de longueur de l'algorithme tient une place centrale.
/
La compressibilité au sens de Kolmogorov
@pesdecoa: si tu prends la suite pour n>=0, des 2^(-n), il y en a une infinité, ils convergent vers 0, la somme des termes vaut 2 : un des algos le plus simple pour calculer la somme des termes serait :
Code:Début. afficher(2); Fin.
C'est ce que feraient alors G. J. Chaitin, C. Bennett, Delahaye .... ?
http://www.cs.auckland.ac.nz/~chaitin/mit.pdf
http://www2.lifl.fr/~delahaye/pls/005.pdf
http://books.google.fr/books/about/C...oC&redir_esc=y
PatrickThe next step in this program of research would be to proceed from static snapshots to time-varying situations, in other words, to set up a discrete universe with probabilistic state transitions and to show that there is a certain probability that a certain level of organization will be reached by a certain time.
More generally, one would like to determine the probability distribution of the maximum degree of organization of any organism at time t + delat as a function of it at time t
Let us propose an initial proof strategy for setting up a nontrivial example of the evolution of organisms: construct a series of intermediate evolutionary
forms, argue that increased complexity gives organisms a selective advantage, and show that no primitive organism is so successful or lethal that it diverts or blocks this gradual evolutionary pathway.
Dernière modification par invite6754323456711 ; 18/04/2012 à 11h42.
Cet exemple est très parlant!
La complexité est basse (voir ton code) car tu as une sacrée information! Tu sais que la somme vaut 2. Cette information engendre un dégonflement de la complexité. Si tu n'a pas cette information ("la somme vaut 2"), alors tu dois faire le calcul de tous les termes, les uns après les autres.
Et c'est peut-être ici qu'il faut utiliser les probabilités conditionelles...
Bon, dans tes documents on peut lire :
Ce morceau, tu m'arrêtes si je me trompe, explique simplement et rapidement l'approche de Bennett. On utilise le temps de calcul du plus petit programme et non le programme dont le temps de calcul est le plus court. On a besoin de pouvoir estimer ce temps de calcul, et pour cela on peut utiliser la complexité algorithmique «calulatoire», mais elle n'est utilisée pour autre chose ...
Tu peux me dire que Bennett propose aussi une définition utilisant un algorithme presque minimal mais cela uniquement car on n'arrive à trouver l'algorithme le plus court (dans le sens le moins grand en longueur, et non le plus rapide) et qu'il faut bien faire avec.
Donc, non, ce n'est pas ce que font G. J. Chaitin, C. Bennett, Delahaye ....
C'est surtout qu'elle ne décrit rien du tout.
Patrick
Non, il faut bien replacer tout ça.
1. La complexité n'est pas basse dans ce cas, car mon algo est plus long que la réponse : 2
2. L'information que l'on a ou que l'on a pas n'influe en rien sur la complexité aléatoire, car à priori la seule information dont on dispose est la chaine de départ.
Soit tu poses le problème en :
«quelle est la complexité algorithmique (pas Kolmogorov) d'un algorithme devant calculer la somme infinie des puissance d'un nombre calculable» : pas complexe, la réponse est donné en temps constant
«quelle est la complexité de Kolmogorov de la suite des n puissances d'un nombre calculable»
Deux questions totalement différentes.
Ben oui il faut le même référentiel pour la complexité aléatoire et la complexité organisé, sauf que l'on ne mesure pas la même chose. On doit dire la même chose, mais différemment
L'idée de C. Bennett est de rattacher la complexité organisée au temps de calcul qu'il faut pour produire une description.
Patrick
C'est curieux mais ces deux complexités me font penser à la dualité entre algèbre et géométrie.
La complexité algorithmique traduit le temps pour trouver 2. C'est de l'algèbre.
La complexité de Kolmogorov traduit le plot pour afficher (sur un graphe pour imager) les points 1, 1.5, 1.75,....., 1.98,... C'est de la géométrie.
Mais le point central pour Kolmogorov et cie est l'algorithme de plus petite longueur, la durée de ce plus petit programme est prise en compte pour étendre la théorie : la durée et pas la complexité algorithmique (pas Kolmogorov).Ben oui il faut le même référentiel pour la complexité aléatoire et la complexité organisé, sauf que l'on ne mesure pas la même chose. On doit dire la même chose, mais différemment
L'idée de C. Bennett est de rattacher la complexité organisée au temps de calcul qu'il faut pour produire une description.
Patrick
Le problème est leur nom ... elles portent le même mais ne parlent pas de la même chose (du tout) ... sans compter que dans cette discussion on ajoute d'autres noms et on les confond toutes.
Le plus simple serait de parler :
Complexité aléatoire : Kolmogorov et cie
Complexité organisée : Bennett et cie
Complexité algorithmique : sens commun en informatique.
Dans ce sens la complexité algorithmique n'est pas un un référentiel pour les deux autres. Je m'explique pourquoi :
d'abord la complexité algorithmique ne s'intéresse pas du tout à la longueur de l'algorithme (sauf dans le sens où un algorithme est une suite finie d'instruction), elle s'intéresse effectivement au temps d'exécution mais pas uniquement, et elle s'intéresse surtout à estimer ces métriques en fonction de la taille des entrées données à l'algorithme.
Ensuite la complexité aléatoire s'intéresse principalement à la longueur d'un algorithme, donc à priori rien à voir avec la complexité algorithmique, si ce n'est que certains outils utilisés sont communs, comme une MTU (machine de Turing universeele) par exemple, mais aussi plus basiquement le formalisme pour écrire un algorithme.
Quant à la complexité organisée, elle étend la complexité aléatoire en prenant en compte le temps d'exécution d'un algorithme. Alors évidemment, elle utilise des résultats de la complexité algorithmique, mais elle utilise aussi des résultats de beaucoup d'autres domaines des mathématiques. Je considère, peut être à tort, qu'autant la complexité aléatoire est un référentiel pour la complexité organisée, autant la complexité algorithmique (au même titre que l'arithmétique par exemple) n'en est pas un.
Finalement, les trois complexité ont bien un tronc commun : la définition de ce qu'est un algorithme (toutes trois en ont la même définition), les outils de bases de l'informatique théorique (MT, ...). Mais elles parlent toutes trois de notions différentes.
Pourtant c'est bien de l'application de la théorie algorithmique de l'information dont parle Kolmogorov et Bennett et bien d'autre (ils sont nombreux) tout comme il est bien souvent question d'application de théorie mathématique dans bon nombre de domaine. C'est juste l'espace des objets sur lequel on l'applique qui diffère.
Patrick
Oui, Kolmogorov et cie définissent la théorie algorithmique de l'information (qui n'existait pas avant eux). La théorie de la complexité des algorithmes parle d'autre chose de complètement différent, le champs d'étude n'est absolument pas le même. Elles ont toutes pour tronc commun la théorie de la calculabilité.
La physique est totalement différente des mathématiques pure est pourtant il est abondamment fait usage du cadre de la théorie des groupes et de leur représentation. Si c'est cela que tu insinues alors effectivement ce n'est pas la même chose. Il faut juste faire preuve d'un peu d'abstraction pour rendre applicable des concepts abstrait dans des cadres dit concret.
Patrick
Je n'insinue rien. Dans mon message #94 j'explique à la suite de Deedee81 qu'il ne faut pas confondre 2 notions différentes (ce qui est fait dans cette discussion),puis tu t'interroges dans ton message #95 si justement ces deux notions ne découlent pas finalement l'une (complexité aléatoire et complexité organisée) de l'autre (complexité algorithmique) comme tu sembles le comprendre dans les sources que tu cites. C'est pourquoi j'explique que non seulement elles ne sont pas confondues dans les documents cités, mais qu'elles n'ont effectivement aucune filiation entre elles (je parle des notions de complexité aléatoire et organisée par rapport à la notion de complexité algorithmique), que si tu cherches une filiation quelconque entre les différentes théories alors il faut plus regarder le tronc commun qui est la théorie de la calculabilité.
Jusqu'à la il a été clairement mentionné les différences et le point commun qui les unis le discours descriptif.
Sur quoi reposent les discours de Jean-Paul Delahaye, G. J. Chaitin ?(je parle des notions de complexité aléatoire et organisée par rapport à la notion de complexité algorithmique),
In discussions of the nature of life, the terms "complexity," "organism," and "information content," are sometimes used in ways remarkably analogous to the approach of algorithmic information theory, a mathematical discipline which studies the amount of information necessary for computations.
Tu en as peut être une autre compréhension qui t'es propre.
Patrick
Ce que Chaitin (et cie) développe(nt) est une théorie de l'information, ce qui est développé s'intéresse à mesurer une quantité d'information contenue dans un objet fini, a priori quelconque. On définit la complexité aléatoire de cet objet en fonction d'un algorithme spécifique et déterminé, le plus court où à défaut le plus court que nous connaissons ce qui n'en donnera qu'une limite supérieure. Bennett précise la notion de profondeur logique/complexité organisée, il étend la théorie algorithmique de l'information en considérant toujours cet algorithme spécifique à un objet donné mais en en étudiant la durée d'exécution.
Il existe d'autres théories de l'information.
La théorie de la complexité algorithmique ne s'intéresse en rien à l'information en tant qu'objet, elle ne définit ni ne quantifie cette notion. Dès lors il est clair que ce dont je parle ici n'a rien à voir avec l'étude du paragraphe précédent. Cette théorie, en gros, étudie une classe d'objets bien spécifiques (et non quelconques) : les algorithmes. On mesure tout un tas de choses, le comportement d'un algorithme en fonction de ses entrées (considérées comme quelconques) aussi bien en temps, qu'en espace, ou tout autre métrique adaptée ...
Ces deux théories ne parlent pas de la même chose, même si des mots comme «algorithmique» ou «complexité» sont identiques : elles n'ont pas le même champs d'étude. Mais même si elles interagissent (la théorie de la complexité algorithmique peut donner des outils pour mesurer le temps d'exécution d'un algorithme particulier utilisé dans la théorie algorithmique de l'information) elles sont distinctes.
Tu peux me dire où cette lecture te semble erronée selon toi ?
Tu la fait reposé par rapport à ton référentiel et il n'y a pas de référentiel privilégier. Chaitin (et cie) l'applique à autre autre choses, que la vision purement informatique que tu en donnes, qui est en quelque sorte l'algorithmie pour décrire un objet.
La théorie des groupes s'intéressent en mathématique au groupe abstrait pour ce qu'il sont alors qu'une application en physique porte sur un autre objectif la fécondité de son usage sur un espace d'ensemble objet physique.
Patrick
Dernière modification par invite6754323456711 ; 18/04/2012 à 14h36.
Comme je le disais : je ne fast que répondre à ton interrogation du message #95. Je ne prends aucun référentiels : je prends les champs d'applications définis par ces théories respectives (a priori une démarche scientifique, non ?), rien de plus. Ma conclusion est simple : les champs sont différents donc les théories n'étudient pas les mêmes choses.
Es-tu au moins en accord avec ça ?
Le mieux est que chacun construise sa propre conclusion à la lecture des différentes références données afin d'éviter toute lutte pour la possession du sens.
Chaitin, Delahaye, .. savent de quoi ils parlent et on certainement bien réfléchi au vocabulaire qu'ils utilisent pour réduire la confusion.
Patrick
Justement non !
Ces théories sont effectivement très bien développées et ont une assise solide. Comme toute théorie scientifique, elles définissent leur champs d'application. D'ailleurs Delahaye le vulgarise très clairement au début de la video dont tu as envoyé le lien :
à partie de 10' du début : «si on pense qu'il y a des objets dans le monde réel qui ne se ramènent pas à une suite de 0 et de 1 alors la complexité de Kolmogorov on en parle pas : elle ne s'intéresse qu'aux objets qu'on peut décrire par des 0 et des 1»
Il explique le champs d'application, si on en sort on dit n'importe quoi, on fait surtout dire à la théorie des choses dont elle ne se préoccupe même pas.
Donc c'est important de savoir sur quoi porte une théorie afin de ne pas raconter des bêtises, et la détermination du champs d'application n'est certainement pas laissé à l'appréciation du lecteur.
Malheureusement le vocabulaire est proche, utilise des mots identiques, dans théorie algorithmique de l'information l'adjectif algorithmique indique qu'il s'agit d'une théorie de l'information (objet étudié = information ) qui va utiliser (outil) des algorithmes comme brique de base ; dans théorie de la complexité algorithmique, le même adjectif signifie que l'objet de base étudié est l'algorithme et qu'on va en étudier la complexité en utilisant des outils mathématiques divers portant sur des métriques.
Oui, comme tout autant que de vouloir imposer son interprétation. Nous savons lire. :
2. Algorithmic Information Theory ... se paragraphe ne servirait qu'a créer la confusion
3
how to define \life," \complexity," \organism," and \information content of organism." The attempted contribution of this paper is that we propose a rigorous quantitative de finition of these concepts and are able to prove theorems about them.
However a strong note of caution is in order:
We agree with [1] that a de definition of \life" is valid as long as anything that satisfies the de finition and is likely to appear in the universe under consideration, either is alive or is a by-product of living beings or their activities.
Je le redis c'est à chacun de nous de lire ce qui est écrit en toute lettre dans les articles citées et de se construire sa propre opinion.
Patrick
##### ménage Mon but n'est pas de diriger le lecteur vers une opinion qui serait la mienne, mais de l'aider à s'en faire une qui soit basée sur des éléments clairs sans entretenir la confusion (que ton interrogation me semble-t-il à introduite, je pense par mégarde ou mécompréhension).Oui, comme tout autant que de vouloir imposer son interprétation. Nous savons lire. :
2. Algorithmic Information Theory ... se paragraphe ne servirait qu'a créer la confusion
3
how to define \life," \complexity," \organism," and \information content of organism." The attempted contribution of this paper is that we propose a rigorous quantitative definition of these concepts and are able to prove theorems about them.
However a strong note of caution is in order:
We agree with [1] that a dedefinition of \life" is valid as long as anything that satisfies the definition and is likely to appear in the universe under consideration, either is alive or is a by-product of living beings or their activities.
Je le redis c'est à chacun de nous de lire ce qui est écrit en toute lettre dans les articles citées et de se construire sa propre opinion.
Patrick
Dernière modification par JPL ; 18/04/2012 à 18h31.
Complexité algorithmique est un synonyme de complexité de Kolmogorov. Complexité au sens de Benett s'appelle "profondeure logique" (logical deep).
Question intéressante. Comme elle converge il existe un algorithme court et prenant peu de temps pour trouver le résultat. Ce n'est donc complexe ni au sens de Benett ni au sens de Kolmogorov. Par contre, ta quesiton illustre le problème de la (non)calculabilité: si on ne savait pas comment trouver vers quoi la série converge, on pourrait avoir l'impression qu'il faut vraiment faire une somme infinie de terme, auquel cas la complexité serait apparement grande au sens de Benett (pas au sens de Kolmogorov toutefois) alors qu'elle ne l'est pas. Dans le cas général, on a aucun moyen d'être certain qu'un objet n'est pas moins complexe qu'il ne parait (on peut mettre une limite supérieure cependant).
Effectivement, il y a confusion des termes (même terme mais 2 notions différentes). Complexité algorithmique se rapporte (dans le jargon de l'informatique théorique) à la théorie de la complexité des algorithmes, et malheureusement aussi à la complexité de Kolmogorov qui sont deux choses différentes. C'est pourquoi je propose tout simplement de parler de la complexité de Kolmogorov quand il s'agit de la complexité de Kolmogorov (cela me semble simple et logique) et de réserver le terme complexité algorithmique à la complexité d'un algorithme telle que la définit la théorie de la complexité des algorithmes.
Il y a une raison à cela, car avec Bennett la théorie de la complexité des algorithmes intervient, alors comment savoir à quoi l'on se réfère lorsqu'on qu'on parle de complité algorithmique dans ce contexte, si ce n'est en différenciant clairement la complexité de Kolmogorov de la complexité algorithmique (avec le sens tel que je le propose) ?
Edit: en voulant rajouter des liens, je me suis aperçu (pour lever le doute, même si la source est wikipédia) que wikipedia propose une page d'homonymie quand on demande l'article complexité algorithmique : http://fr.wikipedia.org/wiki/Complex..._algorithmique). Un lien sur les deux pages, un peu de lecture, et je pense que le lecteur sera persuadé du bien fondé de mes propos ...
[plectere, plecto, plexi, plexum (lat.) nouer, tresser]
Un système complexe est formé par des élements qui sont noués/liés entre eux. La mesure de la complexité d'un système doit se faire à travers le nombre de liaisons entre les éléments.
Un example :
Antoine va venir à la fête si Denise est là et si Christian n'est pas là.
Blanche va venir si Émile est là.
Christian va venir si Blanche est là.
Denise va venir si Émile est là.
Émile va venir si Christian n'est pas là.
Florian va venir si Christian est là et si Émile n'est pas là.
Les six éléments (A...F) sont liés entre eux, parce que le comportement de chacun est lié à celui d'un où de de plusieurs d'autres. Par conséquent, le changement du comportement de l'un va se répercuter sur tout le système (la fête).
Maintenant, la fête commence. Tout les invités regardent en même temps qui est là. Au départ, il n'y a personne, ce qui remplit seulement la condition d'Émile.
A la deuxième itération, la présence d'Émile fait que la condition de Blanche et de Dénise (et toujours celle d'Émile) est remplie.
A la troisième itération, aussi Antoine et Christian peuvent venir.
Mais, ceci fait quitter Émile et Antoine à la quatrième itération,...
Le schéma de la participation se présente ainsi :
(o = absent, x = présent)
it. .ABCDEF
0 - oooooo
1 - ooooxo
2 - oxoxxo
3 - xxxxxo
4 - oxxxoo
5 - ooxoox
6 - ooooox
7 - ooooxo = it 1
8 -.............= it 2 etc.
On tombe alors sur une périodicité de 6.
Notons que ce schéma constitue un automate cellulaire unidimensionel comme décrit par Stephen Wolfram dans son livre "A new kind of science" - la formation d'une nouvelle ligne suit des règles qui se réfèrent sur la composition de la ligne précedente, tel que "le carreau x devient noir si le carreau y de la ligne précédente est noir et le carreau z est blanc, autrement il reste blanc".
Le système décrit est plus complexe qu'un autre, ou les éléments sont moins liés entre eux, par exemple si tous les six personnes viennent sans référence à des autres.
Oui c'est vrai que c'est un autre sens possible, mais ce nom suggère une interprétation fausse àmha. Ce qui est complexe en théorie de la complexité ce ne sont pas les algorithmes mais les problèmes: par exemple l'algorithme de pesdecoa prend un temps infini actuel (donc hors Turing!) alors qu'en fait le résultat peut s'obtenir beaucoup plus rapidement. Il n'y a donc pas de sens (ou pas de sens utile*) à classifier la complexité en fonction du comportement des algorithmes. En classifiant en fonction des problèmes (et des ressources) on aboutit directement à classifier la complexité en fonction du meilleur algorithme donnant le même résultat, ce qui est plus intéressant.
En fait "complexité algorithmique" est une traduction un peu malheureuse de "Computational Complexity Theory"... complexité computationnelle serait àmha un meilleur choix, ou complexité calculatoire si on préfère le laid à l'anglicisme.
* quoique... on pourrait peut-être obtenir des classes intéressantes en fonction de la facilité à trouver un algorithme qui résout les problèmes de cette classe plutôt que de l'algorithme le plus efficace... je ne sais pas si cela à vraiment un sens mais ce serait peut-être intéressant d'y réfléchir. Merci pour cette piste de réflexion suscitée!
le nombre des equation toujour egale au nombre des inconu pour fair trouv la soluti.......
