S’informer et apprendre en ligne

OWL, LMS, iLES.

Accueil > Ressources > Nombres, programmes et complexité

Nombres, programmes et complexité

lundi 6 avril 1998

Considérons deux suites de nombres :
- 3, 11, 1, 7, 15, 9, 5, 17, 19, 13
- 1, 3, 5, 7, 9, 11, 13, 15, 17, 19

La première suite nous semble aléatoire alors que la seconde ne nous paraît pas l’être. Mais les deux suites auraient très bien pu être obtenues par un processus aléatoire, par exemple en tirant au hasard d’une urne des boules portant les dix premiers entiers impairs. La probabilité d’obtenir la première suite est alors rigoureusement égale à celle d’obtenir la seconde ! Ce n’est donc pas ici la façon dont les suites ont été obtenues qui leur confère un aspect aléatoire ou pas. Ce que nous exprimons intuitivement quand nous disons que la première suite semble aléatoire et que la deuxième ne paraît pas l’être est lié à la possibilité de comprimer « l’information » nécessaire à reproduire chacune de ces suites. Nous pourrions préciser cette intuition en écrivant les nombres de ces suites sous forme binaire, en déterminant le nombre de bits nécessaires à les exprimer et en comparant ce nombre à la taille du programme (également exprimée en bits) chargé de reproduire chacune d’elles. La taille du premier programme est de l’ordre de la taille de la suite qu’il exprime alors que la taille du second est plus petite. La différence de taille serait évidemment renforcée avec des suites plus longues. Ceci nous amène à donner les deux définitions suivantes :
- Une suite est aléatoire si le plus petit algorithme capable de la construire est d’une taille équivalente à la taille de la suite ;
- La complexité d’une suite est la taille en bits du programme minimal qui peut la générer.

Lettre précédente
Lettre suivante


Voir en ligne : Lettre au format pdf