KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

Carte mentale

Élargissez votre recherche dans Universalis

La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la théorie de l'information de l'Américain Claude Shannon (1916-2001), dont elle est la généralisation. Le revers de la médaille de cette généralité de la complexité de Kolmogorov est son lien avec les théorèmes d'incomplétude de l'Austro-Américain Kurt Gödel (1906-1978). En particulier, ce lien a pour conséquence qu'il ne peut exister aucun mécanisme général de calcul pour déterminer sans erreur K(S) pour toute séquence S. On croyait donc que ce qui est la plus générale des mesures de complexité ne pourrait pas trouver à s'appliquer concrètement et resterait seulement un outil mathématique pour envisager, dans l'abstrait, les concepts d'information et de complexité, sans impact d'aucune sorte dans aucune discipline.

Une série de travaux viennent d'établir que ce n'est pas le cas et que la notion abstraite conduit à des applications à l'utilité incontestable. La méthode suivie repose sur l'utilisation des algorithmes de compression de données qui sont devenus centraux pour nombre d'applications informatiques en même temps qu'ils sont devenus efficaces. On peut les voir comme des outils de recherche de régularités dans les séquences numériques – les fichiers informatiques – et leur exploitation pour transformer un fichier F en un fichier compressé C(F), ce qui peut être vu comme un calcul approché de K(S). Le savoir-faire accumulé depuis plus de trente ans dans ces algorithmes de compression de données a pour conséquence que la valeur approchée qu'ils évaluent de K(S) est dans bien des cas assez précise. Cela a conduit à des méthodes de classification automatique : on évalue la complexité de [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 2 pages




Écrit par :

Classification


Autres références

«  KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE  » est également traité dans :

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 mots

Dans le chapitre « La complexité algorithmique »  : […] Les difficultés mathématiques rencontrées sont peut-être liées aux résultats logiques d'incomplétude (démontrés par Gödel en 1930) et dont la compréhension n'a cessé de s'approfondir, en particulier grâce à la théorie de la complexité d'Andreï Kolmogorov (1903-1987), formulée simultanément en 1965 par Kolmogorov et Gregory Chaitin. Cette théorie dite de la complexité algorithmique développe math […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_42524

INFORMATION THÉORIE DE L'

  • Écrit par 
  • Henri ATLAN, 
  • Jean-Paul DELAHAYE, 
  • Étienne KLEIN
  •  • 3 074 mots

Dans le chapitre « Théorie algorithmique de l'information »  : […] Si l'on se fixe pour but de compresser la chaîne de caractères s et si l'on suppose qu'on dispose pour cela d'une machine M, alors la valeur de l'information de s est la longueur du plus petit programme (écrit en binaire) qui, lorsqu'il fonctionne dans M, reconstitue la chaîne s . La puissance des machines n'est pas sans limite. Dès qu'on a affaire à des machines d'une certaine puissance, leur p […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-de-l-information/#i_42524

Pour citer l’article

Jean-Paul DELAHAYE, « KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE », Encyclopædia Universalis [en ligne], consulté le 10 décembre 2019. URL : http://www.universalis.fr/encyclopedie/theorie-de-la-complexite-de-kolmogorov/