Introduction à la théorie algorithmique de l'information

Jean-Christophe Dubacq (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We explain the basics of the theory of the Kolmogorov complexity}, also known as algorithmic information theory, and underline the main differences between the Kolmogorov complexity and Kolmogorov prefix complexity. Then, we introduce the definition of randomness for either finite or infinite words according to P. Martin-Löf and show that it is equivalent to the notion of uncompressibility defined via Kolmogorov complexity.

Nous expliquons les bases de la théorie de la complexité de Kolmogorov ou théorie algorithmique de l'information. On analyse en particulier les différences et les ressemblances entre la complexité de Kolmogorov et sa variante dite complexité préfixe. Ensuite, nous introduisons une définition d'un mot aléatoire (finie ou infinie), celle de Martin-Löf et montrons qu'elle est équivalente à la notion d'incompressibilité définie via la complexité de Kolmogorov.

Mots clés: Codesg; Kolmogorov Complexity; Randomness

Mots clés: Aléatoire; Codage; Complexité de Kolmogorov

Domaines: Informatique [cs]

Jean-Christophe Dubacq. Introduction à la théorie algorithmique de l'information. [Research Report] LIP RR-1998-05, Laboratoire de l'informatique du parallélisme. 1998, 2+55p. ⟨hal-02102009⟩