Complexité de Kolmogorov
De Wikipedia, l'encyclopédie encyclopedia
Cet article concerne complexité de Kolmogorov. Pour une autre mesure de complexité, voir complexité de Lempel-Ziv.
En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, image numérique, chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963[1],[2]. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff[réf. nécessaire][Par qui ?]. Cette quantité peut être vue comme une évaluation d'une forme de complexité de l'objet.
Cet article sur l'informatique doit être recyclé ().
Une réorganisation et une clarification du contenu paraissent nécessaires. Améliorez-le, discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.