Complexite de Kolmogorov

Complexite de Kolmogorov

Complexité de Kolmogorov

La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction (plus précisément un ensemble de fonctions) permettant d'évaluer la complexité de calcul d'un nombre ou d'une suite.

Sommaire

Présentation informelle

Considérons une machine informatique M pouvant exécuter des programmes. On dit que cette machine est universelle lorsqu’elle peut émuler n'importe quelle autre machine informatique. La machine de Turing universelle en est un exemple.

On note PM l'ensemble des programmes écrits pour la machine M. Pour un programme p \in P_M, on note l(p) sa longueur en nombre d’instructions pour la machine M et s(p) sa sortie. La complexité de Kolmogorov KM(x), ou complexité algorithmique, d’une suite x = (xi)i pour une machine M est définie par :

K_M (x) = \min_{p\in P_M} \{l(p), s(p) = x\}.

C’est donc la longueur du plus petit programme écrit pour la machine M qui génère la suite x. Une suite constante a une complexité faible car les programmes qui la génèrent peuvent être très courts.

Reste à savoir dans quelle mesure la fonction KM(x) dépend de la machine M, car on peut tout à fait imaginer une machine possédant des instructions simples pour générer certaines suites complexes. La réponse est la suivante : il existe une machine universelle U (souvent qualifiée d'additivement optimale) telle que pour toute machine M il existe une constante cM vérifiant pour toute suite x l'inégalité

 K_U(x) \leq K_M(x) + c_M

Intuitivement, cM est la longueur d'un interpréteur (ou d'un émulateur), écrit pour la machine U, du langage utilisé par la machine M. On parle alors d’universalité de la complexité de Kolmogorov, en ce sens qu'elle ne dépend pas, à une constante additive près, de la machine considérée.

Une suite peut alors être considérée comme d’autant plus « aléatoire » que sa complexité est grande par rapport à sa taille. De ce point de vue, les décimales des nombres π, e ou \sqrt2 ne sont pas vraiment aléatoires puisqu'il existe des algorithmes très simples pour les calculer.

Propriétés

La complexité de Kolmogorov n'est pas calculable. En d'autre termes il n'existe pas de programme informatique qui prenne en entrée s et renvoie K(s). Raisonnons par l'absurde et supposons qu'une telle fonction Kolmo existe; la taille de cette fonction (nombre de caractères) est connue et égale à k. On pourrait alors écrire l'algorithme suivant:

  n :=1 
     Tant que Kolmo(n)<k+100 faire:
        n:=n+1
     Fin du Tant que
  écrire n

Ainsi cet algorithme écrit le plus petit nombre à avoir une complexité de Kolmogorov supérieure à k+100 (ce nombre existe nécessairement car il n'y a qu'un nombre fini de programmes de tailles plus petite que k+100 et il y a une infinité de nombres entiers naturels).

Mais l'algorithme ci-dessus s'écrit justement avec moins de k+100 caractères : il est donc de complexité inférieure à k+100, or il écrit justement un nombre de complexité supérieure à k+100, ce qui est absurde.

Donc il n'existe pas de fonction qui calcule la complexité de Kolmogorov.


Voir aussi

Articles connexes

Références

Une partie de cet article (ou d'une version antérieure) est adaptée de [1], sous GFDL.

Ce document provient de « Complexit%C3%A9 de Kolmogorov ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Complexite de Kolmogorov de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Complexité De Kolmogorov — La complexité de Kolmogorov (nommée d après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction (plus précisément un ensemble de fonctions) permettant d évaluer la complexité de… …   Wikipédia en Français

  • Complexité de kolmogorov — La complexité de Kolmogorov (nommée d après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction (plus précisément un ensemble de fonctions) permettant d évaluer la complexité de… …   Wikipédia en Français

  • Complexité de Kolmogorov — La complexité de Kolmogorov (nommée d après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithme[1] nécessaire pour… …   Wikipédia en Français

  • complexité de Kolmogorov — ● loc. f. ►INTART Du nom de Kolmogorov, Andreï. Mesure de la complexité d un objet constitué d une suite d informations, et calculée comme étant la taille en bits du plus petit programme capable de l engendrer …   Dictionnaire d'informatique francophone

  • Complexite — Complexité 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 hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

  • Complexité politique — Complexité 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 hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

  • Complexité sociale — Complexité 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 hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

  • Complexité — 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 …   Wikipédia en Français

  • Kolmogorov — Andreï Kolmogorov Andreï Kolmogorov Andreï Nikolaïevitch Kolmogorov (en russe : Андрей Николаевич Колмогоров ; 25 avril 1903 à Tambov 20 octobre 1987 à …   Wikipédia en Français

  • Complexite P — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”