संरचित प्रोग्राम प्रमेय: Difference between revisions

Revision as of 12:27, 6 August 2023

संरचित प्रोग्राम प्रमेय, जिसे बोहम-जैकोपिनी प्रमेय भी कहा जाता है,^[1]^[2] प्रोग्रामिंग भाषा सिद्धांत का एक परिणाम है। इसमें कहा गया है कि नियंत्रण-प्रवाह ग्राफ का वर्ग (ऐतिहासिक रूप से इस संदर्भ में प्रवाह संचित्र कहा जाता है) किसी भी गणना योग्य संक्रिया की गणना कर सकता है यदि यह उपप्रोग्राम को मात्र तीन विशिष्ट विधियों (नियंत्रण संरचनाओं) में जोड़ता है। ये इस प्रकार निम्नलिखित हैं-

एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम)
बूलियन डेटा प्रकार अभिव्यक्ति (चयन) के मूल्य के अनुसार दो उपप्रोग्रामों में से को निष्पादित करना
जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति)

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

प्रमेय संरचित प्रोग्रामिंग का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो के लिए जाओ से बचता है and exclusively uses subroutines, sequences, selection and iteration.

उत्पत्ति और प्रकार

प्रमेय को आमतौर पर श्रेय दिया जाता है^[3]^: 381 कोराडो बोहम और ग्यूसेप जैकोपिनी द्वारा 1966 के पेपर में।^[4] डेविड हरेल ने 1980 में लिखा था कि बोहम-जैकोपिनी पेपर को सार्वभौमिक लोकप्रियता मिली,^[3]^: 381 विशेष रूप से संरचित प्रोग्रामिंग के समर्थकों के साथ। हरेल ने यह भी कहा कि अपनी तकनीकी शैली के कारण [1966 बोहम-जैकोपिनी पेपर] को स्पष्ट रूप से विस्तार से पढ़ने की तुलना में अधिक बार उद्धृत किया जाता है।^[3]^: 381 और, 1980 तक प्रकाशित बड़ी संख्या में पत्रों की समीक्षा करने के बाद, हरेल ने तर्क दिया कि बोहम-जैकोपिनी प्रमाण की सामग्री को आमतौर पर गणितीय लोककथा के रूप में गलत तरीके से प्रस्तुत किया गया था जिसमें अनिवार्य रूप से सरल परिणाम शामिल है, परिणाम जो स्वयं जॉन वॉन न्यूमैन के पत्रों में आधुनिक कंप्यूटिंग सिद्धांत की शुरुआत से पता लगाया जा सकता है।^[5] और स्टीफन कोल क्लेन।^[3]^: 383

हरेल यह भी लिखते हैं कि अधिक सामान्य नाम हरलान मिल्स|एच.डी. द्वारा प्रस्तावित किया गया था। 1970 के दशक की शुरुआत में संरचना प्रमेय के रूप में मिल्स।^[3]^: 381

सिंगल-व्हाइल-लूप, प्रमेय का लोक संस्करण

प्रमेय का यह संस्करण सभी मूल प्रोग्राम के नियंत्रण प्रवाह को वैश्विक से बदल देता है while लूप जो मूल गैर-संरचित प्रोग्राम में सभी संभावित लेबल (फ़्लोचार्ट बॉक्स) पर जाने वाले प्रोग्राम गणक का अनुकरण करता है। हरेल ने कंप्यूटिंग की शुरुआत को चिह्नित करने वाले दो पत्रों में इस लोक प्रमेय की उत्पत्ति का पता लगाया। इनमें से वॉन न्यूमैन वास्तुकला का 1946 का विवरण है, जो बताता है कि प्रोग्राम काउंटर थोड़ी देर के लूप के संदर्भ में कैसे संचालित होता है। हारेल का कहना है कि संरचित प्रोग्रामिंग प्रमेय के लोक संस्करण द्वारा उपयोग किया जाने वाला एकल लूप मूल रूप से वॉन न्यूमैन कंप्यूटर पर फ्लोचार्ट के निष्पादन के लिए परिचालन शब्दार्थ प्रदान करता है।^[3]^: 383 और, यहां तक कि पुराना स्रोत कि हरेल ने प्रमेय के लोक संस्करण का पता लगाया, वह 1936 से स्टीफन क्लेन का क्लेन का टी विधेय है।^[3]^: 383

डोनाल्ड नुथ ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा छद्मकोड मिलता है, यह इंगित करते हुए कि मूल प्रोग्राम की संरचना इस परिवर्तन में पूरी तरह से खो गई है।^[6]^: 274 इसी तरह, ब्रूस इयान मिल्स ने इस दृष्टिकोण के बारे में लिखा है कि ब्लॉक संरचना की भावना शैली है, भाषा नहीं। वॉन न्यूमैन मशीन का अनुकरण करके, हम ब्लॉक-संरचित भाषा की सीमा के भीतर किसी भी स्पेगेटी कोड के व्यवहार का उत्पादन कर सकते हैं। यह इसे स्पेगेटी होने से नहीं रोकता है।^[7]

p := 1
while p > 0 do
    if p = 1 then
        perform step 1 from the flowchart
        p := resulting successor step number of step 1 from the flowchart (0 if no successor)
    end if
    if p = 2 then
        perform step 2 from the flowchart
        p := resulting successor step number of step 2 from the flowchart (0 if no successor)
    end if
    ...
    if p = n then
        perform step n from the flowchart
        p := resulting successor step number of step n from the flowchart (0 if no successor)
    end if
end while

बोहम और जैकोपिनी का प्रमाण

बोहम और जैकोपिनी के पेपर में प्रमाण प्रवाह चार्ट के संरचनात्मक प्रेरण द्वारा आगे बढ़ता है।^[3]^: 381 क्योंकि इसमें सबग्राफ समरूपता समस्या को नियोजित किया गया था, बोहम और जैकोपिनी का प्रमाण वास्तव में प्रोग्राम परिवर्तन एल्गोरिदम के रूप में व्यावहारिक नहीं था, और इस प्रकार इस दिशा में अतिरिक्त शोध के लिए द्वार खुल गया।^[8]

निहितार्थ और परिशोधन

