Essential complexity
આવશ્યક જટિલતા એ આંકડાકીય માપ છે જે થોમસ જે. મેકકેબ, સિનિયર દ્વારા તેમના અત્યંત ટાંકવામાં આવેલા, 1976 ના પેપરમાં વ્યાખ્યાયિત કરવામાં આવ્યું છે, જે ચક્રીય જટિલતાને રજૂ કરવા માટે વધુ જાણીતું છે. મેકકેબે આવશ્યક જટિલતાને તમામ સંરચિત પ્રોગ્રામિંગ નિયંત્રણ માળખાઓને પુનરાવર્તિત રીતે બદલીને (ઘટાડીને) પછી ઘટાડેલા સી. એફ. જી. (નિયંત્રણ-પ્રવાહ આલેખ) ની ચક્રીય જટિલતા તરીકે વ્યાખ્યાયિત કરી, એટલે કે. પ્લેસહોલ્ડર સિંગલ સ્ટેટમેન્ટ સાથે સિંગલ એન્ટ્રી પોઇન્ટ અને સિંગલ એક્ઝિટ પોઇન્ટ (ઉદાહરણ તરીકે જો-પછી-અન્ય અને જ્યારે લૂપ્સ) ધરાવતા લોકો. મેકકેબની ઘટાડાની પ્રક્રિયાનો હેતુ સબરૂટિન કૉલ્સ સાથે નિયંત્રણ માળખાઓ (અને તેમાં રહેલા વાસ્તવિક નિવેદનો) ની વૈચારિક બદલીનું અનુકરણ કરવાનો છે, તેથી નિયંત્રણ માળખાઓ માટે એક જ પ્રવેશ અને એક જ નિકાસ બિંદુ હોવું જરૂરી છે. (આજકાલ આ પ્રકારની પ્રક્રિયા રીફેક્ટરિંગના છત્ર શબ્દ હેઠળ આવે છે.) તમામ સંરચિત કાર્યક્રમોમાં દેખીતી રીતે મેકકેબે દ્વારા વ્યાખ્યાયિત 1 ની આવશ્યક જટિલતા હોય છે કારણ કે તે બધાને પુનરાવર્તિત રીતે ટોચના-સ્તરના સબરૂટિનમાં એક જ કૉલમાં ઘટાડી શકાય છે. જેમ કે મેકકેબે તેમના પેપરમાં સમજાવે છે, તેમના આવશ્યક જટિલતા મેટ્રિકની રચના આ આદર્શ (સંપૂર્ણપણે સંરચિત થવાનો) આપેલ પ્રોગ્રામ કેટલો દૂર હતો તે માપ આપવા માટે કરવામાં આવી હતી. આમ 1 થી વધુ આવશ્યક જટિલતા સંખ્યાઓ, જે ફક્ત બિન-સંરચિત કાર્યક્રમો માટે જ મેળવી શકાય છે, તે સૂચવે છે કે તેઓ સંરચિત પ્રોગ્રામિંગ આદર્શથી વધુ દૂર છે. માળખાગત કાર્યક્રમોમાં ઘટાડાની વિવિધ ધારણાઓ વચ્ચે મૂંઝવણ ટાળવા માટે, એ નોંધવું અગત્યનું છે કે મેકકેબના પેપરમાં ટૂંકમાં ચર્ચા કરવામાં આવી છે અને તે પછી એસ. રાવ કોસારાજુના 1973 ના પેપરના સંદર્ભમાં કામ કરે છે, જેણે માળખાગત પ્રોગ્રામ થીયરમનું શુદ્ધિકરણ (અથવા વૈકલ્પિક દૃષ્ટિકોણ) આપ્યું હતું. બોહમ અને જેકોપિનીના 1966ના મૂળભૂત પેપરમાં દર્શાવવામાં આવ્યું હતું કે તમામ પ્રોગ્રામ્સને માત્ર માળખાગત પ્રોગ્રામિંગ રચનાઓનો ઉપયોગ કરીને લખી શકાય છે, (ઉર્ફ ડી સ્ટ્રક્ચર્સઃ ક્રમ, જો-પછી-અન્ય, અને જ્યારે-લૂપ), જો કે, રેન્ડમ પ્રોગ્રામને માળખાગત પ્રોગ્રામમાં રૂપાંતરિત કરવા માટે વધારાના ચલો રજૂ કરવાની જરૂર પડી શકે છે (અને પરીક્ષણોમાં ઉપયોગમાં લેવાય છે) અને કેટલાક કોડની નકલ થઈ શકે છે. તેમના પેપરમાં, બોહમ અને જેકોપિનીએ અનુમાન લગાવ્યું હતું, પરંતુ તે સાબિત કર્યું ન હતું કે ચોક્કસ પ્રકારના બિન-સંરચિત કાર્યક્રમો માટે આવા વધારાના ચલ રજૂ કરવાની જરૂર હતી જેથી તેમને સંરચિત કાર્યક્રમોમાં રૂપાંતરિત કરી શકાય. પ્રોગ્રામનું ઉદાહરણ (જે આપણે હવે જાણીએ છીએ) માટે આવા વધારાના ચલની જરૂર પડે છે તે તેની અંદર બે શરતી બહાર નીકળતા લૂપ છે. બોહમ અને જેકોપિનીના અનુમાનને સંબોધવા માટે, કોસારાજુએ બોહમ અને જેકોપિની દ્વારા ઉપયોગમાં લેવાતા ટ્યુરિંગ સમાનતા કરતાં પ્રોગ્રામ ઘટાડાની વધુ પ્રતિબંધિત કલ્પનાને વ્યાખ્યાયિત કરી. અનિવાર્યપણે, કોસરાજુની ઘટાડાની કલ્પના એ સ્પષ્ટ જરૂરિયાત ઉપરાંત લાદે છે કે બંને પ્રોગ્રામ્સે સમાન ઇનપુટ્સને ધ્યાનમાં રાખીને સમાન મૂલ્યની ગણતરી કરવી જોઈએ (અથવા સમાપ્ત ન કરવું જોઈએ), કે બંને પ્રોગ્રામ્સે સમાન આદિમ ક્રિયાઓ અને આગાહીઓનો ઉપયોગ કરવો જોઈએ, જે બાદમાં શરતોમાં ઉપયોગમાં લેવાતી અભિવ્યક્તિઓ તરીકે સમજાય છે. આ પ્રતિબંધોને કારણે, કોસરાજુનો ઘટાડો વધારાના ચલોની રજૂઆતને મંજૂરી આપતો નથી; આ ચલોને સોંપવાથી નવી આદિમ ક્રિયાઓ પેદા થશે અને તેમના મૂલ્યોનું પરીક્ષણ શરતોમાં ઉપયોગમાં લેવાતા આગાહીઓને બદલશે. ઘટાડાની આ વધુ પ્રતિબંધિત કલ્પનાનો ઉપયોગ કરીને, કોસરાજુએ બોહમ અને જેકોપિનીના અનુમાનને સાબિત કર્યું, એટલે કે બે બહાર નીકળવાના લૂપને વધારાના ચલ રજૂ કર્યા વિના સંરચિત પ્રોગ્રામમાં રૂપાંતરિત કરી શકાતો નથી, પરંતુ આગળ વધીને સાબિત કર્યું કે બહુ-સ્તરના વિરામ (લૂપ્સમાંથી) ધરાવતા પ્રોગ્રામ્સ એક પદાનુક્રમ બનાવે છે, જેમ કે કોઈ પણ વ્યક્તિ હંમેશા ઊંડાઈ n ના બહુ-સ્તરના વિરામ સાથે પ્રોગ્રામ શોધી શકે છે, જેને ફરીથી વધારાના ચલ રજૂ કર્યા વિના, n કરતા ઓછી ઊંડાઈ સાથે બહુ-સ્તરના વિરામના પ્રોગ્રામમાં ઘટાડી શકાતો નથી. મેકકેબે તેમના પેપરમાં નોંધે છે કે કોસારાજુના પરિણામોને ધ્યાનમાં રાખીને, તેઓ તેમના નિયંત્રણ-પ્રવાહ આલેખના સંદર્ભમાં બિન-સંરચિત કાર્યક્રમોના આવશ્યક ગુણધર્મોને મેળવવાનો માર્ગ શોધવાનો ઇરાદો ધરાવતા હતા. તેઓ પહેલા નાના બિન-સંરચિત પ્રોગ્રામ્સને અનુરૂપ નિયંત્રણ-પ્રવાહ આલેખની ઓળખ કરીને આગળ વધે છે (તેમાં લૂપમાં શાખાઓ બનાવવી, લૂપમાંથી શાખાઓ બનાવવી અને તેમના જો-પછી-અન્ય સમકક્ષોનો સમાવેશ થાય છે) જેનો ઉપયોગ તેઓ કુરાટોવ્સ્કીના પ્રમેયને અનુરૂપ પ્રમેય ઘડવા માટે કરે છે, અને ત્યારબાદ તેઓ પ્રોગ્રામના નિયંત્રણ-પ્રવાહ આલેખની રચના કરવામાં આવી છે કે નહીં તે પ્રશ્નના હા/ના જવાબને બદલે સ્કેલ જવાબ (તેમના શબ્દોમાં "પ્રોગ્રામની સંરચનાનું માપ") આપવા માટે આવશ્યક જટિલતાની તેમની કલ્પનાનો પરિચય આપે છે. છેવટે, મેકકેબે દ્વારા સી. એફ. જી. ને ઘટાડવા માટે ઉપયોગમાં લેવાતા ઘટાડાની કલ્પના એ કોસારાજુની ફ્લોચાર્ટ ઘટાડવાની કલ્પના જેવી નથી. સી. એફ. જી. પર વ્યાખ્યાયિત ઘટાડો પ્રોગ્રામના ઇનપુટ્સ વિશે જાણતો નથી અથવા તેની કાળજી લેતો નથી, તે ફક્ત ગ્રાફ પરિવર્તન છે. ઉદાહરણ તરીકે, નીચેના સી પ્રોગ્રામના ભાગમાં 1 ની આવશ્યક જટિલતા છે, કારણ કે આંતરિક ઇફ્ સ્ટેટમેન્ટ અને ફોર ઘટાડી શકાય છે, એટલે કે. તે એક સંરચિત કાર્યક્રમ છે. માટે (i = 0; i <3; i + +) {જો (a [i] = = 0) b [i] + = 2;} નીચેના C પ્રોગ્રામ ટુકડામાં ચારની આવશ્યક જટિલતા છે; તેનું CFG ઈરીડ્યુસિબલ છે. પ્રોગ્રામ ઝેડની પ્રથમ પંક્તિ શોધે છે જે તમામ શૂન્ય છે અને તે અનુક્રમણિકાને i માં મૂકે છે; જો કોઈ ન હોય તો, તે i માં-1 મૂકે છે. માટે (i = 0; i <m; i + +) {માટે (j = 0; j <n; j + +) {જો (z [i] [j]! = 0) ગોટો નોન _ ઝીરો;} ગોટો મળે; નોન _ ઝીરોઃ} i =-1; મળ્યુંઃ પેટા-આલેખોના ક્રમિક પતન દ્વારા CFG ઘટાડાનો વિચાર (આખરે સારી વર્તણૂકવાળા CFG માટે એક જ નોડ પર) આધુનિક સંકલન ઑપ્ટિમાઇઝેશનમાં પણ વપરાય છે. જો કે સિંગલ-એન્ટ્રી અને સિંગલ-એક્ઝિટ કંટ્રોલ સ્ટ્રક્ચરના સ્ટ્રક્ચર્ડ પ્રોગ્રામિંગની કલ્પનાને નેચરલ લૂપ સાથે બદલવામાં આવે છે, જેને "સિંગલ-એન્ટ્રી, મલ્ટિપલ-એક્ઝિટ લૂપ" તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જેમાં તેની અંદરથી એન્ટ્રી પર માત્ર એક જ શાખા હોય છે. સી. એફ. જી. ના વિસ્તારો કે જેને કુદરતી લૂપ્સમાં ઘટાડી શકાતા નથી તેને અયોગ્ય પ્રદેશો કહેવામાં આવે છે; આ પ્રદેશો એકદમ સરળ વ્યાખ્યા ધરાવે છેઃ બહુવિધ-પ્રવેશ, સી. એફ. જી. ના મજબૂત રીતે જોડાયેલા ઘટકો. આમ સૌથી સરળ અયોગ્ય વિસ્તાર બે પ્રવેશ બિંદુઓ સાથેનું લૂપ છે. બહુવિધ એક્ઝિટ આધુનિક કમ્પાઇલર્સમાં વિશ્લેષણ સમસ્યાઓનું કારણ નથી. અયોગ્ય પ્રદેશો (લૂપ્સમાં બહુવિધ એન્ટ્રીઓ) કોડને ઓપ્ટિમાઇઝ કરવામાં વધારાની મુશ્કેલીઓનું કારણ બને છે. સોફ્ટવેર ઇજનેરીનો ઇતિહાસ નિર્ણય-થી-નિર્ણય માર્ગ ચક્રીય જટિલતા સંદર્ભો સોફ્ટવેર પ્રોજેક્ટ મેનેજમેન્ટ સોફ્ટવેર મેટ્રિક્સનો ઇતિહાસ પણ જુઓ.