التعقيد الحلقي

التعقيد الحلقي هو مقياس برمجي يستخدم للإشارة إلى تعقيد البرنامج . وهو مقياس كمي لعدد المسارات المستقلة خطيًا عبر الكود المصدر للبرنامج . تم تطويره بواسطة توماس جيه ماكابي الأب في عام 1976.

يتم حساب التعقيد الحلقي باستخدام الرسم البياني لتدفق التحكم في البرنامج. تتوافق عقد الرسم البياني مع مجموعات غير قابلة للتجزئة من أوامر البرنامج، ويربط الحافة الموجهة بين عقدتين إذا كان من الممكن تنفيذ الأمر الثاني مباشرة بعد الأمر الأول. يمكن أيضًا تطبيق التعقيد الحلقي على الوظائف الفردية أو الوحدات النمطية أو الطرق أو الفئات داخل البرنامج.

إحدى استراتيجيات الاختبار ، والتي أطلق عليها ماكابي اسم اختبار المسار الأساسي والذي اقترحه لأول مرة، هي اختبار كل مسار مستقل خطيًا خلال البرنامج. في هذه الحالة، سيكون عدد حالات الاختبار مساويًا للتعقيد الدائري للبرنامج. ^[1]

توجد طرق متعددة لتحديد التعقيد الحلقي لقسم من التعليمات البرمجية المصدرية . إحدى الطرق الشائعة هي عدد المسارات المستقلة خطيًا داخلها. تكون مجموعة المسارات مستقلة خطيًا إذا لم تكن مجموعة الحواف لأي مسار في اتحاد مجموعات الحواف للمسارات في بعض مجموعات فرعية من . إذا لم يحتوي التعليمات البرمجية المصدرية على عبارات تدفق التحكم (الشروط أو نقاط القرار)، فسيكون التعقيد 1، حيث لن يكون هناك سوى مسار واحد عبر التعليمات البرمجية. إذا كان التعليمات البرمجية تحتوي على عبارة IF واحدة ذات شرط واحد، فسيكون هناك مساران عبر التعليمات البرمجية: أحدهما حيث تكون عبارة IF صحيحة والآخر حيث تكون خاطئة. هنا، سيكون التعقيد 2. ستنتج حالتا IF متداخلتان ذات شرط واحد، أو عبارة IF واحدة بشرطين، تعقيدًا قدره 3. ${\displaystyle S}$${\displaystyle P}$${\displaystyle S}$${\displaystyle S/P}$

هناك طريقة أخرى لتحديد التعقيد الحلقي لبرنامج ما وهي النظر إلى مخطط تدفق التحكم الخاص به ، وهو مخطط موجه يحتوي على الكتل الأساسية للبرنامج، مع وجود حافة بين كتلتين أساسيتين إذا كان التحكم قد ينتقل من الأولى إلى الثانية. ثم يتم تعريف التعقيد M على النحو التالي ^[2]

$${\displaystyle M=E-N+2P,}$$

أين

• E = عدد حواف الرسم البياني.
• N = عدد عقد الرسم البياني.
• P = عدد المكونات المتصلة .

صيغة بديلة لذلك، كما هو مقترح في الأصل، هي استخدام رسم بياني حيث تكون كل نقطة خروج متصلة مرة أخرى بنقطة الدخول. في هذه الحالة، يكون الرسم البياني متصلاً بقوة . هنا، تكون التعقيد الحلقي للبرنامج مساوية للرقم الحلقي لرسمه البياني (المعروف أيضًا باسم رقم بيتي الأول )، والذي يتم تعريفه على أنه ^[2] $${\displaystyle M=E-N+P.}$$

يمكن اعتبار ذلك بمثابة حساب عدد الدورات المستقلة خطيًا الموجودة في الرسم البياني: تلك الدورات التي لا تحتوي على دورات أخرى داخلها. ولأن كل نقطة خروج تعود إلى نقطة الدخول، فهناك دورة واحدة على الأقل لكل نقطة خروج.

بالنسبة لبرنامج واحد (أو برنامج فرعي أو طريقة)، فإن P يساوي دائمًا 1؛ الصيغة الأبسط لبرنامج فرعي واحد هي ^[3] $${\displaystyle M=E-N+2.}$$