बोहम-जैकोपिनी प्रमाण ने इस सवाल का समाधान नहीं किया कि सॉफ्टवेयर विकास के लिए संरचित प्रोग्रामिंग को अपनाया जाए या नहीं, आंशिक रूप से क्योंकि निर्माण में किसी प्रोग्राम को सुधारने की तुलना में उसे अस्पष्ट करने की अधिक संभावना थी। इसके विपरीत, इसने बहस की शुरुआत का संकेत दिया। एडवर्ड डिज्क्स्ट्रा का प्रसिद्ध पत्र, हानिकारक माना जाता है, 1968 में अनुसरण किया गया।^[9] कुछ शिक्षाविदों ने बोहम-जैकोपिनी परिणाम के लिए शुद्धतावादी दृष्टिकोण अपनाया और तर्क दिया कि निर्देश भी पसंद करते हैं break और return लूप के बीच से निकालना खराब अभ्यास है क्योंकि बोहम-जैकोपिनी प्रमाण में उनकी आवश्यकता नहीं है, और इस प्रकार उन्होंने वकालत की कि सभी लूप में ही निकास बिंदु होना चाहिए। यह शुद्धतावादी दृष्टिकोण पास्कल (प्रोग्रामिंग भाषा) (1968-1969 में डिज़ाइन किया गया) में सन्निहित है, जो 1990 के दशक के मध्य तक शिक्षा जगत में परिचयात्मक प्रोग्रामिंग कक्षाओं को पढ़ाने के लिए पसंदीदा उपकरण था।^[10] एडवर्ड योरडन कहते हैं कि 1970 के दशक में असंरचित प्रोग्रामों को स्वचालित माध्यमों से संरचित प्रोग्रामों में बदलने का दार्शनिक विरोध भी था, इस तर्क के आधार पर कि किसी को शुरू से ही संरचित प्रोग्रामिंग फैशन में सोचने की जरूरत थी। व्यावहारिक प्रतिवाद यह था कि ऐसे परिवर्तनों से मौजूदा प्रोग्रामों के बड़े समूह को लाभ हुआ।^[11] स्वचालित परिवर्तन के पहले प्रस्तावों में एडवर्ड एशक्रॉफ्ट और जोहार मन्ना का 1971 का पेपर था।^[12] बोहम-जैकोपिनी प्रमेय के प्रत्यक्ष अनुप्रयोग के परिणामस्वरूप संरचित चार्ट में अतिरिक्त स्थानीय चर पेश किए जा सकते हैं, और इसके परिणामस्वरूप कुछ कोड दोहराव भी हो सकता है।^[13] बाद वाले मुद्दे को इस संदर्भ में लूप एंड हाफ समस्या कहा जाता है।^[14] पास्कल इन दोनों समस्याओं से प्रभावित है और एरिक एस. रॉबर्ट्स द्वारा उद्धृत अनुभवजन्य अध्ययनों के अनुसार, छात्र प्रोग्रामरों को पास्कल में कई सरल समस्याओं के लिए सही समाधान तैयार करने में कठिनाई हुई, जिसमें सरणी में तत्व की खोज के लिए संक्रिया लिखना भी शामिल था। रॉबर्ट्स द्वारा उद्धृत हेनरी शापिरो के 1980 के अध्ययन में पाया गया कि मात्र पास्कल द्वारा प्रदान की गई नियंत्रण संरचनाओं का उपयोग करके, मात्र 20% विषयों द्वारा सही समाधान दिया गया था, जबकि किसी भी विषय ने इस समस्या के लिए गलत कोड नहीं लिखा था, अगर उन्हें लूप के बीच से रिटर्न लिखने की अनुमति दी गई थी।^[10]

1973 में, एस. राव कोसाराजू ने साबित किया कि संरचित प्रोग्रामिंग में अतिरिक्त चर जोड़ने से बचना संभव है, जब तक कि लूप से मनमानी-गहराई, बहु-स्तरीय ब्रेक की अनुमति है।^[1]^[15] इसके अलावा, कोसाराजू ने साबित किया कि प्रोग्रामों का सख्त पदानुक्रम मौजूद है, जिसे आजकल कोसाराजू पदानुक्रम कहा जाता है, जिसमें प्रत्येक पूर्णांक n के लिए, गहराई n के बहु-स्तरीय ब्रेक वाला प्रोग्राम मौजूद होता है जिसे n से कम गहराई के बहु-स्तरीय ब्रेक वाले प्रोग्राम के रूप में फिर से नहीं लिखा जा सकता है (अतिरिक्त चर पेश किए बिना)।^[1]कोसाराजू BLISS प्रोग्रामिंग भाषा में बहु-स्तरीय ब्रेक निर्माण का हवाला देते हैं। मल्टी-लेवल ब्रेक, फॉर्म ए में leave label कीवर्ड वास्तव में उस भाषा के BLISS-11 संस्करण में पेश किए गए थे; मूल BLISS में मात्र एकल-स्तरीय ब्रेक थे। भाषाओं के BLISS परिवार ने अप्रतिबंधित गोटो प्रदान नहीं किया। जावा (प्रोग्रामिंग भाषा) भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।^[16]^{: 960–965}

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

लूप से शाखा निकलना (लूप चक्र परीक्षण के अलावा)
एक लूप में शाखाबद्ध होना
किसी निर्णय में शाखा लगाना (अर्थात if शाखा में)
किसी निर्णय से बाहर निकलना

मैककेबे ने वास्तव में पाया कि सबग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त शर्त यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से सबग्राफ के रूप में होना चाहिए। उन्होंने यह भी पाया कि यदि किसी गैर-संरचित प्रोग्राम में इन चार उप-ग्राफ़ों में से शामिल है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में मदद करता है कि कैसे गैर-संरचित प्रोग्राम का नियंत्रण प्रवाह लोकप्रिय रूप से स्पेगेटी कोड कहे जाने वाले में उलझ जाता है। मैककेबे ने संख्यात्मक माप भी तैयार किया, जो मनमाने प्रोग्राम को देखते हुए, यह निर्धारित करता है कि यह संरचित प्रोग्राम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।^[17] संरचित प्रोग्रामिंग के लिए निषिद्ध ग्राफ़ के मैककेब के लक्षण वर्णन को अधूरा माना जा सकता है, कम से कम अगर दिज्क्स्ट्रा की डी संरचनाओं को बिल्डिंग ब्लॉक माना जाता है।^[18]^{: 274–275}

1990 तक मौजूदा प्रोग्रामों से गोटो को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित तरीके थे। इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं, जो ऊपर चर्चा किए गए लोक प्रमेय जैसे आउटपुट से बचने के लिए, मात्र ट्यूरिंग समतुल्यता से अधिक कठोर हैं। समतुल्यता की चुनी गई धारणा की कठोरता आवश्यक नियंत्रण प्रवाह संरचनाओं के न्यूनतम सेट को निर्धारित करती है। लाइल रामशॉ द्वारा 1988 का जेएसीएम पेपर उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।^[19] उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा decompiler ्स में किया गया था क्योंकि जावा वर्चुअल मशीन कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखा निर्देश होते हैं, लेकिन उच्च-स्तरीय जावा भाषा में मात्र बहु-स्तरीय होता है break और continue बयान.^[20]^[21]^[22] अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।^[8]

कोबोल पर अनुप्रयोग

1980 के दशक में IBM के शोधकर्ता हरलान मिल्स ने COBOL स्ट्रक्चरिंग सुविधा के विकास का निरीक्षण किया, जिसने COBOL कोड के लिए स्ट्रक्चरिंग एल्गोरिदम लागू किया। मिल्स के परिवर्तन में प्रत्येक प्रक्रिया के लिए निम्नलिखित चरण शामिल थे।

प्रक्रिया में बुनियादी ब्लॉकों की पहचान करें।
प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय लेबल (प्रोग्रामिंग भाषा) निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें।
प्रक्रिया को उसके मूल खंडों में विभाजित करें।
प्रत्येक ब्लॉक के लिए जो मात्र निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः कनेक्ट करें।
प्रक्रिया में नया चर घोषित करें (संदर्भ के लिए एल कहा जाता है)।
प्रत्येक शेष असंबद्ध निकास पथ पर, कथन जोड़ें जो उस पथ पर लेबल मान पर L सेट करता है।
परिणामी प्रोग्रामों को चयन विवरण में संयोजित करें जो प्रोग्राम को एल द्वारा इंगित प्रवेश पथ लेबल के साथ निष्पादित करता है
एक लूप बनाएं जो इस चयन कथन को तब तक निष्पादित करे जब तक L 0 न हो।
एक अनुक्रम का निर्माण करें जो L से 1 आरंभ करता है और लूप निष्पादित करता है।

