Essential complexity
आवश्यक जटिलता एक संख्यात्मक माप है जिसे थॉमस जे. मैककेब, सीनियर द्वारा परिभाषित किया गया है, जो अपने अत्यधिक उद्धृत, 1976 के पेपर में साइक्लोमैटिक जटिलता को पेश करने के लिए जाना जाता है। मैककेब ने आवश्यक जटिलता को सभी संरचित प्रोग्रामिंग नियंत्रण संरचनाओं को बार-बार बदलने (कम करने) के बाद कम सी. एफ. जी. (नियंत्रण-प्रवाह ग्राफ) की चक्रीय जटिलता के रूप में परिभाषित किया, अर्थात। जिनके पास एकल प्रवेश बिंदु और एकल निकास बिंदु है (उदाहरण के लिए यदि-तब-अन्य और जबकि लूप) प्लेसहोल्डर एकल बयानों के साथ। मैककेब की कमी प्रक्रिया का उद्देश्य सबरूटीन कॉल के साथ नियंत्रण संरचनाओं (और उनमें शामिल वास्तविक बयानों) के वैचारिक प्रतिस्थापन का अनुकरण करना है, इसलिए नियंत्रण संरचनाओं के लिए एक एकल प्रविष्टि और एक एकल निकास बिंदु की आवश्यकता है। (आजकल इस तरह की प्रक्रिया रिफैक्टरिंग के छत्र शब्द के तहत आती है।) सभी संरचित कार्यक्रमों में स्पष्ट रूप से 1 की एक आवश्यक जटिलता होती है जैसा कि मैककेब द्वारा परिभाषित किया गया है क्योंकि उन सभी को एक शीर्ष-स्तरीय सबरूटीन के लिए एक कॉल तक कम किया जा सकता है। जैसा कि मैककेब अपने पेपर में बताते हैं, उनकी आवश्यक जटिलता मीट्रिक को इस बात का एक माप प्रदान करने के लिए डिज़ाइन किया गया था कि यह आदर्श (पूरी तरह से संरचित होने का) एक दिया गया कार्यक्रम कितना दूर था। इस प्रकार 1 से अधिक आवश्यक जटिलता संख्याएँ, जो केवल गैर-संरचित कार्यक्रमों के लिए प्राप्त की जा सकती हैं, इंगित करती हैं कि वे संरचित प्रोग्रामिंग आदर्श से बहुत दूर हैं। संरचित कार्यक्रमों को कम करने की विभिन्न धारणाओं के बीच भ्रम से बचने के लिए, यह ध्यान रखना महत्वपूर्ण है कि मैककेब का पेपर संक्षेप में चर्चा करता है और फिर एस. राव कोसाराजू द्वारा 1973 के पेपर के संदर्भ में काम करता है, जिसने संरचित प्रोग्राम प्रमेय का एक परिष्करण (या वैकल्पिक दृष्टिकोण) दिया। बोहम और जैकोपिनी के 1966 के मौलिक शोध पत्र से पता चला कि सभी कार्यक्रमों को केवल संरचित प्रोग्रामिंग संरचनाओं का उपयोग करके [पुनः] लिखा जा सकता है, (उर्फ डी संरचनाएंः अनुक्रम, यदि-तो-अन्य, और जबकि-लूप), हालांकि, एक यादृच्छिक कार्यक्रम को एक संरचित कार्यक्रम में बदलने में अतिरिक्त चर पेश करने की आवश्यकता हो सकती है (और परीक्षणों में उपयोग किया जा सकता है) और कुछ कोड को दोहराया जा सकता है। अपने पेपर में, बोहम और जैकोपिनी ने अनुमान लगाया, लेकिन यह साबित नहीं किया कि कुछ प्रकार के गैर-संरचित कार्यक्रमों के लिए इस तरह के अतिरिक्त चर को शामिल करना आवश्यक था ताकि उन्हें संरचित कार्यक्रमों में बदला जा सके। प्रोग्राम (जिसे हम अब जानते हैं) के एक उदाहरण के लिए इस तरह के अतिरिक्त चर की आवश्यकता होती है, एक लूप जिसके अंदर दो सशर्त निकास होते हैं। बोहम और जैकोपिनी के अनुमान को संबोधित करने के लिए, कोसाराजू ने बोहम और जैकोपिनी द्वारा उपयोग की जाने वाली ट्यूरिंग समानता की तुलना में कार्यक्रम में कमी की अधिक प्रतिबंधात्मक धारणा को परिभाषित किया। अनिवार्य रूप से, कोसराजू की कमी की धारणा इस स्पष्ट आवश्यकता के अलावा लागू करती है कि दोनों कार्यक्रमों को एक ही इनपुट को देखते हुए एक ही मूल्य (या समाप्त नहीं) की गणना करनी चाहिए, कि दोनों कार्यक्रमों को एक ही आदिम कार्यों और विधेय का उपयोग करना चाहिए, जिसे बाद वाले को शर्तों में उपयोग की जाने वाली अभिव्यक्तियों के रूप में समझा जाता है। इन प्रतिबंधों के कारण, कोसराजू की कमी अतिरिक्त चरों की शुरुआत की अनुमति नहीं देती है; इन चरों को निर्दिष्ट करने से नई आदिम क्रियाएँ पैदा होंगी और उनके मूल्यों का परीक्षण करने से शर्तों में उपयोग किए जाने वाले विधेय बदल जाएंगे। कमी की इस अधिक प्रतिबंधात्मक धारणा का उपयोग करते हुए, कोसाराजू ने बोहम और जैकोपिनी के अनुमान को साबित किया, अर्थात् दो निकास के साथ एक लूप को अतिरिक्त चर पेश किए बिना एक संरचित कार्यक्रम में परिवर्तित नहीं किया जा सकता है, लेकिन आगे जाकर साबित किया कि बहु-स्तरीय ब्रेक (लूप से) वाले प्रोग्राम एक पदानुक्रम बनाते हैं, जैसे कि कोई हमेशा गहराई n के बहु-स्तरीय ब्रेक के साथ एक प्रोग्राम पा सकता है जिसे n से कम गहराई के साथ बहु-स्तरीय ब्रेक के कार्यक्रम में कम नहीं किया जा सकता है, फिर से अतिरिक्त चर पेश किए बिना। मैककेब ने अपने पेपर में नोट किया कि कोसाराजू के परिणामों को देखते हुए, उनका इरादा गैर-संरचित कार्यक्रमों के आवश्यक गुणों को उनके नियंत्रण-प्रवाह ग्राफ के संदर्भ में पकड़ने का एक तरीका खोजना था। वह पहले सबसे छोटे गैर-संरचित कार्यक्रमों के अनुरूप नियंत्रण-प्रवाह ग्राफ की पहचान करके आगे बढ़ते हैं (इनमें एक लूप में शाखा बनाना, एक लूप से बाहर शाखा बनाना और उनके यदि-तो-अन्य समकक्ष शामिल हैं) जिसका उपयोग वह कुराटोव्स्की के प्रमेय के अनुरूप एक प्रमेय तैयार करने के लिए करते हैं, और उसके बाद वे एक पैमाने का उत्तर देने के लिए आवश्यक जटिलता की अपनी धारणा का परिचय देते हैं (अपने शब्दों में एक कार्यक्रम की संरचना का माप) बजाय इस सवाल के कि क्या एक कार्यक्रम का नियंत्रण-प्रवाह ग्राफ संरचित है या नहीं। अंत में, सी. एफ. जी. को कम करने के लिए मैककेब द्वारा उपयोग की जाने वाली कमी की धारणा कोसाराजू की फ्लोचार्ट को कम करने की धारणा के समान नहीं है। सी. एफ. जी. पर परिभाषित कमी कार्यक्रम के निवेश के बारे में नहीं जानती है या परवाह नहीं करती है, यह केवल एक ग्राफ परिवर्तन है। उदाहरण के लिए, निम्नलिखित सी प्रोग्राम टुकड़े में 1 की एक आवश्यक जटिलता है, क्योंकि इनर इफ स्टेटमेंट और फॉर को कम किया जा सकता है, अर्थात। यह एक संरचित कार्यक्रम है। (i = 0; i <3; i + +) के लिए {यदि (a [i] = = 0) b [i] + = 2;} निम्नलिखित C प्रोग्राम टुकड़े में चार की एक आवश्यक जटिलता है; इसका CFG इरेड्यूसिबल है। प्रोग्राम z की पहली पंक्ति पाता है जो सभी शून्य है और उस सूचकांक को i में रखता है; यदि कोई नहीं है, तो यह-1 को i में रखता है। हालांकि एकल-प्रवेश और एकल-निकास नियंत्रण संरचना की संरचित प्रोग्रामिंग की धारणा को प्राकृतिक लूप के साथ बदल दिया गया है, जिसे "एकल-प्रवेश, एकाधिक-निकास लूप के रूप में परिभाषित किया गया है, जिसमें केवल एक शाखा इसके भीतर से प्रवेश पर वापस आती है।" सी. एफ. जी. के जिन क्षेत्रों को प्राकृतिक लूप तक कम नहीं किया जा सकता है, उन्हें अनुचित क्षेत्र कहा जाता है; इन क्षेत्रों में काफी सरल परिभाषा होती हैः सी. एफ. जी. के एकाधिक-प्रवेश, दृढ़ता से जुड़े घटक। इस प्रकार सबसे सरल अनुचित क्षेत्र दो प्रवेश बिंदुओं वाला एक लूप है। कई निकास आधुनिक संकलकों में विश्लेषण समस्याओं का कारण नहीं बनते हैं। अनुचित क्षेत्र (लूप में कई-प्रविष्टियाँ) कोड को अनुकूलित करने में अतिरिक्त कठिनाइयाँ पैदा करते हैं। सॉफ्टवेयर इंजीनियरिंग निर्णय-से-निर्णय पथ का इतिहास भी देखें चक्रीय जटिलता संदर्भ सॉफ्टवेयर परियोजना प्रबंधन सॉफ्टवेयर मेट्रिक्स