श्रृंखला-समानांतर आंशिक क्रम: Difference between revisions
(Created page with "File:Series-parallel partial order.svg|thumb|upright=1.35|एक श्रृंखला-समानांतर आंशिक क्रम, हस्स आरेख...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Series-parallel partial order.svg|thumb|upright=1.35|एक श्रृंखला-समानांतर आंशिक क्रम, हस्स आरेख के रूप में दिखाया गया है।]][[आदेश सिद्धांत | [[File:Series-parallel partial order.svg|thumb|upright=1.35|एक श्रृंखला-समानांतर आंशिक क्रम, हस्स आरेख के रूप में दिखाया गया है।]][[आदेश सिद्धांत|क्रम-सैद्धांतिक]] गणित में, एक श्रृंखला-समानांतर आंशिक क्रम एक आंशिक रूप से क्रमबद्ध समुच्चय है, जो दो सरल संरचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक क्रमों से निर्मित होता है।<ref name="bgr">{{citation | ||
| last1 = Bechet | first1 = Denis | | last1 = Bechet | first1 = Denis | ||
| last2 = De Groote | first2 = Philippe | | last2 = De Groote | first2 = Philippe | ||
| Line 21: | Line 21: | ||
| volume = 255 | | volume = 255 | ||
| year = 1989}}.</ref> | | year = 1989}}.</ref> | ||
श्रृंखला-समानांतर आंशिक | |||
'''| क्रम-सैद्धांतिक गणित में, एक श्रृंखला-समानांतर आंशिक क्रम एक आंशिक रूप से क्रमबद्ध समुच्चय है जो दो सरल संरचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक क्रमों से निर्मित होता है।''' | |||
श्रृंखला-समानांतर आंशिक क्रमों को N-मुक्त परिमित आंशिक क्रमों के रूप में वर्णित किया जा सकता है; उनके पास [[आदेश आयाम|क्रम आयाम]] अधिकतम दो हैं।<ref name="bgr" /><ref name="vtl">{{citation | |||
| last1 = Valdes | first1 = Jacobo | | last1 = Valdes | first1 = Jacobo | ||
| last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan | | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan | ||
| Line 31: | Line 33: | ||
| title = The recognition of series parallel digraphs | | title = The recognition of series parallel digraphs | ||
| volume = 11 | | volume = 11 | ||
| year = 1982}}.</ref> इनमें | | year = 1982}}.</ref> वे अशक्त क्रम और निर्देशित ट्री और निर्देशित श्रृंखला-समानांतर रेखांकन में पुन: योग्यता संबंध सम्मिलित हैं। '''इनमें (ग्राफ़ थ्योरी) और निर्देशित श्रृंखला-समानांतर ग्राफ़ में अशक्त क्रम और [[गम्यता]] संबंध सम्मिलित हैं।'''<ref name="m" /><ref name="vtl" /> श्रृंखला-समानांतर आंशिक क्रमों की तुलनात्मकता रेखांकन [[कोग्राफ]] हैं।<ref name="m" /><ref name="j" /> | ||
[[जॉब शॉप शेड्यूलिंग]] | [[जॉब शॉप शेड्यूलिंग]],<ref>{{citation | ||
| last = Lawler | first = Eugene L. | authorlink = Eugene Lawler | | last = Lawler | first = Eugene L. | authorlink = Eugene Lawler | ||
| doi = 10.1016/S0167-5060(08)70323-6 | | doi = 10.1016/S0167-5060(08)70323-6 | ||
| Line 41: | Line 43: | ||
| title = Sequencing jobs to minimize total weighted completion time subject to precedence constraints | | title = Sequencing jobs to minimize total weighted completion time subject to precedence constraints | ||
| volume = 2 | | volume = 2 | ||
| year = 1978| isbn = 9780720410433 }}.</ref> [[समय श्रृंखला]] डेटा में | | year = 1978| isbn = 9780720410433 }}.</ref> [[समय श्रृंखला]] डेटा में इवेंट अनुक्रमण की [[ यंत्र अधिगम |मशीन लर्निंग]],<ref name="mm" /> [[मल्टीमीडिया]] डेटा के प्रसारण अनुक्रमण,<ref name="accdc" /> और डेटाफ्लो प्रोग्रामिंग में थ्रूपुट अधिकतमकरण में श्रृंखला-समानांतर आंशिक क्रम प्रयुक्त किए गए हैं।<ref name="cnns" /> | ||
'''में श्रृंखला-समानांतर आंशिक क्रम प्रयुक्त किए गए हैं, डेटा में घटना अनुक्रमण की , डेटा का प्रसारण अनुक्रमण, और डेटा प्रवाह प्रोग्रामिंग में थ्रूपुट अधिकतमकरण।''' | |||
श्रृंखला-समानांतर आंशिक | श्रृंखला-समानांतर आंशिक क्रमों को मल्टीट्रीज़ भी कहा जाता है;<ref name="j">{{citation | ||
| last = Jung | first = H. A. | | last = Jung | first = H. A. | ||
| title = On a class of posets and the corresponding comparability graphs | | title = On a class of posets and the corresponding comparability graphs | ||
| Line 53: | Line 57: | ||
|mr=0491356 | |mr=0491356 | ||
| doi = 10.1016/0095-8956(78)90013-8| doi-access = free | | doi = 10.1016/0095-8956(78)90013-8| doi-access = free | ||
}}.</ref> | }}.</ref> चूँकि, यह नाम अस्पष्ट है: [[ हॉटलाइन | मल्टीट्रीज़]] आंशिक क्रम को भी संदर्भित करता है, जिसमें कोई चार-तत्व हीरा उपक्रम नहीं होता है<ref>{{citation | ||
| last1 = Furnas | first1 = George W. | | last1 = Furnas | first1 = George W. | ||
| last2 = Zacks | first2 = Jeff | | last2 = Zacks | first2 = Jeff | ||
| Line 61: | Line 65: | ||
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) | | title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) | ||
| year = 1994| s2cid = 18710118 | | year = 1994| s2cid = 18710118 | ||
}}.</ref> और कई | }}.</ref> और कई ट्री से बनी अन्य संरचनाओं के लिए नहीं होता है। | ||
== परिभाषा == | == परिभाषा == | ||
दो आंशिक क्रमित समुच्चय {{mvar|P}} और {{mvar|Q}} पर विचार करें। {{mvar|P}} और {{mvar|Q}} की श्रृंखला संरचना, {{math|''P''; ''Q''}} लिखी गई है, | |||
'''विचार करना और , दो आंशिक रूप से क्रम किए गए समुच्चय। की श्रृंखला संरचना और , लिखा हुआ ,'''<ref name="accdc" /> {{math|''P'' * ''Q''}},<ref name="m" />या {{math|''P'' ⧀ ''Q''}},<ref name="bgr" /> आंशिक रूप से क्रमबद्ध समुच्चय है जिसके अवयव {{mvar|P}} और {{mvar|Q}} के तत्वों के अलग संघ हैं। '''असंयुक्त संघ हैं और . में''' {{math|''P''; ''Q''}} में, दो तत्व {{mvar|x}} और {{mvar|y}} जो दोनों {{mvar|P}} से संबंधित हैं या दोनों {{mvar|Q}} से संबंधित हैं, उनका समान क्रम संबंध है जो वे क्रमशः {{mvar|P}} या {{mvar|Q}} में करते हैं। '''हैं या दोनों के हैं''' '''का वही क्रम''' '''संबंध है जो वे करते हैं क्रमश।''' चूंकि, प्रत्येक जोड़ी {{mvar|x}}, {{mvar|y}} के लिए जहाँ {{mvar|x}}, {{mvar|P}} से संबंधित है और {{mvar|y}}, {{mvar|Q}} से संबंधित है, श्रृंखला संरचना में एक अतिरिक्त क्रम संबंध {{math|''x'' ≤ ''y''}} है। '''से संबंधित , एक अतिरिक्त क्रम संबंध है''' श्रृं'''खला संरचना में।''' श्रृंखला संरचना एक साहचर्य संक्रिया है: कोई {{math|''P''; ''Q''; ''R''}} लिख सकता है; तीन क्रमों की श्रृंखला संरचना के रूप में, अस्पष्टता के बिना कि कैसे उन्हें जोड़ी में संयोजित किया जाए, क्योंकि दोनों कोष्ठक {{math|(''P''; ''Q''); ''R''}} और {{math|''P''; (''Q''; ''R'')}} उसी आंशिक क्रम का वर्णन करें। चूँकि, यह एक [[क्रमविनिमेय संचालन|कम्यूटेटिव ऑपरेशन]] नहीं है, क्योंकि {{mvar|P}} और {{mvar|Q}} की भूमिकाओं को बदलने से एक अलग आंशिक क्रम उत्पन्न होगा जो {{mvar|P}} में एक तत्व और {{mvar|Q}} में एक के साथ जोड़े के क्रम संबंधों को उलट देता है।<ref name="bgr" /> '''और एक में .''' | |||
{{mvar|P}} और {{mvar|Q}} की समानांतर संरचना, {{math|''P'' {{!}}{{!}} ''Q''}},<ref name="accdc" /> {{math|''P'' + ''Q''}},<ref name="m" /> या {{math|''P'' ⊕ ''Q''}} इसी तरह परिभाषित किया गया है, '''लिखी गई है,'''<ref name="bgr" /> {{mvar|P}} में तत्वों और {{mvar|Q}} में तत्वों के असंयुक्त संघ से, तत्वों के जोड़े के साथ जो दोनों {{mvar|P}} या दोनों {{mvar|Q}} से संबंधित हैं, उसी क्रम में हैं जैसे वे क्रमशः {{mvar|P}} या {{mvar|Q}} में करते हैं। '''या दोनों को उसी क्रम में जैसा वे करते हैं या क्रमश।''' {{math|''P'' {{!}}{{!}} ''Q''}} में, एक जोड़ी {{mvar|x}}, {{mvar|y}} जब भी अतुलनीय है, जब भी {{mvar|x}} {{mvar|P}} से संबंधित होता है और {{mvar|y}} {{mvar|Q}} से संबंधित होता है। '''संबंधित .''' समानांतर संरचना कम्यूटेटिव और साहचर्य दोनों होती है।<ref name="bgr" /> | |||
श्रृंखला-समानांतर आंशिक क्रम का वर्ग आंशिक क्रम का समुच्चय है, जिसे इन दो परिचालनों का उपयोग करके एकल-तत्व आंशिक क्रम से बनाया जा सकता है। समतुल्य रूप से, यह आंशिक क्रमों का सबसे छोटा समुच्चय है, जिसमें एकल-तत्व आंशिक क्रम सम्मिलित हैं और श्रृंखला और समानांतर संरचना संचालन के अनुसार क्लोजर है।<ref name="bgr" /><ref name="m" /> | |||
एक अशक्त क्रम संरचना संचालन के एक अनुक्रम से प्राप्त श्रृंखला समानांतर आंशिक क्रम है, जिसमें सभी समानांतर संरचनाएं पहले की जाती हैं, और फिर इन संरचनाओं के परिणाम केवल श्रृंखला संरचनाओं का उपयोग करके संयुक्त होते हैं।<ref name="m" /> | |||
एक | == निषिद्ध उपक्रम लक्षण वर्णन == | ||
चार तत्वों {{mvar|a}}, {{mvar|b}}, {{mvar|c}}, और {{mvar|d}} के साथ आंशिक क्रम एन और बिल्कुल तीन आदेश संबंध {{math|''a'' ≤ ''b'' ≥ ''c'' ≤ ''d''}} एक फेंस या ज़िगज़ैग पोसेट का एक उदाहरण है; इसके हस्से आरेख में बड़े अक्षर N का आकार है। यह श्रृंखला-समानांतर नहीं है, क्योंकि इसे दो छोटे आंशिक क्रमों की श्रृंखला या समानांतर संरचना में विभाजित करने की कोई विधि नहीं है। एक आंशिक क्रम {{mvar|P}} को N-मुक्त कहा जाता है, यदि इसमें चार तत्वों का एक समुच्चय {{mvar|P}} उपस्थित नहीं है, जैसे कि उन तत्वों के लिए {{mvar|P}} का प्रतिबंध {{mvar|N}} के लिए क्रम-आइसोमॉर्फिक है। श्रृंखला-समानांतर आंशिक क्रम बिल्कुल गैर-रिक्त परिमित N-मुक्त आंशिक क्रम हैं।<ref name="bgr"/><ref name="m"/><ref name="vtl"/> | |||
'''आंशिक क्रम {{mvar|N}} चार तत्वों के साथ , , , और और बिल्कुल तीन क्रम संबंध (गणित) या ज़िगज़ैग पॉसमुच्चय का एक उदाहरण है; इसके हस्से आरेख में बड़े अक्षर का आकार है। N-मुक्त यदि का प्रतिबंध उन तत्वों के लिए .''' | |||
यह इससे तुरंत अनुसरण करता है (चूंकि यह सीधे भी सिद्ध किया जा सकता है) कि श्रृंखला-समानांतर आंशिक क्रम का कोई भी गैर-रिक्त प्रतिबंध स्वयं एक श्रृंखला-समानांतर आंशिक क्रम है।<ref name="bgr" /> | |||
== | == क्रम आयाम == | ||
आंशिक | आंशिक क्रम {{mvar|P}} का क्रम आयाम, {{mvar|P}} के एक रियलाइज़र का न्यूनतम आकार है, {{mvar|P}} के [[रैखिक विस्तार]] का एक समुच्चय, संपत्ति के साथ, जो {{mvar|P}} के प्रत्येक दो अलग-अलग तत्वों {{mvar|x}} और {{mvar|y}} के लिए, {{math|''x'' ≤ ''y''}} {{mvar|P}} में यदि और केवल यदि {{mvar|x}} की रिलीवर के प्रत्येक रैखिक विस्तार में {{mvar|y}} की तुलना में पहले की स्थिति है। ''', में यदि और केवल यदि की तुलना में पहले की स्थिति है रियालीजर के प्रत्येक रैखिक विस्तार में।''' श्रृंखला-समानांतर आंशिक क्रम में अधिकतम दो क्रम आयाम होते हैं। यदि {{mvar|P}} और {{mvar|Q}} के पास क्रमशः {{math|{''L''{{sub|1}}, ''L''{{sub|2}}} }} और {{math|{''L''{{sub|3}}, ''L''{{sub|4}}<nowiki>}</nowiki>}} रियलाइज़र हैं, तो {{math|{''L''{{sub|1}}''L''{{sub|3}}, ''L''{{sub|2}}''L''{{sub|4}}} }} श्रृंखला संयोजन {{math|''P''; ''Q''}} का एक बोध कराने वाला है, और {{math|{''L''{{sub|1}}''L''{{sub|3}}, ''L''{{sub|4}}''L''{{sub|2}}} }} समानांतर संरचना {{math|''P'' {{!}}{{!}} ''Q''}} का एक बोध कराने वाला है।<ref name="m"/><ref name="vtl"/> एक आंशिक क्रम श्रृंखला-समानांतर होती है, यदि और केवल यदि उसके पास एक बोधकर्ता है, जिसमें दो क्रमपरिवर्तनों में से एक पहचान है और दूसरा एक वियोज्य क्रमपरिवर्तन है। | ||
यह ज्ञात है कि एक आंशिक | यह ज्ञात है कि एक आंशिक क्रम {{mvar|P}} का क्रम आयाम दो है यदि और केवल यदि समान तत्वों पर कोई संयुग्मी क्रम {{mvar|Q}} उपस्थित है, इस संपत्ति के साथ कि कोई भी दो अलग-अलग तत्व {{mvar|x}} और {{mvar|y}} इन दो क्रमों में से किसी एक पर तुलनीय हैं। श्रृंखला समानांतर आंशिक क्रमों की स्थिति में, एक संयुग्मित क्रम जो स्वयं श्रृंखला समानांतर है, उसी क्रम में संरचना संचालन के अनुक्रम को उसी क्रम में प्राप्त किया जा सकता है, जो समान तत्वों पर {{mvar|P}} को परिभाषित करते हैं, लेकिन प्रत्येक समानांतर रचना के लिए {{mvar|P}} के अपघटन में और इसके विपरीत एक श्रृंखला संरचना का प्रदर्शन करते हैं। '''जो परिभाषित करते हैं समान तत्वों पर, लेकिन के अपघटन में प्रत्येक समांतर संरचना के लिए श्रृंखला संरचना का प्रदर्शन करना और इसके विपरीत।''' अधिक दृढ़ता से, चूंकि एक आंशिक क्रम में कई अलग-अलग संयुग्म हो सकते हैं, एक श्रृंखला समानांतर आंशिक क्रम के प्रत्येक संयुग्म को स्वयं श्रृंखला समानांतर होना चाहिए।<ref name="m"/> | ||
== ग्राफ सिद्धांत से संबंध == | == ग्राफ सिद्धांत से संबंध == | ||
किसी भी आंशिक क्रम को एक निर्देशित विश्वकोश ग्राफ द्वारा दर्शाया जा सकता है ( | किसी भी आंशिक क्रम को एक निर्देशित विश्वकोश ग्राफ द्वारा दर्शाया जा सकता है (सामान्यतः एक से अधिक तरीकों से) जिसमें से एक रास्ता होता है {{mvar|x}} को {{mvar|y}} जब कभी भी {{mvar|x}} और {{mvar|y}} आंशिक क्रम के तत्व हैं {{math|''x'' ≤ ''y''}}. इस तरह से श्रृंखला-समानांतर आंशिक क्रमों का प्रतिनिधित्व करने वाले ग्राफ़ को वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है, और उनके सकर्मक कटौती (आंशिक क्रम के [[कवरिंग संबंध|कवरिंग संबंधों]] के ग्राफ़) को न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है।<ref name="vtl"/> निर्देशित पेड़ और (दो-टर्मिनल) श्रृंखला समानांतर रेखांकन न्यूनतम वर्टेक्स श्रृंखला समानांतर रेखांकन के उदाहरण हैं; इसलिए, श्रृंखला समानांतर आंशिक क्रमों का उपयोग निर्देशित ट्री और श्रृंखला समानांतर रेखांकन में पुन: योग्यता संबंधों का प्रतिनिधित्व करने के लिए किया जा सकता है।<ref name="m"/><ref name="vtl"/> | ||
एक आंशिक क्रम का तुलनीयता ग्राफ प्रत्येक तत्व के लिए एक शीर्ष के साथ [[अप्रत्यक्ष ग्राफ]] है और अलग-अलग तत्वों की प्रत्येक जोड़ी के लिए एक अप्रत्यक्ष किनारा है। {{mvar|x}}, {{mvar|y}} किसी के साथ {{math|''x'' ≤ ''y''}} या {{math|''y'' ≤ ''x''}}. अर्थात्, यह प्रत्येक किनारे के [[अभिविन्यास (ग्राफ सिद्धांत)]] को भूलकर एक न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ से बनता है। श्रृंखला-समानांतर आंशिक क्रम का तुलनीयता ग्राफ एक कॉग्राफ है: आंशिक क्रम की श्रृंखला और समानांतर | एक आंशिक क्रम का तुलनीयता ग्राफ प्रत्येक तत्व के लिए एक शीर्ष के साथ [[अप्रत्यक्ष ग्राफ]] है और अलग-अलग तत्वों की प्रत्येक जोड़ी के लिए एक अप्रत्यक्ष किनारा है। {{mvar|x}}, {{mvar|y}} किसी के साथ {{math|''x'' ≤ ''y''}} या {{math|''y'' ≤ ''x''}}. अर्थात्, यह प्रत्येक किनारे के [[अभिविन्यास (ग्राफ सिद्धांत)]] को भूलकर एक न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ से बनता है। श्रृंखला-समानांतर आंशिक क्रम का तुलनीयता ग्राफ एक कॉग्राफ है: आंशिक क्रम की श्रृंखला और समानांतर संरचना संचालन तुलनात्मकता ग्राफ पर संचालन को जन्म देते हैं जो दो सबग्राफ के असंयुक्त संघ का निर्माण करते हैं या जो सभी संभावित किनारों से दो सबग्राफ को जोड़ते हैं; ये दो ऑपरेशन मूल ऑपरेशन हैं जिनसे कोग्राफ परिभाषित किए गए हैं। इसके विपरीत, प्रत्येक कोग्राफ एक श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है। यदि एक आंशिक क्रम में इसकी तुलनात्मकता ग्राफ के रूप में एक कोग्राफ है, तो यह एक श्रृंखला-समानांतर आंशिक क्रम होना चाहिए, क्योंकि हर दूसरे प्रकार के आंशिक क्रम में एक एन उप-क्रम होता है जो इसकी तुलनात्मकता ग्राफ में एक प्रेरित चार-वर्टेक्स पथ के अनुरूप होगा, और कोग्राफ में ऐसे रास्ते प्रतिबंधित हैं।<ref name="m"/><ref name="j"/> | ||
== कम्प्यूटेशनल जटिलता == | == कम्प्यूटेशनल जटिलता == | ||
श्रृंखला-समानांतर आंशिक | श्रृंखला-समानांतर आंशिक क्रमों के निषिद्ध उप-क्रम लक्षण वर्णन को एक एल्गोरिथ्म के आधार के रूप में इस्तेमाल किया जा सकता है जो परीक्षण करता है कि क्या एक दिया गया द्विआधारी संबंध एक श्रृंखला-समानांतर आंशिक क्रम है, जो संबंधित जोड़े की संख्या में रैखिक है।<ref name="m"/><ref name="vtl"/>वैकल्पिक रूप से, यदि एक आंशिक क्रम को एक निर्देशित एसाइक्लिक ग्राफ के रीचैबिलिटी क्रम के रूप में वर्णित किया गया है, तो यह परीक्षण करना संभव है कि क्या यह एक श्रृंखला-समानांतर आंशिक क्रम है, और यदि ऐसा है, तो इसके सकर्मक बंद होने की गणना करें, समय में वर्टिकल की संख्या के अनुपात में और सकर्मक बंद होने में किनारों; यह खुला रहता है कि क्या श्रृंखला-समानांतर पुन: योग्यता क्रमों को पहचानने का समय इनपुट ग्राफ के आकार में रैखिक होने के लिए सुधारा जा सकता है।<ref>{{citation | ||
| last1 = Ma | first1 = Tze-Heng | | last1 = Ma | first1 = Tze-Heng | ||
| last2 = Spinrad | first2 = Jeremy | | last2 = Spinrad | first2 = Jeremy | ||
| Line 103: | Line 113: | ||
| year = 1991| s2cid = 120935610 | | year = 1991| s2cid = 120935610 | ||
}}.</ref> | }}.</ref> | ||
यदि एक श्रृंखला-समानांतर आंशिक क्रम को एक [[अभिव्यक्ति वृक्ष]] के रूप में दर्शाया जाता है जो श्रृंखला और समानांतर | यदि एक श्रृंखला-समानांतर आंशिक क्रम को एक [[अभिव्यक्ति वृक्ष]] के रूप में दर्शाया जाता है जो श्रृंखला और समानांतर संरचना संचालन का वर्णन करता है, तो आंशिक क्रम के तत्वों को अभिव्यक्ति वृक्ष की पत्तियों द्वारा दर्शाया जा सकता है। किसी भी दो तत्वों के बीच तुलना संबंधित दो पत्तियों के [[सबसे कम सामान्य पूर्वज]] की खोज करके एल्गोरिथम द्वारा की जा सकती है; यदि वह पूर्वज एक समानांतर संरचना है, तो दो तत्व अतुलनीय हैं, और अन्यथा श्रृंखला संरचना संचालन का क्रम तत्वों के क्रम को निर्धारित करता है। इस तरह, एक श्रृंखला-समानांतर आंशिक क्रम पर {{mvar|n}} तत्वों में प्रतिनिधित्व किया जा सकता है {{math|[[Big O notation|''O'']](''n'')}} स्पेस के साथ {{math|''O''(1)}} किसी भी तुलना मान को निर्धारित करने का समय।<ref name="m"/> | ||
दो श्रृंखला-समानांतर आंशिक | दो श्रृंखला-समानांतर आंशिक क्रमों के लिए परीक्षण करने के लिए यह एनपी-पूर्ण है {{mvar|P}} और {{mvar|Q}}, चाहे {{mvar|P}} में एक आइसोमोर्फिक प्रतिबंध सम्मिलित है {{mvar|Q}}.<ref name="vtl"/> | ||
चूंकि एक मनमानी आंशिक क्रम के रैखिक विस्तार की संख्या की गणना करने की समस्या तीव्र-पी-पूर्ण है|#पी-पूर्ण,<ref>{{citation | |||
| last1 = Brightwell | first1 = Graham R. | | last1 = Brightwell | first1 = Graham R. | ||
| last2 = Winkler | first2 = Peter | author2-link = Peter Winkler | | last2 = Winkler | first2 = Peter | author2-link = Peter Winkler | ||
| Line 117: | Line 127: | ||
| volume = 8 | | volume = 8 | ||
| year = 1991| s2cid = 119697949 | | year = 1991| s2cid = 119697949 | ||
}}.</ref> इसे श्रृंखला-समानांतर आंशिक | }}.</ref> इसे श्रृंखला-समानांतर आंशिक क्रमों के लिए बहुपद समय में हल किया जा सकता है। विशेष रूप से, यदि {{math|''L''(''P'')}} आंशिक क्रम के रैखिक विस्तार की संख्या को दर्शाता है {{mvar|P}}, तब {{math|1=''L''(''P''; ''Q'') = ''L''(''P'')''L''(''Q'')}} और | ||
:<math>L(P||Q)=\frac{(|P|+|Q|)!}{|P|!|Q|!} L(P)L(Q),</math> | :<math>L(P||Q)=\frac{(|P|+|Q|)!}{|P|!|Q|!} L(P)L(Q),</math> | ||
इसलिए दिए गए श्रृंखला-समानांतर क्रम के अपघटन वृक्ष के रूप में एक अभिव्यक्ति वृक्ष का उपयोग करके रैखिक विस्तार की संख्या की गणना की जा सकती है।<ref name="m"/> | इसलिए दिए गए श्रृंखला-समानांतर क्रम के अपघटन वृक्ष के रूप में एक अभिव्यक्ति वृक्ष का उपयोग करके रैखिक विस्तार की संख्या की गणना की जा सकती है।<ref name="m"/> | ||
| Line 123: | Line 133: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
{{harvtxt|Mannila|Meek|2000}} समय श्रृंखला डेटा में घटनाओं के अनुक्रम के लिए एक मॉडल के रूप में श्रृंखला-समानांतर आंशिक | {{harvtxt|Mannila|Meek|2000}} समय श्रृंखला डेटा में घटनाओं के अनुक्रम के लिए एक मॉडल के रूप में श्रृंखला-समानांतर आंशिक क्रम का उपयोग करें। वे इस प्रकार के मॉडल का अनुमान लगाने के लिए मशीन लर्निंग एल्गोरिदम का वर्णन करते हैं, और छात्र नामांकन डेटा और मॉडलिंग वेब ब्राउज़र उपयोग पैटर्न से पाठ्यक्रम की पूर्वापेक्षाओं का अनुमान लगाने में इसकी प्रभावशीलता प्रदर्शित करते हैं।<ref name="mm">{{citation | ||
| last1 = Mannila | first1 = Heikki | author1-link = Heikki Mannila | | last1 = Mannila | first1 = Heikki | author1-link = Heikki Mannila | ||
| last2 = Meek | first2 = Christopher | | last2 = Meek | first2 = Christopher | ||
| Line 133: | Line 143: | ||
}}.</ref> | }}.</ref> | ||
{{harvtxt|Amer|Chassot|Connolly|Diaz|1994}} तर्क देते हैं कि श्रृंखला-समानांतर आंशिक | {{harvtxt|Amer|Chassot|Connolly|Diaz|1994}} तर्क देते हैं कि श्रृंखला-समानांतर आंशिक क्रम मल्टीमीडिया प्रस्तुतियों की संचरण अनुक्रमण आवश्यकताओं के मॉडलिंग के लिए उपयुक्त हैं। वे मल्टीमीडिया ट्रांसमिशन एल्गोरिदम के विश्लेषण के आधार के रूप में श्रृंखला-समानांतर आंशिक क्रम के रैखिक एक्सटेंशन की संख्या की गणना करने के लिए सूत्र का उपयोग करते हैं।<ref name="accdc">{{citation | ||
| last1 = Amer | first1 = Paul D. | |||
| last2 = Chassot | first2 = Christophe | |||
| last3 = Connolly | first3 = Thomas J. | |||
| last4 = Diaz | first4 = Michel | |||
| last5 = Conrad | first5 = Phillip | |||
| doi = 10.1109/90.336326 | |||
| issue = 5 | |||
| journal = IEEE/ACM Transactions on Networking | |||
| pages = 440–456 | |||
| title = Partial-order transport service for multimedia and other applications | |||
| volume = 2 | |||
| year = 1994| s2cid = 1974607 | |||
}}.</ref> | |||
{{harvtxt|Choudhary|Narahari|Nicol|Simha|1994}} [[कंप्यूटर दृष्टि]] के लिए बड़े पैमाने पर डेटा प्रोसेसिंग के [[ डेटा प्रवाह ]] मॉडल में कार्य निर्भरताओं को मॉडल करने के लिए श्रृंखला-समानांतर आंशिक | {{harvtxt|Choudhary|Narahari|Nicol|Simha|1994}} [[कंप्यूटर दृष्टि]] के लिए बड़े पैमाने पर डेटा प्रोसेसिंग के [[ डेटा प्रवाह ]] मॉडल में कार्य निर्भरताओं को मॉडल करने के लिए श्रृंखला-समानांतर आंशिक क्रम का उपयोग करें। वे दिखाते हैं कि, इस समस्या के लिए श्रृंखला-समानांतर क्रमों का उपयोग करके, एक अनुकूलित शेड्यूल का कुशलतापूर्वक निर्माण करना संभव है जो सिस्टम के थ्रूपुट को अनुकूलित करने के लिए [[समानांतर कंप्यूटिंग]] सिस्टम के विभिन्न प्रोसेसरों को अलग-अलग कार्य प्रदान करता है।<ref name="cnns">{{citation | ||
| last1 = Choudhary | first1 = A. N. | | last1 = Choudhary | first1 = A. N. | ||
| last2 = Narahari | first2 = B. | | last2 = Narahari | first2 = B. | ||
| Line 162: | Line 172: | ||
| url = https://surface.syr.edu/eecs/33 | | url = https://surface.syr.edu/eecs/33 | ||
}}.</ref> | }}.</ref> | ||
श्रृंखला-समानांतर आंशिक | श्रृंखला-समानांतर आंशिक क्रमों की तुलना में कुछ अधिक सामान्य क्रमों का एक वर्ग PQ ट्री द्वारा प्रदान किया जाता है, डेटा संरचनाएं जो एल्गोरिदम में परीक्षण के लिए प्रयुक्त की गई हैं कि क्या एक ग्राफ़ [[प्लेनर ग्राफ]] है और [[अंतराल ग्राफ]]़ को पहचानता है।<ref>{{citation | ||
| last1 = Booth | first1 = Kellogg S. | | last1 = Booth | first1 = Kellogg S. | ||
| last2 = Lueker | first2 = George S. | | last2 = Lueker | first2 = George S. | ||
| Line 172: | Line 182: | ||
| volume = 13 | | volume = 13 | ||
| year = 1976| doi-access = free | | year = 1976| doi-access = free | ||
}}.</ref> एक पीक्यू पेड़ का एपी नोड अपने बच्चों के सभी संभावित | }}.</ref> एक पीक्यू पेड़ का एपी नोड अपने बच्चों के सभी संभावित क्रमिंग की अनुमति देता है, जैसे आंशिक क्रम की समांतर संरचना, जबकि एक क्यू नोड को आंशिक क्रम की श्रृंखला संरचना की तरह एक निश्चित रैखिक क्रम में बच्चों की आवश्यकता होती है। चूँकि, श्रृंखला-समानांतर आंशिक क्रमों के विपरीत, PQ पेड़ किसी भी Q नोड के रैखिक क्रम को उलटने की अनुमति देते हैं। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 02:27, 10 April 2023
क्रम-सैद्धांतिक गणित में, एक श्रृंखला-समानांतर आंशिक क्रम एक आंशिक रूप से क्रमबद्ध समुच्चय है, जो दो सरल संरचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक क्रमों से निर्मित होता है।[1][2]
| क्रम-सैद्धांतिक गणित में, एक श्रृंखला-समानांतर आंशिक क्रम एक आंशिक रूप से क्रमबद्ध समुच्चय है जो दो सरल संरचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक क्रमों से निर्मित होता है। श्रृंखला-समानांतर आंशिक क्रमों को N-मुक्त परिमित आंशिक क्रमों के रूप में वर्णित किया जा सकता है; उनके पास क्रम आयाम अधिकतम दो हैं।[1][3] वे अशक्त क्रम और निर्देशित ट्री और निर्देशित श्रृंखला-समानांतर रेखांकन में पुन: योग्यता संबंध सम्मिलित हैं। इनमें (ग्राफ़ थ्योरी) और निर्देशित श्रृंखला-समानांतर ग्राफ़ में अशक्त क्रम और गम्यता संबंध सम्मिलित हैं।[2][3] श्रृंखला-समानांतर आंशिक क्रमों की तुलनात्मकता रेखांकन कोग्राफ हैं।[2][4]
जॉब शॉप शेड्यूलिंग,[5] समय श्रृंखला डेटा में इवेंट अनुक्रमण की मशीन लर्निंग,[6] मल्टीमीडिया डेटा के प्रसारण अनुक्रमण,[7] और डेटाफ्लो प्रोग्रामिंग में थ्रूपुट अधिकतमकरण में श्रृंखला-समानांतर आंशिक क्रम प्रयुक्त किए गए हैं।[8]
में श्रृंखला-समानांतर आंशिक क्रम प्रयुक्त किए गए हैं, डेटा में घटना अनुक्रमण की , डेटा का प्रसारण अनुक्रमण, और डेटा प्रवाह प्रोग्रामिंग में थ्रूपुट अधिकतमकरण।
श्रृंखला-समानांतर आंशिक क्रमों को मल्टीट्रीज़ भी कहा जाता है;[4] चूँकि, यह नाम अस्पष्ट है: मल्टीट्रीज़ आंशिक क्रम को भी संदर्भित करता है, जिसमें कोई चार-तत्व हीरा उपक्रम नहीं होता है[9] और कई ट्री से बनी अन्य संरचनाओं के लिए नहीं होता है।
परिभाषा
दो आंशिक क्रमित समुच्चय P और Q पर विचार करें। P और Q की श्रृंखला संरचना, P; Q लिखी गई है,
विचार करना और , दो आंशिक रूप से क्रम किए गए समुच्चय। की श्रृंखला संरचना और , लिखा हुआ ,[7] P * Q,[2]या P ⧀ Q,[1] आंशिक रूप से क्रमबद्ध समुच्चय है जिसके अवयव P और Q के तत्वों के अलग संघ हैं। असंयुक्त संघ हैं और . में P; Q में, दो तत्व x और y जो दोनों P से संबंधित हैं या दोनों Q से संबंधित हैं, उनका समान क्रम संबंध है जो वे क्रमशः P या Q में करते हैं। हैं या दोनों के हैं का वही क्रम संबंध है जो वे करते हैं क्रमश। चूंकि, प्रत्येक जोड़ी x, y के लिए जहाँ x, P से संबंधित है और y, Q से संबंधित है, श्रृंखला संरचना में एक अतिरिक्त क्रम संबंध x ≤ y है। से संबंधित , एक अतिरिक्त क्रम संबंध है श्रृंखला संरचना में। श्रृंखला संरचना एक साहचर्य संक्रिया है: कोई P; Q; R लिख सकता है; तीन क्रमों की श्रृंखला संरचना के रूप में, अस्पष्टता के बिना कि कैसे उन्हें जोड़ी में संयोजित किया जाए, क्योंकि दोनों कोष्ठक (P; Q); R और P; (Q; R) उसी आंशिक क्रम का वर्णन करें। चूँकि, यह एक कम्यूटेटिव ऑपरेशन नहीं है, क्योंकि P और Q की भूमिकाओं को बदलने से एक अलग आंशिक क्रम उत्पन्न होगा जो P में एक तत्व और Q में एक के साथ जोड़े के क्रम संबंधों को उलट देता है।[1] और एक में .
P और Q की समानांतर संरचना, P || Q,[7] P + Q,[2] या P ⊕ Q इसी तरह परिभाषित किया गया है, लिखी गई है,[1] P में तत्वों और Q में तत्वों के असंयुक्त संघ से, तत्वों के जोड़े के साथ जो दोनों P या दोनों Q से संबंधित हैं, उसी क्रम में हैं जैसे वे क्रमशः P या Q में करते हैं। या दोनों को उसी क्रम में जैसा वे करते हैं या क्रमश। P || Q में, एक जोड़ी x, y जब भी अतुलनीय है, जब भी x P से संबंधित होता है और y Q से संबंधित होता है। संबंधित . समानांतर संरचना कम्यूटेटिव और साहचर्य दोनों होती है।[1]
श्रृंखला-समानांतर आंशिक क्रम का वर्ग आंशिक क्रम का समुच्चय है, जिसे इन दो परिचालनों का उपयोग करके एकल-तत्व आंशिक क्रम से बनाया जा सकता है। समतुल्य रूप से, यह आंशिक क्रमों का सबसे छोटा समुच्चय है, जिसमें एकल-तत्व आंशिक क्रम सम्मिलित हैं और श्रृंखला और समानांतर संरचना संचालन के अनुसार क्लोजर है।[1][2]
एक अशक्त क्रम संरचना संचालन के एक अनुक्रम से प्राप्त श्रृंखला समानांतर आंशिक क्रम है, जिसमें सभी समानांतर संरचनाएं पहले की जाती हैं, और फिर इन संरचनाओं के परिणाम केवल श्रृंखला संरचनाओं का उपयोग करके संयुक्त होते हैं।[2]
निषिद्ध उपक्रम लक्षण वर्णन
चार तत्वों a, b, c, और d के साथ आंशिक क्रम एन और बिल्कुल तीन आदेश संबंध a ≤ b ≥ c ≤ d एक फेंस या ज़िगज़ैग पोसेट का एक उदाहरण है; इसके हस्से आरेख में बड़े अक्षर N का आकार है। यह श्रृंखला-समानांतर नहीं है, क्योंकि इसे दो छोटे आंशिक क्रमों की श्रृंखला या समानांतर संरचना में विभाजित करने की कोई विधि नहीं है। एक आंशिक क्रम P को N-मुक्त कहा जाता है, यदि इसमें चार तत्वों का एक समुच्चय P उपस्थित नहीं है, जैसे कि उन तत्वों के लिए P का प्रतिबंध N के लिए क्रम-आइसोमॉर्फिक है। श्रृंखला-समानांतर आंशिक क्रम बिल्कुल गैर-रिक्त परिमित N-मुक्त आंशिक क्रम हैं।[1][2][3]
आंशिक क्रम N चार तत्वों के साथ , , , और और बिल्कुल तीन क्रम संबंध (गणित) या ज़िगज़ैग पॉसमुच्चय का एक उदाहरण है; इसके हस्से आरेख में बड़े अक्षर का आकार है। N-मुक्त यदि का प्रतिबंध उन तत्वों के लिए .
यह इससे तुरंत अनुसरण करता है (चूंकि यह सीधे भी सिद्ध किया जा सकता है) कि श्रृंखला-समानांतर आंशिक क्रम का कोई भी गैर-रिक्त प्रतिबंध स्वयं एक श्रृंखला-समानांतर आंशिक क्रम है।[1]
क्रम आयाम
आंशिक क्रम P का क्रम आयाम, P के एक रियलाइज़र का न्यूनतम आकार है, P के रैखिक विस्तार का एक समुच्चय, संपत्ति के साथ, जो P के प्रत्येक दो अलग-अलग तत्वों x और y के लिए, x ≤ y P में यदि और केवल यदि x की रिलीवर के प्रत्येक रैखिक विस्तार में y की तुलना में पहले की स्थिति है। , में यदि और केवल यदि की तुलना में पहले की स्थिति है रियालीजर के प्रत्येक रैखिक विस्तार में। श्रृंखला-समानांतर आंशिक क्रम में अधिकतम दो क्रम आयाम होते हैं। यदि P और Q के पास क्रमशः {L1, L2} और {L3, L4} रियलाइज़र हैं, तो {L1L3, L2L4} श्रृंखला संयोजन P; Q का एक बोध कराने वाला है, और {L1L3, L4L2} समानांतर संरचना P || Q का एक बोध कराने वाला है।[2][3] एक आंशिक क्रम श्रृंखला-समानांतर होती है, यदि और केवल यदि उसके पास एक बोधकर्ता है, जिसमें दो क्रमपरिवर्तनों में से एक पहचान है और दूसरा एक वियोज्य क्रमपरिवर्तन है।
यह ज्ञात है कि एक आंशिक क्रम P का क्रम आयाम दो है यदि और केवल यदि समान तत्वों पर कोई संयुग्मी क्रम Q उपस्थित है, इस संपत्ति के साथ कि कोई भी दो अलग-अलग तत्व x और y इन दो क्रमों में से किसी एक पर तुलनीय हैं। श्रृंखला समानांतर आंशिक क्रमों की स्थिति में, एक संयुग्मित क्रम जो स्वयं श्रृंखला समानांतर है, उसी क्रम में संरचना संचालन के अनुक्रम को उसी क्रम में प्राप्त किया जा सकता है, जो समान तत्वों पर P को परिभाषित करते हैं, लेकिन प्रत्येक समानांतर रचना के लिए P के अपघटन में और इसके विपरीत एक श्रृंखला संरचना का प्रदर्शन करते हैं। जो परिभाषित करते हैं समान तत्वों पर, लेकिन के अपघटन में प्रत्येक समांतर संरचना के लिए श्रृंखला संरचना का प्रदर्शन करना और इसके विपरीत। अधिक दृढ़ता से, चूंकि एक आंशिक क्रम में कई अलग-अलग संयुग्म हो सकते हैं, एक श्रृंखला समानांतर आंशिक क्रम के प्रत्येक संयुग्म को स्वयं श्रृंखला समानांतर होना चाहिए।[2]
ग्राफ सिद्धांत से संबंध
किसी भी आंशिक क्रम को एक निर्देशित विश्वकोश ग्राफ द्वारा दर्शाया जा सकता है (सामान्यतः एक से अधिक तरीकों से) जिसमें से एक रास्ता होता है x को y जब कभी भी x और y आंशिक क्रम के तत्व हैं x ≤ y. इस तरह से श्रृंखला-समानांतर आंशिक क्रमों का प्रतिनिधित्व करने वाले ग्राफ़ को वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है, और उनके सकर्मक कटौती (आंशिक क्रम के कवरिंग संबंधों के ग्राफ़) को न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है।[3] निर्देशित पेड़ और (दो-टर्मिनल) श्रृंखला समानांतर रेखांकन न्यूनतम वर्टेक्स श्रृंखला समानांतर रेखांकन के उदाहरण हैं; इसलिए, श्रृंखला समानांतर आंशिक क्रमों का उपयोग निर्देशित ट्री और श्रृंखला समानांतर रेखांकन में पुन: योग्यता संबंधों का प्रतिनिधित्व करने के लिए किया जा सकता है।[2][3]
एक आंशिक क्रम का तुलनीयता ग्राफ प्रत्येक तत्व के लिए एक शीर्ष के साथ अप्रत्यक्ष ग्राफ है और अलग-अलग तत्वों की प्रत्येक जोड़ी के लिए एक अप्रत्यक्ष किनारा है। x, y किसी के साथ x ≤ y या y ≤ x. अर्थात्, यह प्रत्येक किनारे के अभिविन्यास (ग्राफ सिद्धांत) को भूलकर एक न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ से बनता है। श्रृंखला-समानांतर आंशिक क्रम का तुलनीयता ग्राफ एक कॉग्राफ है: आंशिक क्रम की श्रृंखला और समानांतर संरचना संचालन तुलनात्मकता ग्राफ पर संचालन को जन्म देते हैं जो दो सबग्राफ के असंयुक्त संघ का निर्माण करते हैं या जो सभी संभावित किनारों से दो सबग्राफ को जोड़ते हैं; ये दो ऑपरेशन मूल ऑपरेशन हैं जिनसे कोग्राफ परिभाषित किए गए हैं। इसके विपरीत, प्रत्येक कोग्राफ एक श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है। यदि एक आंशिक क्रम में इसकी तुलनात्मकता ग्राफ के रूप में एक कोग्राफ है, तो यह एक श्रृंखला-समानांतर आंशिक क्रम होना चाहिए, क्योंकि हर दूसरे प्रकार के आंशिक क्रम में एक एन उप-क्रम होता है जो इसकी तुलनात्मकता ग्राफ में एक प्रेरित चार-वर्टेक्स पथ के अनुरूप होगा, और कोग्राफ में ऐसे रास्ते प्रतिबंधित हैं।[2][4]
कम्प्यूटेशनल जटिलता
श्रृंखला-समानांतर आंशिक क्रमों के निषिद्ध उप-क्रम लक्षण वर्णन को एक एल्गोरिथ्म के आधार के रूप में इस्तेमाल किया जा सकता है जो परीक्षण करता है कि क्या एक दिया गया द्विआधारी संबंध एक श्रृंखला-समानांतर आंशिक क्रम है, जो संबंधित जोड़े की संख्या में रैखिक है।[2][3]वैकल्पिक रूप से, यदि एक आंशिक क्रम को एक निर्देशित एसाइक्लिक ग्राफ के रीचैबिलिटी क्रम के रूप में वर्णित किया गया है, तो यह परीक्षण करना संभव है कि क्या यह एक श्रृंखला-समानांतर आंशिक क्रम है, और यदि ऐसा है, तो इसके सकर्मक बंद होने की गणना करें, समय में वर्टिकल की संख्या के अनुपात में और सकर्मक बंद होने में किनारों; यह खुला रहता है कि क्या श्रृंखला-समानांतर पुन: योग्यता क्रमों को पहचानने का समय इनपुट ग्राफ के आकार में रैखिक होने के लिए सुधारा जा सकता है।[10] यदि एक श्रृंखला-समानांतर आंशिक क्रम को एक अभिव्यक्ति वृक्ष के रूप में दर्शाया जाता है जो श्रृंखला और समानांतर संरचना संचालन का वर्णन करता है, तो आंशिक क्रम के तत्वों को अभिव्यक्ति वृक्ष की पत्तियों द्वारा दर्शाया जा सकता है। किसी भी दो तत्वों के बीच तुलना संबंधित दो पत्तियों के सबसे कम सामान्य पूर्वज की खोज करके एल्गोरिथम द्वारा की जा सकती है; यदि वह पूर्वज एक समानांतर संरचना है, तो दो तत्व अतुलनीय हैं, और अन्यथा श्रृंखला संरचना संचालन का क्रम तत्वों के क्रम को निर्धारित करता है। इस तरह, एक श्रृंखला-समानांतर आंशिक क्रम पर n तत्वों में प्रतिनिधित्व किया जा सकता है O(n) स्पेस के साथ O(1) किसी भी तुलना मान को निर्धारित करने का समय।[2]
दो श्रृंखला-समानांतर आंशिक क्रमों के लिए परीक्षण करने के लिए यह एनपी-पूर्ण है P और Q, चाहे P में एक आइसोमोर्फिक प्रतिबंध सम्मिलित है Q.[3]
चूंकि एक मनमानी आंशिक क्रम के रैखिक विस्तार की संख्या की गणना करने की समस्या तीव्र-पी-पूर्ण है|#पी-पूर्ण,[11] इसे श्रृंखला-समानांतर आंशिक क्रमों के लिए बहुपद समय में हल किया जा सकता है। विशेष रूप से, यदि L(P) आंशिक क्रम के रैखिक विस्तार की संख्या को दर्शाता है P, तब L(P; Q) = L(P)L(Q) और
इसलिए दिए गए श्रृंखला-समानांतर क्रम के अपघटन वृक्ष के रूप में एक अभिव्यक्ति वृक्ष का उपयोग करके रैखिक विस्तार की संख्या की गणना की जा सकती है।[2]
अनुप्रयोग
Mannila & Meek (2000) समय श्रृंखला डेटा में घटनाओं के अनुक्रम के लिए एक मॉडल के रूप में श्रृंखला-समानांतर आंशिक क्रम का उपयोग करें। वे इस प्रकार के मॉडल का अनुमान लगाने के लिए मशीन लर्निंग एल्गोरिदम का वर्णन करते हैं, और छात्र नामांकन डेटा और मॉडलिंग वेब ब्राउज़र उपयोग पैटर्न से पाठ्यक्रम की पूर्वापेक्षाओं का अनुमान लगाने में इसकी प्रभावशीलता प्रदर्शित करते हैं।[6]
Amer et al. (1994) तर्क देते हैं कि श्रृंखला-समानांतर आंशिक क्रम मल्टीमीडिया प्रस्तुतियों की संचरण अनुक्रमण आवश्यकताओं के मॉडलिंग के लिए उपयुक्त हैं। वे मल्टीमीडिया ट्रांसमिशन एल्गोरिदम के विश्लेषण के आधार के रूप में श्रृंखला-समानांतर आंशिक क्रम के रैखिक एक्सटेंशन की संख्या की गणना करने के लिए सूत्र का उपयोग करते हैं।[7]
Choudhary et al. (1994) कंप्यूटर दृष्टि के लिए बड़े पैमाने पर डेटा प्रोसेसिंग के डेटा प्रवाह मॉडल में कार्य निर्भरताओं को मॉडल करने के लिए श्रृंखला-समानांतर आंशिक क्रम का उपयोग करें। वे दिखाते हैं कि, इस समस्या के लिए श्रृंखला-समानांतर क्रमों का उपयोग करके, एक अनुकूलित शेड्यूल का कुशलतापूर्वक निर्माण करना संभव है जो सिस्टम के थ्रूपुट को अनुकूलित करने के लिए समानांतर कंप्यूटिंग सिस्टम के विभिन्न प्रोसेसरों को अलग-अलग कार्य प्रदान करता है।[8] श्रृंखला-समानांतर आंशिक क्रमों की तुलना में कुछ अधिक सामान्य क्रमों का एक वर्ग PQ ट्री द्वारा प्रदान किया जाता है, डेटा संरचनाएं जो एल्गोरिदम में परीक्षण के लिए प्रयुक्त की गई हैं कि क्या एक ग्राफ़ प्लेनर ग्राफ है और अंतराल ग्राफ़ को पहचानता है।[12] एक पीक्यू पेड़ का एपी नोड अपने बच्चों के सभी संभावित क्रमिंग की अनुमति देता है, जैसे आंशिक क्रम की समांतर संरचना, जबकि एक क्यू नोड को आंशिक क्रम की श्रृंखला संरचना की तरह एक निश्चित रैखिक क्रम में बच्चों की आवश्यकता होती है। चूँकि, श्रृंखला-समानांतर आंशिक क्रमों के विपरीत, PQ पेड़ किसी भी Q नोड के रैखिक क्रम को उलटने की अनुमति देते हैं।
यह भी देखें
- श्रृंखला और समांतर सर्किट
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Bechet, Denis; De Groote, Philippe; Retoré, Christian (1997), "A complete axiomatisation for the inclusion of series-parallel partial orders", Rewriting Techniques and Applications, Lecture Notes in Computer Science, vol. 1232, Springer-Verlag, pp. 230–240, doi:10.1007/3-540-62950-5_74.
- ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 2.11 2.12 2.13 2.14 Möhring, Rolf H. (1989), "Computationally tractable classes of ordered sets", in Rival, Ivan (ed.), Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canada, May 31-June 13, 1987, NATO Science Series C, vol. 255, Springer-Verlag, pp. 105–194, ISBN 978-0-7923-0007-6.
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982), "The recognition of series parallel digraphs", SIAM Journal on Computing, 11 (2): 298–313, doi:10.1137/0211023.
- ↑ 4.0 4.1 4.2 Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
- ↑ Lawler, Eugene L. (1978), "Sequencing jobs to minimize total weighted completion time subject to precedence constraints", Annals of Discrete Mathematics, 2: 75–90, doi:10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, MR 0495156.
- ↑ 6.0 6.1 Mannila, Heikki; Meek, Christopher (2000), "Global partial orders from sequential data", Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000), pp. 161–168, doi:10.1145/347090.347122, S2CID 14735932.
- ↑ 7.0 7.1 7.2 7.3 Amer, Paul D.; Chassot, Christophe; Connolly, Thomas J.; Diaz, Michel; Conrad, Phillip (1994), "Partial-order transport service for multimedia and other applications", IEEE/ACM Transactions on Networking, 2 (5): 440–456, doi:10.1109/90.336326, S2CID 1974607.
- ↑ 8.0 8.1 Choudhary, A. N.; Narahari, B.; Nicol, D. M.; Simha, R. (1994), "Optimal processor assignment for a class of pipelined computations", IEEE Transactions on Parallel and Distributed Systems, 5 (4): 439–445, doi:10.1109/71.273050, S2CID 5588390.
- ↑ Furnas, George W.; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94), pp. 330–336, doi:10.1145/191666.191778, S2CID 18710118.
- ↑ Ma, Tze-Heng; Spinrad, Jeremy (1991), "Transitive closure for restricted classes of partial orders", Order, 8 (2): 175–183, doi:10.1007/BF00383402, S2CID 120935610.
- ↑ Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444, S2CID 119697949.
- ↑ Booth, Kellogg S.; Lueker, George S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", Journal of Computer and System Sciences, 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1.