ध्यान दें कि चयन विवरण के कुछ मामलों को उपप्रक्रियाओं में परिवर्तित करके इस निर्माण में सुधार किया जा सकता है।

यह भी देखें

संरचित प्रोग्रामिंग
ट्यूरिंग पूर्णता

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Dexter Kozen and Wei-Lung Dustin Tseng (2008). The Böhm–Jacopini Theorem Is False, Propositionally (PDF). pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. {{cite book}}: |journal= ignored (help)
↑ "CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Harel, David (1980). "लोक प्रमेयों पर" (PDF). Communications of the ACM. 23 (7): 379–389. doi:10.1145/358886.358892. S2CID 16300625.
↑ Bohm, Corrado; Giuseppe Jacopini (May 1966). "केवल दो गठन नियमों के साथ प्रवाह आरेख, ट्यूरिंग मशीनें और भाषाएँ". Communications of the ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439.
↑ Burks, Arthur W.; Goldstine, Herman; von Neumann, John (1947), Preliminary discussion of the Logical Design of an Electronic Computing Instrument, Princeton, NJ: Institute for Advanced Study
↑ Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.
↑ Bruce Ian Mills (2005). प्रोग्रामिंग का सैद्धांतिक परिचय. Springer. p. 279. ISBN 978-1-84628-263-8.
↑ ^8.0 ^8.1 Ammarguellat, Z. (1992). "एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता". IEEE Transactions on Software Engineering. 18 (3): 237–251. doi:10.1109/32.126773.
↑ Dijkstra, Edsger (1968). "हानिकारक माने जाने वाले कथन पर जाएँ". Communications of the ACM. 11 (3): 147–148. doi:10.1145/362929.362947. S2CID 17469809. Archived from the original on 2007-07-03.
↑ ^10.0 ^10.1 Roberts, E. [1995] "Loop Exits and Structured Programming: Reopening the Debate," ACM SIGCSE Bulletin, (27)1: 268–272.
↑ E. N. Yourdon (1979). सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7.
↑ Ashcroft, Edward; Zohar Manna (1971). "प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में". Proceedings of IFIP Congress. The paper, which is difficult to obtain in the original conference proceedings due to their limited distribution, was republished in Yourdon's 1979 book pp. 51-65
↑ David Anthony Watt; William Findlay (2004). प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7.
↑ Kenneth C. Louden; Kenneth A. Lambert (2011). Programming Languages: Principles and Practices (3 ed.). Cengage Learning. pp. 422–423. ISBN 978-1-111-52941-3.
↑ KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup. Theory of Computing, (May 1973), 240-252; also Kosaraju, S. Rao (1974). "Analysis of structured programs". Journal of Computer and System Sciences. 9 (3): 232–255. doi:10.1016/S0022-0000(74)80043-7. cited by Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.
↑ Brender, Ronald F. (2002). "The BLISS programming language: a history" (PDF). Software: Practice and Experience. 32 (10): 955–981. doi:10.1002/spe.470. S2CID 45466625.
↑ The original paper is Thomas J. McCabe (December 1976). "A Complexity Measure". IEEE Transactions on Software Engineering. SE-2 (4): 315–318. doi:10.1109/tse.1976.233837. S2CID 9116234. For a secondary exposition see Paul C. Jorgensen (2002). Software Testing: A Craftsman's Approach, Second Edition (2nd ed.). CRC Press. pp. 150–153. ISBN 978-0-8493-0809-3.
↑ Williams, M. H. (1983). "फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या". The Computer Journal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270.
↑ Ramshaw, L. (1988). "प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना". Journal of the ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665.
↑ Godfrey Nolan (2004). जावा को विघटित करना. Apress. p. 142. ISBN 978-1-4302-0739-9.
↑ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf^{[bare URL PDF]}
↑ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf^{[bare URL PDF]}

अग्रिम पठन

Material not yet covered above:

DeMillo, Richard A. (1980). "Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem". Journal of the ACM. 27 (1): 123–127. doi:10.1145/322169.322180. S2CID 15669719.
Devienne, Philippe (1994). "One binary horn clause is enough". Stacs 94. Lecture Notes in Computer Science. Vol. 775. pp. 19–32. CiteSeerX 10.1.1.14.537. doi:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0.

[kozen-1] 1.0 ^1.1 ^1.2 Dexter Kozen and Wei-Lung Dustin Tseng (2008). The Böhm–Jacopini Theorem Is False, Propositionally (PDF). pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. {{cite book}}: |journal= ignored (help)

[2] "CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.

