सूचना दूरी

सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक कंप्यूटर में बदल देती है यह जटिलता का विस्तार है इसमें एकल परिमित वस्तु की कोलमोगोरोव जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु से या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित और जांच की गई थी ऊष्मागतिकीय सिद्धांतों पर आधारित यह सामान्यीकृत संपीड़न दूरी और सामान्यीकृत दूरी में लागू होता है।

गुण

औपचारिक रूप से सूचना दूरी के $ID(x,y)$ बीच में $x$ और $y$ द्वारा परिभाषित किया गया है

$ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},$

साथ $p$ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को में परिभाषित करें इससे यह सिद्ध है कि$ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ साथ

$E(x,y)=\max\{K(x\mid y),K(y\mid x)\},$ जहाँ $K(\cdot \mid \cdot )$ द्वारा परिभाषित कोलमोगोरोव की जटिलता है।

सार्वभौमिकता

सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे $D(x,y)$ जो घनत्व की स्थिति को संतुष्ट करता है

$\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,$

यह अप्रासंगिक दूरियों को बाहर करता है जैसे $D(x,y)={\frac {1}{2}}$ के लिए $x\neq y$ यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है तो $D\in \Delta$ तब $E(x,y)\leq D(x,y)$ यह एक निरंतर योगात्मक शब्द तक की दूरी संभाव्यता अभिव्यक्तियाँ सूचना सममित में पहला वर्ग है जिसे सार्वभौमिकता संपत्ति के रूप में जाना जा सकता है।

मीट्रिक

दूरी $E(x,y)$ योज्य तक एक प्रवेशिका स्थान है जो $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ प्रवेशिका 1981 में हान द्वारा दिखाया गया कि प्रवेशिका का संभाव्य संस्करण में अद्वितीय है।

अधिकतम अतिच्छादन

अगर $E(x,y)=K(x\mid y)$ एक कार्यक्रम होता है तो $p$ लंबाई $K(x\mid y)$ में परिवर्तित हो जाता है $y$ को $x$ और एक कार्यक्रम $q$ लंबाई का $K(y\mid x)-K(x\mid y)$ ऐसा रूपांतरण है कि कार्यक्रम $qp$ धर्मान्तरित $x$ तथा $y$.अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है $K(x\mid y)\leq K(y\mid x)$ इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें $x$ वस्तु के लिए $y$और दूसरा कार्यक्रम जो पहले धर्मान्तरित के साथ जुड़ा हुआ है जैसे $y$ तथा $x$ जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।

न्यूनतम अतिच्छादन

कार्यक्रम को वस्तुओं के बीच बदलने के लिए $x$ और $y$ न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ $p$ लंबाई$O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ है यहाँ $y$ तथा $x$ छोटी जटिलता है जब $x$ ज्ञात है तो ($K(p\mid x)\approx 0$).जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है इसमें शैन्य सूचना सिद्धांत और जटिलता सिद्धांत के बीच समानता रखनी चाहिए।

अनुप्रयोग

सैद्धांतिक

इसमें ऊपर न्यूनतम अतिच्छादन पर एक महत्वपूर्ण सैद्धांतिक अनुप्रयोग दिखाया जा रहा है कि इसमें कुछ संकेत एकत्रित हैं यह किसी वस्तु से परिमित लक्ष्य पर जाने के लिए कार्यरत् है जो लक्ष्य वस्तु पर निर्भर करता है ।

व्यावहारिक

इसमें भाषा, संगीत, इंटरनेट और सॉफ़्टवेयर कार्यक्रम आदि वस्तुओं की समानता निर्धारित करने के लिए सूचना दूरी को सामान्यीकृत किया जाता है यह कोलमोगोरोव जटिलता की शर्तों को वास्तविक दुनिया द्वारा जोड़कर अनुमानित किया जाता है यह परिणामतः वस्तुओं के बीच सामान्यीकृत संपीड़न दूरी निर्धारित करता है तथा कंप्यूटर फाइलों के रूप में दी गई वस्तुओं से संबंधित है जैसे कि माउस या किसी पुस्तक का पाठ आदि।

संबंधित साहित्य

• Arkhangel'skii, A. V.; Pontryagin, L. S. (1990), General Topology I: Basic Concepts and Constructions Dimension Theory, Encyclopaedia of Mathematical Sciences, Springer, ISBN 3-540-18178-4

श्रेणी:सांख्यिकीय दूरी