يمكن تطبيق التعقيد الحلقي على العديد من هذه البرامج أو البرامج الفرعية في نفس الوقت (على جميع الطرق في فئة واحدة، على سبيل المثال). في هذه الحالات، سوف يساوي P عدد البرامج المعنية، وسوف يظهر كل برنامج فرعي كمجموعة فرعية منفصلة عن الرسم البياني.

أظهر ماكابي أن التعقيد الحلقي لبرنامج منظم بنقطة دخول واحدة ونقطة خروج واحدة يساوي عدد نقاط القرار (عبارات "إذا" أو حلقات شرطية) الموجودة في هذا البرنامج زائد واحد. هذا صحيح فقط لنقاط القرار المحسوبة في أدنى تعليمات على مستوى الآلة. ^[4] يجب حساب القرارات التي تنطوي على مسندات مركبة مثل تلك الموجودة في اللغات عالية المستوى مثل IF cond1 AND cond2 THEN ...من حيث متغيرات المسند المعنية. في هذا المثال، يجب حساب نقطتي قرار لأنه على مستوى الآلة يعادل IF cond1 THEN IF cond2 THEN .... ^{[2] [5]}

يمكن توسيع التعقيد الحلقي ليشمل برنامجًا يحتوي على نقاط خروج متعددة. في هذه الحالة، يكون التعقيد الحلقي مساويًا لـ حيث هو عدد نقاط القرار في البرنامج و s هو عدد نقاط الخروج. ^{[5] [6]}$${\displaystyle \pi -s+2,}$$${\displaystyle \pi }$

الرسم البياني الفرعي الزوجي للرسم البياني (المعروف أيضًا باسم الرسم البياني الفرعي أويلري ) هو الرسم البياني الذي تتقاطع فيه كل رأس مع عدد زوجي من الحواف. هذه الرسوم البيانية الفرعية عبارة عن اتحادات لدورات ورؤوس معزولة. سيتم تحديد الرسوم البيانية الفرعية بمجموعات حوافها، وهو ما يعادل النظر فقط في الرسوم البيانية الفرعية الزوجية التي تحتوي على جميع رؤوس الرسم البياني الكامل.

مجموعة جميع الرسوم البيانية الفرعية الزوجية للرسم البياني مغلقة تحت الفرق المتماثل ، وبالتالي يمكن اعتبارها فضاء متجه على GF(2) . يسمى فضاء المتجه هذا فضاء الدورة للرسم البياني. يتم تعريف العدد الدائري للرسم البياني على أنه بُعد هذا الفضاء. نظرًا لأن GF(2) يحتوي على عنصرين وفضاء الدورة محدود بالضرورة، فإن العدد الدائري يساوي أيضًا اللوغاريتم 2 لعدد العناصر في فضاء الدورة.

يمكن إنشاء أساس لمساحة الدورة بسهولة من خلال تحديد غابة ممتدة للرسم البياني أولاً، ثم النظر في الدورات التي تشكلها حافة واحدة ليست في الغابة والمسار في الغابة الذي يربط بين نقاط النهاية لتلك الحافة. ​​تشكل هذه الدورات أساسًا لمساحة الدورة. كما أن العدد الدائري يساوي عدد الحواف غير الموجودة في غابة ممتدة قصوى للرسم البياني. نظرًا لأن عدد الحواف في غابة ممتدة قصوى للرسم البياني يساوي عدد الرؤوس مطروحًا منه عدد المكونات، فإن الصيغة تحدد العدد الدائري. ^[7]${\displaystyle E-N+P}$

يمكن تعريف التعقيد الحلقي أيضًا على أنه رقم بيتي نسبي ، وهو حجم مجموعة التشابه النسبي :

$${\displaystyle M:=b_{1}(G,t):=\اسم المشغل {الرتبة} H_{1}(G,t),}$$

والتي تُقرأ على أنها "رتبة المجموعة المتجانسة الأولى للرسم البياني G بالنسبة إلى العقد الطرفية t ". هذه طريقة فنية لقول "عدد المسارات المستقلة خطيًا عبر الرسم البياني للتدفق من نقطة دخول إلى نقطة خروج"، حيث:

• "مستقل خطيًا" يتوافق مع التماثل، والرجوع إلى الوراء ليس محسوبًا مرتين؛
• "المسارات" تتوافق مع التشابه الأول (المسار هو كائن أحادي البعد)؛ و
• "نسبيًا" يعني أن المسار يجب أن يبدأ وينتهي عند نقطة دخول (أو خروج).

يمكن حساب هذا التعقيد الحلقي. ويمكن أيضًا حسابه عبر رقم بيتي المطلق من خلال تحديد العقد الطرفية على مكون معين، أو رسم مسارات تربط المخارج بالمدخل. يحصل الرسم البياني الجديد المعزز على${\displaystyle {\tilde {G}}}$$${\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}$$

يمكن أيضًا حسابها عبر التماثل . إذا تم اعتبار رسم بياني للتحكم في التدفق (متصل) مركبًا أحادي البعد CW يسمى ، فإن المجموعة الأساسية لـ ستكون . قيمة هي التعقيد الحلقي. تحسب المجموعة الأساسية عدد الحلقات الموجودة عبر الرسم البياني حتى التماثل، والمحاذاة كما هو متوقع. ${\displaystyle X}$${\displaystyle X}$${\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}$${\displaystyle n+1}$

في عرضه التقديمي "مقاييس جودة البرمجيات لتحديد المخاطر" ^[8] لوزارة الأمن الداخلي، قدم توم ماكابي التصنيف التالي للتعقيد الدائري:

• 1 - 10: إجراء بسيط ومخاطر قليلة
• 11 - 20: أكثر تعقيدًا، ومخاطر معتدلة
• 21 - 50: معقدة، عالية الخطورة
• > 50: كود غير قابل للاختبار، ومخاطر عالية جدًا

كان أحد التطبيقات الأصلية لمكابي هو الحد من تعقيد الروتينات أثناء تطوير البرنامج. أوصى بأن يقوم المبرمجون بحساب تعقيد الوحدات التي يطورونها، وتقسيمها إلى وحدات أصغر كلما تجاوز التعقيد الحلقي للوحدة 10. ^[2] تم تبني هذه الممارسة من قبل منهجية الاختبار المنظم NIST ، والتي لاحظت أنه منذ نشر مكابي الأصلي، تلقى الرقم 10 أدلة داعمة كبيرة. ومع ذلك، فقد لاحظت أيضًا أنه في بعض الظروف قد يكون من المناسب تخفيف القيد والسماح بوحدات ذات تعقيد يصل إلى 15. نظرًا لأن المنهجية أقرت بوجود أسباب عرضية لتجاوز الحد المتفق عليه، فقد صاغت توصيتها على النحو التالي "بالنسبة لكل وحدة، إما الحد من التعقيد الحلقي إلى [الحد المتفق عليه] أو تقديم تفسير مكتوب لسبب تجاوز الحد". ^[9]

يتناول القسم السادس من ورقة ماكابي لعام 1976 تحديد شكل الرسوم البيانية لتدفق التحكم (CFGs) للبرامج غير المنظمة من حيث الرسوم البيانية الفرعية الخاصة بها، والتي حددها ماكابي. (للتفاصيل، انظر نظرية البرنامج المنظم .) واختتم ماكابي هذا القسم باقتراح مقياس عددي لمدى قرب برنامج معين من المثل الأعلى للبرمجة المنظمة، أي "بنيته". أطلق ماكابي على المقياس الذي ابتكره لهذا الغرض التعقيد الأساسي . ^[2]

لحساب هذا المقياس، يتم تقليل CFG الأصلي بشكل تكراري من خلال تحديد الرسوم البيانية الفرعية التي تحتوي على نقطة دخول واحدة ونقطة خروج واحدة، والتي يتم استبدالها بعد ذلك بعقدة واحدة. يتوافق هذا التخفيض مع ما سيفعله الإنسان إذا استخرج برنامجًا فرعيًا من قطعة التعليمات البرمجية الأكبر. (في الوقت الحاضر، تندرج مثل هذه العملية تحت مصطلح إعادة الهيكلة الشامل ). تم تسمية طريقة التخفيض الخاصة بـ McCabe لاحقًا بالتكثيف في بعض الكتب المدرسية، لأنه كان يُنظر إليها على أنها تعميم للتكثيف على المكونات المستخدمة في نظرية الرسم البياني . ^[10] إذا كان البرنامج منظمًا، فإن عملية التخفيض/التكثيف الخاصة بـ McCabe تقلله إلى عقدة CFG واحدة. على النقيض من ذلك، إذا لم يكن البرنامج منظمًا، فستحدد العملية التكرارية الجزء غير القابل للاختزال. مقياس التعقيد الأساسي الذي حدده McCabe هو ببساطة التعقيد الدائري لهذا الرسم البياني غير القابل للاختزال، لذلك سيكون 1 على وجه التحديد لجميع البرامج المنظمة، ولكن أكبر من واحد للبرامج غير المنظمة. ^{[9] : 80}

