NDLR: Ceci est une ébauche de l’article provenant de l’encyclopédie en ligne Wikipédia. Le contenu est sous licence Creative Commons BY-SA.
Bonne lecture !
[hr]
La Théorie algorithmique de l’information, initiée par Andreï Kolmogorov, Ray Solomonov et Gregory Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d’un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing.
Cette théorie permet également de formaliser la notion de complexité d’un objet, dans la mesure où l’on considère qu’un objet (au sens large) est d’autant plus complexe qu’il faut beaucoup d’informations pour le décrire, ou – à l’inverse -, qu’un objet contient d’autant plus d’informations que sa description est longue. La théorie algorithmique de l’information est fondée sur cette équivalence : la description d’un objet est formalisée par un algorithme d’une machine de Turing, et sa complexité, ou son contenu en information, est alors formalisé par certaines caractéristiques de l’algorithme : sa longueur ou son temps de calcul.
Ces fondements sont différents de ceux de la théorie de l’information de Claude Shannon : cette dernière n’utilise pas la notion de calculabilité et n’a de sens que par rapport à un ensemble statistique de données. Cependant, les deux théories sont compatibles et des liens formels entre elles peuvent être établis.
Tandis que la théorie de l’information de Shannon a eu de nombreuses applications en informatique, télécommunications, traitement de signal et neurosciences computationnelles, la théorie algorithmique de l’information a été utilisée avec succès dans les domaines de la biologie, de la physique et même de la philosophie.