लूप इनवेरिएंट: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Invariants used to prove properties of loops}} {{for|the computer programming optimization technique|Loop-invariant code motion}} कंप्यूट...")
 
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Invariants used to prove properties of loops}}
{{Short description|Invariants used to prove properties of loops}}
{{for|the computer programming  optimization technique|Loop-invariant code motion}}
{{for|कंप्यूटर प्रोग्रामिंग अनुकूलन तकनीक|लूप-अपरिवर्तनीय कोड गति}}


[[कंप्यूटर विज्ञान]] में, एक लूप इनवेरिएंट एक [[कंप्यूटर प्रोग्राम]] नियंत्रण प्रवाह # लूप्स की एक संपत्ति है जो प्रत्येक पुनरावृत्ति से पहले (और बाद में) सत्य है। यह एक तार्किक अभिकथन है, जिसे कभी-कभी कोड [[अभिकथन (सॉफ़्टवेयर विकास)]] के साथ जांचा जाता है। लूप के प्रभाव को समझने के लिए इसके अपरिवर्तनीयों को जानना आवश्यक है।
[[कंप्यूटर विज्ञान]] में, लूप इनवेरिएंट [[कंप्यूटर प्रोग्राम]] लूप का गुण है, जो प्रत्येक पुनरावृत्ति से पहले (और बाद में) सत्य होती है। यह तार्किक अभिकथन है, जिसे कभी-कभी कोड [[अभिकथन (सॉफ़्टवेयर विकास)]] के साथ जांचा जाता है। लूप के प्रभाव को समझने के लिए इसके अपरिवर्तनीयों को जानना आवश्यक है।


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


