Introduction à la théorie algorithmique de l'information - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1998

Introduction à la théorie algorithmique de l'information

Résumé

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.
Fichier principal
Vignette du fichier
RR1998-05.pdf (469.24 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102009 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102009 , version 1

Citer

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⟩
69 Consultations
482 Téléchargements

Partager

Gmail Facebook X LinkedIn More