सूचना दूरी

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

गुण

औपचारिक रूप से सूचना दूरी के $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

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