N xojiyeva, B. Sharipov, sh. Muxsinov

§ 11. 2. Programmalıq támiynat aǵımınıń quramalılıǵı o'lshewleri
Ólshewlerdiń náwbettegi úlken klası programmalardıń muǵdarlıq ko'rsetkishlerge emes, bálki programmanıń basqarıw grafini analiz etiwge tiykarlanǵan bolıp, Programmalıq támiynatrni basqarıw aǵımınıń quramalılıq olchovlari dep ataladı. Qandayda programma usınıs etilgen bolsın. Bul programma ushın tek bir kirisiw hám bir shıǵıwdı óz ishine alǵan jo'neltirilgen graf dúziledi. Grafning úshleri programma kodınıń tek izbe-ız esap -kitaplar ámeldegi bolǵan bólimleri menen baylanıslı bolıp, bul jerde tarmaqlanıw hám udayı tákirarlanatuǵın operatorları joq hám ayqulaqlar bloktan blokǵa o'tiw hám programmanı orınlaw shaqları menen korrelyatsiya etiledi. Bul grafni dúziw shárti sonnan ibarat, hár bir shıńǵa baslanǵısh shıńdan, juwmaqlawshı shıńǵa bolsa basqa hár qanday shıńdan shıǵıw múmkin baladı.
Alınǵan graf analizine tiykarlanǵan eń keń tarqalǵan bahalaw bul programmanıń siklomatik quramalılıǵı (Makkeybning siklomatik nomeri). Al v (G) =e - n + 2 p retinde anıqlanadı, bul jerde e - ayqulaqlar sanı, n - shıńlar sanı, p - baylanısqan komponentler sanı. Grafning baylanısqan komponentleri sanın grafni kúshli baylanısqanǵa aylandırıw ushın qosılıwı kerek bolǵan ayqulaqlar sanı dep esaplaw múmkin. Grafning qálegen eki uchi óz-ara bir-birine jetip barıwı múmkin bolsa, al kúshli baylanısqan dep ataladı. Tuwrı programmalardıń graflari, yaǵnıy kirisiw noqatı hám " osilgan" kirisiw hám shıǵıw noqatlarınan jetip bolmaytuǵın segmentlerge iye bolmaǵan graflar ushın, ádetde, programmanıń aqırın ayqulaq penen belgileytuǵın shıńnı jabıw arqalı kúshli baylanısqan grafik alınadı. bul programmaǵa kirisiw noqatın belgileytuǵın shıń. Tiykarınan, v (G) kúshli baylanısqan grafdagi sızıqlı ǵárezsiz konturlar sanın anıqlaydı. Sanday etip, jaqsı jazılǵan programmalarda p=1 hám sal sebepli siklomatik quramalılıqtı esaplaw formulası to'mendegishe baladı :
v (G) =e — n + 2.
Ápiwayı programmanıń basqarıw aǵımı grafi. Programma qızıl túyinde atqarılıwın baslaydı, keyininen ciklǵa kiredi (qızıl túyindiń astındaǵı ush túyinnen ibarat gruppa ). Cikldan shıǵıwda shártli operator ámeldegi (cikl astındaǵı gruppa ) hám aqır-aqıbetde programma kók túyinde shıǵadı. Bul grafda 9 qırlar, 8 túyinler hám 1 jalǵanǵan komponent ámeldegi, sal sebepli programmanıń siklomatik quramalılıǵı
9 - 8 + 2 * 1 = 3 ke teń.
Programmanıń siklomatik quramalılıǵı derek kodı sızıqlı ǵárezsiz sanı jollar onıń ishinde - " sızıqlı ǵárezsiz" degeni, hár bir jol basqa jollardıń birinde bolmaǵan keminde bir shetke iye. Mısalı, eger derek kodında " joq" bolsa basqarıw aǵıslarındaǵı operatorlar (shártli yamasa qarar noqatları ), quramalılıǵı 1 ge teń baladı, sebebi kod arqalı tek bir jol baladı. Eger kod bir shártli IF operatorına iye bolsa, kod arqalı eki jol bolıwı kerek edi: IF ańlatpa TRUE ga, basqası FALSE ga teń bolsa quramalılıq 2 ge teń baladı. Eki bir shártli IF yamasa eki shártli bir IF operatorı ámeldegi bolsa quramalılıq 3 ke teń baladı.

11.1-súwret. Ápiwayı programmanıń basqarıw aǵımı grafi.

Ókiniw menen aytamız, bul bahalaw udayı tákirarlanatuǵın hám shártli konstruktsiyalarni ajrata almaydı. Bul jantasıwdıń taǵı bir zárúrli kemshiligi sanda, birdey graflar menen ko'rsetilgen programmalar quramalılıǵı boyınsha pútkilley basqasha predikatlarga ıyelewi múmkin (predikat keminde bir o'zgeriwshin óz ishine alǵan logikalıq ańlatpa bolıp tabıladı). Bul kemshilikti ońlaw ushın G. Myers jańa usıldı islep shıqtı. Baha retinde al intervaldı (bul baha aralıq dep de ataladı ) [v (G), v (G) +h] alıwdı usınıs etdi, bunda ápiwayı predikatlar ushın h nolǵa teń, n-jaylı predikatlar ushın h=n -1 ge teń. Bul usıl hár túrlı quramalılıqtaǵı predikatlarni parıqlaw imkaniyatın beredi, lekin ámelde al derlik isletilmaydi.
McCabe usılınıń taǵı bir modifikatsiyası Hansen usılı bolıp tabıladı. Bul halda programma quramalılıǵı o'lshewi ciklomatik quramalılıq, operatorlar sanı juftligi retinde ańlatpalanadı. Bul usıldıń abzallıǵı onıń programmalıq támiynat dúzilisine salıstırǵanda bayqaǵıshlıǵı bolıp tabıladı. Chenning tapologik o'lshewi programmanıń quramalılıǵın programma grafi tárepinen islengen aymaqlar arasındaǵı shegara kesilisiwler sanı boyınsha ańlatadı. Bul jantasıw tek basqarıw konstruktsiyalarini izbe-ız jalǵaw imkaniyatın beretuǵın strukturalı programmalarǵa salıstırǵanda qollanıladı. Strukturalıq bolmaǵan programmalar ushın Chen o'lshewi shártli hám shártsiz o'tiw operatorlarına baylanıslı baladı. Bunday halda o'lshewdiń joqarı hám to'mengi shegaraların belgilew múmkin. Joqarı shegarası m + 1, bul jerde m - o'tiw operatorları óz-ara ichma-jumıs jaylastırılǵan logikalıq operatorlar sanı. To'mengi shegarası 2 ge teń. Programmanıń basqarıw grafi tek bir baylanısqan komponentke iye bolsa, Chen o'lshewi McCabe siklomatik o'lshewine uyqas túsedi.
Programmanıń basqarıw grafini analiz qılıwdı dawam ettirsak, o'lshewlerdiń taǵı bir kisi taparın ajıratıp ko'rsetiw múmkin - Xarrison hám Meigel o'lshewleri. Bul usıllar ichma-jumıs jaylasıw dárejesin hám programmanıń dawam etiw waqtinı esapqa aladı. Hár bir shıń al suwretlegen operatorǵa uyqas túrde ayriqsha quramalılıq penen belgilenedi. Shıńdıń bul baslanǵısh quramalılıǵın hár qanday usılda, sanday-aq Halsted o'lshewleri járdeminde esaplaw múmkin. Hár bir predikat shıń ushın odan shıǵıs ayqulaqlardıń úshleri bolǵan shıńlar tárepinen payda etińan subgrafni belgileymiz. Sonıń menen birge, hár bir bunday shıńdan (to'mengi sızıqtıń to'mengi shegarası ) erisiw múmkin bolǵan shıńlardı hám qanday de to'mengi shegarada predikat shıńdan shıǵıs jollarda jatqan shıńlardı ajıratıp ko'rsetemiz. Bul subgraf predikat túyininiń tásir sheńberi dep ataladı.
Predikat túyininiń keltirilgen quramalılıǵı onıń tásir sheńberine kiretuǵın túyinlerdiń baslanǵısh yamasa keltirilgen quramalılıqları jıyındısı, sonıń menen birge, predikat túyininiń ozıniń baslanǵısh quramalılıǵı. Programmanıń funktsional o'lshewi (SCOPE) - bul basqarıw grafining barlıq shıńlarınıń keltirilgen quramalılıqlarınıń jıyındısı bolıp tabıladı. Funktsional munasábet (SCORT) - bul basqarıw grafidagi shıńlar sanınıń onıń funktsional quramalılıǵına qatnası bolıp tabıladı, bunda úshleri sanınan ohirgi túyinllar shıǵarıp taslanadı. SCORT birdey siklomatik nomerge iye graflar ushın túrli bahalardı qabıllawı múmkin.
Pivovarskiy metrikasi siklomatik quramalılıq o'lshewiniń taǵı bir modifikatsiyası bolıp tabıladı. Al tekǵana izbe-ız hám ishki basqarıw konstruksiyaları, bálki strukturalastırılgan hám strukturalastırılmaǵan programmalar arasındaǵı ayırmashılıqlardı baqlaw imkaniyatın beredi. Al N (G) = v * (G) + sum (Pi) munasábeti menen ańlatpalanadı, bul jerde v* (G) ańlatpası v (G) menen birdey tárzde esaplanǵan modifikatsiya etilgen siklomatik quramalılıq bolıp tabıladı, lekin bir parq penen: n shıǵıwǵa iye CASE operatorı “n- 1” operatorlar kompleksi sıyaqlı emes, bálki bir logikalıq operator retinde qabıl etiledi. Pi - i-nchi predikat túyininiń ichma-jumıs jaylasıw tereńligi. Predikat túyinleriniń tereńligin esaplaw ushın " tásir do'ńgelekleri" sanı qollanıladı. Ichma-jumıs jaylasıw tereńligi degende ko'rip shıǵılıp atırǵan shıń sferasida tolıq jaylasqan yamasa al menen kesilisken predikatlarning barlıq " tásir do'ńgelekleri" sanı túsiniledi. Ichma-jumıs jaylasıw tereńligi predikatlarning o'zleri emes, bálki " tásir do'ńgelekleri" dıń ichma-jumıs jaylasıwı sebepli artadı. Pivovarskiy o'lshewi izbe-ız dúzilgen programmalardan ichma-jumıs jaylasqan programmalarǵa o'tiwde hám keyinirek strukturalastırılmaǵan programmalarǵa o'tiw processinde artıp baradı, bul onıń bul gruppanıń basqa ko'plegen o'lshewlerinen úlken abzallıǵı bar ekenin ańlatadı.
vudvord o'lshewi - basqarıw grafi ayqulaqlarınıń kesilisiwleri sanı. Bunday jaǵdaylar jaqsı strukturalastırılgan programmada júzege kelmewi kerekligi sebepli, bul o'lshew tiykarınan hálsiz strukturalastırılgan tillerde qollanıladı. Kesilisiw noqatı basqarıw izbe-ız operatorlar bolǵan eki joqarı shegarasınan tısqarına shıqqanda júz baladı.
Shegaralıq baha usılı de programmanıń bosqaruv grafini analiz etiwge tiykarlanadı. Bul usıldı anıqlaw ushın bir neshe qosımsha túsiniklerdi kirgiziw kerek. Birden-bir baslang'ch hám birden-bir aqırǵı shıńǵa iye bolǵan programmanıń basqarıw grafi G bolsın. Bul grafda ayqulaqlardıń kiretuǵın shıńları sanı shıńdıń keri dárejesi, shıńdan shıǵıwshı ayqulaqlar sanı bolsa shıńdıń oń dárejesi dep ataladı. Al halda graf shıńları kompleksin eki gruppaǵa bolıw múmkin: oń dárejesi <=1 bolǵan shıńlar ; oń dárejesi >=2 bolǵan shıńlar. Birinshi gruppanıń shıńları qabıl etiwshi shıńlar, eginwi gruppanıń shıńları bolsa tańlaw shıńları dep ataladı. 0 ge teń keltirilgen quramalılıqqa iye bolǵan juwmaqlawshı shıńdan tısqarı hár bir qabıl etiwshi shıń 1 ge teń keltirilgen quramalılıqqa iye. G dagi barlıq shıńlardıń keltirilgen quramalılıqları bahaları programmanıń tolıq shegara quramalılıǵın payda etiw ushın qosıladı. Sonnan keyin, programmanıń salıstırmalı shegara quramalılıǵı anıqlanadı :