Introduction

(Article par Franck Dory, Vincent Gautier, Maxime Arnstamm)

Andrei Kolmogorov (1903 - 1987) était un enseignant chercheur en mathématiques, connu mondialement.

Il est un des fondateurs de la théorie de la complexité algorithmique.

Son principal travail dans ce domaine précis portait sur la complexité d'une chaine (de bits ou de caractères), ce qui permettait de caractériser le nombre de calculs qu'aurait à faire un système pour gérer cette chaine.

La complexité d'une chaine selon Kolmogorov est la longueur de la description la plus courte de la chaine suivant un language donné.

L'exemple le plus parlant consiste à définir les deux chaines de bits suivantes :

1. 01010101010101010101010101010101

2. 01011101011010010101010111110110

Dans cet exemple, la chaine 1 peut être décrite comme 16 fois "01" alors que la chaine 2 n'a pas de meilleur descripteur qu'elle même.