O’zbekiston respublikasi axborot texnologiyalari va kommunikasiyalarini rivojlantirish vazirligi

§ 11.2. Dasturiy ta’minot oqimining murakkabligi o’lchovlari

O’lchovlarning navbatdagi katta sinfi dasturlarning miqdoriy ko’rsatkichlarga emas, balki dasturning boshqarish grafini tahlil qilishga asoslangan bo’lib, Dasturiy ta’minotrni boshqarish oqimining murakkablik olchovlari deb ataladi. Biron dastur taqdim etilgan bo’lsin. Ushbu dastur uchun faqat bitta kirish va bitta chiqishni o’z ichiga olgan yo’naltirilgan graf tuziladi. Grafning uchlari dastur kodining faqat
ketma-ket hisob-kitoblar mavjud bo’lgan bo’limlari bilan bog’liq bo’lib, bu yerda tarmoqlanish va davriy operatorlari mavjud emas va yoylar blokdan blokga o’tish va dasturni bajarish shoxlari bilan korrelyatsiya qilinadi. Bu grafni tuzish sharti shundan iboratki, har bir cho’qqiga boshlang’ich cho’qqidan, yakuniy cho’qqiga esa boshqa har qanday cho’qqidan chiqish mumkin bo’ladi.
Olingan graf tahliliga asoslangan eng keng tarqalgan baholash bu dasturning siklomatik murakkabligi (Makkeybning siklomatik raqami). U V(G)=e - n + 2p sifatida aniqlanadi, bu yerda e - yoylar soni, n - cho’qqilar soni, p - bog’langan komponentlar soni. Grafning bog’langan komponentlari sonini grafni kuchli bog’langanga aylantirish uchun qo’shilishi kerak bo’lgan yoylar soni deb hisoblash mumkin. Grafning istalgan ikkita uchi oʻzaro bir-biriga yetib borishi mumkin boʻlsa, u kuchli bogʻlangan deb ataladi. To’g’ri dasturlarning graflari, ya’ni kirish nuqtasi va "osilgan" kirish va chiqish nuqtalaridan yetib bo’lmaydigan segmentlarga ega bo’lmagan graflar uchun, odatda, dasturning oxirini yoy bilan belgilovchi cho’qqini yopish orqali kuchli bog’langan grafik olinadi. ushbu dasturga kirish nuqtasini belgilovchi cho’qqi. Aslida, V (G) kuchli bog’langan grafdagi chiziqli mustaqil konturlar sonini aniqlaydi. Shunday qilib, yaxshi yozilgan dasturlarda p=1 va shuning uchun siklomatik murakkablikni hisoblash formulasi quyidagicha bo’ladi:
V(G)=e — n + 2.
Oddiy dasturning boshqaruv oqimi grafi. Dastur qizil tugunda bajarilishini boshlaydi, so’ngra tsiklga kiradi (qizil tugunning ostidagi uchta tugundan iborat guruh). Tsikldan chiqishda shartli operator mavjud (tsikl ostidagi guruh) va nihoyat dastur ko’k tugunda chiqadi. Ushbu grafda 9 ta qirralar, 8 ta tugunlar va 1 ta ulangan komponent mavjud, shuning uchun dasturning siklomatik murakkabligi
9 - 8 + 2 * 1 = 3 ga teng.
Dasturning siklomatik murakkabligi manba kodi chiziqli mustaqil soni yo’llar uning ichida - "chiziqli mustaqil" degani, har bir yo’l boshqa yo’llarning birida bo’lmagan kamida bitta chekkaga ega. Masalan, agar manba kodida "yo’q" bo’lsa boshqaruv oqimlaridagi operatorlar (shartli yoki qaror nuqtalari), murakkabligi 1 ga teng bo’ladi, chunki kod orqali faqat bitta yo’l bo’ladi. Agar kod bitta shartli IF
operatoriga ega bo’lsa, kod orqali ikkita yo’l bo’lishi kerak edi: IF ifoda TRUE ga, boshqasi FALSE ga teng bo’lsa murakkablik 2 ga teng bo’ladi. Ikkita bir shartli IF yoki ikki shartli bitta IF operatori mavjud bo’lsa murakkablik 3 ga teng bo’ladi.
11.1-rasm. Oddiy dasturning boshqaruv oqimi grafi²⁵.
Afsuski, bu baholash davriy va shartli konstruktsiyalarni ajrata olmaydi. Ushbu yondashuvning yana bir muhim kamchiligi shundaki, bir xil graflar bilan ifodalangan dasturlar murakkabligi bo’yicha butunlay boshqacha predikatlarga ega bo’lishi mumkin (predikat kamida bitta o’zgaruvchini o’z ichiga olgan mantiqiy ifodadir). Ushbu kamchilikni tuzatish uchun G. Myers yangi usulni ishlab chiqdi. Baho sifatida u intervalni (bu baho oraliq deb ham ataladi) [V(G),V(G)+h] olishni taklif qildi, bunda oddiy predikatlar uchun h nolga teng, n-joyli predikatlar uchun h=n -1 ga teng. Bu usul har xil murakkablikdagi predikatlarni farqlash imkonini beradi, lekin amalda u deyarli ishlatilmaydi.
McCabe usulining yana bir modifikatsiyasi Hansen usulidir. Bu holda dastur murakkabligi o’lchovi tsiklomatik murakkablik, operatorlar soni juftligi sifatida ifodalanadi. Ushbu usulning afzalligi uning dasturiy ta’minot tuzilishiga nisbatan sezgirligidir. Chenning topologik o’lchovi dasturning murakkabligini dastur grafi tomonidan tashkil etilgan hududlar orasidagi chegara kesishishlar soni bo’yicha



²⁵ Б.В. Черников. Управление качеством программного обеспечения: Учебник - М.: ИД ФОРУМ: ИНФРА-М, 2012.
ifodalaydi. Ushbu yondashuv faqat boshqaruv konstruktsiyalarini ketma-ket ulash imkonini beruvchi strukturali dasturlarga nisbatan qo’llaniladi. Strukturaviy bo’lmagan dasturlar uchun Chen o’lchovi shartli va shartsiz o’tish operatorlariga bog’liq bo’ladi. Bunday holda o’lchovning yuqori va pastki chegaralarini belgilash mumkin. Yuqori chegarasi m + 1, bu yerda m - o’tish operatorlari o’zaro ichma-ich joylashtirilgan mantiqiy operatorlar soni. Pastki chegarasi 2 ga teng. Dasturning boshqaruv grafi faqat bitta bog’langan komponentga ega bo’lsa, Chen o’lchovi McCabe siklomatik o’lchoviga mos tushadi.
Dasturning boshqaruv grafini tahlil qilishni davom ettirsak, o’lchovlarning yana bir kichik guruhini ajratib ko’rsatish mumkin - Xarrison va Meigel o’lchovlari. Ushbu usullar ichma-ich joylashish darajasini va dasturning davomiyligini hisobga oladi. Har bir cho’qqi u tasvirlagan operatorga mos ravishda o’ziga xos murakkablik bilan belgilanadi. Cho’qqining ushbu boshlang’ich murakkabligini har qanday usulda, shu jumladan Halsted o’lchovlari yordamida hisoblash mumkin. Har bir predikat cho’qqi uchun undan chiqadigan yoylarning uchlari bo’lgan cho’qqilar tomonidan hosil qilingan subgrafni belgilaymiz. Shuningdek, har bir bunday cho’qqidan (pastki chiziqning pastki chegarasi) erishish mumkin bo’lgan cho’qqilarni va qandaydir pastki chegarada predikat cho’qqidan chiqadigan yo’llarda yotgan cho’qqilarni ajratib ko’rsatamiz. Ushbu subgraf predikat tugunining ta’sir doirasi deb ataladi.
Predikat tugunining keltirilgan murakkabligi uning ta’sir doirasiga kiruvchi tugunlarning boshlang’ich yoki keltirilgan murakkabliklari yig’indisi, shuningdek, predikat tugunining o’zining birlamchi murakkabligi. Dasturning funktsional o’lchovi (SCOPE) - bu boshqarish grafining barcha cho’qqilarining keltirilgan murakkabliklarining yig’indisidir. Funktsional munosabat (SCORT) - bu boshqaruv grafidagi cho’qqilar sonining uning funktsional murakkabligiga nisbatidir, bunda uchlari sonidan ohirgi tugunllar chiqarib tashlanadi. SCORT bir xil siklomatik raqamga ega graflar uchun turli qiymatlarni qabul qilishi mumkin.
Pivovarskiy metrikasi siklomatik murakkablik o’lchovining yana bir modifikatsiyasidir. U nafaqat ketma-ket va ichki boshqaruv konstruksiyalari, balki
strukturalashtirilgan va strukturalashtirilmagan dasturlar orasidagi farqlarni kuzatish imkonini beradi. U N(G) = v *(G) + sum(Pi) munosabati bilan ifodalanadi, bu yerda v*(G) ifodasi V(G) bilan bir xil tarzda hisoblangan modifikatsiya qilingan siklomatik murakkablikdir, lekin bir farq bilan: n chiqishga ega CASE operatori “n- 1” operatorlar to’plami kabi emas, balki bitta mantiqiy operator sifatida qabul qilinadi. P_i - i-nchi predikat tugunining ichma-ich joylashish chuqurligi. Predikat tugunlarining chuqurligini hisoblash uchun "ta’sir doiralari" soni qo’llaniladi. Ichma-ich joylashish chuqurligi deganda ko’rib chiqilayotgan cho’qqi sferasida to’liq joylashgan yoki u bilan kesishgan predikatlarning barcha "ta’sir doiralari" soni tushuniladi. Ichma-ich joylashish chuqurligi predikatlarning o’zlari emas, balki "ta’sir doiralari" ning ichma-ich joylashishi tufayli ortadi. Pivovarskiy o’lchovi ketma-ket tuzilgan dasturlardan ichma-ich joylashgan dasturlarga o’tishda va keyinchalik strukturalashtirilmagan dasturlarga o’tish jarayonida ortib boradi, bu uning ushbu guruhning boshqa ko’plab o’lchovlaridan katta afzalligi borligini bildiradi.
Vudvord o’lchovi - boshqaruv grafi yoylarining kesishishlari soni. Bunday holatlar yaxshi strukturalashtirilgan dasturda yuzaga kelmasligi kerakligi sababli, bu o’lchov asosan zaif strukturalashtirilgan tillarda qo’llaniladi. Kesishish nuqtasi boshqaruv ketma-ket operatorlar bo’lgan ikkita yuqori chegarasidan tashqariga chiqqanda sodir bo’ladi.
Chegaraviy qiymat usuli ham dasturning bosqaruv grafini tahlil qilishga asoslanadi. Ushbu usulni aniqlash uchun bir nechta qo’shimcha tushunchalarni kiritish kerak. Yagona boshlang’ch va yagona oxirgi cho’qqiga ega bo’lgan dasturning boshqaruv grafi G bo’lsin. Bu grafda yoylarning kiruvchi cho’qqilari soni cho’qqining manfiy darajasi, cho’qqidan chiquvchi yoylar soni esa cho’qqining musbat darajasi deyiladi. U holda graf cho’qqilari to’plamini ikki guruhga bo’lish mumkin: musbat darajasi <=1 bo’lgan cho’qqilar; musbat darajasi >=2 bo’lgan cho’qqilar. Birinchi guruhning cho’qqilari qabul qiluvchi cho’qqilar, ikkinchi guruhning cho’qqilari esa tanlash cho’qqilari deb ataladi. 0 ga teng keltirilgan murakkablikka ega bo’lgan yakuniy cho’qqidan tashqari har bir qabul qiluvchi
cho’qqi 1 ga teng keltirilgan murakkablikka ega. G dagi barcha cho’qqilarning keltirilgan murakkabliklari qiymatlari dasturning mutlaq chegara murakkabligini hosil qilish uchun qo’shiladi. Shundan so’ng, dasturning nisbiy chegara murakkabligi aniqlanadi:

^S0^=1-(v-1)/Sa^,

Bu yerda S₀ - dasturning nisbiy chegara murakkabligi, S_a - dasturning mutlaq chegara murakkabligi, v - dastur grafining umumiy cho’qqilari soni.
Boshqarish grafida mumkin bo’lgan yo’llar soni orqali ifodalangan Schneidewind o’lchovi mavjud.