आश्रितता ग्राफ: Difference between revisions

Latest revision as of 10:32, 18 July 2023

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

परिभाषा

वस्तुओं के एक समुच्चय को देखते हुए S और एक सकर्मक संबंध $R\subseteq S\times S$ $(a,b)\in R$ के साथ एक आश्रितता मॉडलिंग "a, b पर आश्रित है" (a से पहले b का मूल्यांकन करने की आवश्यकता है), आश्रितता ग्राफ एक ग्राफ $G=(S,T)$ है जिसमें $T\subseteq R$ R का सकर्मक समानयन है|

उदाहरण के लिए, एक साधारण परिकलित्र को कल्पना करते हैं। यह परिकलित्र चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। "A = B+C; B = 5+D; C=4; D=2;" जैसे कई समीकरण दिए गए हैं, तो $S=\{A,B,C,D\}$ और $R=\{(A,B),(A,C),(B,D)\}$ | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: A, B और C पर आश्रित है, क्योंकि आप दो चरों को जोड़ सकते हैं यदि और केवल तभी जब आप दोनों चरों के मान जानते हों। इस प्रकार, A को परिकलित करने से पहले B को परिकलित करना होता है। हालाँकि, C और D के मान शीघ्र ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।

असंभव मूल्यांकन को पहचानना

आश्रितता ग्राफ में, आश्रितता का चक्र (जिसे वत्तीय आश्रितता भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन अनुक्रम उपस्थित नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई वत्तीय आश्रितता नहीं है, तो यह एक दिष्ट चक्रीय ग्राफ बनाता है, और सांस्थितिक शाटन द्वारा एक मूल्यांकन अनुक्रम प्राप्त किया जा सकता है। अधिकांश सांस्थितिक शाटन एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित प्रबंधन प्रदान करने के लिए सांस्थितिक शाटन से अलग चक्र का पता लगाना वांछनीय हो सकता है।

पहले से साधारण परिकलित्र को कल्पना करते हैं। समीकरण पद्धति "A=B; B=D+C; C=D+A; D=12;" इसमें A, B और C द्वारा गठित एक वत्तीय आश्रितता सम्मिलित है, क्योंकि B का मूल्यांकन A से पहले किया जाना चाहिए, C का मूल्यांकन B से पहले किया जाना चाहिए, और A का मूल्यांकन C से पहले किया जाना चाहिए |

मूल्यांकन अनुक्रम व्युत्पत्ति

एक सही मूल्यांकन अनुक्रम उन वस्तुओं का संख्यांकन $n:S\rightarrow \mathbb {N}$ है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: $n(a)<n(b)\Rightarrow (a,b)\notin R$ $a,b\in S$ के साथ है। इसका अर्थ है, यदि संख्यांकन दो अवयवों $a$ और $b$ को क्रमबद्ध करता है ताकि $a$ का मूल्यांकन $b$ से पहले किया जाएगा, तो $a$ को $b$ पर आश्रित नहीं होना चाहिए।

एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक सांस्थितिक अनुक्रम है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, और एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है।

ऊपर दिए गए साधारण परिकलित्र की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति "A = B+C; B = 5+D; C=4; D=2;" को देखते हुए, एक सही मूल्यांकन अनुक्रम (D, C, B, A) होता है। हालाँकि, (C, D, B, A) भी एक सही मूल्यांकन अनुक्रम है।

एकाभ संरचना

एक अचक्रीय आश्रितता ग्राफ एक अनुरेख एकाभ के अनुरेख से इस प्रकार संगत है:^[1]^: 12

एक फलन $\phi :S\to \Sigma$ प्रत्येक शीर्ष को वर्णाक्षर $\Sigma$ के एक प्रतीक के साथ लेबल करता है
कोई किनारा $a\to b$ या $b\to a$ है यदि और केवल यदि $(\phi (a),\phi (b))$ आश्रितता संबंध $D$ में है|
दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे संगत होते है।

फिर एक सही मूल्यांकन अनुक्रम द्वारा क्रमित शीर्ष लेबल वाली श्रृंखला एक अनुरेख की एक श्रृंखला के संगत है।

मोनोइडल प्रचालन $(S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})$ दो ग्राफों के शीर्ष समुच्चयों के असंयुक्त संयोग $S_{12}=S_{1}\sqcup S_{2}$ को लेता है, प्रत्येक ग्राफ़ में उपस्थित किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता (ड्रॉ) है जहां आश्रितता संबंध अनुमति देता है,^[1]^: 14

R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}

तत्समक (सर्वसमिका) रिक्त ग्राफ है|

उदाहरण

आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है:

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

आश्रितता ग्राफ़ इसका एक अभिमुखता (आस्पेक्ट) है:

विनिर्माण यंत्र के प्रकार: अनिर्मित सामग्रियों को कई आश्रित चरणों के माध्यम से गुणनफलों में प्रक्रमित किया जाता है।
जॉब शॉप नियोजन: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह है।

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). निशानों की किताब. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.
↑ Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.
↑ Keval Vora; Rajiv Gupta; Guoqing Xu (2017). "KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations". In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17). pp. 237–251. doi:10.1145/3093337.3037748.
↑ Gilbert, Ron. "पहेली निर्भरता चार्ट". Grumpy Gamer (in English). Retrieved 11 January 2020.

Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)

[IntroToTraceTheory-1] 1.0 ^1.1 Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). निशानों की किताब. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.

[2] Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.

[3] Keval Vora; Rajiv Gupta; Guoqing Xu (2017). "KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations". In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17). pp. 237–251. doi:10.1145/3093337.3037748.

[4] Gilbert, Ron. "पहेली निर्भरता चार्ट". Grumpy Gamer (in English). Retrieved 11 January 2020.

[1]

[2]

[3]

[4]

@@ Line 4: / Line 4: @@
 == परिभाषा ==
-[[File:Dependencygraph.png|right]]वस्तुओं का एक सेट दिया गया <math>S</math> और एक [[सकर्मक संबंध]] <math>R \subseteq S \times S</math> साथ <math>(a,b) \in R</math> आश्रितता का मॉडलिंग a, b पर निर्भर करता है (a को पहले b का मूल्यांकन करने की आवश्यकता है), आश्रितता ग्राफ एक ग्राफ है <math>G = (S, T)</math> साथ <math>T \subseteq R</math> आर की [[सकर्मक कमी]]
+[[File:Dependencygraph.png|right]]वस्तुओं के एक समुच्चय को देखते हुए ''S'' और एक [[सकर्मक संबंध]] <math>R \subseteq S \times S</math>  <math>(a,b) \in R</math> के साथ एक आश्रितता मॉडलिंग "''a'', ''b'' पर आश्रित है" (''a'' ''से पहले'' ''b'' ''का मूल्यांकन करने की आवश्यकता है''), आश्रितता ग्राफ एक ग्राफ <math>G = (S, T)</math> है जिसमें <math>T \subseteq R</math>  ''R'' का [[सकर्मक समानयन]] है|
-उदाहरण के लिए, एक साधारण कैलकुलेटर मान लें। यह कैलकुलेटर वेरिएबल्स के लिए स्थिर मानों को निर्दिष्ट करने और तीसरे वेरिएबल को ठीक दो वेरिएबल्स का योग निर्दिष्ट करने का समर्थन करता है। A = B+C जैसे कई समीकरण दिए गए हैं; बी = 5+डी; सी=4; डी=2; , तब <math>S=\{A,B,C,D\}</math> और <math>R=\{(A,B),(A,C),(B,D)\}</math>. आप इस संबंध को सीधे प्राप्त कर सकते हैं: A, B और C पर निर्भर करता है, क्योंकि आप दो चर जोड़ सकते हैं यदि और केवल तभी जब आप दोनों चर के मान जानते हों। इस प्रकार, A की गणना करने से पहले B की गणना की जानी चाहिए। हालाँकि, C और D के मान तुरंत ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।
+उदाहरण के लिए, एक साधारण परिकलित्र को कल्पना करते हैं। यह परिकलित्र चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। ''"A = B+C; B = 5+D; C=4; D=2;"'' जैसे कई समीकरण दिए गए हैं, तो <math>S=\{A,B,C,D\}</math> और <math>R=\{(A,B),(A,C),(B,D)\}</math> | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: ''A'', ''B'' और ''C'' पर आश्रित है, क्योंकि आप दो चरों को जोड़ सकते हैं [[यदि और केवल तभी]] जब आप दोनों चरों के मान जानते हों। इस प्रकार, ''A'' को परिकलित करने से पहले ''B'' को परिकलित करना होता है। हालाँकि, ''C'' और ''D'' के मान शीघ्र ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।
 == असंभव मूल्यांकन को पहचानना ==
-आश्रितता ग्राफ में, आश्रितता के चक्र (जिसे परिपत्र आश्रितता भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन आदेश मौजूद नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई परिपत्र आश्रितता नहीं है, तो यह एक दिष्ट चक्रीय ग्राफ बनाता है, और [[ टोपोलॉजिकल छँटाई ]] द्वारा एक मूल्यांकन क्रम पाया जा सकता है। अधिकांश टोपोलॉजिकल सॉर्टिंग एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित हैंडलिंग प्रदान करने के लिए टोपोलॉजिकल सॉर्टिंग से अलग चक्र का पता लगाना (ग्राफ सिद्धांत) करना वांछनीय हो सकता है।
+आश्रितता ग्राफ में, आश्रितता का चक्र (जिसे '''वत्तीय आश्रितता''' भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन अनुक्रम उपस्थित नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई वत्तीय आश्रितता नहीं है, तो यह एक [[दिष्ट चक्रीय ग्राफ]] बनाता है, और [[ टोपोलॉजिकल छँटाई |सांस्थितिक शाटन]] द्वारा एक मूल्यांकन अनुक्रम प्राप्त किया जा सकता है। अधिकांश सांस्थितिक शाटन एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित प्रबंधन प्रदान करने के लिए सांस्थितिक शाटन से अलग [[चक्र]] का पता लगाना वांछनीय हो सकता है।
-पहले से सरल कैलकुलेटर मान लें। समीकरण प्रणाली ''A''=''B''; ''बी''=''डी''+''सी''; ''सी''=''डी''+''ए''; ''डी''=12; ''ए'', ''बी'' और ''सी'' द्वारा बनाई गई एक गोलाकार आश्रितता शामिल है, क्योंकि ''बी'' का मूल्यांकन ''ए'' से पहले किया जाना चाहिए, ''सी'' का मूल्यांकन '' से पहले किया जाना चाहिए 'बी', और 'ए' का मूल्यांकन 'सी' से पहले किया जाना चाहिए।
+पहले से साधारण परिकलित्र को कल्पना करते हैं। समीकरण पद्धति ''"A=B; B=D+C; C=D+A; D=12'';" इसमें ''A, B'' और ''C'' द्वारा गठित एक [[वत्तीय आश्रितता]] सम्मिलित है, क्योंकि ''B'' का मूल्यांकन ''A'' से पहले किया जाना चाहिए, ''C'' का मूल्यांकन ''B'' से पहले किया जाना चाहिए'','' और ''A'' का मूल्यांकन ''C'' से पहले किया जाना चाहिए'' |''
-== मूल्यांकन आदेश निकालना ==
+== मूल्यांकन अनुक्रम व्युत्पत्ति ==
-एक सही मूल्यांकन क्रम एक क्रमांकन है <math> n : S \rightarrow \mathbb{N}</math> वे वस्तुएँ जो आश्रितता ग्राफ़ के नोड्स बनाती हैं ताकि निम्नलिखित समीकरण कायम रहे: <math> n(a) < n(b) \Rightarrow (a, b) \notin R </math> साथ <math> a, b \in S</math>. इसका मतलब है, यदि क्रमांकन दो तत्वों का आदेश देता है <math>a</math> और <math>b</math> ताकि <math>a</math> पहले मूल्यांकन किया जाएगा <math>b</math>, तब <math>a</math> पर निर्भर नहीं रहना चाहिए <math>b</math>.
+एक '''सही मूल्यांकन अनुक्रम''' उन वस्तुओं का संख्यांकन <math> n : S \rightarrow \mathbb{N}</math> है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: <math> n(a) < n(b) \Rightarrow (a, b) \notin R </math>  <math> a, b \in S</math>  के साथ है। इसका अर्थ है, यदि संख्यांकन दो अवयवों <math>a</math> और <math>b</math> को क्रमबद्ध करता है ताकि <math>a</math> का मूल्यांकन <math>b</math> से पहले किया जाएगा, तो <math>a</math> को <math>b</math> पर आश्रित नहीं होना चाहिए।
-एक से अधिक सही मूल्यांकन क्रम हो सकते हैं। वास्तव में, एक सही नंबरिंग एक टोपोलॉजिकल सॉर्टिंग है, और कोई भी टोपोलॉजिकल ऑर्डर एक सही नंबरिंग है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही टोपोलॉजिकल ऑर्डर प्राप्त करता है, एक सही मूल्यांकन क्रम प्राप्त करता है।
+एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक [[सांस्थितिक अनुक्रम]] है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, और एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है।
-ऊपर दिए गए सरल कैलकुलेटर को एक बार फिर से मान लें। समीकरण प्रणाली A = B+C दिया गया है; बी = 5+डी; सी=4; डी=2; , एक सही मूल्यांकन क्रम होगा (डी, सी, बी, ए)। हालाँकि, (सी, डी, बी, ए) भी एक सही मूल्यांकन क्रम है।
+ऊपर दिए गए साधारण परिकलित्र की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति ''"A = B+C; B = 5+D; C=4; D=2;"'' को देखते हुए, एक सही मूल्यांकन अनुक्रम (''D, C, B, A'') होता है। हालाँकि, (''C, D, B, A'') भी एक सही मूल्यांकन अनुक्रम है।
-== मोनोइड संरचना ==
+== एकाभ संरचना ==
-एक एसाइक्लिक आश्रितता ग्राफ एक [[ट्रेस मोनॉइड]] के ट्रेस से इस प्रकार मेल खाता है:<ref name=IntroToTraceTheory>{{cite book |last1=Mazurkiewicz |first1=Antoni |editor1-last=Rozenberg |editor1-first=G. |editor2-last=Diekert |editor2-first=V. |title=निशानों की किताब|date=1995 |publisher=World Scientific |location=Singapore |isbn=981-02-2058-8 |chapter-url=http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf |access-date=18 April 2021 |chapter=Introduction to Trace Theory}}</ref>{{rp|12}}
+एक अचक्रीय आश्रितता ग्राफ एक [[ट्रेस मोनॉइड|अनुरेख एकाभ]] के अनुरेख से इस प्रकार संगत है:<ref name=IntroToTraceTheory>{{cite book |last1=Mazurkiewicz |first1=Antoni |editor1-last=Rozenberg |editor1-first=G. |editor2-last=Diekert |editor2-first=V. |title=निशानों की किताब|date=1995 |publisher=World Scientific |location=Singapore |isbn=981-02-2058-8 |chapter-url=http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf |access-date=18 April 2021 |chapter=Introduction to Trace Theory}}</ref>{{rp|12}}
-* एक समारोह <math>\phi : S \to \Sigma</math> प्रत्येक शीर्ष को वर्णमाला के एक प्रतीक के साथ लेबल करें <math>\Sigma</math>
+* एक फलन <math>\phi : S \to \Sigma</math> प्रत्येक शीर्ष को वर्णाक्षर <math>\Sigma</math> के एक प्रतीक के साथ लेबल करता है
-*एक किनारा है <math>a \to b</math> या <math>b \to a</math> अगर और केवल अगर <math>(\phi(a),\phi(b))</math> [[निर्भरता संबंध|आश्रितता संबंध]] में है <math>D</math>.
+*कोई किनारा <math>a \to b</math> या <math>b \to a</math> है यदि और केवल यदि <math>(\phi(a),\phi(b))</math> [[निर्भरता संबंध|आश्रितता संबंध]] <math>D</math> में है|
-* दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे मेल खाते हों।
+* दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे संगत होते है।
-फिर एक सही मूल्यांकन क्रम द्वारा क्रमित शीर्ष लेबल वाली स्ट्रिंग एक ट्रेस की एक स्ट्रिंग से मेल खाती है।
+फिर एक सही मूल्यांकन अनुक्रम द्वारा क्रमित शीर्ष लेबल वाली श्रृंखला एक अनुरेख की एक श्रृंखला के संगत है।
-[[मोनोइड]]ल ऑपरेशन <math>(S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)</math> [[असंयुक्त संघ]] लेता है <math>S_{12}=S_1 \sqcup S_2</math> दो ग्राफ़ के शीर्ष सेटों में से, प्रत्येक ग्राफ़ में मौजूदा किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता है जहां आश्रितता संबंध अनुमति देता है,<ref name=IntroToTraceTheory/>{{rp|14}}
+[[मोनोइड|मोनोइडल]] प्रचालन <math>(S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)</math> दो ग्राफों के शीर्ष समुच्चयों के [[असंयुक्त संयोग]] <math>S_{12}=S_1 \sqcup S_2</math> को लेता है, प्रत्येक ग्राफ़ में उपस्थित किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता (ड्रॉ) है जहां आश्रितता संबंध अनुमति देता है,<ref name=IntroToTraceTheory/>{{rp|14}}
 :<math>R_{12} = R_1 \sqcup R_2 \sqcup \{(a,b)\mid a\in S_1 \land b\in S_2 \land (\phi(a),\phi(b))\in D\}</math>
-पहचान खाली ग्राफ है.
+तत्समक (सर्वसमिका) रिक्त ग्राफ है|
 ==उदाहरण==
 आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है:
-* स्वचालित सॉफ़्टवेयर [[ इंस्टालर ]]: वे सॉफ़्टवेयर पैकेज (इंस्टॉलेशन) की तलाश में ग्राफ़ पर चलते हैं जो आवश्यक हैं लेकिन अभी तक इंस्टॉल नहीं हुए हैं। आश्रितता पैकेजों के [[युग्मन (कंप्यूटर विज्ञान)]] द्वारा दी जाती है।
+* स्वचालित सॉफ़्टवेयर [[ इंस्टालर |अधिष्ठापक]]: वे ऐसे [[सॉफ़्टवेयर पैकगों]] की खोज में ग्राफ़ पर चलते हैं जिनकी आवश्यकता है लेकिन अभी तक अधिष्ठापित नहीं हुए हैं। आश्रितता पैकगों के [[युग्मन]] द्वारा दी जाती है।
-* सॉफ्टवेयर बिल्ड स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) ]], नोड.जेएस एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या अपाचे एंट। उन्हें यह जानने की जरूरत है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को फिर से संकलित करने की जरूरत है।
+* सॉफ्टवेयर निर्माण स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) |मेक]], [[नोड]] एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या [[अपाचे एंट]] सम्मिलित हैं। उन्हें यह जानने की आवश्यकता है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को पुन:अनुभाषित करने की आवश्यकता है।
-* [[संकलक]] प्रौद्योगिकी और [[औपचारिक भाषा]] कार्यान्वयन में:
+* [[संकलक|अनुभाषक]] तकनीक और [[औपचारिक भाषा]] कार्यान्वयन में:
-**निर्देश शेड्यूलिंग: आश्रितता ग्राफ़ की गणना [[असेंबली कोड]] या मध्यवर्ती निर्देशों के ऑपरेंड के लिए की जाती है और निर्देशों के लिए इष्टतम क्रम निर्धारित करने के लिए उपयोग किया जाता है।
+**[[अनुदेश नियोजन]]: आश्रितता ग्राफ़ का अभिकलन [[असेंबली कोड|कोड़ांतरण]] या मध्यवर्ती अनुदेशों के संचालन के लिए किया जाता है और अनुदेशों के लिए इष्टतम अनुक्रम निर्धारित करने के लिए उपयोग किया जाता है।
-** डेड कोड उन्मूलन: यदि कोई दुष्प्रभावित ऑपरेशन किसी वेरिएबल पर निर्भर नहीं करता है, तो इस वेरिएबल को डेड माना जाता है और इसे हटाया जा सकता है।
+** डेड कोड विलोपनांक: यदि कोई दुष्प्रभावित प्रचालन किसी चर पर आश्रित नहीं होता है, तो इस चर को डेड माना जाता है और इसे हटाया जा सकता है।
-* डायनामिक ग्राफ एनालिटिक्स: ग्राफबोल्ट<ref>{{cite conference |author1=Mugilan Mariappan |author2=Keval Vora |title=GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs |book-title=In European Conference on Computer Systems (EuroSys'19)|pages=25:1–25:16|year=2019|doi=10.1145/3302424.3303974 }}</ref> और किकस्टार्टर<ref>{{cite conference |author1=Keval Vora |author2=Rajiv Gupta |author3=Guoqing Xu |title=KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations |book-title=In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17)|pages=237–251|year=2017|doi=10.1145/3093337.3037748 |doi-access=free }}</ref> ग्राफ़ संरचना में परिवर्तन होने पर [[वृद्धिशील कंप्यूटिंग]] के लिए मूल्य आश्रितताएँ कैप्चर करें।
+* गतिक ग्राफ वैश्लेषिकी: ग्राफ़ संरचना में परिवर्तन होने पर ग्राफबोल्ट<ref>{{cite conference |author1=Mugilan Mariappan |author2=Keval Vora |title=GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs |book-title=In European Conference on Computer Systems (EuroSys'19)|pages=25:1–25:16|year=2019|doi=10.1145/3302424.3303974 }}</ref> और किकस्टार्टर<ref>{{cite conference |author1=Keval Vora |author2=Rajiv Gupta |author3=Guoqing Xu |title=KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations |book-title=In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17)|pages=237–251|year=2017|doi=10.1145/3093337.3037748 |doi-access=free }}</ref> [[वार्धिक अभिकलन]] के लिए मान आश्रितता को कैप्चर (प्रग्रहण) करते हैं।
-* [[स्प्रेडशीट]] कैलकुलेटर। उन्हें इस आलेख में उपयोग किए गए उदाहरण के समान एक सही गणना क्रम प्राप्त करने की आवश्यकता है।
+* [[स्प्रेडशीट]] परिकलित्र। उन्हें इस आलेख में उपयोग किए गए उदाहरण के समान एक सही परिकलन अनुक्रम प्राप्त करने की आवश्यकता है।
-* मॉडल में डेटा बदलने पर कौन से विज़ुअल तत्वों को अपडेट करना है, यह जानने के लिए [[XForms]] जैसे वेब फॉर्म मानक।
+* यदि निदर्श में डेटा बदलता है तो कौन से विज़ुअल अवयवों को अपडेट करना है, यह जानने के लिए वेब फॉर्म मानक जैसे कि [[XForms]] हैं।
-* वीडियो गेम, विशेष रूप से [[पहेली वीडियो गेम]] और [[ साहसिक खेल ]], जिन्हें अक्सर इन-गेम क्रियाओं के बीच निर्भर संबंधों के ग्राफ के रूप में डिज़ाइन किया जाता है।<ref>{{cite web |last1=Gilbert |first1=Ron |title=पहेली निर्भरता चार्ट|url=https://grumpygamer.com/puzzle_dependency_charts |website=Grumpy Gamer |access-date=11 January 2020 |language=en}}</ref>
+* वीडियो गेम, विशेष रूप से [[पहेली वीडियो गेम|पजल]] और [[ साहसिक खेल |एडवेंचर वीडियो गेम]], जिन्हें अधिकतर इन-गेम क्रियाओं के मध्य आश्रित संबंधों के ग्राफ के रूप में अभिकल्पित किया जाता है।<ref>{{cite web |last1=Gilbert |first1=Ron |title=पहेली निर्भरता चार्ट|url=https://grumpygamer.com/puzzle_dependency_charts |website=Grumpy Gamer |access-date=11 January 2020 |language=en}}</ref>
-आश्रितता ग्राफ़ इसका एक पहलू है:
+आश्रितता ग्राफ़ इसका एक अभिमुखता (आस्पेक्ट) है:
-* बाधाओं का सिद्धांत#पौधे के प्रकार: कच्चे माल को कई निर्भर चरणों के माध्यम से उत्पादों में संसाधित किया जाता है।
+* [[विनिर्माण यंत्र के प्रकार:]] अनिर्मित सामग्रियों को कई आश्रित चरणों के माध्यम से गुणनफलों में प्रक्रमित किया जाता है।
-* [[जॉब शॉप शेड्यूलिंग]]: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह।
+* [[जॉब शॉप शेड्यूलिंग|जॉब शॉप नियोजन]]: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह है।
 ==यह भी देखें==
 * [[कॉल ग्राफ़]]
-* [[टोपोलॉजिकल सॉर्ट]]
+* [[टोपोलॉजिकल सॉर्ट|सांस्थितिक शाटन]]
 * [[डेटा निर्भरता|डेटा आश्रितता]]
@@ Line 55: / Line 55: @@
 {{Reflist}}
 *Balmas, Francoise (2001) ''[http://www.ai.univ-paris8.fr/~fb/version-ps/pdep.ps Displaying dependence graphs: a hierarchical approach],'' [http://doi.ieeecomputersociety.org/10.1109/WCRE.2001.957830] wcre, p.&nbsp;261,  Eighth Working Conference on Reverse Engineering (WCRE'01)
-[[Category: निर्देशित रेखांकन]] [[Category: अनुप्रयोग-विशिष्ट ग्राफ़]]
+[[Category:All articles lacking in-text citations]]
+[[Category:Articles lacking in-text citations from June 2013]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 11/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:अनुप्रयोग-विशिष्ट ग्राफ़]]
+[[Category:निर्देशित रेखांकन]]

Anonymous

Search

आश्रितता ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:32, 18 July 2023

Contents

परिभाषा

असंभव मूल्यांकन को पहचानना

मूल्यांकन अनुक्रम व्युत्पत्ति

एकाभ संरचना

उदाहरण

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आश्रितता ग्राफ: Difference between revisions

Latest revision as of 10:32, 18 July 2023

परिभाषा

असंभव मूल्यांकन को पहचानना

मूल्यांकन अनुक्रम व्युत्पत्ति

एकाभ संरचना

उदाहरण

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories