KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

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 Kolmogorov relative d'une séquenc […]