تطبيق آخر للتعقيد الحلقي هو تحديد عدد حالات الاختبار اللازمة لتحقيق تغطية اختبار شاملة لوحدة معينة.

إنه مفيد بسبب خاصيتين للتعقيد الحلقي، M ، لوحدة محددة:

• M هو الحد الأعلى لعدد حالات الاختبار اللازمة لتحقيق تغطية فرعية كاملة .
• M هو الحد الأدنى لعدد المسارات عبر الرسم البياني لتدفق التحكم (CFG). بافتراض أن كل حالة اختبار تأخذ مسارًا واحدًا، فإن عدد الحالات اللازمة لتحقيق تغطية المسار يساوي عدد المسارات التي يمكن اتخاذها بالفعل. ولكن قد يكون من المستحيل اتخاذ بعض المسارات ، لذلك على الرغم من أن عدد المسارات عبر الرسم البياني لتدفق التحكم (CFG) هو بوضوح الحد الأعلى لعدد حالات الاختبار اللازمة لتغطية المسار، فإن هذا العدد الأخير (من المسارات المحتملة ) يكون أحيانًا أقل من M.

قد تكون الأرقام الثلاثة المذكورة أعلاه متساوية: تغطية الفرع، التعقيد الدائري، عدد المسارات. ${\displaystyle \leq }$${\displaystyle \leq }$

على سبيل المثال، ضع في اعتبارك برنامجًا يتكون من عبارتين متتاليتين if-then-else.

إذا ( c1 ()) f1 (); وإلا f2 (); 
    

    

إذا ( c2 ()) f3 (); وإلا f4 (); 
    

    

في هذا المثال، تكون حالتا اختبار كافيتين لتحقيق تغطية كاملة للفرع، بينما تكون أربع حالات اختبار ضرورية لتغطية المسار بالكامل. التعقيد الحلقي للبرنامج هو 3 (حيث يحتوي الرسم البياني المتصل بقوة للبرنامج على 9 حواف و7 عقد ومكون متصل واحد) ( 9 − 7 + 1 ).

بشكل عام، من أجل اختبار وحدة كاملة، يجب ممارسة جميع مسارات التنفيذ عبر الوحدة. وهذا يعني أن الوحدة ذات رقم التعقيد العالي تتطلب جهد اختبار أكبر من الوحدة ذات القيمة الأقل لأن رقم التعقيد الأعلى يشير إلى المزيد من المسارات عبر الكود. وهذا يعني أيضًا أن الوحدة ذات التعقيد الأعلى يصعب فهمها لأن المبرمج يجب أن يفهم المسارات المختلفة ونتائج تلك المسارات.

لسوء الحظ، ليس من العملي دائمًا اختبار جميع المسارات الممكنة من خلال برنامج. بالنظر إلى المثال أعلاه، في كل مرة تتم إضافة عبارة if-then-else إضافية، ينمو عدد المسارات الممكنة بعامل 2. ومع نمو البرنامج بهذه الطريقة، فإنه يصل بسرعة إلى النقطة التي يصبح فيها اختبار جميع المسارات غير عملي.

إحدى استراتيجيات الاختبار الشائعة، التي تبناها على سبيل المثال منهجية الاختبار المنظم NIST، هي استخدام التعقيد الدوري لوحدة ما لتحديد عدد اختبارات الصندوق الأبيض المطلوبة للحصول على تغطية كافية للوحدة. في جميع الحالات تقريبًا، وفقًا لهذه المنهجية، يجب أن تحتوي الوحدة على عدد من الاختبارات يساوي على الأقل تعقيدها الدوري. في معظم الحالات، يكون هذا العدد من الاختبارات كافيًا لممارسة جميع المسارات ذات الصلة بالوظيفة. ^[9]

