POUR L'INFORMATIQUE
Sur un exemple
Un programme de compression de données permet d'évaluer à la fois la complexité de Kolmogorov et la profondeur logique de Bennett. L'idée est que la version compressée d'un fichier doit
être vue comme un court programme engendrant le fichier. La taille de ce fichier indique donc
une valeur approchée de la complexité de Kolmogorov. De plus, le temps nécessaire à la décompression du fichier est assimilable au temps de calcul de ce court programme pour produire le
fichier initial, donc peut être vu comme une évaluation de sa profondeur logique de Bennett.
Voici concrètement ce que l'on obtient avec des images. Les expériences ont été réalisées par Hector Zenil, Cédric Gaucherel et l'auteur. On a pris sept images de même format que l'on a compressées par utilisation d'un algorithme de compression sans perte O'image que l'on retrouve après
décompression est exactement celle avant compression).
La première série indique le classement des images par ordre croissant de taille du fichier compressé. Le classement est donc celui par complexité de Kolmogorov K(s ) croissante. Sans surprise, l'image toute noire (image 1, en haut à gauche) a le contenu en information le plus petit,
et l'image composée de pixels tirés aléatoirement (image 7) est celle qui exige la plus grande
quantité de mémoire (K(s) est maximal). Les autres images sont classées à peu près comme on
s'y attend : le texte écrit à la main (image 2) demande assez peu de mémoire car il y a beaucoup
de blanc ; un réseau périodique (image 3) ; une courbe de Peano (image 4) ; une image irrégulière mais avec deux axes de symétrie (image 5) ; un microprocesseur (image 6).
La seconde série d'images (ligne du bas) reprend les sept mêmes images, mais cette fois par
ordre croissant de temps de décompression, ce qui donne des valeurs approchées de la profondeur logique de Bennett, P(s), et donc un classement par complexité structurelle croissante.
L'image 7 du premier classement (qui est parfaitement aléatoire) est maintenant parmi les premières, conformément à l'idée qu'un hasard parfait est sans structure. Le microprocesseur est
bien identifié comme le plus complexe structuralement. La courbe de Peano est sans surprise toujours considérée comme contenant des structures un peu plus riches que le motif périodique. Le
texte écrit et le motif symétrique changent de position, donnant au total un classement compatible avec ce qui, intuitivement, correspond à une complexité structurelle croissante.
Hors-série n° 52. Mathématiques & informatique Tangente
Sur un exemple
Un programme de compression de données permet d'évaluer à la fois la complexité de Kolmogorov et la profondeur logique de Bennett. L'idée est que la version compressée d'un fichier doit
être vue comme un court programme engendrant le fichier. La taille de ce fichier indique donc
une valeur approchée de la complexité de Kolmogorov. De plus, le temps nécessaire à la décompression du fichier est assimilable au temps de calcul de ce court programme pour produire le
fichier initial, donc peut être vu comme une évaluation de sa profondeur logique de Bennett.
Voici concrètement ce que l'on obtient avec des images. Les expériences ont été réalisées par Hector Zenil, Cédric Gaucherel et l'auteur. On a pris sept images de même format que l'on a compressées par utilisation d'un algorithme de compression sans perte O'image que l'on retrouve après
décompression est exactement celle avant compression).
La première série indique le classement des images par ordre croissant de taille du fichier compressé. Le classement est donc celui par complexité de Kolmogorov K(s ) croissante. Sans surprise, l'image toute noire (image 1, en haut à gauche) a le contenu en information le plus petit,
et l'image composée de pixels tirés aléatoirement (image 7) est celle qui exige la plus grande
quantité de mémoire (K(s) est maximal). Les autres images sont classées à peu près comme on
s'y attend : le texte écrit à la main (image 2) demande assez peu de mémoire car il y a beaucoup
de blanc ; un réseau périodique (image 3) ; une courbe de Peano (image 4) ; une image irrégulière mais avec deux axes de symétrie (image 5) ; un microprocesseur (image 6).
La seconde série d'images (ligne du bas) reprend les sept mêmes images, mais cette fois par
ordre croissant de temps de décompression, ce qui donne des valeurs approchées de la profondeur logique de Bennett, P(s), et donc un classement par complexité structurelle croissante.
L'image 7 du premier classement (qui est parfaitement aléatoire) est maintenant parmi les premières, conformément à l'idée qu'un hasard parfait est sans structure. Le microprocesseur est
bien identifié comme le plus complexe structuralement. La courbe de Peano est sans surprise toujours considérée comme contenant des structures un peu plus riches que le motif périodique. Le
texte écrit et le motif symétrique changent de position, donnant au total un classement compatible avec ce qui, intuitivement, correspond à une complexité structurelle croissante.
Hors-série n° 52. Mathématiques & informatique Tangente