[Harel-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Harel, David (1980). "लोक प्रमेयों पर" (PDF). Communications of the ACM. 23 (7): 379–389. doi:10.1145/358886.358892. S2CID 16300625.

[4] Bohm, Corrado; Giuseppe Jacopini (May 1966). "केवल दो गठन नियमों के साथ प्रवाह आरेख, ट्यूरिंग मशीनें और भाषाएँ". Communications of the ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439.

[5] Burks, Arthur W.; Goldstine, Herman; von Neumann, John (1947), Preliminary discussion of the Logical Design of an Electronic Computing Instrument, Princeton, NJ: Institute for Advanced Study

[6] Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.

[Mills2005-7] Bruce Ian Mills (2005). प्रोग्रामिंग का सैद्धांतिक परिचय. Springer. p. 279. ISBN 978-1-84628-263-8.

[amma92-8] 8.0 ^8.1 Ammarguellat, Z. (1992). "एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता". IEEE Transactions on Software Engineering. 18 (3): 237–251. doi:10.1109/32.126773.

[9] Dijkstra, Edsger (1968). "हानिकारक माने जाने वाले कथन पर जाएँ". Communications of the ACM. 11 (3): 147–148. doi:10.1145/362929.362947. S2CID 17469809. Archived from the original on 2007-07-03.

[roberts-10] 10.0 ^10.1 Roberts, E. [1995] "Loop Exits and Structured Programming: Reopening the Debate," ACM SIGCSE Bulletin, (27)1: 268–272.

[Yourdon1979-11] E. N. Yourdon (1979). सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7.

[12] Ashcroft, Edward; Zohar Manna (1971). "प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में". Proceedings of IFIP Congress. The paper, which is difficult to obtain in the original conference proceedings due to their limited distribution, was republished in Yourdon's 1979 book pp. 51-65

[WattFindlay2004-13] David Anthony Watt; William Findlay (2004). प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7.

[LoudenLambert2011-14] Kenneth C. Louden; Kenneth A. Lambert (2011). Programming Languages: Principles and Practices (3 ed.). Cengage Learning. pp. 422–423. ISBN 978-1-111-52941-3.

[15] KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup. Theory of Computing, (May 1973), 240-252; also Kosaraju, S. Rao (1974). "Analysis of structured programs". Journal of Computer and System Sciences. 9 (3): 232–255. doi:10.1016/S0022-0000(74)80043-7. cited by Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.

[16] Brender, Ronald F. (2002). "The BLISS programming language: a history" (PDF). Software: Practice and Experience. 32 (10): 955–981. doi:10.1002/spe.470. S2CID 45466625.

[McCabe-17] The original paper is Thomas J. McCabe (December 1976). "A Complexity Measure". IEEE Transactions on Software Engineering. SE-2 (4): 315–318. doi:10.1109/tse.1976.233837. S2CID 9116234. For a secondary exposition see Paul C. Jorgensen (2002). Software Testing: A Craftsman's Approach, Second Edition (2nd ed.). CRC Press. pp. 150–153. ISBN 978-0-8493-0809-3.

[18] Williams, M. H. (1983). "फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या". The Computer Journal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270.

[19] Ramshaw, L. (1988). "प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना". Journal of the ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665.

[Nolan2004-20] Godfrey Nolan (2004). जावा को विघटित करना. Apress. p. 142. ISBN 978-1-4302-0739-9.

[21] ttps://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf^{[bare URL PDF]}

[22] ttp://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf^{[bare URL PDF]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 1: / Line 1: @@
 {{short description|Control-flow graphs with 3 types of control structures can compute any computable function}}
-संरचित कार्यक्रम प्रमेय, जिसे बोहम-जैकोपिनी प्रमेय भी कहा जाता है,<ref name="kozen">{{cite book|url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |title=The Böhm–Jacopini Theorem Is False, Propositionally|author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|doi=10.1007/978-3-540-70594-9_11|journal=MPC 2008|volume=5133|pages=177–192|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-70593-2|citeseerx=10.1.1.218.9241}}</ref><ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html |title=CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM |publisher=Cse.buffalo.edu |date=2004-11-22 |access-date=2013-08-24}}</ref> [[प्रोग्रामिंग भाषा सिद्धांत]] में परिणाम है। इसमें कहा गया है कि [[नियंत्रण-प्रवाह ग्राफ]]़ का वर्ग (ऐतिहासिक रूप से इस संदर्भ में [[प्रवाह संचित्र]] कहा जाता है) किसी भी गणना योग्य फ़ंक्शन की गणना कर सकता है यदि यह उपप्रोग्राम को केवल तीन विशिष्ट तरीकों ([[नियंत्रण संरचना]]ओं) में जोड़ता है। ये
+संरचित प्रोग्राम प्रमेय, जिसे बोहम-जैकोपिनी प्रमेय भी कहा जाता है,<ref name="kozen">{{cite book|url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |title=The Böhm–Jacopini Theorem Is False, Propositionally|author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|doi=10.1007/978-3-540-70594-9_11|journal=MPC 2008|volume=5133|pages=177–192|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-70593-2|citeseerx=10.1.1.218.9241}}</ref><ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html |title=CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM |publisher=Cse.buffalo.edu |date=2004-11-22 |access-date=2013-08-24}}</ref> [[प्रोग्रामिंग भाषा सिद्धांत]] का एक परिणाम है। इसमें कहा गया है कि [[नियंत्रण-प्रवाह ग्राफ]] का वर्ग (ऐतिहासिक रूप से इस संदर्भ में [[प्रवाह संचित्र]] कहा जाता है) किसी भी गणना योग्य संक्रिया की गणना कर सकता है यदि यह उपप्रोग्राम को मात्र तीन विशिष्ट विधियों ([[नियंत्रण संरचना|नियंत्रण संरचनाओं]]) में जोड़ता है। ये इस प्रकार निम्नलिखित हैं-
 #एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम)
 #[[बूलियन डेटा प्रकार]] अभिव्यक्ति (चयन) के मूल्य के अनुसार दो उपप्रोग्रामों में से को निष्पादित करना
 #जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति)
-इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, हालांकि जानकारी का ट्रैक रखने के लिए [[ अंश ]]्स के रूप में अतिरिक्त चर का उपयोग कर सकता है (मूल प्रमाण में अतिरिक्त पूर्णांक चर में संग्रहीत) जो मूल कार्यक्रम कार्यक्रम स्थान द्वारा प्रस्तुत करता है। निर्माण बोहम की प्रोग्रामिंग भाषा P' पर आधारित था।
+इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, हालांकि जानकारी का ट्रैक रखने के लिए [[ अंश |अंश]] ्स के रूप में अतिरिक्त चर का उपयोग कर सकता है (मूल प्रमाण में अतिरिक्त पूर्णांक चर में संग्रहीत) जो मूल प्रोग्राम प्रोग्राम स्थान द्वारा प्रस्तुत करता है। निर्माण बोहम की प्रोग्रामिंग भाषा P' पर आधारित था।
-प्रमेय [[संरचित प्रोग्रामिंग]] का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो [[ के लिए जाओ ]] से बचता है and exclusively uses subroutines, sequences, selection and iteration.[[File:Structured program patterns.svg|संरचित कार्यक्रम प्रमेय के तीन बुनियादी पैटर्न का ग्राफिकल प्रतिनिधित्व - अनुक्रम, चयन, और पुनरावृत्ति - नासी-श्नीडरमैन आरेख (नीला) और [[प्रवाह चार्ट]] (हरा) का उपयोग करके।|अंगूठा|केंद्र|सीमा|700पीएक्स]]
+प्रमेय [[संरचित प्रोग्रामिंग]] का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो [[ के लिए जाओ |के लिए जाओ]] से बचता है and exclusively uses subroutines, sequences, selection and iteration.[[File:Structured program patterns.svg|संरचित कार्यक्रम प्रमेय के तीन बुनियादी पैटर्न का ग्राफिकल प्रतिनिधित्व - अनुक्रम, चयन, और पुनरावृत्ति - नासी-श्नीडरमैन आरेख (नीला) और [[प्रवाह चार्ट]] (हरा) का उपयोग करके।|अंगूठा|केंद्र|सीमा|700पीएक्स]]
 == उत्पत्ति और प्रकार ==
@@ Line 15: / Line 15: @@
 === सिंगल-व्हाइल-लूप, प्रमेय का लोक संस्करण ===