प्रोग्रामिंग पद्धति के दृष्टिकोण से, लूप इनवेरिएंट को लूप के अधिक अमूर्त विनिर्देश के रूप में देखा जा सकता है, जो इस कार्यान्वयन के विवरण से परे लूप के गहरे उद्देश्य को दर्शाता है। एक सर्वेक्षण आलेख <ref>Carlo A. Furia, [[Bertrand Meyer]] and Sergey Velder. "Loop invariants: analysis, classification, and examples."ACM Computing Surveys.  vol. 46, no. 3, February 2014([http://se.ethz.ch/~meyer/publications/methodology/invariants.pdf]</ref> कंप्यूटर विज्ञान (खोज, छँटाई, अनुकूलन, अंकगणित आदि) के कई क्षेत्रों से मौलिक एल्गोरिदम को शामिल करता है, उनमें से प्रत्येक को उसके अपरिवर्तनीय के दृष्टिकोण से चित्रित करता है।
प्रोग्रामिंग पद्धति के दृष्टिकोण से, लूप इनवेरिएंट को लूप के अधिक अमूर्त विनिर्देश के रूप में देखा जा सकता है, जो इस कार्यान्वयन के विवरण से हटकर लूप के गहरे उद्देश्य को दर्शाता है। सर्वेक्षण आलेख <ref>Carlo A. Furia, [[Bertrand Meyer]] and Sergey Velder. "Loop invariants: analysis, classification, and examples."ACM Computing Surveys.  vol. 46, no. 3, February 2014([http://se.ethz.ch/~meyer/publications/methodology/invariants.pdf]</ref> कंप्यूटर विज्ञान (खोज, छँटाई, अनुकूलन, अंकगणित आदि) के कई क्षेत्रों से मौलिक एल्गोरिदम को सम्मिलित करता है, उनमें से प्रत्येक को उसके अपरिवर्तनीय के दृष्टिकोण से चित्रित करता है।


लूप और [[ प्रत्यावर्तन ]] प्रोग्राम की समानता के कारण, इनवेरिएंट के साथ लूप की आंशिक शुद्धता साबित करना [[संरचनात्मक प्रेरण]] के माध्यम से रिकर्सिव प्रोग्राम की शुद्धता साबित करने के समान है। वास्तव में, लूप इनवेरिएंट अक्सर किसी दिए गए लूप के समतुल्य पुनरावर्ती कार्यक्रम के लिए सिद्ध की जाने वाली आगमनात्मक परिकल्पना के समान होता है।
लूप और [[ प्रत्यावर्तन |प्रत्यावर्तन]] प्रोग्राम की समानता के कारण, इनवेरिएंट के साथ लूप की आंशिक शुद्धता प्रमाणित करना [[संरचनात्मक प्रेरण]] के माध्यम से रिकर्सिव प्रोग्राम की शुद्धता प्रमाणित करने के समान है। वास्तव में, लूप इनवेरिएंट अधिकांशतः किसी दिए गए लूप के समतुल्य पुनरावर्ती कार्यक्रम के लिए सिद्ध की जाने वाली आगमनात्मक परिकल्पना के समान होता है।


==अनौपचारिक उदाहरण==
==अनौपचारिक उदाहरण==
निम्नलिखित [[सी (प्रोग्रामिंग भाषा)]] [[सबरूटीन]] <code>max()</code> इसके तर्क सरणी में अधिकतम मान लौटाता है <code>a[]</code>, इसकी लंबाई प्रदान की गई <code>n</code> कम से कम 1 है.
निम्नलिखित [[सी (प्रोग्रामिंग भाषा)|C (प्रोग्रामिंग भाषा)]] [[सबरूटीन]] <code>max()</code> अपने तर्क सरणी <code>a[]</code> में अधिकतम मान लौटाता है, इसकी लंबाई प्रदान की गई <code>n</code> कम से कम 1 हो। टिप्पणियाँ पंक्तियों 3, 6, 9, 11 और 13 पर प्रदान की जाती हैं। प्रत्येक टिप्पणी फलन के उस चरण में एक या अधिक चर के मूल्यों के बारे में सत्यापन करती है। लूप बॉडी के अन्दर, लूप के प्रारंभ और अंत में हाइलाइट किए गए प्रमाण (पंक्तियाँ 6 और 11), बिल्कुल समान हैं। इस प्रकार वे लूप की अपरिवर्तनीय गुण का वर्णन करते हैं। जब पंक्ति 13 पर पहुँच जाता है, तब भी यह अपरिवर्तनीय रहता है, और यह ज्ञात होता है कि पंक्ति 5 से लूप की स्थिति <code>i!=n</code> असत्य हो गयी है। दोनों गुण मिलकर यही दर्शाते हैं कि <code>m</code> में अधिकतम मान <code>a[0...n-1]</code> के बराबर है, अर्थात्, पंक्ति 14 से सही मान लौटाया जाता है।<syntaxhighlight>
टिप्पणियाँ पंक्ति 3, 6, 9, 11 और 13 पर प्रदान की जाती हैं। प्रत्येक टिप्पणी फ़ंक्शन के उस चरण में एक या अधिक चर के मूल्यों के बारे में दावा करती है।
int max(int n, const int a[]) {
लूप बॉडी के भीतर, लूप की शुरुआत और अंत में हाइलाइट किए गए दावे (पंक्तियाँ 6 और 11), बिल्कुल समान हैं। इस प्रकार वे लूप की एक अपरिवर्तनीय संपत्ति का वर्णन करते हैं।
जब पंक्ति 13 पर पहुँच जाता है, तब भी यह अपरिवर्तनीय रहता है, और यह ज्ञात होता है कि लूप की स्थिति क्या है <code>i!=n</code> पंक्ति 5 से असत्य हो गया है। दोनों गुण मिलकर यही दर्शाते हैं <code>m</code> में अधिकतम मान के बराबर है <code>a[0...n-1]</code>, अर्थात्, पंक्ति 14 से सही मान लौटाया जाता है।
<!---Usage of (source) tag see http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi--->
<सिंटैक्सहाइलाइट लैंग= सी लाइन हाइलाइट= 6,11 >
int max(int ​​n, const int a[]) {
     int m = a[0];
     int m = a[0];
     // m a[0...0] में अधिकतम मान के बराबर है
     // m equals the maximum value in a[0...0]
     पूर्णांक मैं = 1;
     int i = 1;
     जबकि (i != n) {
     while (i != n) {
         // m a[0...i-1] में अधिकतम मान के बराबर है
         // m equals the maximum value in a[0...i-1]
         अगर (एम < [i])
         if (m < a[i])
             एम = [आई];
             m = a[i];
         // m a[0...i] में अधिकतम मान के बराबर है
         // m equals the maximum value in a[0...i]
         ++मैं;
         ++i;
         // m a[0...i-1] में अधिकतम मान के बराबर है
         // m equals the maximum value in a[0...i-1]
     }
     }
     // m a[0...i-1] में अधिकतम मान के बराबर है, और i==n
     // m equals the maximum value in a[0...i-1], and i==n
     वापसी एम;
     return m;
}
}
</सिंटैक्सहाइलाइट>
</syntaxhighlight>[[रक्षात्मक प्रोग्रामिंग]] प्रतिमान का पालन करते हुए, पंक्ति 5 में लूप स्थिति <code>i!=n</code> को उत्तम ढंग से <code>i<n</code> संशोधित किया जाना चाहिए, जिससे <code>n</code> के अवैध नकारात्मक मूल्यों के लिए अंतहीन लूपिंग से बचा जा सके। चूँकि सहज रूप से कोड में इस परिवर्तन से कोई फर्क नहीं पड़ना चाहिए, लेकिन इसके सही होने की ओर ले जाने वाला तर्क कुछ अधिक जटिल हो जाता है, तभी से पंक्ति 13 में केवल <code>i>=n</code> ज्ञात है। इसे प्राप्त करने के लिए <code>i<=n</code> का भी मानना है, स्थिति को लूप इनवेरिएंट में सम्मिलित करना होगा। यह देखना सरल है कि <code>i<=n</code> भी लूप का अपरिवर्तनीय है, क्योंकि पंक्ति 6 में <code>i<n</code> पंक्ति 5 में (संशोधित) लूप स्थिति से प्राप्त किया जा सकता है, और इसलिए <code>i<=n</code> पंक्ति में रहता है, 11 के बाद <code>i</code> को पंक्ति 10 में बढ़ा दिया गया है। चूँकि, जब औपचारिक कार्यक्रम सत्यापन के लिए लूप इनवेरिएंट को मैन्युअल रूप से प्रदान करना पड़ता है, तो <code>i<=n</code> जैसे सहज रूप से स्पष्ट गुणों को अधिकांशतः अनदेखा कर दिया जाता है।
[[रक्षात्मक प्रोग्रामिंग]] प्रतिमान के बाद, लूप स्थिति <code>i!=n</code> पंक्ति 5 में बेहतर ढंग से संशोधित किया जाना चाहिए <code>i<n</code>, नाजायज नकारात्मक मूल्यों के लिए अंतहीन लूपिंग से बचने के लिए <code>n</code>. हालाँकि सहज रूप से कोड में इस बदलाव से कोई फर्क नहीं पड़ना चाहिए, लेकिन इसके सही होने की ओर ले जाने वाला तर्क कुछ अधिक जटिल हो जाता है, तभी से <code>i>=n</code> पंक्ति 13 में ज्ञात है। उसे भी प्राप्त करने के लिए <code>i<=n</code> धारण करता है, उस शर्त को लूप इनवेरिएंट में शामिल करना होगा। यह देखना आसान है <code>i<=n</code>, भी, लूप का एक अपरिवर्तनीय है <code>i<n</code> पंक्ति 6 ​​में पंक्ति 5 में (संशोधित) लूप स्थिति से प्राप्त किया जा सकता है, और इसलिए <code>i<=n</code> के बाद पंक्ति 11 में रहता है <code>i</code> पंक्ति 10 में वृद्धि की गई है। हालाँकि, जब औपचारिक कार्यक्रम सत्यापन के लिए लूप इनवेरिएंट को मैन्युअल रूप से प्रदान करना पड़ता है, तो ऐसे सहज रूप से बहुत स्पष्ट गुण होते हैं <code>i<=n</code> अक्सर नजरअंदाज कर दिया जाता है.


==फ्लोयड-होरे तर्क==
==फ्लोयड-होरे तर्क==
होरे तर्क में|फ्लोयड-होरे तर्क,<ref>{{cite book  
फ्लोयड-होरे तर्क,<ref>{{cite book  
  | contribution-url=http://www.cse.chalmers.se/edu/year/2017/course/TDA384_LP1/files/lectures/additional-material/AssigningMeanings1967.pdf
  | contribution-url=http://www.cse.chalmers.se/edu/year/2017/course/TDA384_LP1/files/lectures/additional-material/AssigningMeanings1967.pdf
  | author=Robert W. Floyd
  | author=Robert W. Floyd
Line 67: Line 60:


:<math>\frac{\{C\land I\}\;\mathrm{body}\;\{I\}} {\{I\}\;\mathtt{while}\ (C)\ \mathrm{body}\;\{\lnot C\land I\}}</math>
:<math>\frac{\{C\land I\}\;\mathrm{body}\;\{I\}} {\{I\}\;\mathtt{while}\ (C)\ \mathrm{body}\;\{\lnot C\land I\}}</math>
इसका मतलब यह है:
इसका अर्थ यह है:
*यदि कुछ संपत्ति {{mvar|I}} कोड द्वारा संरक्षित है <math>\mathrm{body}</math> -अधिक सटीक रूप से, यदि {{mvar|I}} के निष्पादन के बाद धारण करता है <math>\mathrm{body}</math> जब भी दोनों {{mvar|C}} और {{mvar|I}} पहले से आयोजित - (ऊपरी पंक्ति) फिर
*यदि कुछ गुण {{mvar|I}} को कोड <math>\mathrm{body}</math> द्वारा संरक्षित किया जाता है -अधिक स्पष्ट रूप से, यदि {{mvar|I}} <math>\mathrm{body}</math> के निष्पादन के बाद धारण करता है, जब भी दोनों {{mvar|C}} और {{mvar|I}} पहले से होल्ड करते हैं - (ऊपरी पंक्ति) फिर
* {{mvar|C}} और {{mvar|I}} पूरे लूप के निष्पादन के बाद क्रमशः गलत और सत्य होने की गारंटी है <math>\mathtt{while}\ (C)\ \mathrm{body}</math>, बशर्ते {{mvar|I}} लूप (निचली रेखा) से पहले सत्य था।
* {{mvar|C}} और {{mvar|I}} पूरे लूप के निष्पादन के बाद क्रमशः असत्य और सत्य होने की गारंटी <math>\mathtt{while}\ (C)\ \mathrm{body}</math> है, बशर्ते {{mvar|I}} लूप (निचली रेखा) से पहले सत्य था।


दूसरे शब्दों में: उपरोक्त नियम एक निगमनात्मक कदम है जिसका आधार [[होरे ट्रिपल]] है <math>\{C\land I\}\;\mathrm{body}\;\{I\}</math>. यह त्रिगुण वास्तव में मशीन अवस्थाओं पर एक [[संबंध (गणित)]] है। यह तब भी लागू होता है जब बूलियन अभिव्यक्ति एक ऐसी स्थिति से शुरू होती है <math>C\land I</math> सत्य है और कुछ कोड को सफलतापूर्वक निष्पादित कर रहा है <math>\mathrm{body}</math>, मशीन ऐसी स्थिति में समाप्त हो जाती है {{mvar|I}} क्या सच है। यदि यह संबंध सिद्ध किया जा सकता है, तो नियम हमें कार्यक्रम के सफल निष्पादन का निष्कर्ष निकालने की अनुमति देता है <math>\mathtt{while}\ (C)\ \mathrm{body}</math> जिस राज्य से नेतृत्व करेंगे {{mvar|I}} उस स्थिति के लिए सत्य है जिसमें <math>\lnot C\land I</math> धारण करता है. बूलियन सूत्र {{mvar|I}} इस नियम को लूप इनवेरिएंट कहा जाता है।
दूसरे शब्दों में: उपरोक्त नियम निगमनात्मक चरण है, जिसका आधार <math>\{C\land I\}\;\mathrm{body}\;\{I\}</math> [[होरे ट्रिपल]] है। यह त्रिगुण वास्तव में मशीन अवस्थाओं पर [[संबंध (गणित)]] है। यह तब भी प्रयुक्त होता है, जब बूलियन अभिव्यक्ति ऐसी स्थिति से प्रारंभ होती है, <math>C\land I</math> सत्य है और कुछ कोड <math>\mathrm{body}</math> को सफलतापूर्वक निष्पादित कर रहा है, मशीन ऐसी स्थिति में समाप्त हो जाती है {{mvar|I}} क्या सत्य है। यदि यह संबंध सिद्ध किया जा सकता है, तो नियम <math>\mathtt{while}\ (C)\ \mathrm{body}</math> हमें कार्यक्रम के सफल निष्पादन का निष्कर्ष निकालने की अनुमति देता है, जिस स्थिति से नेतृत्व करेंगे {{mvar|I}} उस स्थिति के लिए सत्य है जिसमें <math>\lnot C\land I</math> धारण करता है। बूलियन सूत्र {{mvar|I}} नियम को लूप इनवेरिएंट कहा जाता है।


प्रयुक्त नोटेशन में कुछ भिन्नताओं के साथ, और इस आधार पर कि लूप रुक जाता है, इस नियम को अपरिवर्तनीय संबंध प्रमेय के रूप में भी जाना जाता है।<ref name="conway-gries">{{cite book |last1=Conway |first1=Richard |author-link1=Richard W. Conway |last2=Gries |first2=David |author-link2=David Gries|year=1973 |title=An Introduction to Programming: A Structured Approach using PL/1 and PL/C |publisher=Winthrop |location=Cambridge, Massachusetts | pages=198–200 }}</ref><ref>{{cite book | title=परीक्षण और विश्लेषण के माध्यम से सॉफ़्टवेयर त्रुटि का पता लगाना| author-first=J. C. | author-last= Huang | publisher=John Wiley & Sons |location= Hoboken, New Jersey | year= 2009 | pages=156–157 }}</ref> जैसा कि 1970 के दशक की एक पाठ्यपुस्तक इसे छात्र प्रोग्रामरों के लिए सुलभ बनाने के तरीके से प्रस्तुत करती है:<ref name="conway-gries"/>
प्रयुक्त संकेतन में कुछ भिन्नताओं के साथ, और इस आधार पर कि लूप रुक जाता है, इस नियम को अपरिवर्तनीय संबंध प्रमेय के रूप में भी जाना जाता है।<ref name="conway-gries">{{cite book |last1=Conway |first1=Richard |author-link1=Richard W. Conway |last2=Gries |first2=David |author-link2=David Gries|year=1973 |title=An Introduction to Programming: A Structured Approach using PL/1 and PL/C |publisher=Winthrop |location=Cambridge, Massachusetts | pages=198–200 }}</ref><ref>{{cite book | title=परीक्षण और विश्लेषण के माध्यम से सॉफ़्टवेयर त्रुटि का पता लगाना| author-first=J. C. | author-last= Huang | publisher=John Wiley & Sons |location= Hoboken, New Jersey | year= 2009 | pages=156–157 }}</ref> जैसा कि 1970 के दशक की पाठ्यपुस्तक इसे छात्र प्रोग्रामरों के लिए सुलभ बनाने की विधियों से प्रस्तुत करती है:<ref name="conway-gries"/>


चलो संकेतन <code>P { seq } Q</code> मतलब कि अगर <code>P</code> कथनों के अनुक्रम से पहले सत्य है <code>seq</code> फिर भागो <code>Q</code> इसके बाद सच है. तब अपरिवर्तनीय संबंध प्रमेय यही मानता है
मान लीजिए कि संकेतन <code>P { seq } Q</code> का अर्थ है कि यदि कथनों के क्रम <code>seq</code> चलने से पहले <code>P</code> सत्य है, तो उसके बाद <code>Q</code> सत्य है। तब अपरिवर्तनीय संबंध प्रमेय यही मानता है


:<code>P & c { seq } P</code>
:<code>P & c { seq } P</code>
Line 83: Line 76:


===उदाहरण===
===उदाहरण===
निम्नलिखित उदाहरण दिखाता है कि यह नियम कैसे काम करता है। कार्यक्रम पर विचार करें
निम्नलिखित उदाहरण दिखाता है कि यह नियम कैसे काम करता है। कार्यक्रम पर विचार करें<syntaxhighlight>
while (x < 10)
    x := x+1;
</syntaxhighlight>


जबकि (x <10)
फिर कोई निम्नलिखित होरे ट्रिपल को प्रमाणित कर सकता है:
    एक्स := एक्स+1;
 
फिर कोई निम्नलिखित होरे ट्रिपल को साबित कर सकता है:


:<math>\{x\leq10\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{x=10\}</math>
:<math>\{x\leq10\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{x=10\}</math>
की स्थिति सी <code>while</code> लूप है <math>x<10</math>. एक उपयोगी लूप अपरिवर्तनीय {{mvar|I}} अनुमान लगाना होगा; ऐसा हो जायेगा <math>x\leq10</math> उपयुक्त है। इन धारणाओं के तहत निम्नलिखित होरे ट्रिपल को साबित करना संभव है:
<code>while</code> लूप की C स्थिति <math>x<10</math> है। {{mvar|I}} उपयोगी लूप अपरिवर्तनीय का अनुमान लगाना होगा; इससे पता चलेगा कि <math>x\leq10</math> उपयुक्त है। इन धारणाओं के अनुसार निम्नलिखित होरे ट्रिपल को प्रमाणित करना संभव है:


:<math>\{x<10 \land x\leq10\}\; x := x+1 \;\{x\leq10\}</math>
:<math>\{x<10 \land x\leq10\}\; x := x+1 \;\{x\leq10\}</math>
हालाँकि इस ट्रिपल को औपचारिक रूप से फ्लोयड-होरे लॉजिक गवर्निंग असाइनमेंट के नियमों से प्राप्त किया जा सकता है, यह सहज रूप से उचित भी है: गणना उस स्थिति में शुरू होती है जहां <math>x<10 \land x\leq10</math> सत्य है, जिसका सीधा सा अर्थ है <math>x<10</math> क्या सच है। गणना में 1 जोड़ा जाता है {{mvar|x}}, जिसका अर्थ है कि <math>x\leq10</math> अभी भी सत्य है (पूर्णांक x के लिए)।
चूँकि इस ट्रिपल को औपचारिक रूप से फ्लोयड-होरे लॉजिक गवर्निंग असाइनमेंट के नियमों से प्राप्त किया जा सकता है, यह सहज रूप से उचित भी है: गणना उस स्थिति में शुरू होती है जहां <math>x<10 \land x\leq10</math> सत्य है, जिसका सीधा सा अर्थ है, <math>x<10</math> क्या सत्य है। {{mvar|x}} की गणना में 1 जोड़ा जाता है, जिसका अर्थ है कि <math>x\leq10</math> अभी भी सत्य है (पूर्णांक x के लिए)।


इस आधार के अंतर्गत, नियम के लिए <code>while</code> लूप्स निम्नलिखित निष्कर्ष की अनुमति देता है:
इस आधार के अंतर्गत, नियम के लिए <code>while</code> लूप्स निम्नलिखित निष्कर्ष की अनुमति देता है:


:<math>\{x\leq10\}\; \mathtt{while}\ (x<10)\ x := x+1 \;\{\lnot(x<10) \land x\leq10\}</math>
:<math>\{x\leq10\}\; \mathtt{while}\ (x<10)\ x := x+1 \;\{\lnot(x<10) \land x\leq10\}</math>
हालाँकि, बाद की स्थिति <math>\lnot(x<10)\land x\leq10</math> ({{mvar|x}} 10 से कम या उसके बराबर है, लेकिन यह 10 से कम नहीं है) [[तार्किक तुल्यता]] है <math>x=10</math>, जो हम दिखाना चाहते थे।
चूँकि, बाद की स्थिति <math>\lnot(x<10)\land x\leq10</math> ({{mvar|x}} 10 से कम या उसके बराबर है, लेकिन यह 10 से कम नहीं है) [[तार्किक तुल्यता]] <math>x=10</math> है, जो हम दिखाना चाहते थे।
 
गुण <math>0 \leq x</math> उदाहरण लूप का एक और अपरिवर्तनीय और तुच्छ गुण <math>\mathrm{true}</math> है।


संपत्ति <math>0 \leq x</math> उदाहरण लूप का एक और अपरिवर्तनीय और तुच्छ गुण है <math>\mathrm{true}</math> एक और है.
उपरोक्त अनुमान नियम को पूर्व अपरिवर्तनीय पैदावार पर प्रयुक्त करना <math>\{0 \leq x\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{10 \leq x\}</math>.
उपरोक्त अनुमान नियम को पूर्व अपरिवर्तनीय पैदावार पर लागू करना <math>\{0 \leq x\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{10 \leq x\}</math>.
इसे अपरिवर्तनीय पर प्रयुक्त करना <math>\mathrm{true}</math> पैदावार <math>\{\mathrm{true}\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{10 \leq x\}</math>, जो थोड़ा अधिक अभिव्यंजक है।
इसे अपरिवर्तनीय पर लागू करना <math>\mathrm{true}</math> पैदावार <math>\{\mathrm{true}\}\; \mathtt{while}\ (x<10)\ x := x+1\;\{10 \leq x\}</math>, जो थोड़ा अधिक अभिव्यंजक है।


==प्रोग्रामिंग भाषा समर्थन==
==प्रोग्रामिंग भाषा समर्थन==


===एफिल===
===एफिल===
[[एफिल (प्रोग्रामिंग भाषा)]] प्रोग्रामिंग भाषा लूप इनवेरिएंट के लिए मूल समर्थन प्रदान करती है।<ref>[[Bertrand Meyer|Meyer, Bertrand]], ''Eiffel: The Language,'' [[Prentice Hall]], 1991, pp. 129–131.</ref> एक लूप इनवेरिएंट को [[ वर्ग अपरिवर्तनीय ]] के लिए उपयोग किए गए समान सिंटैक्स के साथ व्यक्त किया जाता है। नीचे दिए गए नमूने में, लूप अपरिवर्तनीय अभिव्यक्ति <code>x&nbsp;<=&nbsp;10</code> लूप आरंभीकरण के बाद और लूप बॉडी के प्रत्येक निष्पादन के बाद सत्य होना चाहिए; इसे रनटाइम पर जांचा जाता है।
[[एफिल (प्रोग्रामिंग भाषा)]] प्रोग्रामिंग भाषा लूप इनवेरिएंट के लिए मूल समर्थन प्रदान करती है।<ref>[[Bertrand Meyer|Meyer, Bertrand]], ''Eiffel: The Language,'' [[Prentice Hall]], 1991, pp. 129–131.</ref> लूप इनवेरिएंट को [[ वर्ग अपरिवर्तनीय |वर्ग अपरिवर्तनीय]] के लिए उपयोग किए गए समान सिंटैक्स के साथ व्यक्त किया जाता है। नीचे दिए गए नमूने में, लूप अपरिवर्तनीय अभिव्यक्ति <code>x&nbsp;<=&nbsp;10</code> लूप आरंभीकरण के बाद और लूप बॉडी के प्रत्येक निष्पादन के बाद सत्य होना चाहिए; इसे रनटाइम पर जांचा जाता है।


<syntaxhighlight lang="eiffel">    from
<syntaxhighlight lang="eiffel">    from
Line 148: Line 143:
</syntaxhighlight>
</syntaxhighlight>


  <code>max()</code> e> फ़ंक्शन पूर्णांक सरणी में सबसे बड़ा तत्व निर्धारित करता है। इसे परिभाषित करने के लिए, सरणी में कम से कम एक तत्व होना चाहिए। के बाद की शर्तें <code>max()</code> आवश्यक है कि लौटाया गया मान है: (1) किसी भी तत्व से छोटा नहीं; और, (2) कि यह कम से कम एक तत्व से मेल खाता हो। लूप इनवेरिएंट को दो के माध्यम से आगमनात्मक रूप से परिभाषित किया गया है <code>where</code> खंड, जिनमें से प्रत्येक पोस्टकंडीशन में एक खंड से मेल खाता है। मूलभूत अंतर यह है कि लूप इनवेरिएंट का प्रत्येक खंड परिणाम को वर्तमान तत्व तक सही होने की पहचान करता है <code>i</code>, जबकि पोस्टकंडिशन परिणाम को सभी तत्वों के लिए सही होने की पहचान करता है।
  <code>max()</code> e> फलन पूर्णांक सरणी में सबसे बड़ा तत्व निर्धारित करता है। इसे परिभाषित करने के लिए, सरणी में कम से कम एक तत्व होना चाहिए। के बाद के नियम <code>max()</code> आवश्यक है कि लौटाया गया मान है: (1) किसी भी तत्व से छोटा नहीं; और, (2) कि यह कम से कम एक तत्व से मेल खाता हो। लूप इनवेरिएंट को दो के माध्यम से आगमनात्मक रूप से परिभाषित किया गया है <code>where</code> खंड, जिनमें से प्रत्येक पोस्टकंडीशन में एक खंड से मेल खाता है। मूलभूत अंतर यह है कि लूप इनवेरिएंट का प्रत्येक खंड परिणाम को वर्तमान तत्व तक सही होने की पहचान करता है <code>i</code>, जबकि पोस्टकंडिशन परिणाम को सभी तत्वों के लिए सही होने की पहचान करता है।


==लूप इनवेरिएंट का उपयोग==
==लूप इनवेरिएंट का उपयोग==


एक लूप इनवेरिएंट निम्नलिखित उद्देश्यों में से एक को पूरा कर सकता है:
लूप इनवेरिएंट निम्नलिखित उद्देश्यों में से एक को पूरा कर सकता है:
# विशुद्ध रूप से वृत्तचित्र
# विशुद्ध रूप से वृत्तचित्र
# को कोड के भीतर जांचा जाना चाहिए, उदा. एक अभिकथन कॉल द्वारा
# को कोड के अन्दर जांचा जाना चाहिए, उदाहरण अभिकथन कॉल द्वारा
# होरे तर्क|फ्लोयड-होरे दृष्टिकोण के आधार पर सत्यापित किया जाना है
# होरे तर्क|फ्लोयड-होरे दृष्टिकोण के आधार पर सत्यापित किया जाना है


1. के लिए, एक प्राकृतिक भाषा टिप्पणी (जैसे <code>// m equals the maximum value in a[0...i-1]</code> #अनौपचारिक उदाहरण उदाहरण में) पर्याप्त है।
1. के लिए, प्राकृतिक भाषा टिप्पणी (जैसे <code>// m equals the maximum value in a[0...i-1]</code> अनौपचारिक उदाहरण में) पर्याप्त है।


2. के लिए, प्रोग्रामिंग भाषा समर्थन की आवश्यकता है, जैसे सी (प्रोग्रामिंग भाषा) लाइब्रेरीassert.h, या #एफिल-दिखाया गया <code>invariant</code> एफिल में खंड. अक्सर, कंपाइलर या रनटाइम विकल्प द्वारा रन-टाइम चेकिंग को चालू (डिबगिंग रन के लिए) और बंद (प्रोडक्शन रन के लिए) किया जा सकता है।{{citation needed|reason=hope that C's or/and Eiffel assert.h supports that?|date=May 2016}}
2. के लिए, प्रोग्रामिंग भाषा समर्थन की आवश्यकता है, जैसे C (प्रोग्रामिंग भाषा) लाइब्रेरी assert.h, या एफिल-दिखाया गया <code>invariant</code> एफिल में खंड. अधिकांशतः, कंपाइलर या रनटाइम विकल्प द्वारा रन-टाइम चेकिंग को प्रारंभ (डिबगिंग रन के लिए) और बंद (प्रोडक्शन रन के लिए) किया जा सकता है।


3. के लिए, गणितीय प्रमाणों का समर्थन करने के लिए कुछ उपकरण मौजूद हैं, जो आमतौर पर #फ्लोयड-होरे तर्क-दिखाए गए फ़्लॉइड-होरे नियम पर आधारित होते हैं, कि एक दिया गया लूप कोड वास्तव में दिए गए (सेट) लूप इनवेरिएंट को संतुष्ट करता है।
3. के लिए, गणितीय प्रमाणों का समर्थन करने के लिए कुछ उपकरण उपस्थित हैं, जो सामान्यतः फ्लोयड-होरे तर्क-दिखाए गए फ़्लॉइड-होरे नियम पर आधारित होते हैं, कि दिया गया लूप कोड वास्तव में दिए गए (सेट) लूप इनवेरिएंट को संतुष्ट करता है।


[[अमूर्त व्याख्या]] की तकनीक का उपयोग दिए गए कोड के लूप इनवेरिएंट का स्वचालित रूप से पता लगाने के लिए किया जा सकता है। हालाँकि, यह दृष्टिकोण बहुत ही सरल अपरिवर्तनीयों तक ही सीमित है (जैसे <code>0<=i && i<=n && i%2==0</code>).
[[अमूर्त व्याख्या]] की तकनीक का उपयोग दिए गए कोड के लूप इनवेरिएंट का स्वचालित रूप से पता लगाने के लिए किया जा सकता है। चूँकि, यह दृष्टिकोण बहुत ही सरल अपरिवर्तनीयों तक ही सीमित है (जैसे <code>0<=i && i<=n && i%2==0</code>)


==लूप-अपरिवर्तनीय कोड से अंतर==
==लूप-अपरिवर्तनीय कोड से अंतर==
{{see|Loop-invariant code motion}}
{{see|लूप-अपरिवर्तनीय कोड गति}}
लूप-इनवेरिएंट कोड में ऐसे कथन या अभिव्यक्ति शामिल होते हैं जिन्हें प्रोग्राम शब्दार्थ को प्रभावित किए बिना लूप बॉडी के बाहर ले जाया जा सकता है। ऐसे परिवर्तन, जिन्हें [[ लूप-अपरिवर्तनीय कोड गति ]] कहा जाता है, कुछ कंपाइलरों द्वारा कंपाइलर प्रोग्राम को अनुकूलित करने के लिए किए जाते हैं।
 
एक लूप-इनवेरिएंट कोड उदाहरण (सी (प्रोग्रामिंग भाषा) में) है
लूप-इनवेरिएंट कोड में ऐसे कथन या अभिव्यक्ति सम्मिलित होते हैं जिन्हें प्रोग्राम शब्दार्थ को प्रभावित किए बिना लूप बॉडी के बाहर ले जाया जा सकता है। ऐसे परिवर्तन, जिन्हें [[ लूप-अपरिवर्तनीय कोड गति |लूप-अपरिवर्तनीय कोड गति]] कहा जाता है, कुछ कंपाइलरों द्वारा कंपाइलर प्रोग्राम को अनुकूलित करने के लिए किए जाते हैं। लूप-इनवेरिएंट कोड उदाहरण (C (प्रोग्रामिंग भाषा) में) है
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
for (int i=0; i<n; ++i) {
for (int i=0; i<n; ++i) {
Line 183: Line 178:
}
}
</syntaxhighlight>
</syntaxhighlight>
इसके विपरीत, उदा. संपत्ति <code>0<=i && i<=n</code> मूल और अनुकूलित प्रोग्राम दोनों के लिए एक लूप अपरिवर्तनीय है, लेकिन यह कोड का हिस्सा नहीं है, इसलिए इसे लूप से बाहर ले जाने की बात करने का कोई मतलब नहीं है।
इसके विपरीत, उदा. गुण <code>0<=i && i<=n</code> मूल और अनुकूलित प्रोग्राम दोनों के लिए लूप अपरिवर्तनीय है, लेकिन यह कोड का हिस्सा नहीं है, इसलिए इसे लूप से बाहर ले जाने की बात करने का कोई अर्थ नहीं है।


लूप-इनवेरिएंट कोड संबंधित लूप-इनवेरिएंट संपत्ति को प्रेरित कर सकता है।{{clarify|reason=I guess, once the notion of 'loop-invariant code' is defined in a sufficiently formal way, it can be proven that loop-invariant code *always* induces a corresponding loop invariant property.|date=March 2016}} उपरोक्त उदाहरण के लिए, इसे देखने का सबसे आसान तरीका एक प्रोग्राम पर विचार करना है जहां लूप इनवेरिएंट कोड की गणना लूप के पहले और भीतर दोनों जगह की जाती है:
लूप-इनवेरिएंट कोड संबंधित लूप-इनवेरिएंट गुण को प्रेरित कर सकता है। उपरोक्त उदाहरण के लिए, इसे देखने की सबसे आसान विधि प्रोग्राम पर विचार करना है, जहां लूप इनवेरिएंट कोड की गणना लूप के पहले और अन्दर दोनों जगह की जाती है:
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
x1 = y+z;
x1 = y+z;
Line 194: Line 189:
}
}
</syntaxhighlight>
</syntaxhighlight>
इस कोड की एक लूप-अपरिवर्तनीय संपत्ति है <code>(x1==x2 && t1==x2*x2) || i==0</code>, यह दर्शाता है कि लूप से पहले गणना किए गए मान भीतर गणना किए गए मानों से सहमत हैं (पहले पुनरावृत्ति से पहले को छोड़कर)।
इस कोड की लूप-अपरिवर्तनीय गुण <code>(x1==x2 && t1==x2*x2) || i==0</code> है, यह दर्शाता है कि लूप से पहले गणना किए गए मान अन्दर गणना किए गए मानों से सहमत हैं (पहले पुनरावृत्ति से पहले को छोड़कर)।


== यह भी देखें ==
== यह भी देखें ==
Line 200: Line 195:
* लूप-अपरिवर्तनीय कोड गति
* लूप-अपरिवर्तनीय कोड गति
* [[लूप वैरिएंट]]
* [[लूप वैरिएंट]]
* विधेय ट्रांसफार्मर शब्दार्थ#व्हाइल लूप|व्हाइल लूप की सबसे कमजोर-पूर्व शर्ते
* विधेय ट्रांसफार्मर शब्दार्थ व्हाइल लूप की सबसे कमजोर-पूर्व नियम


== संदर्भ ==
== संदर्भ ==
Line 214: Line 209:
* Michael Huth, Mark Ryan. "[https://books.google.com/books?id=eUggAwAAQBAJ&q=%22loop+invariant%22 Logic in Computer Science].", Second Edition.
* Michael Huth, Mark Ryan. "[https://books.google.com/books?id=eUggAwAAQBAJ&q=%22loop+invariant%22 Logic in Computer Science].", Second Edition.


{{DEFAULTSORT:Loop Invariant}}[[Category: औपचारिक तरीके]] [[Category: बहाव को काबू करें]]
{{DEFAULTSORT:Loop Invariant}}
 
 


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Loop Invariant]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023|Loop Invariant]]
[[Category:Lua-based templates|Loop Invariant]]
[[Category:Machine Translated Page|Loop Invariant]]
[[Category:Pages with script errors|Loop Invariant]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Templates Vigyan Ready|Loop Invariant]]
[[Category:Templates that add a tracking category|Loop Invariant]]
[[Category:Templates that generate short descriptions|Loop Invariant]]
[[Category:Templates using TemplateData|Loop Invariant]]
[[Category:औपचारिक तरीके|Loop Invariant]]
[[Category:बहाव को काबू करें|Loop Invariant]]

Latest revision as of 10:17, 28 July 2023

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

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

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

लूप और प्रत्यावर्तन प्रोग्राम की समानता के कारण, इनवेरिएंट के साथ लूप की आंशिक शुद्धता प्रमाणित करना संरचनात्मक प्रेरण के माध्यम से रिकर्सिव प्रोग्राम की शुद्धता प्रमाणित करने के समान है। वास्तव में, लूप इनवेरिएंट अधिकांशतः किसी दिए गए लूप के समतुल्य पुनरावर्ती कार्यक्रम के लिए सिद्ध की जाने वाली आगमनात्मक परिकल्पना के समान होता है।

अनौपचारिक उदाहरण

निम्नलिखित C (प्रोग्रामिंग भाषा) सबरूटीन max() अपने तर्क सरणी a[] में अधिकतम मान लौटाता है, इसकी लंबाई प्रदान की गई n कम से कम 1 हो। टिप्पणियाँ पंक्तियों 3, 6, 9, 11 और 13 पर प्रदान की जाती हैं। प्रत्येक टिप्पणी फलन के उस चरण में एक या अधिक चर के मूल्यों के बारे में सत्यापन करती है। लूप बॉडी के अन्दर, लूप के प्रारंभ और अंत में हाइलाइट किए गए प्रमाण (पंक्तियाँ 6 और 11), बिल्कुल समान हैं। इस प्रकार वे लूप की अपरिवर्तनीय गुण का वर्णन करते हैं। जब पंक्ति 13 पर पहुँच जाता है, तब भी यह अपरिवर्तनीय रहता है, और यह ज्ञात होता है कि पंक्ति 5 से लूप की स्थिति i!=n असत्य हो गयी है। दोनों गुण मिलकर यही दर्शाते हैं कि m में अधिकतम मान a[0...n-1] के बराबर है, अर्थात्, पंक्ति 14 से सही मान लौटाया जाता है।

int max(int n, const int a[]) {
    int m = a[0];
    // m equals the maximum value in a[0...0]
    int i = 1;
    while (i != n) {
        // m equals the maximum value in a[0...i-1]
        if (m < a[i])
            m = a[i];
        // m equals the maximum value in a[0...i]
        ++i;
        // m equals the maximum value in a[0...i-1]
    }
    // m equals the maximum value in a[0...i-1], and i==n
    return m;
}

रक्षात्मक प्रोग्रामिंग प्रतिमान का पालन करते हुए, पंक्ति 5 में लूप स्थिति i!=n को उत्तम ढंग से i<n संशोधित किया जाना चाहिए, जिससे n के अवैध नकारात्मक मूल्यों के लिए अंतहीन लूपिंग से बचा जा सके। चूँकि सहज रूप से कोड में इस परिवर्तन से कोई फर्क नहीं पड़ना चाहिए, लेकिन इसके सही होने की ओर ले जाने वाला तर्क कुछ अधिक जटिल हो जाता है, तभी से पंक्ति 13 में केवल i>=n ज्ञात है। इसे प्राप्त करने के लिए i<=n का भी मानना है, स्थिति को लूप इनवेरिएंट में सम्मिलित करना होगा। यह देखना सरल है कि i<=n भी लूप का अपरिवर्तनीय है, क्योंकि पंक्ति 6 में i<n पंक्ति 5 में (संशोधित) लूप स्थिति से प्राप्त किया जा सकता है, और इसलिए i<=n पंक्ति में रहता है, 11 के बाद i को पंक्ति 10 में बढ़ा दिया गया है। चूँकि, जब औपचारिक कार्यक्रम सत्यापन के लिए लूप इनवेरिएंट को मैन्युअल रूप से प्रदान करना पड़ता है, तो i<=n जैसे सहज रूप से स्पष्ट गुणों को अधिकांशतः अनदेखा कर दिया जाता है।

फ्लोयड-होरे तर्क

फ्लोयड-होरे तर्क,[2][3] थोड़ी देर के लूप की आंशिक शुद्धता अनुमान के निम्नलिखित नियम द्वारा नियंत्रित होती है:

इसका अर्थ यह है:

  • यदि कुछ गुण I को कोड द्वारा संरक्षित किया जाता है -अधिक स्पष्ट रूप से, यदि I के निष्पादन के बाद धारण करता है, जब भी दोनों C और I पहले से होल्ड करते हैं - (ऊपरी पंक्ति) फिर
  • C और I पूरे लूप के निष्पादन के बाद क्रमशः असत्य और सत्य होने की गारंटी है, बशर्ते I लूप (निचली रेखा) से पहले सत्य था।

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

प्रयुक्त संकेतन में कुछ भिन्नताओं के साथ, और इस आधार पर कि लूप रुक जाता है, इस नियम को अपरिवर्तनीय संबंध प्रमेय के रूप में भी जाना जाता है।[4][5] जैसा कि 1970 के दशक की पाठ्यपुस्तक इसे छात्र प्रोग्रामरों के लिए सुलभ बनाने की विधियों से प्रस्तुत करती है:[4]

मान लीजिए कि संकेतन P { seq } Q का अर्थ है कि यदि कथनों के क्रम seq चलने से पहले P सत्य है, तो उसके बाद Q सत्य है। तब अपरिवर्तनीय संबंध प्रमेय यही मानता है

P & c { seq } P
तात्पर्य
P { DO WHILE (c); seq END; } P & ¬c


उदाहरण

निम्नलिखित उदाहरण दिखाता है कि यह नियम कैसे काम करता है। कार्यक्रम पर विचार करें

while (x < 10)
    x := x+1;


फिर कोई निम्नलिखित होरे ट्रिपल को प्रमाणित कर सकता है:

while लूप की C स्थिति है। I उपयोगी लूप अपरिवर्तनीय का अनुमान लगाना होगा; इससे पता चलेगा कि उपयुक्त है। इन धारणाओं के अनुसार निम्नलिखित होरे ट्रिपल को प्रमाणित करना संभव है:

चूँकि इस ट्रिपल को औपचारिक रूप से फ्लोयड-होरे लॉजिक गवर्निंग असाइनमेंट के नियमों से प्राप्त किया जा सकता है, यह सहज रूप से उचित भी है: गणना उस स्थिति में शुरू होती है जहां सत्य है, जिसका सीधा सा अर्थ है, क्या सत्य है। x की गणना में 1 जोड़ा जाता है, जिसका अर्थ है कि अभी भी सत्य है (पूर्णांक x के लिए)।

इस आधार के अंतर्गत, नियम के लिए while लूप्स निम्नलिखित निष्कर्ष की अनुमति देता है:

चूँकि, बाद की स्थिति (x 10 से कम या उसके बराबर है, लेकिन यह 10 से कम नहीं है) तार्किक तुल्यता है, जो हम दिखाना चाहते थे।

गुण उदाहरण लूप का एक और अपरिवर्तनीय और तुच्छ गुण है।

उपरोक्त अनुमान नियम को पूर्व अपरिवर्तनीय पैदावार पर प्रयुक्त करना . इसे अपरिवर्तनीय पर प्रयुक्त करना पैदावार , जो थोड़ा अधिक अभिव्यंजक है।

प्रोग्रामिंग भाषा समर्थन

एफिल

एफिल (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा लूप इनवेरिएंट के लिए मूल समर्थन प्रदान करती है।[6] लूप इनवेरिएंट को वर्ग अपरिवर्तनीय के लिए उपयोग किए गए समान सिंटैक्स के साथ व्यक्त किया जाता है। नीचे दिए गए नमूने में, लूप अपरिवर्तनीय अभिव्यक्ति x <= 10 लूप आरंभीकरण के बाद और लूप बॉडी के प्रत्येक निष्पादन के बाद सत्य होना चाहिए; इसे रनटाइम पर जांचा जाता है।

    from
        x := 0
    invariant
        x <= 10
    until
        x > 10
    loop
        x := x + 1
    end


जबकि

वाइली (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा लूप इनवेरिएंट के लिए प्रथम श्रेणी का समर्थन भी प्रदान करती है।[7] लूप इनवेरिएंट को एक या अधिक का उपयोग करके व्यक्त किया जाता है where उपवाक्य, जैसा कि निम्नलिखित में दर्शाया गया है:

function max(int[] items) -> (int r)
// Requires at least one element to compute max
requires |items| > 0
// (1) Result is not smaller than any element
ensures all { i in 0..|items| | items[i] <= r }
// (2) Result matches at least one element
ensures some { i in 0..|items| | items[i] == r }:
    //
    nat i = 1
    int m = items[0]
    //
    while i < |items|
    // (1) No item seen so far is larger than m
    where all { k in 0..i | items[k] <= m }
    // (2) One or more items seen so far matches m
    where some { k in 0..i | items[k] == m }:
        if items[i] > m:
            m = items[i]
        i = i + 1
    //
    return m
max() e> फलन पूर्णांक सरणी में सबसे बड़ा तत्व निर्धारित करता है। इसे परिभाषित करने के लिए, सरणी में कम से कम एक तत्व होना चाहिए। के बाद के नियम max() आवश्यक है कि लौटाया गया मान है: (1) किसी भी तत्व से छोटा नहीं; और, (2) कि यह कम से कम एक तत्व से मेल खाता हो। लूप इनवेरिएंट को दो के माध्यम से आगमनात्मक रूप से परिभाषित किया गया है where खंड, जिनमें से प्रत्येक पोस्टकंडीशन में एक खंड से मेल खाता है। मूलभूत अंतर यह है कि लूप इनवेरिएंट का प्रत्येक खंड परिणाम को वर्तमान तत्व तक सही होने की पहचान करता है i, जबकि पोस्टकंडिशन परिणाम को सभी तत्वों के लिए सही होने की पहचान करता है।

लूप इनवेरिएंट का उपयोग

लूप इनवेरिएंट निम्नलिखित उद्देश्यों में से एक को पूरा कर सकता है:

  1. विशुद्ध रूप से वृत्तचित्र
  2. को कोड के अन्दर जांचा जाना चाहिए, उदाहरण अभिकथन कॉल द्वारा
  3. होरे तर्क|फ्लोयड-होरे दृष्टिकोण के आधार पर सत्यापित किया जाना है

1. के लिए, प्राकृतिक भाषा टिप्पणी (जैसे // m equals the maximum value in a[0...i-1] अनौपचारिक उदाहरण में) पर्याप्त है।

2. के लिए, प्रोग्रामिंग भाषा समर्थन की आवश्यकता है, जैसे C (प्रोग्रामिंग भाषा) लाइब्रेरी assert.h, या एफिल-दिखाया गया invariant एफिल में खंड. अधिकांशतः, कंपाइलर या रनटाइम विकल्प द्वारा रन-टाइम चेकिंग को प्रारंभ (डिबगिंग रन के लिए) और बंद (प्रोडक्शन रन के लिए) किया जा सकता है।

3. के लिए, गणितीय प्रमाणों का समर्थन करने के लिए कुछ उपकरण उपस्थित हैं, जो सामान्यतः फ्लोयड-होरे तर्क-दिखाए गए फ़्लॉइड-होरे नियम पर आधारित होते हैं, कि दिया गया लूप कोड वास्तव में दिए गए (सेट) लूप इनवेरिएंट को संतुष्ट करता है।

अमूर्त व्याख्या की तकनीक का उपयोग दिए गए कोड के लूप इनवेरिएंट का स्वचालित रूप से पता लगाने के लिए किया जा सकता है। चूँकि, यह दृष्टिकोण बहुत ही सरल अपरिवर्तनीयों तक ही सीमित है (जैसे 0<=i && i<=n && i%2==0)।

लूप-अपरिवर्तनीय कोड से अंतर

लूप-इनवेरिएंट कोड में ऐसे कथन या अभिव्यक्ति सम्मिलित होते हैं जिन्हें प्रोग्राम शब्दार्थ को प्रभावित किए बिना लूप बॉडी के बाहर ले जाया जा सकता है। ऐसे परिवर्तन, जिन्हें लूप-अपरिवर्तनीय कोड गति कहा जाता है, कुछ कंपाइलरों द्वारा कंपाइलर प्रोग्राम को अनुकूलित करने के लिए किए जाते हैं। लूप-इनवेरिएंट कोड उदाहरण (C (प्रोग्रामिंग भाषा) में) है

for (int i=0; i<n; ++i) {
    x = y+z;
    a[i] = 6*i + x*x;
}

जहां गणना x = y+z और x*x लूप से पहले ले जाया जा सकता है, जिसके परिणामस्वरूप एक समतुल्य, लेकिन तेज़ प्रोग्राम बनता है:

x = y+z;
t1 = x*x;
for (int i=0; i<n; ++i) {
    a[i] = 6*i + t1;
}

इसके विपरीत, उदा. गुण 0<=i && i<=n मूल और अनुकूलित प्रोग्राम दोनों के लिए लूप अपरिवर्तनीय है, लेकिन यह कोड का हिस्सा नहीं है, इसलिए इसे लूप से बाहर ले जाने की बात करने का कोई अर्थ नहीं है।

लूप-इनवेरिएंट कोड संबंधित लूप-इनवेरिएंट गुण को प्रेरित कर सकता है। उपरोक्त उदाहरण के लिए, इसे देखने की सबसे आसान विधि प्रोग्राम पर विचार करना है, जहां लूप इनवेरिएंट कोड की गणना लूप के पहले और अन्दर दोनों जगह की जाती है:

x1 = y+z;
t1 = x1*x1;
for (int i=0; i<n; ++i) {
    x2 = y+z;
    a[i] = 6*i + t1;
}

इस कोड की लूप-अपरिवर्तनीय गुण (x1==x2 && t1==x2*x2) || i==0 है, यह दर्शाता है कि लूप से पहले गणना किए गए मान अन्दर गणना किए गए मानों से सहमत हैं (पहले पुनरावृत्ति से पहले को छोड़कर)।

यह भी देखें

संदर्भ

  1. Carlo A. Furia, Bertrand Meyer and Sergey Velder. "Loop invariants: analysis, classification, and examples."ACM Computing Surveys. vol. 46, no. 3, February 2014([1]
  2. Robert W. Floyd (1967). "Assigning Meanings to Programs" (PDF). In J.T. Schwartz (ed.). Proceedings of Symposia in Applied Mathematics. Mathematical Aspects of Computer Science. Vol. 19. Providence, RI: American Mathematical Society. pp. 19–32.
  3. Hoare, C. A. R. (October 1969). "An axiomatic basis for computer programming" (PDF). Communications of the ACM. 12 (10): 576–580. doi:10.1145/363235.363259. S2CID 207726175. Archived from the original (PDF) on 2016-03-04.
  4. 4.0 4.1 Conway, Richard; Gries, David (1973). An Introduction to Programming: A Structured Approach using PL/1 and PL/C. Cambridge, Massachusetts: Winthrop. pp. 198–200.
  5. Huang, J. C. (2009). परीक्षण और विश्लेषण के माध्यम से सॉफ़्टवेयर त्रुटि का पता लगाना. Hoboken, New Jersey: John Wiley & Sons. pp. 156–157.
  6. Meyer, Bertrand, Eiffel: The Language, Prentice Hall, 1991, pp. 129–131.
  7. Pearce, David J.; Groves, Lindsay (2015). "Designing a Verifying Compiler: Lessons Learned from Developing Whiley". Science of Computer Programming. 113: 191–220. doi:10.1016/j.scico.2015.09.006.


अग्रिम पठन