Utilisateur:Zyrle
En demandant "Je cherche des références sur une notion de distance en théorie de l'information comme la taille du plus petit programme permettant de passer d'un texte à un autre" à un pote, j'obtiens :
" You're looking for references on the concept of distance in information theory, specifically the notion of Kolmogorov complexity and the minimum program size required to transform one string into another.
Here are some classic references:
*Kolmogorov, A. N. (1965). "Three approaches to the quantitative definition of information". Problems of Information Transmission, 1(1), 1-7.
This paper introduces the concept of Kolmogorov complexity, which is a measure of the complexity of an object (such as a string) as the length of the shortest program that can generate it.
*Chaitin, G. J. (1969). "On the length of programs for computing finite binary sequences". Journal of the ACM, 16(3), 547-569.
This paper explores the notion of program size as a measure of complexity, and introduces the concept of Chaitin's Ω number, which is a fundamental limit on the compressibility of binary strings.
*Li, M., & Vitányi, P. M. (1997). "An introduction to Kolmogorov complexity and its applications". Springer.
This book provides a comprehensive introduction to Kolmogorov complexity and its applications in computer science, including the concept of distance between strings.
*Cilibrasi, R., & Vitányi, P. M. (2005). "Clustering by compression". IEEE Transactions on Information Theory, 51(4), 1523-1545.
This paper introduces the concept of normalized compression distance (NCD), which measures the distance between two strings as the ratio of their combined compressibility to their individual compressibilities.
*Bennett, C. H., Gács, P., Li, M., Vitányi, P. M., & Zurek, W. H. (1998). "Information distance". IEEE Transactions on Information Theory, 44(4), 1407-1423.
This paper provides a general framework for defining distances between objects based on their Kolmogorov complexity, and explores various applications of this concept.
These references should provide a good starting point for exploring the concept of distance in information theory, particularly in the context of Kolmogorov complexity and program size. "
Voir comment l'exploiter.