-प्रमेय का यह संस्करण सभी मूल प्रोग्राम के नियंत्रण प्रवाह को वैश्विक से बदल देता है <code>while</code> लूप जो मूल गैर-संरचित प्रोग्राम में सभी संभावित लेबल (फ़्लोचार्ट बॉक्स) पर जाने वाले [[ कार्यक्रम गणक ]] का अनुकरण करता है। हरेल ने कंप्यूटिंग की शुरुआत को चिह्नित करने वाले दो पत्रों में इस लोक प्रमेय की उत्पत्ति का पता लगाया। इनमें से [[वॉन न्यूमैन वास्तुकला]] का 1946 का विवरण है, जो बताता है कि प्रोग्राम काउंटर थोड़ी देर के लूप के संदर्भ में कैसे संचालित होता है। हारेल का कहना है कि संरचित प्रोग्रामिंग प्रमेय के लोक संस्करण द्वारा उपयोग किया जाने वाला एकल लूप मूल रूप से वॉन न्यूमैन कंप्यूटर पर फ्लोचार्ट के निष्पादन के लिए [[परिचालन शब्दार्थ]] प्रदान करता है।<ref name="Harel"/>{{rp|383}} और, यहां तक कि पुराना स्रोत कि हरेल ने प्रमेय के लोक संस्करण का पता लगाया, वह 1936 से [[स्टीफन क्लेन]] का क्लेन का टी विधेय है।<ref name="Harel"/>{{rp|383}}
+प्रमेय का यह संस्करण सभी मूल प्रोग्राम के नियंत्रण प्रवाह को वैश्विक से बदल देता है <code>while</code> लूप जो मूल गैर-संरचित प्रोग्राम में सभी संभावित लेबल (फ़्लोचार्ट बॉक्स) पर जाने वाले [[ कार्यक्रम गणक |प्रोग्राम गणक]] का अनुकरण करता है। हरेल ने कंप्यूटिंग की शुरुआत को चिह्नित करने वाले दो पत्रों में इस लोक प्रमेय की उत्पत्ति का पता लगाया। इनमें से [[वॉन न्यूमैन वास्तुकला]] का 1946 का विवरण है, जो बताता है कि प्रोग्राम काउंटर थोड़ी देर के लूप के संदर्भ में कैसे संचालित होता है। हारेल का कहना है कि संरचित प्रोग्रामिंग प्रमेय के लोक संस्करण द्वारा उपयोग किया जाने वाला एकल लूप मूल रूप से वॉन न्यूमैन कंप्यूटर पर फ्लोचार्ट के निष्पादन के लिए [[परिचालन शब्दार्थ]] प्रदान करता है।<ref name="Harel"/>{{rp|383}} और, यहां तक कि पुराना स्रोत कि हरेल ने प्रमेय के लोक संस्करण का पता लगाया, वह 1936 से [[स्टीफन क्लेन]] का क्लेन का टी विधेय है।<ref name="Harel"/>{{rp|383}}
-[[डोनाल्ड नुथ]] ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा [[छद्मकोड]] मिलता है, यह इंगित करते हुए कि मूल कार्यक्रम की संरचना इस परिवर्तन में पूरी तरह से खो गई है।<ref>{{cite journal
+[[डोनाल्ड नुथ]] ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा [[छद्मकोड]] मिलता है, यह इंगित करते हुए कि मूल प्रोग्राम की संरचना इस परिवर्तन में पूरी तरह से खो गई है।<ref>{{cite journal
   |  author = Donald Knuth
   |   title = Structured Programming with go to Statements
@@ Line 50: / Line 50: @@
 === बोहम और जैकोपिनी का प्रमाण ===
-बोहम और जैकोपिनी के पेपर में प्रमाण प्रवाह चार्ट के [[संरचनात्मक प्रेरण]] द्वारा आगे बढ़ता है।<ref name="Harel"/>{{rp|381}} क्योंकि इसमें [[सबग्राफ समरूपता समस्या]] को नियोजित किया गया था, बोहम और जैकोपिनी का प्रमाण वास्तव में [[कार्यक्रम परिवर्तन]] एल्गोरिदम के रूप में व्यावहारिक नहीं था, और इस प्रकार इस दिशा में अतिरिक्त शोध के लिए द्वार खुल गया।<ref name="amma92"/>
+बोहम और जैकोपिनी के पेपर में प्रमाण प्रवाह चार्ट के [[संरचनात्मक प्रेरण]] द्वारा आगे बढ़ता है।<ref name="Harel"/>{{rp|381}} क्योंकि इसमें [[सबग्राफ समरूपता समस्या]] को नियोजित किया गया था, बोहम और जैकोपिनी का प्रमाण वास्तव में [[कार्यक्रम परिवर्तन|प्रोग्राम परिवर्तन]] एल्गोरिदम के रूप में व्यावहारिक नहीं था, और इस प्रकार इस दिशा में अतिरिक्त शोध के लिए द्वार खुल गया।<ref name="amma92"/>
 == निहितार्थ और परिशोधन ==
 बोहम-जैकोपिनी प्रमाण ने इस सवाल का समाधान नहीं किया कि सॉफ्टवेयर विकास के लिए संरचित प्रोग्रामिंग को अपनाया जाए या नहीं, आंशिक रूप से क्योंकि निर्माण में किसी प्रोग्राम को सुधारने की तुलना में उसे अस्पष्ट करने की अधिक संभावना थी। इसके विपरीत, इसने बहस की शुरुआत का संकेत दिया। [[एडवर्ड डिज्क्स्ट्रा]] का प्रसिद्ध पत्र, [[हानिकारक माना जाता है]], 1968 में अनुसरण किया गया।<ref>{{cite journal|last=Dijkstra|first=Edsger|author-link=Edsger W. Dijkstra|year=1968|title=हानिकारक माने जाने वाले कथन पर जाएँ|journal=Communications of the ACM|volume=11|issue=3|pages=147–148|doi=10.1145/362929.362947|s2cid=17469809 |url=http://www.acm.org/classics/oct95/|url-status=dead|archive-url=https://web.archive.org/web/20070703050443/http://www.acm.org/classics/oct95/|archive-date=2007-07-03}}</ref>
 कुछ शिक्षाविदों ने बोहम-जैकोपिनी परिणाम के लिए शुद्धतावादी दृष्टिकोण अपनाया और तर्क दिया कि निर्देश भी पसंद करते हैं <code>break</code> और <code>return</code> लूप के बीच से निकालना खराब अभ्यास है क्योंकि बोहम-जैकोपिनी प्रमाण में उनकी आवश्यकता नहीं है, और इस प्रकार उन्होंने वकालत की कि सभी लूप में ही निकास बिंदु होना चाहिए। यह शुद्धतावादी दृष्टिकोण [[पास्कल (प्रोग्रामिंग भाषा)]] (1968-1969 में डिज़ाइन किया गया) में सन्निहित है, जो 1990 के दशक के मध्य तक शिक्षा जगत में परिचयात्मक प्रोग्रामिंग कक्षाओं को पढ़ाने के लिए पसंदीदा उपकरण था।<ref name="roberts">Roberts, E. [1995] "[http://cs.stanford.edu/people/eroberts/papers/SIGCSE-1995/LoopExits.pdf Loop Exits and Structured Programming: Reopening the Debate]," ACM SIGCSE Bulletin, (27)1: 268–272.</ref>
-एडवर्ड योरडन कहते हैं कि 1970 के दशक में असंरचित कार्यक्रमों को स्वचालित माध्यमों से संरचित कार्यक्रमों में बदलने का दार्शनिक विरोध भी था, इस तर्क के आधार पर कि किसी को शुरू से ही संरचित प्रोग्रामिंग फैशन में सोचने की जरूरत थी। व्यावहारिक प्रतिवाद यह था कि ऐसे परिवर्तनों से मौजूदा कार्यक्रमों के बड़े समूह को लाभ हुआ।<ref name="Yourdon1979">{{cite book|author=E. N. Yourdon|title=सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स|year=1979|publisher=Yourdon Press|isbn=978-0-917072-14-7|pages=[https://archive.org/details/classicsinsoftwa00your/page/49 49–50]|url-access=registration|url=https://archive.org/details/classicsinsoftwa00your/page/49}}</ref> स्वचालित परिवर्तन के पहले प्रस्तावों में एडवर्ड एशक्रॉफ्ट और [[जोहार मन्ना]] का 1971 का पेपर था।<ref>{{cite journal|last=Ashcroft|first=Edward|author2=Zohar Manna |year=1971|title=प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में|journal=[[Proceedings of IFIP Congress]]}} The paper, which is difficult to obtain in the original conference proceedings due to their limited distribution, was republished in Yourdon's 1979 book pp. 51-65</ref>
+एडवर्ड योरडन कहते हैं कि 1970 के दशक में असंरचित प्रोग्रामों को स्वचालित माध्यमों से संरचित प्रोग्रामों में बदलने का दार्शनिक विरोध भी था, इस तर्क के आधार पर कि किसी को शुरू से ही संरचित प्रोग्रामिंग फैशन में सोचने की जरूरत थी। व्यावहारिक प्रतिवाद यह था कि ऐसे परिवर्तनों से मौजूदा प्रोग्रामों के बड़े समूह को लाभ हुआ।<ref name="Yourdon1979">{{cite book|author=E. N. Yourdon|title=सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स|year=1979|publisher=Yourdon Press|isbn=978-0-917072-14-7|pages=[https://archive.org/details/classicsinsoftwa00your/page/49 49–50]|url-access=registration|url=https://archive.org/details/classicsinsoftwa00your/page/49}}</ref> स्वचालित परिवर्तन के पहले प्रस्तावों में एडवर्ड एशक्रॉफ्ट और [[जोहार मन्ना]] का 1971 का पेपर था।<ref>{{cite journal|last=Ashcroft|first=Edward|author2=Zohar Manna |year=1971|title=प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में|journal=[[Proceedings of IFIP Congress]]}} The paper, which is difficult to obtain in the original conference proceedings due to their limited distribution, was republished in Yourdon's 1979 book pp. 51-65</ref>
-बोहम-जैकोपिनी प्रमेय के प्रत्यक्ष अनुप्रयोग के परिणामस्वरूप संरचित चार्ट में अतिरिक्त स्थानीय चर पेश किए जा सकते हैं, और इसके परिणामस्वरूप कुछ [[कोड दोहराव]] भी हो सकता है।<ref name="WattFindlay2004">{{cite book|author1=David Anthony Watt|author2=William Findlay|title=प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ|url=https://archive.org/details/programminglangu00watt_497|url-access=limited|year=2004|publisher=John Wiley & Sons|isbn=978-0-470-85320-7|page=[https://archive.org/details/programminglangu00watt_497/page/n246 228]}}</ref> बाद वाले मुद्दे को इस संदर्भ में लूप एंड हाफ समस्या कहा जाता है।<ref name="LoudenLambert2011">{{cite book|author1=Kenneth C. Louden|author2=Kenneth A. Lambert|title=Programming Languages: Principles and Practices|url=https://archive.org/details/programminglangu00loud_140|url-access=limited|year=2011|publisher=Cengage Learning|isbn=978-1-111-52941-3|pages=[https://archive.org/details/programminglangu00loud_140/page/n426 422]–423|edition=3}}</ref> पास्कल इन दोनों समस्याओं से प्रभावित है और एरिक एस. रॉबर्ट्स द्वारा उद्धृत अनुभवजन्य अध्ययनों के अनुसार, छात्र प्रोग्रामरों को पास्कल में कई सरल समस्याओं के लिए सही समाधान तैयार करने में कठिनाई हुई, जिसमें सरणी में तत्व की खोज के लिए फ़ंक्शन लिखना भी शामिल था। रॉबर्ट्स द्वारा उद्धृत हेनरी शापिरो के 1980 के अध्ययन में पाया गया कि केवल पास्कल द्वारा प्रदान की गई नियंत्रण संरचनाओं का उपयोग करके, केवल 20% विषयों द्वारा सही समाधान दिया गया था, जबकि किसी भी विषय ने इस समस्या के लिए गलत कोड नहीं लिखा था, अगर उन्हें लूप के बीच से रिटर्न लिखने की अनुमति दी गई थी।<ref name="roberts"/>
+बोहम-जैकोपिनी प्रमेय के प्रत्यक्ष अनुप्रयोग के परिणामस्वरूप संरचित चार्ट में अतिरिक्त स्थानीय चर पेश किए जा सकते हैं, और इसके परिणामस्वरूप कुछ [[कोड दोहराव]] भी हो सकता है।<ref name="WattFindlay2004">{{cite book|author1=David Anthony Watt|author2=William Findlay|title=प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ|url=https://archive.org/details/programminglangu00watt_497|url-access=limited|year=2004|publisher=John Wiley & Sons|isbn=978-0-470-85320-7|page=[https://archive.org/details/programminglangu00watt_497/page/n246 228]}}</ref> बाद वाले मुद्दे को इस संदर्भ में लूप एंड हाफ समस्या कहा जाता है।<ref name="LoudenLambert2011">{{cite book|author1=Kenneth C. Louden|author2=Kenneth A. Lambert|title=Programming Languages: Principles and Practices|url=https://archive.org/details/programminglangu00loud_140|url-access=limited|year=2011|publisher=Cengage Learning|isbn=978-1-111-52941-3|pages=[https://archive.org/details/programminglangu00loud_140/page/n426 422]–423|edition=3}}</ref> पास्कल इन दोनों समस्याओं से प्रभावित है और एरिक एस. रॉबर्ट्स द्वारा उद्धृत अनुभवजन्य अध्ययनों के अनुसार, छात्र प्रोग्रामरों को पास्कल में कई सरल समस्याओं के लिए सही समाधान तैयार करने में कठिनाई हुई, जिसमें सरणी में तत्व की खोज के लिए संक्रिया लिखना भी शामिल था। रॉबर्ट्स द्वारा उद्धृत हेनरी शापिरो के 1980 के अध्ययन में पाया गया कि मात्र पास्कल द्वारा प्रदान की गई नियंत्रण संरचनाओं का उपयोग करके, मात्र 20% विषयों द्वारा सही समाधान दिया गया था, जबकि किसी भी विषय ने इस समस्या के लिए गलत कोड नहीं लिखा था, अगर उन्हें लूप के बीच से रिटर्न लिखने की अनुमति दी गई थी।<ref name="roberts"/>
 में, एस. राव कोसाराजू ने साबित किया कि संरचित प्रोग्रामिंग में अतिरिक्त चर जोड़ने से बचना संभव है, जब तक कि लूप से मनमानी-गहराई, बहु-स्तरीय ब्रेक की अनुमति है।<ref name="kozen"/><ref>KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup.
@@ Line 69: / Line 69: @@
 |   citeseerx = 10.1.1.103.6084
   | s2cid = 207630080
-  }}</ref> इसके अलावा, कोसाराजू ने साबित किया कि कार्यक्रमों का सख्त पदानुक्रम मौजूद है, जिसे आजकल कोसाराजू पदानुक्रम कहा जाता है, जिसमें प्रत्येक पूर्णांक n के लिए, गहराई n के बहु-स्तरीय ब्रेक वाला प्रोग्राम मौजूद होता है जिसे n से कम गहराई के बहु-स्तरीय ब्रेक वाले प्रोग्राम के रूप में फिर से नहीं लिखा जा सकता है (अतिरिक्त चर पेश किए बिना)।<ref name="kozen"/>कोसाराजू [[BLISS]] प्रोग्रामिंग भाषा में बहु-स्तरीय ब्रेक निर्माण का हवाला देते हैं। मल्टी-लेवल ब्रेक, फॉर्म ए में <code>leave ''label''</code> कीवर्ड वास्तव में उस भाषा के BLISS-11 संस्करण में पेश किए गए थे; मूल BLISS में केवल एकल-स्तरीय ब्रेक थे। भाषाओं के BLISS परिवार ने अप्रतिबंधित गोटो प्रदान नहीं किया। [[जावा (प्रोग्रामिंग भाषा)]] भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।<ref>{{cite journal | doi = 10.1002/spe.470 | title=The BLISS programming language: a history | journal=Software: Practice and Experience | date=2002 | volume=32 | issue=10 | pages=955–981 | first=Ronald F. | last=Brender | s2cid=45466625 | url = https://www.cs.tufts.edu/~nr/cs257/archive/ronald-brender/bliss.pdf}}</ref>{{rp|960–965}}
+  }}</ref> इसके अलावा, कोसाराजू ने साबित किया कि प्रोग्रामों का सख्त पदानुक्रम मौजूद है, जिसे आजकल कोसाराजू पदानुक्रम कहा जाता है, जिसमें प्रत्येक पूर्णांक n के लिए, गहराई n के बहु-स्तरीय ब्रेक वाला प्रोग्राम मौजूद होता है जिसे n से कम गहराई के बहु-स्तरीय ब्रेक वाले प्रोग्राम के रूप में फिर से नहीं लिखा जा सकता है (अतिरिक्त चर पेश किए बिना)।<ref name="kozen"/>कोसाराजू [[BLISS]] प्रोग्रामिंग भाषा में बहु-स्तरीय ब्रेक निर्माण का हवाला देते हैं। मल्टी-लेवल ब्रेक, फॉर्म ए में <code>leave ''label''</code> कीवर्ड वास्तव में उस भाषा के BLISS-11 संस्करण में पेश किए गए थे; मूल BLISS में मात्र एकल-स्तरीय ब्रेक थे। भाषाओं के BLISS परिवार ने अप्रतिबंधित गोटो प्रदान नहीं किया। [[जावा (प्रोग्रामिंग भाषा)]] भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।<ref>{{cite journal | doi = 10.1002/spe.470 | title=The BLISS programming language: a history | journal=Software: Practice and Experience | date=2002 | volume=32 | issue=10 | pages=955–981 | first=Ronald F. | last=Brender | s2cid=45466625 | url = https://www.cs.tufts.edu/~nr/cs257/archive/ronald-brender/bliss.pdf}}</ref>{{rp|960–965}}
-कोसाराजू के पेपर से सरल परिणाम यह है कि प्रोग्राम संरचित प्रोग्राम (वैरिएबल जोड़े बिना) में कम किया जा सकता है यदि और केवल तभी इसमें दो अलग-अलग निकास के साथ लूप शामिल नहीं है। रिड्यूसिबिलिटी को कोसाराजू द्वारा परिभाषित किया गया था, मोटे तौर पर, ही फ़ंक्शन की गणना करने और मूल कार्यक्रम के रूप में समान आदिम क्रियाओं और विधेय का उपयोग करने के रूप में, लेकिन संभवतः विभिन्न नियंत्रण प्रवाह संरचनाओं का उपयोग करते हुए। (यह बोहम-जैकोपिनी द्वारा उपयोग की जाने वाली रिड्यूसिबिलिटी की तुलना में संकीर्ण धारणा है।) इस परिणाम से प्रेरित होकर, अपने अत्यधिक उद्धृत पेपर के खंड VI में, जिसने साइक्लोमैटिक जटिलता की धारणा पेश की, थॉमस जे। मैककेबे ने गैर-संरचित कार्यक्रमों के नियंत्रण-प्रवाह ग्राफ़ (सीएफजी) के लिए कुराटोस्की के प्रमेय के एनालॉग का वर्णन किया, जिसका अर्थ है, न्यूनतम प्रेरित सबग्राफ जो कार्यक्रम के सीएफजी को गैर-संरचित बनाता है। इन उपसमूहों का प्राकृतिक भाषा में बहुत अच्छा वर्णन है। वे हैं:
+कोसाराजू के पेपर से सरल परिणाम यह है कि प्रोग्राम संरचित प्रोग्राम (वैरिएबल जोड़े बिना) में कम किया जा सकता है यदि और मात्र तभी इसमें दो अलग-अलग निकास के साथ लूप शामिल नहीं है। रिड्यूसिबिलिटी को कोसाराजू द्वारा परिभाषित किया गया था, मोटे तौर पर, ही संक्रिया की गणना करने और मूल प्रोग्राम के रूप में समान आदिम क्रियाओं और विधेय का उपयोग करने के रूप में, लेकिन संभवतः विभिन्न नियंत्रण प्रवाह संरचनाओं का उपयोग करते हुए। (यह बोहम-जैकोपिनी द्वारा उपयोग की जाने वाली रिड्यूसिबिलिटी की तुलना में संकीर्ण धारणा है।) इस परिणाम से प्रेरित होकर, अपने अत्यधिक उद्धृत पेपर के खंड VI में, जिसने साइक्लोमैटिक जटिलता की धारणा पेश की, थॉमस जे। मैककेबे ने गैर-संरचित प्रोग्रामों के नियंत्रण-प्रवाह ग्राफ़ (सीएफजी) के लिए कुराटोस्की के प्रमेय के एनालॉग का वर्णन किया, जिसका अर्थ है, न्यूनतम प्रेरित सबग्राफ जो प्रोग्राम के सीएफजी को गैर-संरचित बनाता है। इन उपसमूहों का प्राकृतिक भाषा में बहुत अच्छा वर्णन है। वे हैं:
 # लूप से शाखा निकलना (लूप चक्र परीक्षण के अलावा)
 # एक लूप में शाखाबद्ध होना
 # किसी निर्णय में शाखा लगाना (अर्थात if शाखा में)
 #किसी निर्णय से बाहर निकलना
-मैककेबे ने वास्तव में पाया कि सबग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त शर्त यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से सबग्राफ के रूप में होना चाहिए। उन्होंने यह भी पाया कि यदि किसी गैर-संरचित कार्यक्रम में इन चार उप-ग्राफ़ों में से शामिल है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में मदद करता है कि कैसे गैर-संरचित प्रोग्राम का नियंत्रण प्रवाह लोकप्रिय रूप से [[स्पेगेटी कोड]] कहे जाने वाले में उलझ जाता है। मैककेबे ने संख्यात्मक माप भी तैयार किया, जो मनमाने कार्यक्रम को देखते हुए, यह निर्धारित करता है कि यह संरचित कार्यक्रम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।<ref name="McCabe">The original paper is {{cite journal |author=Thomas J. McCabe |date=December 1976 |journal=IEEE Transactions on Software Engineering |issue=4 |pages=315–318 |title=A Complexity Measure|url=https://books.google.com/books?id=vtNWAAAAMAAJ&pg=PA3 |doi=10.1109/tse.1976.233837 |volume=SE-2|s2cid=9116234 }} For a secondary exposition see {{cite book|author=Paul C. Jorgensen|title=Software Testing: A Craftsman's Approach, Second Edition|url=https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150|year=2002|publisher=CRC Press|isbn=978-0-8493-0809-3|pages=150–153|edition=2nd}}</ref>
+मैककेबे ने वास्तव में पाया कि सबग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त शर्त यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से सबग्राफ के रूप में होना चाहिए। उन्होंने यह भी पाया कि यदि किसी गैर-संरचित प्रोग्राम में इन चार उप-ग्राफ़ों में से शामिल है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में मदद करता है कि कैसे गैर-संरचित प्रोग्राम का नियंत्रण प्रवाह लोकप्रिय रूप से [[स्पेगेटी कोड]] कहे जाने वाले में उलझ जाता है। मैककेबे ने संख्यात्मक माप भी तैयार किया, जो मनमाने प्रोग्राम को देखते हुए, यह निर्धारित करता है कि यह संरचित प्रोग्राम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।<ref name="McCabe">The original paper is {{cite journal |author=Thomas J. McCabe |date=December 1976 |journal=IEEE Transactions on Software Engineering |issue=4 |pages=315–318 |title=A Complexity Measure|url=https://books.google.com/books?id=vtNWAAAAMAAJ&pg=PA3 |doi=10.1109/tse.1976.233837 |volume=SE-2|s2cid=9116234 }} For a secondary exposition see {{cite book|author=Paul C. Jorgensen|title=Software Testing: A Craftsman's Approach, Second Edition|url=https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150|year=2002|publisher=CRC Press|isbn=978-0-8493-0809-3|pages=150–153|edition=2nd}}</ref>
 संरचित प्रोग्रामिंग के लिए [[निषिद्ध ग्राफ]]़ के मैककेब के लक्षण वर्णन को अधूरा माना जा सकता है, कम से कम अगर दिज्क्स्ट्रा की डी संरचनाओं को बिल्डिंग ब्लॉक माना जाता है।<ref>{{cite journal | doi = 10.1093/comjnl/26.3.270 | title=फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या| journal=The Computer Journal | date=1983 | volume=26 | issue=3 | pages=270–276 | first=M. H. | last=Williams| doi-access=free }}</ref>{{rp|274–275}}
-तक मौजूदा कार्यक्रमों से गोटो को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित तरीके थे। इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं, जो ऊपर चर्चा किए गए लोक प्रमेय जैसे आउटपुट से बचने के लिए, केवल ट्यूरिंग समतुल्यता से अधिक कठोर हैं। समतुल्यता की चुनी गई धारणा की कठोरता आवश्यक नियंत्रण प्रवाह संरचनाओं के न्यूनतम सेट को निर्धारित करती है। लाइल रामशॉ द्वारा 1988 का [[जेएसीएम]] पेपर उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।<ref>{{Cite journal | doi = 10.1145/48014.48021| title = प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना| journal = Journal of the ACM| volume = 35| issue = 4| pages = 893–920| year = 1988| last1 = Ramshaw | first1 = L. | s2cid = 31001665}}</ref> उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा [[ decompiler ]]्स में किया गया था क्योंकि [[जावा वर्चुअल मशीन]] कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखा निर्देश होते हैं, लेकिन उच्च-स्तरीय जावा भाषा में केवल बहु-स्तरीय होता है <code>break</code> और <code>continue</code> बयान.<ref name="Nolan2004">{{cite book|author=Godfrey Nolan|title=जावा को विघटित करना|year=2004|publisher=Apress|isbn=978-1-4302-0739-9|page=142}}</ref><ref>https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf {{Bare URL PDF|date=March 2022}}</ref><ref>http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf {{Bare URL PDF|date=March 2022}}</ref> अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।<ref name="amma92">{{cite journal | doi = 10.1109/32.126773 | title=एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता| journal=IEEE Transactions on Software Engineering | date=1992 | volume=18 | issue=3 | pages=237–251 | first=Z. | last=Ammarguellat}}</ref>
+तक मौजूदा प्रोग्रामों से गोटो को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित तरीके थे। इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं, जो ऊपर चर्चा किए गए लोक प्रमेय जैसे आउटपुट से बचने के लिए, मात्र ट्यूरिंग समतुल्यता से अधिक कठोर हैं। समतुल्यता की चुनी गई धारणा की कठोरता आवश्यक नियंत्रण प्रवाह संरचनाओं के न्यूनतम सेट को निर्धारित करती है। लाइल रामशॉ द्वारा 1988 का [[जेएसीएम]] पेपर उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।<ref>{{Cite journal | doi = 10.1145/48014.48021| title = प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना| journal = Journal of the ACM| volume = 35| issue = 4| pages = 893–920| year = 1988| last1 = Ramshaw | first1 = L. | s2cid = 31001665}}</ref> उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा [[ decompiler |decompiler]] ्स में किया गया था क्योंकि [[जावा वर्चुअल मशीन]] कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखा निर्देश होते हैं, लेकिन उच्च-स्तरीय जावा भाषा में मात्र बहु-स्तरीय होता है <code>break</code> और <code>continue</code> बयान.<ref name="Nolan2004">{{cite book|author=Godfrey Nolan|title=जावा को विघटित करना|year=2004|publisher=Apress|isbn=978-1-4302-0739-9|page=142}}</ref><ref>https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf {{Bare URL PDF|date=March 2022}}</ref><ref>http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf {{Bare URL PDF|date=March 2022}}</ref> अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।<ref name="amma92">{{cite journal | doi = 10.1109/32.126773 | title=एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता| journal=IEEE Transactions on Software Engineering | date=1992 | volume=18 | issue=3 | pages=237–251 | first=Z. | last=Ammarguellat}}</ref>
 ==कोबोल पर अनुप्रयोग==
 के दशक में [[IBM]] के शोधकर्ता [[हरलान मिल्स]] ने [[COBOL]] स्ट्रक्चरिंग सुविधा के विकास का निरीक्षण किया, जिसने COBOL कोड के लिए स्ट्रक्चरिंग एल्गोरिदम लागू किया। मिल्स के परिवर्तन में प्रत्येक प्रक्रिया के लिए निम्नलिखित चरण शामिल थे।
@@ Line 86: / Line 86: @@
 #प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय [[लेबल (प्रोग्रामिंग भाषा)]] निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें।
 #प्रक्रिया को उसके मूल खंडों में विभाजित करें।
-#प्रत्येक ब्लॉक के लिए जो केवल निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः कनेक्ट करें।
+#प्रत्येक ब्लॉक के लिए जो मात्र निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः कनेक्ट करें।
 #प्रक्रिया में नया चर घोषित करें (संदर्भ के लिए एल कहा जाता है)।
 # प्रत्येक शेष असंबद्ध निकास पथ पर, कथन जोड़ें जो उस पथ पर लेबल मान पर L सेट करता है।

Anonymous

Search

संरचित प्रोग्राम प्रमेय: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:27, 6 August 2023

Contents

उत्पत्ति और प्रकार

सिंगल-व्हाइल-लूप, प्रमेय का लोक संस्करण

बोहम और जैकोपिनी का प्रमाण

निहितार्थ और परिशोधन

कोबोल पर अनुप्रयोग

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संरचित प्रोग्राम प्रमेय: Difference between revisions

Revision as of 12:27, 6 August 2023

उत्पत्ति और प्रकार

सिंगल-व्हाइल-लूप, प्रमेय का लोक संस्करण

बोहम और जैकोपिनी का प्रमाण

निहितार्थ और परिशोधन

कोबोल पर अनुप्रयोग

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories