Introduction à la théorie algorithmique de l'information

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102009
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:54 AM
Last modification on : Sunday, April 28, 2019 - 1:23:00 AM

File

RR1998-05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102009, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4

Files downloads

11