En théorie de l'information, la distance algorithmique entre deux objets finis est le nombre de bits du programme le plus court qui transforme l'un des objets en l'autre sur un ordinateur universel. Elle s'appuie sur la complexité de KolmogorovLa complexité de Kolmogorov d'un objet correspond à l'information contenue dans cet objet. Ici, il est question de deux objets, dont on veut savoir de combien ils diffèrent en termes de quantité d’information.. En termes de contenu d’information, la distance algorithmique est l'information minimale nécessaire pour passer d'un objet à l'autre. Elle a été définie et étudiée en 1992 par Ming Li et Paul Vitanyi.

Propriétés

Définition La distance d'information entre et est définie par où est un programme pour un ordinateur universel fixé ayant pour entrées des chaînes binaires .

Bennett et al. démontrent. Disponible sur ArXiv : que avec où est la complexité de KolmogorovA.N. Kolmogorov, Trois approches pour la définition quantitative de l'information, Problems Inform. Transmission, 1:1(1965), 1–7L.A. Levin, Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory, Problems Inform. Transmission, 10:3(1974), 30–35 que l'on applique à la paire est la longueur du plus petit programme qui calcule si est fourni par ailleurs.. est la quantité pertinente. En effet, le terme correctif sert à assurer qu'il s'agit bien d'une métrique.

Universalité Soit la classe des distances qui satisfont la condition de densité : Cela exclut les distances non pertinentes telles que pour , et cela assure que si la distance augmente, alors le nombre d'objets à cette distance d'un objet donné augmente. Si , alors à un terme additif constant près. Ces expressions probabilistes de la distance constituent la première classe cohomologique en cohomologie symétrique de l'information, ce qui peut être considéré comme une propriété d'universalité.

Métrique La distance est une métrique au terme additif près. La version probabiliste de la métrique est unique comme l'a montré Te Sun Han en 1981Te Sun Han, A uniqueness of Shannon information distance and related nonnegativity problems, Journal of combinatorics. 6:4 p.320-331 (1981), 30–35.

Chevauchement maximal Si , alors il existe un programme de longueur qui convertit en , et un programme de longueur tel que le programme convertit en . Les programmes sont écrits sous forme auto-délimitée, ce qui signifie que l'on peut décider où un programme se termine et où l'autre commence dans la concaténation des programmes, autrement dit les programmes les plus courts passant d'un objet à l'autre peuvent être rendus maximaux en chevauchement. Chevauchement minimal Les programmes de conversion entre les objets et peuvent également être rendus minimalement chevauchants : il existe un programme de longueur (à un terme additif en près) qui transforme en et a une petite complexité lorsque est connu (). En intervertissant les deux objets, nous obtenons l'autre programme. En gardant à l'esprit le parallélisme entre la théorie de l'information (de Shannon) et la théorie de la complexité de Kolmogorov, on peut dire que ce résultat est analogue aux théorèmes de et de Körner–Imre Csiszár–Marton. Applications Applications théoriques Le théorème d'Andrej Muchnik sur le chevauchement minimal montre qu'à partir de n'importe quel objet, pour aller vers un objet cible, il existe un programme dont la complexité de Kolmogorov ne dépend presque que de l'objet cible ! Ce résultat est à peu près optimal, car le terme d'erreur ne peut pas être significativement amélioréN.K Vereshchagin, M.V. Vyugin, Independent minimum length programs to translate between given strings, Proc. 15th Ann. Conf. Computational Complexity, 2000, 138–144.

Applications pratiques Pour déterminer la similarité entre des objets tels que les génomes, les langues, la musique, les virus informatiques, les logiciels, etc., des approximations de la distance algorithmiqueQui, comme la complexité de Kolmogorov, ne peut être calculée exactement. sont proposées; la complexité de Kolmogorov est remplacée par un algorithme de compression existant réellementLa complexité de Kolmogorov est une borne inférieure de la longueur en bits d'une version compressée de l'objet.. Le concept est alors la (NCD) entre les objets, qui sont donnés sous forme de fichiers informatiques, ainsi le génome d'une souris, le texte d'un livre, la partition d'une œuvre musicale, etc.

Notes et Références

Notes

Références

Littérature connexe

. .

Catégorie:Distance et longueur Catégorie:Théorie algorithmique de l'information Catégorie:Calculabilité