ग्राफ रिडक्सन: Difference between revisions
(Created page with "{{About|the computer science term|the graph theory use|transitive reduction}} कंप्यूटर विज्ञान में, ग्राफ कटौती ग...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{About| | {{About|कंप्यूटर विज्ञान शब्द|ग्राफ़ सिद्धांत का उपयोग|सकर्मक कमी}} | ||
[[कंप्यूटर विज्ञान]] में, ग्राफ | [[कंप्यूटर विज्ञान]] में, '''ग्राफ रिडक्सन''' गैर-सख्त मूल्यांकन का एक कुशल वर्जन प्रयुक्त करती है, एक [[मूल्यांकन रणनीति]] जहां किसी फ़ंक्शन के तर्कों का तुरंत मूल्यांकन नहीं किया जाता है। गैर-सख्त मूल्यांकन के इस रूप को [[आलसी मूल्यांकन|लेजी मूल्यांकन]] के रूप में भी जाना जाता है और इस प्रकार इसका उपयोग [[कार्यात्मक प्रोग्रामिंग|फंक्शनल प्रोग्रामिंग]] में किया जाता है। इस तकनीक को पहली बार 1971 में [[क्रिस वड्सवर्थ]] द्वारा विकसित किया गया था। | ||
== प्रेरणा == | == प्रेरणा == | ||
| Line 15: | Line 15: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
उपरोक्त | उपरोक्त रिडक्सन अनुक्रम एक रणनीति को नियोजित करता है जिसे बाह्यतम ट्री रिडक्सन के रूप में जाना जाता है। उसी अभिव्यक्ति का मूल्यांकन अंतरतम ट्री रिडक्सन का उपयोग करके किया जा सकता है, जिससे रिडक्सन अनुक्रम प्राप्त होता है: | ||
:<math> | :<math> | ||
| Line 27: | Line 27: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
ध्यान दें कि | ध्यान दें कि रिडक्सन का क्रम कोष्ठक जोड़ने से स्पष्ट हो जाता है। इस अभिव्यक्ति का मूल्यांकन केवल दाएँ से बाएँ भी किया जा सकता था, क्योंकि जोड़ एक साहचर्य संक्रिया है। | ||
ट्री डेटा संरचना के रूप में प्रस्तुत, उपरोक्त अभिव्यक्ति इस तरह दिखती है: | ट्री डेटा संरचना के रूप में प्रस्तुत, उपरोक्त अभिव्यक्ति इस तरह दिखती है: | ||
[[Image:Expression Tree.svg|300px]]यहीं से | [[Image:Expression Tree.svg|300px]] | ||
यहीं से ट्री न्यूनीकरण शब्द आया है। जब इसे एक पेड़ के रूप में दर्शाया जाता है, इस प्रकार जिससे हम आंतरिक रिडक्सन को नीचे से ऊपर की ओर कार्य करने के रूप में सोच सकते हैं, जबकि बाहरी रिडक्सन ऊपर से नीचे की ओर कार्य करती है। | |||
अभिव्यक्ति को एक निर्देशित चक्रीय ग्राफ के रूप में भी दर्शाया जा सकता है, जिससे उप-अभिव्यक्तियों को साझा किया जा सकता है: | अभिव्यक्ति को एक निर्देशित चक्रीय ग्राफ के रूप में भी दर्शाया जा सकता है, जिससे उप-अभिव्यक्तियों को साझा किया जा सकता है: | ||
[[Image:Expression Graph.svg|300px]]जहाँ तक | [[Image:Expression Graph.svg|300px]] | ||
जहाँ तक ट्री की बात है, सबसे बाहरी और सबसे अन्दर रिडक्सन ग्राफ़ पर भी प्रयुक्त होती है। इसलिए हमारे पास ग्राफ़ में रिडक्सन है। | |||
अब सबसे बाहरी ग्राफ़ रिडक्सन के साथ मूल्यांकन निम्नानुसार आगे बढ़ सकता है: | |||
[[Image:Expression Graph Reduction.svg|200px]] | |||
ध्यान दें कि मूल्यांकन के लिए अब केवल चार चरणों की आवश्यकता है। इस प्रकार सबसे बाहरी ग्राफ़ में रिडक्सन को लेजी मूल्यांकन के रूप में जाना जाता है और सबसे अन्दर ग्राफ़ में रिडक्सन को [[उत्सुक मूल्यांकन|एगर मूल्यांकन]] के रूप में जाना जाता है। | |||
== | == कॉम्बिनेटर ग्राफ़ रिडक्शन == | ||
कॉम्बिनेटर ग्राफ रिडक्शन | कॉम्बिनेटर ग्राफ रिडक्शन फंक्शनल प्रोग्रामिंग लैंग्वेज के लिए एक मौलिक कार्यान्वयन तकनीक है, इस प्रकार जिसमें एक प्रोग्राम को कॉम्बिनेटर प्रतिनिधित्व में परिवर्तित किया जाता है जिसे कंप्यूटर मेमोरी में एक [[निर्देशित ग्राफ]] [[डेटा संरचना]] में मैप किया जाता है, और प्रोग्राम निष्पादन में इस ग्राफ के कुछ भागो को फिर से लिखना (इसे कम करना) सम्मिलित होता है जिससे उपयोगी परिणामों की ओर बढ़ सकते है। | ||
== इतिहास == | == इतिहास == | ||
ग्राफ | ग्राफ रिडक्सन की अवधारणा जो मूल्यांकन किए गए मूल्यों को साझा करने की अनुमति देती है, सबसे पहले क्रिस वड्सवर्थ ने अपने 1971 पीएच.डी. में विकसित की थी। निबंध <ref>{{cite journal | last = Hudak | first = Paul | title = कार्यात्मक प्रोग्रामिंग भाषाओं की संकल्पना, विकास और अनुप्रयोग| journal = [[Association for Computing Machinery|ACM]] Computing Surveys | volume = 21 | issue = 3 | pages = 359–411 |date=September 1989 | citeseerx = 10.1.1.83.6505 | doi =10.1145/72551.72554 }}</ref> इस शोध प्रबंध को पीटर हेंडरसन और जेम्स एच. मॉरिस जूनियर ने 1976 के पेपर, "एक लेजी मूल्यांकनकर्ता" में उद्धृत किया था।<ref>[http://portal.acm.org/citation.cfm?id=811543 A lazy evaluator]</ref> जिसने लेजी मूल्यांकन की धारणा प्रस्तुत की थी। इस प्रकार 1976 में [[डेविड टर्नर (कंप्यूटर वैज्ञानिक)]] ने कॉम्बिनेटर का उपयोग करके [[एसएएसएल प्रोग्रामिंग भाषा|एसएएसएल प्रोग्रामिंग लैंग्वेज]] में लेजी मूल्यांकन को सम्मिलित किया था।<ref>{{cite conference |last1=Hudak |first1=Paul |last2=Hughes|first2=John|last3=Peyton Jones|first3=Simon|last4=Wadler|first4=Philip |title=A History of Haskell: Being Lazy with Class|url =http://haskell.org/haskellwiki/History_of_Haskell |book-title=History of Programming Languages Conference 2007 }}</ref> | ||
एसएएसएल एक प्रारंभिक | |||
एसएएसएल एक प्रारंभिक फंक्शनल प्रोग्रामिंग लैंग्वेज थी जिसे पहली बार 1972 में टर्नर द्वारा विकसित किया गया था। | |||
==यह भी देखें== | ==यह भी देखें== | ||
*[[ ग्राफ कम करने वाली मशीन ]] | *[[ ग्राफ कम करने वाली मशीन | ग्राफ रिडक्सन मशीन]] | ||
* | *एसईसीडी मशीन | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Revision as of 10:21, 5 August 2023
कंप्यूटर विज्ञान में, ग्राफ रिडक्सन गैर-सख्त मूल्यांकन का एक कुशल वर्जन प्रयुक्त करती है, एक मूल्यांकन रणनीति जहां किसी फ़ंक्शन के तर्कों का तुरंत मूल्यांकन नहीं किया जाता है। गैर-सख्त मूल्यांकन के इस रूप को लेजी मूल्यांकन के रूप में भी जाना जाता है और इस प्रकार इसका उपयोग फंक्शनल प्रोग्रामिंग में किया जाता है। इस तकनीक को पहली बार 1971 में क्रिस वड्सवर्थ द्वारा विकसित किया गया था।
प्रेरणा
अंकगणितीय अभिव्यक्ति के मूल्यांकन का एक सरल उदाहरण इस प्रकार है:
उपरोक्त रिडक्सन अनुक्रम एक रणनीति को नियोजित करता है जिसे बाह्यतम ट्री रिडक्सन के रूप में जाना जाता है। उसी अभिव्यक्ति का मूल्यांकन अंतरतम ट्री रिडक्सन का उपयोग करके किया जा सकता है, जिससे रिडक्सन अनुक्रम प्राप्त होता है:
ध्यान दें कि रिडक्सन का क्रम कोष्ठक जोड़ने से स्पष्ट हो जाता है। इस अभिव्यक्ति का मूल्यांकन केवल दाएँ से बाएँ भी किया जा सकता था, क्योंकि जोड़ एक साहचर्य संक्रिया है।
ट्री डेटा संरचना के रूप में प्रस्तुत, उपरोक्त अभिव्यक्ति इस तरह दिखती है:
यहीं से ट्री न्यूनीकरण शब्द आया है। जब इसे एक पेड़ के रूप में दर्शाया जाता है, इस प्रकार जिससे हम आंतरिक रिडक्सन को नीचे से ऊपर की ओर कार्य करने के रूप में सोच सकते हैं, जबकि बाहरी रिडक्सन ऊपर से नीचे की ओर कार्य करती है।
अभिव्यक्ति को एक निर्देशित चक्रीय ग्राफ के रूप में भी दर्शाया जा सकता है, जिससे उप-अभिव्यक्तियों को साझा किया जा सकता है:
जहाँ तक ट्री की बात है, सबसे बाहरी और सबसे अन्दर रिडक्सन ग्राफ़ पर भी प्रयुक्त होती है। इसलिए हमारे पास ग्राफ़ में रिडक्सन है।
अब सबसे बाहरी ग्राफ़ रिडक्सन के साथ मूल्यांकन निम्नानुसार आगे बढ़ सकता है:
ध्यान दें कि मूल्यांकन के लिए अब केवल चार चरणों की आवश्यकता है। इस प्रकार सबसे बाहरी ग्राफ़ में रिडक्सन को लेजी मूल्यांकन के रूप में जाना जाता है और सबसे अन्दर ग्राफ़ में रिडक्सन को एगर मूल्यांकन के रूप में जाना जाता है।
कॉम्बिनेटर ग्राफ़ रिडक्शन
कॉम्बिनेटर ग्राफ रिडक्शन फंक्शनल प्रोग्रामिंग लैंग्वेज के लिए एक मौलिक कार्यान्वयन तकनीक है, इस प्रकार जिसमें एक प्रोग्राम को कॉम्बिनेटर प्रतिनिधित्व में परिवर्तित किया जाता है जिसे कंप्यूटर मेमोरी में एक निर्देशित ग्राफ डेटा संरचना में मैप किया जाता है, और प्रोग्राम निष्पादन में इस ग्राफ के कुछ भागो को फिर से लिखना (इसे कम करना) सम्मिलित होता है जिससे उपयोगी परिणामों की ओर बढ़ सकते है।
इतिहास
ग्राफ रिडक्सन की अवधारणा जो मूल्यांकन किए गए मूल्यों को साझा करने की अनुमति देती है, सबसे पहले क्रिस वड्सवर्थ ने अपने 1971 पीएच.डी. में विकसित की थी। निबंध [1] इस शोध प्रबंध को पीटर हेंडरसन और जेम्स एच. मॉरिस जूनियर ने 1976 के पेपर, "एक लेजी मूल्यांकनकर्ता" में उद्धृत किया था।[2] जिसने लेजी मूल्यांकन की धारणा प्रस्तुत की थी। इस प्रकार 1976 में डेविड टर्नर (कंप्यूटर वैज्ञानिक) ने कॉम्बिनेटर का उपयोग करके एसएएसएल प्रोग्रामिंग लैंग्वेज में लेजी मूल्यांकन को सम्मिलित किया था।[3]
एसएएसएल एक प्रारंभिक फंक्शनल प्रोग्रामिंग लैंग्वेज थी जिसे पहली बार 1972 में टर्नर द्वारा विकसित किया गया था।
यह भी देखें
- ग्राफ रिडक्सन मशीन
- एसईसीडी मशीन
टिप्पणियाँ
- ↑ Hudak, Paul (September 1989). "कार्यात्मक प्रोग्रामिंग भाषाओं की संकल्पना, विकास और अनुप्रयोग". ACM Computing Surveys. 21 (3): 359–411. CiteSeerX 10.1.1.83.6505. doi:10.1145/72551.72554.
- ↑ A lazy evaluator
- ↑ Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. "A History of Haskell: Being Lazy with Class". History of Programming Languages Conference 2007.
संदर्भ
- Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.
अग्रिम पठन
- Peyton Jones, Simon L. (1987). The Implementation of Functional Programming Languages. Prentice Hall. ISBN 013453333X. LCCN 86020535. Retrieved 2022-04-15.