كمثال على وظيفة تتطلب أكثر من مجرد تغطية فرعية لاختبارها بدقة، أعد النظر في الوظيفة أعلاه. ومع ذلك، افترض أنه لتجنب حدوث خطأ، يجب على أي كود يستدعي أيًا من f1()أو f3()أن يستدعي الآخر أيضًا. ^[أ] بافتراض أن نتائج c1()و c2()مستقلة، فإن الوظيفة كما هو موضح أعلاه تحتوي على خطأ. تسمح تغطية الفرع باختبار الطريقة باختبارين فقط، مثل حالات الاختبار التالية:

• c1()يعود صحيح c2()ويرجع صحيح
• c1()يعود خطأ c2()ويرجع خطأ

لا يكشف أي من الحالتين عن الخطأ. ومع ذلك، إذا استخدمنا التعقيد الحلقي للإشارة إلى عدد الاختبارات التي نحتاجها، فإن العدد يزداد إلى 3. وبالتالي، يتعين علينا اختبار أحد المسارات التالية:

• c1()يعود صحيحًا c2()ويرجع خطأً
• c1()يعود false c2()ويرجع true

سيؤدي أي من هذه الاختبارات إلى الكشف عن الخلل.

لقد بحثت دراسات متعددة في الارتباط بين رقم التعقيد الحلقي لمكابي وتكرار حدوث العيوب في دالة أو طريقة. ^[11] وجدت بعض الدراسات ^[12] ارتباطًا إيجابيًا بين التعقيد الحلقي والعيوب؛ حيث تميل الوظائف والطرق ذات التعقيد الأعلى إلى احتواء معظم العيوب أيضًا. ومع ذلك، فقد تم إثبات الارتباط بين التعقيد الحلقي وحجم البرنامج (الذي يتم قياسه عادةً بسطور التعليمات البرمجية ) عدة مرات. ادعى ليز هاتون ^[13] أن التعقيد له نفس القدرة التنبؤية مثل سطور التعليمات البرمجية. الدراسات التي تتحكم في حجم البرنامج (أي مقارنة الوحدات التي لها تعقيدات مختلفة ولكن الحجم متشابه) تكون أقل حسمًا بشكل عام، حيث لم يجد الكثير منها أي ارتباط مهم، بينما وجد البعض الآخر ارتباطًا. يشكك بعض الباحثين في صحة الأساليب المستخدمة من قبل الدراسات التي لم تجد أي ارتباط. ^[14] على الرغم من وجود هذه العلاقة على الأرجح، إلا أنه لا يمكن استخدامها بسهولة في الممارسة العملية. ^[15] نظرًا لأن حجم البرنامج ليس سمة يمكن التحكم فيها في البرامج التجارية، فقد تم التشكيك في فائدة رقم ماكابي. ^[11] جوهر هذه الملاحظة هو أن البرامج الأكبر حجمًا تميل إلى أن تكون أكثر تعقيدًا ولديها المزيد من العيوب. لم يثبت أن تقليل التعقيد الحلقي للكود يقلل من عدد الأخطاء أو الأخطاء في هذا الكود. ومع ذلك، فإن معايير السلامة الدولية مثل ISO 26262 تفرض إرشادات الترميز التي تفرض تعقيدًا منخفضًا للكود. ^[16]

• تعقيد البرمجة
• فخ التعقيد
• برنامج كمبيوتر
• برمجة الحاسوب
• التحكم في التدفق
• مسار القرار إلى القرار
• مسندات التصميم
• التعقيد الأساسي (المقياس العددي لـ "الهيكلة")
• مقاييس تعقيد هالستيد
• هندسة البرمجيات
• اختبار البرمجيات
• تحليل البرامج الثابتة
• قابلية الصيانة

• إنشاء مقاييس التعقيد الحلقي باستخدام Polyspace
• دور التجريبية في تحسين موثوقية البرمجيات المستقبلية
• التعقيد الحلقي لمكابي ولماذا لا نستخدمه

Original text

Rate this translation

Your feedback will be used to help improve Google Translate