Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Complexité

Introduction

Illustration métaphorique de la complexité. Les objets (tuyaux) intègrent de nombreux facteurs (taille, diamètre, situation, interconnexion, robinets, ...), ce qui rend la compréhension ardue.

La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden (Anthony Wilden, (né le 14 décembre 1935 à Londres) a collaboré avec Jacques Lacan à la critique des écrits de Freud dans la perspective linguistique et sémiotique au moment où il faisait son Ph.D. en...) ou Edgar Morin), en physique (La physique (du grec φυσις, la nature) est étymologiquement la « science de la nature ». Dans un sens général et ancien, la physique désigne la...), en biologie (La biologie, appelée couramment la « bio », est la science du vivant. Prise au sens large de science du vivant, elle recouvre une partie des sciences naturelles et de l'histoire naturelle des êtres vivants (ou...) (par exemple par Henri Atlan), en sociologie, en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement...) ou en sciences de l’information. La définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions...) connaît des nuances importantes selon ces différents domaines.

La complexité du point de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) de la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent...) de l’information

Une notion de complexité est définie en Théorie algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus...) de l'information.

Complexité de Kolmogorov

La théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut être...) de Kolmogorov définit la complexité d’un objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est défini par les relations...) fini par la taille du plus petit programme informatique (Un programme informatique est une liste d'ordres indiquant à un ordinateur ce qu'il doit faire. Il se présente sous la forme d'une ou plusieurs séquences d'instructions,...) (au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du...) 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 (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques...) une construction telle qu’une opération très particulière (par exemple le calcul de pi ou l’impression de l’intégrale (Une intégrale est le résultat de l'opération mathématique, effectuée sur une fonction, appelé intégration. Une intégrale est donc composée d'un intégrande (la...) 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 (La théorie de l'information fut mise au point pour déterminer mathématiquement le taux d’information transmis dans la communication d’un message par un canal de communication, notamment en présence de parasites appelés bruits : en...) 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 (Un paradoxe est une proposition qui contient ou semble contenir une contradiction logique, ou un raisonnement qui, bien que sans faille apparente, aboutit à une absurdité, ou encore, une situation qui contredit l'intuition...) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.) mais la suite des décimales parfaitement calculable. En revanche, le nombre dit Ω de Chaitin ne l'est pas : ce nombre mesure la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet de grande importance donnant lieu...) qu'une machine, alimentée par un programme composé de bits aléatoires, s'arrête. La topologie (La topologie est une branche des mathématiques concernant l'étude des déformations spatiales par des transformations continues (sans arrachages ni...) des nombres incompressibles est intéressante : on conçoit intuitivement que cet ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude...) est dense dans R, mais il est impossible d'exhiber de façon algorithmique un réel incompressible, puisque cela reviendrait à en donner une méthode de calcul efficace. De plus peut démontrer 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 ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème...).

Complexité algorithmique

La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Elle définit plusieurs classes de complexité (P, NP, ...) permettant de classer les algorithmes selon leurs caractéristiques.

Autres complexités

  • Système complexe.
Source: Wikipédia publiée sous licence CC-BY-SA 3.0. Vous pouvez soumettre une modification à cette définition sur cette page.

La liste des auteurs de cet article est disponible ici.