एल्गोरिथम सूचना सिद्धांत: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
'''एल्गोरिथम [[सूचना सिद्धांत]]''' (एआईटी) [[सैद्धांतिक कंप्यूटर विज्ञान]] की एक भाग है। जो संगणना और सूचना के सिद्धांतों के बीच संबंधों से जुडा हुआ है। संगणना के रूप से उत्पन्न वस्तुओं की जानकारी को मापना (जैसा कि उत्पन्न स्टोकेस्टिक प्रक्रिया के विपरीत), जैसे कि [[स्ट्रिंग (कंप्यूटर विज्ञान)]] या कोई अन्य [[डेटा संरचना]] कहा जाता है। दूसरे शब्दों में यह '''एल्गोरिथम सूचना सिद्धांत''' के अन्दर प्रदर्शित किया गया है कि कम्प्यूटेशनल असम्पीड्यता की अनुकरण (एक स्थिरांक को छोड़कर जो केवल चुनी हुई सार्वभौमिक प्रोग्रामिंग भाषा पर निर्भर करता है।) सूचना सिद्धांत में पाए जाने वाले संबंध या असमानताएं दर्शायी जाती हैं।<ref name="Chaitin75">{{harvnb|Chaitin|1975}}</ref> [[ग्रेगरी चैतिन]] के अनुसार यह [[क्लाउड शैनन]] के सूचना सिद्धांत और [[एलन ट्यूरिंग]] [[संगणनीयता सिद्धांत]] को कॉकटेल शेकर में डालने और शीघ्रता के साथ हिलाने का परिणाम है।<ref>[http://www.cs.auckland.ac.nz/research/groups/CDMTCS/docs/ait.php Algorithmic Information Theory<!-- Bot generated title -->]</ref>
'''एल्गोरिथम [[सूचना सिद्धांत]]''' (एआईटी) [[सैद्धांतिक कंप्यूटर विज्ञान]] की एक भाग है। जो संगणना और सूचना के सिद्धांतों के बीच संबंधों से जुडा हुआ है। संगणना के रूप से उत्पन्न वस्तुओं की जानकारी को मापना (जैसा कि उत्पन्न स्टोकेस्टिक प्रक्रिया के विपरीत), जैसे कि [[स्ट्रिंग (कंप्यूटर विज्ञान)]] या कोई अन्य [[डेटा संरचना]] कहा जाता है। दूसरे शब्दों में यह '''एल्गोरिथम सूचना सिद्धांत''' के अन्दर प्रदर्शित किया गया है कि कम्प्यूटेशनल असम्पीड्यता की अनुकरण (एक स्थिरांक को छोड़कर जो केवल चुनी हुई सार्वभौमिक प्रोग्रामिंग भाषा पर निर्भर करता है।) सूचना सिद्धांत में पाए जाने वाले संबंध या असमानताएं दर्शायी जाती हैं।<ref name="Chaitin75">{{harvnb|Chaitin|1975}}</ref> [[ग्रेगरी चैतिन]] के अनुसार यह [[क्लाउड शैनन]] के सूचना सिद्धांत और [[एलन ट्यूरिंग]] [[संगणनीयता सिद्धांत]] को कॉकटेल शेकर में डालने और शीघ्रता के साथ हिलाने का परिणाम है।<ref>[http://www.cs.auckland.ac.nz/research/groups/CDMTCS/docs/ait.php Algorithmic Information Theory<!-- Bot generated title -->]</ref>


कम्प्यूटेशनल रूप से उत्पन्न वस्तुओं की अलघुकरणीय सूचना सामग्री के लिए एक सार्वभौमिक माप की औपचारिकता के अतिरिक्त, एआईटी की कुछ मुख्य उपलब्धियां यह प्रदर्शित करने के लिए थीं कि: वस्तुतः एल्गोरिथम जटिलता (स्व-सीमांकित स्थिति में) समान असमानताएं (एक कॉन्सटेन्ट को छोड़कर)<ref>or, for the mutual algorithmic information, informing the algorithmic complexity of the input along with the input itself.</ref> वह एन्ट्रॉपी (सूचना सिद्धांत) मौलिक सूचना सिद्धांत के रूप में कार्य करता है।<ref name="Chaitin75" /> यादृच्छिकता असंपीड़्यता है<ref name="Calude13">{{harvnb|Calude|2013}}</ref> और उत्कृष्ट रूप से उत्पन्न सॉफ़्टवेयर की निर्धारित सीमा के अन्तर्गत, किसी भी डेटा संरचना के होने की संभावना सबसे छोटे प्रोग्राम के क्रम की प्रक्रिया होती है। जो एक यूनिवर्शल मशीन पर चलने पर इसे उत्पन्न करती है।<ref>{{cite book |first1=Rodney G. |last1=Downey |first2=Denis R. |last2=Hirschfeldt |title=एल्गोरिदम यादृच्छिकता और जटिलता|url=https://books.google.com/books?id=FwIKhn4RYzYC |date=2010 |publisher=Springer |isbn=978-0-387-68441-3}}</ref>
कम्प्यूटेशनल रूप से उत्पन्न वस्तुओं की अलघुकरणीय सूचना सामग्री के लिए एक सार्वभौमिक माप की औपचारिकता के अतिरिक्त, एआईटी की कुछ मुख्य उपलब्धियां यह प्रदर्शित करने के लिए थीं कि: वस्तुतः एल्गोरिथम जटिलता (स्व-सीमांकित स्थिति में) समान असमानताएं (एक कॉन्सटेन्ट को छोड़कर)<ref>or, for the mutual algorithmic information, informing the algorithmic complexity of the input along with the input itself.</ref> वह एन्ट्रॉपी (सूचना सिद्धांत) मौलिक सूचना सिद्धांत के रूप में कार्य करता है।<ref name="Chaitin75" /> यादृच्छिकता असंपीड़्यता है<ref name="Calude13">{{harvnb|Calude|2013}}</ref> और उत्कृष्ट रूप से उत्पन्न सॉफ़्टवेयर की निर्धारित सीमा के अन्तर्गत, किसी भी डेटा संरचना के होने की संभावना सबसे छोटे प्रोग्राम के क्रम की प्रक्रिया होती है। जो एक यूनिवर्शल मशीन पर चलने पर इसे उत्पन्न करती है।<ref>{{cite book |first1=Rodney G. |last1=Downey |first2=Denis R. |last2=Hirschfeldt |title=एल्गोरिदम यादृच्छिकता और जटिलता|url=https://books.google.com/books?id=FwIKhn4RYzYC |date=2010 |publisher=Springer |isbn=978-0-387-68441-3}}</ref>


एआईटी मुख्य रूप से स्ट्रिंग (कंप्यूटर विज्ञान) (या अन्य डेटा संरचनाओं) की अलघुकरणीय सूचना सामग्री के उपायों का अध्ययन करता है। चूँकि अधिकांशतः गणितीय वस्तुओं को स्ट्रिंग्स के रूप में वर्णित किया जा सकता है या स्ट्रिंग्स के [[अनुक्रम की सीमा]] के रूप में वर्णित किया जा सकता है। इसका उपयोग [[पूर्णांक|पूर्णांकों]] सहित विभिन्न प्रकार की गणितीय वस्तुओं का अध्ययन करने के लिए किया जा सकता है। एआईटी के पीछे मुख्य प्रेरणाओं में से एक गणितीय वस्तुओं द्वारा [[मेटामैथमैटिक्स]] के क्षेत्र में की गई जानकारी का बहुत अध्ययन है। उदाहरण के लिए जैसा कि नीचे उल्लिखित अपूर्णता परिणामों द्वारा प्रदर्शित किया गया है। अन्य मुख्य प्रेरणाएँ एकल और निश्चित वस्तुओं के लिए सूचना सिद्धांत की सीमाओं को पार करने, एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम की अवधारणा को औपचारिक रूप प्रदान करने और संभाव्यता वितरण के पूर्व ज्ञान के बिना एक सार्थक [[बायेसियन निष्कर्ष]] खोजने से प्राप्त हुई हैं (उदाहरण के लिए क्या मार्कोव श्रृंखला या [[स्थिर प्रक्रिया]] [[स्वतंत्र और समान रूप से वितरित]] है)। इस प्रकार एआईटी को मूल रूप से तीन मुख्य गणितीय अवधारणाओं और उनके बीच के संबंधों पर स्थापित करने के लिए जाना जाता है। जो गणितीय अवधारणायें निम्नलिखित हैं- [[कोलमोगोरोव जटिलता]], एल्गोरिथम यादृच्छिक अनुक्रम और एल्गोरिथम संभाव्यता।<ref>{{harvnb|Li|Vitanyi|2013}}</ref><ref name="Calude13" />
एआईटी मुख्य रूप से स्ट्रिंग (कंप्यूटर विज्ञान) (या अन्य डेटा संरचनाओं) की अलघुकरणीय सूचना सामग्री के उपायों का अध्ययन करता है। चूँकि अधिकांशतः गणितीय वस्तुओं को स्ट्रिंग्स के रूप में वर्णित किया जा सकता है या स्ट्रिंग्स के [[अनुक्रम की सीमा]] के रूप में वर्णित किया जा सकता है। इसका उपयोग [[पूर्णांक|पूर्णांकों]] सहित विभिन्न प्रकार की गणितीय वस्तुओं का अध्ययन करने के लिए किया जा सकता है। एआईटी के पीछे मुख्य प्रेरणाओं में से एक गणितीय वस्तुओं द्वारा [[मेटामैथमैटिक्स]] के क्षेत्र में की गई जानकारी का बहुत अध्ययन है। उदाहरण के लिए जैसा कि नीचे उल्लिखित अपूर्णता परिणामों द्वारा प्रदर्शित किया गया है। अन्य मुख्य प्रेरणाएँ एकल और निश्चित वस्तुओं के लिए सूचना सिद्धांत की सीमाओं को पार करने, एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम की अवधारणा को औपचारिक रूप प्रदान करने और संभाव्यता वितरण के पूर्व ज्ञान के बिना एक सार्थक [[बायेसियन निष्कर्ष]] खोजने से प्राप्त हुई हैं (उदाहरण के लिए क्या मार्कोव श्रृंखला या [[स्थिर प्रक्रिया]] [[स्वतंत्र और समान रूप से वितरित]] है)। इस प्रकार एआईटी को मूल रूप से तीन मुख्य गणितीय अवधारणाओं और उनके बीच के संबंधों पर स्थापित करने के लिए जाना जाता है। जो गणितीय अवधारणायें निम्नलिखित हैं- [[कोलमोगोरोव जटिलता]], एल्गोरिथम यादृच्छिक अनुक्रम और एल्गोरिथम संभाव्यता।<ref>{{harvnb|Li|Vitanyi|2013}}</ref><ref name="Calude13" />
Line 22: Line 22:
एल्गोरिथम सूचना सिद्धांत की स्थापना [[रे सोलोमनॉफ]] के द्वारा की गयी थी।<ref name=Vitanyi>Vitanyi, P. "[http://homepages.cwi.nl/~paulv/obituary.html Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory"]</ref> जिन्होंने एल्गोरिथम संभाव्यता के अपने आविष्कार के भाग के रूप में मूलभूत विचारों को प्रकाशित किया। जिस पर आंकड़ों में बायस के नियमों के आवेदन से जुड़ी प्रमुख समस्याओं को दूर करने का एक उपाय के क्षेत्र पर आधारित है। उन्होंने पहली बार 1960 में [[कैलटेक]] में एक सम्मेलन में अपने परिणामों का वर्णन किया है<ref name=Caltech1960>Paper from conference on "Cerebral Systems and Computers", California Institute of Technology, February 8–11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1</ref> और फरवरी 1960 की एक रिपोर्ट में आगमनात्मक अनुमान के एक सामान्य सिद्धांत पर एक प्रारंभिक रिपोर्ट प्रस्तुत की थी।<ref name=v131>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma., (November Revision of February 4, 1960 report.)</ref> एल्गोरिथम सूचना सिद्धांत को बाद में 1965 में [[एंड्री कोलमोगोरोव]] और 1966 के पास ग्रेगरी चैतिन द्वारा स्वतंत्र रूप से विकसित किया गया था।
एल्गोरिथम सूचना सिद्धांत की स्थापना [[रे सोलोमनॉफ]] के द्वारा की गयी थी।<ref name=Vitanyi>Vitanyi, P. "[http://homepages.cwi.nl/~paulv/obituary.html Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory"]</ref> जिन्होंने एल्गोरिथम संभाव्यता के अपने आविष्कार के भाग के रूप में मूलभूत विचारों को प्रकाशित किया। जिस पर आंकड़ों में बायस के नियमों के आवेदन से जुड़ी प्रमुख समस्याओं को दूर करने का एक उपाय के क्षेत्र पर आधारित है। उन्होंने पहली बार 1960 में [[कैलटेक]] में एक सम्मेलन में अपने परिणामों का वर्णन किया है<ref name=Caltech1960>Paper from conference on "Cerebral Systems and Computers", California Institute of Technology, February 8–11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1</ref> और फरवरी 1960 की एक रिपोर्ट में आगमनात्मक अनुमान के एक सामान्य सिद्धांत पर एक प्रारंभिक रिपोर्ट प्रस्तुत की थी।<ref name=v131>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma., (November Revision of February 4, 1960 report.)</ref> एल्गोरिथम सूचना सिद्धांत को बाद में 1965 में [[एंड्री कोलमोगोरोव]] और 1966 के पास ग्रेगरी चैतिन द्वारा स्वतंत्र रूप से विकसित किया गया था।


कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई रूप हैं। सबसे व्यापक रूप से प्रयोग किया जाने वाला स्व-सीमांकन कार्यक्रमों पर आधारित है और मुख्य रूप से लियोनिद लेविन (1974) के कारण है। प्रति मार्टिन-लोफ ने अनंत अनुक्रमों के सूचना सिद्धांत में भी महत्वपूर्ण योगदान प्रदान किया है। [[ब्लम स्वयंसिद्ध]] (ब्लम 1967) पर आधारित एल्गोरिथम सूचना सिद्धांत के लिए एक स्वयंसिद्ध दृष्टिकोण मार्क बर्गिन द्वारा एंड्री कोलमोगोरोव (बर्गिन 1982) द्वारा प्रकाशन के लिए प्रस्तुत एक पेपर में प्रस्तुत किया गया था। स्वयंसिद्ध दृष्टिकोण एल्गोरिथम सूचना सिद्धांत में अन्य दृष्टिकोणों को सम्मिलित करता है। एल्गोरिथम जानकारी के स्वयंसिद्ध रूप से परिभाषित उपायों के विशेष स्थितियों के रूप में एल्गोरिथम जानकारी के विभिन्न उपायों को सही करना संभव है। समान प्रमेयों को सिद्ध करने के अतिरिक्त जैसे कि प्रत्येक विशेष माप के लिए मूल व्युत्क्रम प्रमेय, स्वयंसिद्ध सेटिंग में सिद्ध किए गए एक संबंधित प्रमेय से ऐसे सभी परिणामों को   से निकालना संभव है। यह गणित में स्वयंसिद्ध दृष्टिकोण का एक सामान्य लाभ प्राप्त होता है। एल्गोरिथम सूचना सिद्धांत के स्वयंसिद्ध दृष्टिकोण को पुस्तक (बर्जिन 2005) में विकसित किया गया था और सॉफ्टवेयर मेट्रिक्स (देबनाथ और बर्गिन, 2003) पर संचालित किया गया था।
कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई रूप हैं। सबसे व्यापक रूप से प्रयोग किया जाने वाला स्व-सीमांकन कार्यक्रमों पर आधारित है और मुख्य रूप से लियोनिद लेविन (1974) के कारण है। प्रति मार्टिन-लोफ ने अनंत अनुक्रमों के सूचना सिद्धांत में भी महत्वपूर्ण योगदान प्रदान किया है। [[ब्लम स्वयंसिद्ध]] (ब्लम 1967) पर आधारित एल्गोरिथम सूचना सिद्धांत के लिए एक स्वयंसिद्ध दृष्टिकोण मार्क बर्गिन द्वारा एंड्री कोलमोगोरोव (बर्गिन 1982) द्वारा प्रकाशन के लिए प्रस्तुत एक पेपर में प्रस्तुत किया गया था। स्वयंसिद्ध दृष्टिकोण एल्गोरिथम सूचना सिद्धांत में अन्य दृष्टिकोणों को सम्मिलित करता है। एल्गोरिथम जानकारी के स्वयंसिद्ध रूप से परिभाषित उपायों के विशेष स्थितियों के रूप में एल्गोरिथम जानकारी के विभिन्न उपायों को सही करना संभव है। समान प्रमेयों को सिद्ध करने के अतिरिक्त जैसे कि प्रत्येक विशेष माप के लिए मूल व्युत्क्रम प्रमेय, स्वयंसिद्ध सेटिंग में सिद्ध किए गए एक संबंधित प्रमेय से ऐसे सभी परिणामों को से निकालना संभव है। यह गणित में स्वयंसिद्ध दृष्टिकोण का एक सामान्य लाभ प्राप्त होता है। एल्गोरिथम सूचना सिद्धांत के स्वयंसिद्ध दृष्टिकोण को पुस्तक (बर्जिन 2005) में विकसित किया गया था और सॉफ्टवेयर मेट्रिक्स (देबनाथ और बर्गिन, 2003) पर संचालित किया गया था।


== सटीक परिभाषाएँ ==
== सटीक परिभाषाएँ ==
Line 30: Line 30:


{{Main|एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम}}
{{Main|एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम}}
एक अनंत द्विआधारी अनुक्रम को यादृच्छिक कहा जाता है, यदि कुछ निरंतर c के लिए, सभी n के लिए अनुक्रम की लंबाई n के प्रारंभिक खंड की कोलमोगोरोव जटिलता कम से कम n − c होती है। यह प्रदर्शित किया जा सकता है कि लगभग प्रत्येक अनुक्रम (मानक माप (गणित) के दृष्टिकोण से उचित सिक्का या [[लेबेस्ग उपाय]] अनंत बाइनरी अनुक्रमों के स्थान पर यादृच्छिक है। इसके अतिरिक्त, चूंकि यह प्रदर्शित किया जा सकता है कि दो अलग-अलग सार्वभौमिक मशीनों के सापेक्ष कोलमोगोरोव जटिलता एक स्थिरांक से भिन्न होती है। यादृच्छिक अनंत अनुक्रमों का संग्रह सार्वभौमिक मशीन (परिमित तारों के विपरीत) की पसंद पर निर्भर नहीं करता है। यादृच्छिकता की इस परिभाषा को सामान्यतः प्रति मार्टिन-लोफ के बाद मार्टिन-लोफ यादृच्छिकता कहा जाता है। इसे यादृच्छिकता की अन्य शक्तिशाली धारणाओं (2-यादृच्छिकता, 3-यादृच्छिकता आदि) से अलग करने के लिए संभवतः 1-यादृच्छिकता भी कहा जाता है। मार्टिन-लोफ रैंडमनेस कॉन्सेप्ट्स के अतिरिक्त रिकर्सिव रैंडमनेस, श्नोर रैंडमनेस और कर्टज़ रैंडमनेस आदि भी सम्मिलित होतें हैं। [[योंग वांग]] ने प्रदर्शित किया है<ref>{{cite thesis |first=Yongge |last=Wang |title=यादृच्छिकता और जटिलता|type=PhD |year=1996 |url=http://webpages.uncc.edu/yonwang/papers/thesis.pdf |publisher=University of Heidelberg}}</ref> कि ये सभी यादृच्छिकता अवधारणाएँ अलग-अलग होती हैं।
एक अनंत द्विआधारी अनुक्रम को यादृच्छिक कहा जाता है, यदि कुछ निरंतर c के लिए, सभी n के लिए अनुक्रम की लंबाई n के प्रारंभिक खंड की कोलमोगोरोव जटिलता कम से कम n − c होती है। यह प्रदर्शित किया जा सकता है कि लगभग प्रत्येक अनुक्रम (मानक माप (गणित) के दृष्टिकोण से उचित सिक्का या [[लेबेस्ग उपाय]] अनंत बाइनरी अनुक्रमों के स्थान पर यादृच्छिक है। इसके अतिरिक्त, चूंकि यह प्रदर्शित किया जा सकता है कि दो अलग-अलग सार्वभौमिक मशीनों के सापेक्ष कोलमोगोरोव जटिलता एक स्थिरांक से भिन्न होती है। यादृच्छिक अनंत अनुक्रमों का संग्रह सार्वभौमिक मशीन (परिमित तारों के विपरीत) की पसंद पर निर्भर नहीं करता है। यादृच्छिकता की इस परिभाषा को सामान्यतः प्रति मार्टिन-लोफ के बाद मार्टिन-लोफ यादृच्छिकता कहा जाता है। इसे यादृच्छिकता की अन्य शक्तिशाली धारणाओं (2-यादृच्छिकता, 3-यादृच्छिकता आदि) से अलग करने के लिए संभवतः 1-यादृच्छिकता भी कहा जाता है। मार्टिन-लोफ रैंडमनेस कॉन्सेप्ट्स के अतिरिक्त रिकर्सिव रैंडमनेस, श्नोर रैंडमनेस और कर्टज़ रैंडमनेस आदि भी सम्मिलित होतें हैं। [[योंग वांग]] ने प्रदर्शित किया है<ref>{{cite thesis |first=Yongge |last=Wang |title=यादृच्छिकता और जटिलता|type=PhD |year=1996 |url=http://webpages.uncc.edu/yonwang/papers/thesis.pdf |publisher=University of Heidelberg}}</ref> कि ये सभी यादृच्छिकता अवधारणाएँ अलग-अलग होती हैं।


(समुच्चय <math>\{0,1\}</math> के अतिरिक्त अन्य अक्षरों के लिए संबंधित परिभाषाएं बनाई जा सकती हैं।)
(समुच्चय <math>\{0,1\}</math> के अतिरिक्त अन्य अक्षरों के लिए संबंधित परिभाषाएं बनाई जा सकती हैं।)
Line 51: Line 51:
एक निकटतम संबंधित धारणा संभावना है कि एक सार्वभौमिक कंप्यूटर यादृच्छिक रूप से चुने गए प्रोग्राम के साथ प्रदर्शित किये जाने पर कुछ स्ट्रिंग x को आउटपुट करता है। यह एल्गोरिद्मिक प्रायिकता एल्गोरिद्मिक सोलोमनॉफ प्रायिकता (एपी) एक औपचारिक प्रकार से प्रेरण की पुरानी दार्शनिक समस्या को संबोधित करने में महत्वपूर्ण है।
एक निकटतम संबंधित धारणा संभावना है कि एक सार्वभौमिक कंप्यूटर यादृच्छिक रूप से चुने गए प्रोग्राम के साथ प्रदर्शित किये जाने पर कुछ स्ट्रिंग x को आउटपुट करता है। यह एल्गोरिद्मिक प्रायिकता एल्गोरिद्मिक सोलोमनॉफ प्रायिकता (एपी) एक औपचारिक प्रकार से प्रेरण की पुरानी दार्शनिक समस्या को संबोधित करने में महत्वपूर्ण है।


एसी और एपी की बड़ी कमी उनकी अक्षमता को प्रदर्शित करती है। समय-बद्ध लेविन जटिलता एक धीमे कार्यक्रम को उसके चलने के समय के लघुगणक को उसकी लंबाई में जोड़कर दंडित करती है। यह एसी और एपी के कंप्यूटेबल वेरिएंट की ओर जाता है और यूनिवर्सल लेविन सर्च (यूएस) सभी विपरीत समस्याओं को उच्चतम समय में हल करता है (कुछ अवास्तविक रूप से बड़े गुणक स्थिरांक के अतिरिक्त)।
एसी और एपी की बड़ी कमी उनकी अक्षमता को प्रदर्शित करती है। समय-बद्ध लेविन जटिलता एक धीमे कार्यक्रम को उसके चलने के समय के लघुगणक को उसकी लंबाई में जोड़कर दंडित करती है। यह एसी और एपी के कंप्यूटेबल वेरिएंट की ओर जाता है और यूनिवर्सल लेविन सर्च (यूएस) सभी विपरीत समस्याओं को उच्चतम समय में हल करता है (कुछ अवास्तविक रूप से बड़े गुणक स्थिरांक के अतिरिक्त)।


एसी और एपी गैर-निर्धारणा या संभावना के विषय में भौतिक या दार्शनिक अंतर्ज्ञान पर निर्भर नहीं होने के लिए अलग-अलग तारों की यादृच्छिकता की औपचारिक और कठोर परिभाषा की अनुमति भी देते हैं। सामान्यतः एक स्ट्रिंग एल्गोरिथम मार्टिन-लोफ रैंडम (एआर) है। यदि यह इस अर्थ में असम्पीडित है कि इसकी एल्गोरिथम जटिलता इसकी लंबाई के समान है।
एसी और एपी गैर-निर्धारणा या संभावना के विषय में भौतिक या दार्शनिक अंतर्ज्ञान पर निर्भर नहीं होने के लिए अलग-अलग तारों की यादृच्छिकता की औपचारिक और कठोर परिभाषा की अनुमति भी देते हैं। सामान्यतः एक स्ट्रिंग एल्गोरिथम मार्टिन-लोफ रैंडम (एआर) है। यदि यह इस अर्थ में असम्पीडित है कि इसकी एल्गोरिथम जटिलता इसकी लंबाई के समान है।

Revision as of 13:51, 10 May 2023

एल्गोरिथम सूचना सिद्धांत (एआईटी) सैद्धांतिक कंप्यूटर विज्ञान की एक भाग है। जो संगणना और सूचना के सिद्धांतों के बीच संबंधों से जुडा हुआ है। संगणना के रूप से उत्पन्न वस्तुओं की जानकारी को मापना (जैसा कि उत्पन्न स्टोकेस्टिक प्रक्रिया के विपरीत), जैसे कि स्ट्रिंग (कंप्यूटर विज्ञान) या कोई अन्य डेटा संरचना कहा जाता है। दूसरे शब्दों में यह एल्गोरिथम सूचना सिद्धांत के अन्दर प्रदर्शित किया गया है कि कम्प्यूटेशनल असम्पीड्यता की अनुकरण (एक स्थिरांक को छोड़कर जो केवल चुनी हुई सार्वभौमिक प्रोग्रामिंग भाषा पर निर्भर करता है।) सूचना सिद्धांत में पाए जाने वाले संबंध या असमानताएं दर्शायी जाती हैं।[1] ग्रेगरी चैतिन के अनुसार यह क्लाउड शैनन के सूचना सिद्धांत और एलन ट्यूरिंग संगणनीयता सिद्धांत को कॉकटेल शेकर में डालने और शीघ्रता के साथ हिलाने का परिणाम है।[2]

कम्प्यूटेशनल रूप से उत्पन्न वस्तुओं की अलघुकरणीय सूचना सामग्री के लिए एक सार्वभौमिक माप की औपचारिकता के अतिरिक्त, एआईटी की कुछ मुख्य उपलब्धियां यह प्रदर्शित करने के लिए थीं कि: वस्तुतः एल्गोरिथम जटिलता (स्व-सीमांकित स्थिति में) समान असमानताएं (एक कॉन्सटेन्ट को छोड़कर)[3] वह एन्ट्रॉपी (सूचना सिद्धांत) मौलिक सूचना सिद्धांत के रूप में कार्य करता है।[1] यादृच्छिकता असंपीड़्यता है[4] और उत्कृष्ट रूप से उत्पन्न सॉफ़्टवेयर की निर्धारित सीमा के अन्तर्गत, किसी भी डेटा संरचना के होने की संभावना सबसे छोटे प्रोग्राम के क्रम की प्रक्रिया होती है। जो एक यूनिवर्शल मशीन पर चलने पर इसे उत्पन्न करती है।[5]

एआईटी मुख्य रूप से स्ट्रिंग (कंप्यूटर विज्ञान) (या अन्य डेटा संरचनाओं) की अलघुकरणीय सूचना सामग्री के उपायों का अध्ययन करता है। चूँकि अधिकांशतः गणितीय वस्तुओं को स्ट्रिंग्स के रूप में वर्णित किया जा सकता है या स्ट्रिंग्स के अनुक्रम की सीमा के रूप में वर्णित किया जा सकता है। इसका उपयोग पूर्णांकों सहित विभिन्न प्रकार की गणितीय वस्तुओं का अध्ययन करने के लिए किया जा सकता है। एआईटी के पीछे मुख्य प्रेरणाओं में से एक गणितीय वस्तुओं द्वारा मेटामैथमैटिक्स के क्षेत्र में की गई जानकारी का बहुत अध्ययन है। उदाहरण के लिए जैसा कि नीचे उल्लिखित अपूर्णता परिणामों द्वारा प्रदर्शित किया गया है। अन्य मुख्य प्रेरणाएँ एकल और निश्चित वस्तुओं के लिए सूचना सिद्धांत की सीमाओं को पार करने, एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम की अवधारणा को औपचारिक रूप प्रदान करने और संभाव्यता वितरण के पूर्व ज्ञान के बिना एक सार्थक बायेसियन निष्कर्ष खोजने से प्राप्त हुई हैं (उदाहरण के लिए क्या मार्कोव श्रृंखला या स्थिर प्रक्रिया स्वतंत्र और समान रूप से वितरित है)। इस प्रकार एआईटी को मूल रूप से तीन मुख्य गणितीय अवधारणाओं और उनके बीच के संबंधों पर स्थापित करने के लिए जाना जाता है। जो गणितीय अवधारणायें निम्नलिखित हैं- कोलमोगोरोव जटिलता, एल्गोरिथम यादृच्छिक अनुक्रम और एल्गोरिथम संभाव्यता।[6][4]


अवलोकन

एल्गोरिथम सूचना सिद्धांत मुख्य रूप से स्ट्रिंग (कंप्यूटर विज्ञान) (या अन्य डेटा संरचनाओं) पर जटिलता के उपायों का अध्ययन करता है। चूँकि अधिकांशतः गणितीय वस्तुओं को स्ट्रिंग्स के रूप में वर्णित किया जा सकता है या स्ट्रिंग्स के अनुक्रम की सीमा के रूप में वर्णित किया जा सकता है। इसका उपयोग पूर्णांकों के साथ विभिन्न प्रकार की गणितीय वस्तुओं का अध्ययन करने के लिए किया जा सकता है।

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

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

मौलिक सूचना सिद्धांत के विपरीत, एल्गोरिथम सूचना सिद्धांत एक यादृच्छिक स्ट्रिंग की औपचारिक, कठोर परिभाषाएं और एक यादृच्छिक अनंत अनुक्रम प्रदान करता है। जो भौतिक या दार्शनिक अंतर्ज्ञान पर निर्भर नहीं करता है। (यादृच्छिक तार का समुच्चय कोल्मोगोरोव जटिलता को परिभाषित करने के लिए उपयोग की जाने वाली सार्वभौमिक ट्यूरिंग मशीन की पसंद पर निर्भर करता है। किन्तु कोई भी विकल्प समान स्पर्शोन्मुख परिणाम प्रदान करता है क्योंकि एक स्ट्रिंग की कोलमोगोरोव जटिलता केवल सार्वभौमिक ट्यूरिंग की पसंद के आधार पर एक योगात्मक स्थिरांक तक अपरिवर्तनीय होती है। इस कारण से यादृच्छिक अनंत अनुक्रमों का समुच्चय यूनिवर्शल मशीन की पसंद से स्वतंत्र होता है।)

एल्गोरिथम सूचना सिद्धांत के कुछ परिणाम, जैसे कि कोलमोगोरोव जटिलता, चैटिन की अपूर्णता प्रमेय, सामान्य गणितीय और दार्शनिक अंतर्ज्ञान को चुनौती देते प्रतीत होते हैं। इनमें से सबसे उल्लेखनीय चैतिन के स्थिरांक Ω का निर्माण हुआ है। एक वास्तविक संख्या जो इस संभावना को व्यक्त करती है कि एक स्व-सीमांकन यूनिवर्शल ट्यूरिंग मशीन समस्या को रोक देगी। जब इसके इनपुट को एक उचित सिक्के के फ्लिप द्वारा आपूर्ति की जाती है (कभी-कभी संभावना के रूप में सोचा जाता है कि एक रैंडम कंप्यूटर प्रोग्राम अंततः बंद हो जाएगा)। चूंकि Ω को सरलता से परिभाषित किया जा सकता है। किसी भी सुसंगत स्वयंसिद्ध सिद्धांत (गणितीय तर्क) में केवल Ω के कई अंकों की गणना की जा सकती है। इसलिए यह कुछ अर्थों में 'अज्ञात' है। जो ज्ञान पर एक पूर्ण सीमा प्रदान करता है। जो गोडेल के अपूर्णता प्रमेयों को याद रखता है। चूंकि Ω के अंक निर्धारित नहीं किए जा सकते और Ω के कई गुण ज्ञात हैं। उदाहरण के लिए यह एक एल्गोरिथम यादृच्छिक अनुक्रम है और इस प्रकार इसके द्विआधारी अंक समान रूप से वितरित होते हैं (वस्तुतः यह सामान्य संख्या है)।

इतिहास

एल्गोरिथम सूचना सिद्धांत की स्थापना रे सोलोमनॉफ के द्वारा की गयी थी।[7] जिन्होंने एल्गोरिथम संभाव्यता के अपने आविष्कार के भाग के रूप में मूलभूत विचारों को प्रकाशित किया। जिस पर आंकड़ों में बायस के नियमों के आवेदन से जुड़ी प्रमुख समस्याओं को दूर करने का एक उपाय के क्षेत्र पर आधारित है। उन्होंने पहली बार 1960 में कैलटेक में एक सम्मेलन में अपने परिणामों का वर्णन किया है[8] और फरवरी 1960 की एक रिपोर्ट में आगमनात्मक अनुमान के एक सामान्य सिद्धांत पर एक प्रारंभिक रिपोर्ट प्रस्तुत की थी।[9] एल्गोरिथम सूचना सिद्धांत को बाद में 1965 में एंड्री कोलमोगोरोव और 1966 के पास ग्रेगरी चैतिन द्वारा स्वतंत्र रूप से विकसित किया गया था।

कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई रूप हैं। सबसे व्यापक रूप से प्रयोग किया जाने वाला स्व-सीमांकन कार्यक्रमों पर आधारित है और मुख्य रूप से लियोनिद लेविन (1974) के कारण है। प्रति मार्टिन-लोफ ने अनंत अनुक्रमों के सूचना सिद्धांत में भी महत्वपूर्ण योगदान प्रदान किया है। ब्लम स्वयंसिद्ध (ब्लम 1967) पर आधारित एल्गोरिथम सूचना सिद्धांत के लिए एक स्वयंसिद्ध दृष्टिकोण मार्क बर्गिन द्वारा एंड्री कोलमोगोरोव (बर्गिन 1982) द्वारा प्रकाशन के लिए प्रस्तुत एक पेपर में प्रस्तुत किया गया था। स्वयंसिद्ध दृष्टिकोण एल्गोरिथम सूचना सिद्धांत में अन्य दृष्टिकोणों को सम्मिलित करता है। एल्गोरिथम जानकारी के स्वयंसिद्ध रूप से परिभाषित उपायों के विशेष स्थितियों के रूप में एल्गोरिथम जानकारी के विभिन्न उपायों को सही करना संभव है। समान प्रमेयों को सिद्ध करने के अतिरिक्त जैसे कि प्रत्येक विशेष माप के लिए मूल व्युत्क्रम प्रमेय, स्वयंसिद्ध सेटिंग में सिद्ध किए गए एक संबंधित प्रमेय से ऐसे सभी परिणामों को से निकालना संभव है। यह गणित में स्वयंसिद्ध दृष्टिकोण का एक सामान्य लाभ प्राप्त होता है। एल्गोरिथम सूचना सिद्धांत के स्वयंसिद्ध दृष्टिकोण को पुस्तक (बर्जिन 2005) में विकसित किया गया था और सॉफ्टवेयर मेट्रिक्स (देबनाथ और बर्गिन, 2003) पर संचालित किया गया था।

सटीक परिभाषाएँ

एक बाइनरी स्ट्रिंग को यादृच्छिक कहा जाता है, यदि स्ट्रिंग की कोल्मोगोरोव जटिलता कम से कम स्ट्रिंग की लंबाई होती है। एक साधारण गणना तर्क से प्रदर्शित करती है कि किसी भी लंबाई के कुछ तार यादृच्छिक हैं और लगभग सभी तार यादृच्छिक होने के बहुत पास स्थित होते हैं। चूंकि कोल्मोगोरोव जटिलता सार्वभौमिक ट्यूरिंग मशीन (अनौपचारिक रूप से, एक निश्चित विवरण भाषा जिसमें विवरण दिए गए हैं) की एक निश्चित पसंद पर निर्भर करती है। यादृच्छिक तारों का संग्रह निश्चित सार्वभौमिक मशीन की पसंद पर निर्भर करता है। फिर भी यादृच्छिक स्ट्रिंग्स के संग्रह में निश्चित मशीन की देखरेख किए बिना समान गुण होते हैं। इसलिए एक समूह के रूप में यादृच्छिक स्ट्रिंग्स के गुणों के विषय में जानकारी प्राप्त कर सकते हैं और अधिकांशतः पहले के समान एक सार्वभौमिक मशीन निर्दिष्ट किए बिना जानकारी प्राप्त करते हैं।

एक अनंत द्विआधारी अनुक्रम को यादृच्छिक कहा जाता है, यदि कुछ निरंतर c के लिए, सभी n के लिए अनुक्रम की लंबाई n के प्रारंभिक खंड की कोलमोगोरोव जटिलता कम से कम n − c होती है। यह प्रदर्शित किया जा सकता है कि लगभग प्रत्येक अनुक्रम (मानक माप (गणित) के दृष्टिकोण से उचित सिक्का या लेबेस्ग उपाय अनंत बाइनरी अनुक्रमों के स्थान पर यादृच्छिक है। इसके अतिरिक्त, चूंकि यह प्रदर्शित किया जा सकता है कि दो अलग-अलग सार्वभौमिक मशीनों के सापेक्ष कोलमोगोरोव जटिलता एक स्थिरांक से भिन्न होती है। यादृच्छिक अनंत अनुक्रमों का संग्रह सार्वभौमिक मशीन (परिमित तारों के विपरीत) की पसंद पर निर्भर नहीं करता है। यादृच्छिकता की इस परिभाषा को सामान्यतः प्रति मार्टिन-लोफ के बाद मार्टिन-लोफ यादृच्छिकता कहा जाता है। इसे यादृच्छिकता की अन्य शक्तिशाली धारणाओं (2-यादृच्छिकता, 3-यादृच्छिकता आदि) से अलग करने के लिए संभवतः 1-यादृच्छिकता भी कहा जाता है। मार्टिन-लोफ रैंडमनेस कॉन्सेप्ट्स के अतिरिक्त रिकर्सिव रैंडमनेस, श्नोर रैंडमनेस और कर्टज़ रैंडमनेस आदि भी सम्मिलित होतें हैं। योंग वांग ने प्रदर्शित किया है[10] कि ये सभी यादृच्छिकता अवधारणाएँ अलग-अलग होती हैं।

(समुच्चय के अतिरिक्त अन्य अक्षरों के लिए संबंधित परिभाषाएं बनाई जा सकती हैं।)

विशिष्ट अनुक्रम

एल्गोरिथम सूचना सिद्धांत (एआईटी) कंप्यूटर विज्ञान का उपयोग करते हुए व्यक्तिगत वस्तुओं का सूचना सिद्धांत है और संगणना, सूचना और यादृच्छिकता के बीच संबंधों से संबंधित है।

किसी वस्तु की सूचना सामग्री या जटिलता को उसके सबसे छोटे विवरण की लंबाई से मापा जा सकता है। उदाहरण के लिए स्ट्रिंग-

"0101010101010101010101010101010101010101010101010101010101010101"

संक्षिप्त विवरण '01' के 32 दोहराव हैं। जबकि-

"1100100001100001110111101110110011111010010000100101011110010110"

संभवतः स्ट्रिंग को लिखने के अतिरिक्त कोई सरल विवरण नहीं है।

अधिक औपचारिक रूप से कोलमोगोरोव जटिलता एक स्ट्रिंग x के एल्गोरिदमिक जटिलता (एसी) को सबसे छोटे प्रोग्राम की लंबाई के रूप में परिभाषित किया गया है। जो x की गणना या आउटपुट निर्धारित करता है। जहां प्रोग्राम कुछ निश्चित संदर्भ सार्वभौमिक कंप्यूटर पर चलाया जाता है।

एक निकटतम संबंधित धारणा संभावना है कि एक सार्वभौमिक कंप्यूटर यादृच्छिक रूप से चुने गए प्रोग्राम के साथ प्रदर्शित किये जाने पर कुछ स्ट्रिंग x को आउटपुट करता है। यह एल्गोरिद्मिक प्रायिकता एल्गोरिद्मिक सोलोमनॉफ प्रायिकता (एपी) एक औपचारिक प्रकार से प्रेरण की पुरानी दार्शनिक समस्या को संबोधित करने में महत्वपूर्ण है।

एसी और एपी की बड़ी कमी उनकी अक्षमता को प्रदर्शित करती है। समय-बद्ध लेविन जटिलता एक धीमे कार्यक्रम को उसके चलने के समय के लघुगणक को उसकी लंबाई में जोड़कर दंडित करती है। यह एसी और एपी के कंप्यूटेबल वेरिएंट की ओर जाता है और यूनिवर्सल लेविन सर्च (यूएस) सभी विपरीत समस्याओं को उच्चतम समय में हल करता है (कुछ अवास्तविक रूप से बड़े गुणक स्थिरांक के अतिरिक्त)।

एसी और एपी गैर-निर्धारणा या संभावना के विषय में भौतिक या दार्शनिक अंतर्ज्ञान पर निर्भर नहीं होने के लिए अलग-अलग तारों की यादृच्छिकता की औपचारिक और कठोर परिभाषा की अनुमति भी देते हैं। सामान्यतः एक स्ट्रिंग एल्गोरिथम मार्टिन-लोफ रैंडम (एआर) है। यदि यह इस अर्थ में असम्पीडित है कि इसकी एल्गोरिथम जटिलता इसकी लंबाई के समान है।

एसी, एपी और एआर एआईटी के मुख्य उप-विषय हैं। किन्तु एआईटी कई अन्य क्षेत्रों में प्रसारित होता है। यह न्यूनतम विवरण लंबाई (एमडीएल) सिद्धांत के बेस के रूप में कार्य करता है। कम्प्यूटेशनल जटिलता सिद्धांत में प्रमाण को सरल बना सकता है। वस्तुओं के बीच एक सार्वभौमिक समानता मीट्रिक को परिभाषित करने के लिए उपयोग किया गया है। यह मैक्सवेल की डेमन समस्या को हल करता है और कई अन्य कार्यों को भी संचालित करता है।

यह भी देखें

संदर्भ

  1. 1.0 1.1 Chaitin 1975
  2. Algorithmic Information Theory
  3. or, for the mutual algorithmic information, informing the algorithmic complexity of the input along with the input itself.
  4. 4.0 4.1 Calude 2013
  5. Downey, Rodney G.; Hirschfeldt, Denis R. (2010). एल्गोरिदम यादृच्छिकता और जटिलता. Springer. ISBN 978-0-387-68441-3.
  6. Li & Vitanyi 2013
  7. Vitanyi, P. "Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory"
  8. Paper from conference on "Cerebral Systems and Computers", California Institute of Technology, February 8–11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1
  9. Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma., (November Revision of February 4, 1960 report.)
  10. Wang, Yongge (1996). यादृच्छिकता और जटिलता (PDF) (PhD). University of Heidelberg.


बाहरी संबंध


अग्रिम पठन