التعقيد الجوهري

التعقيد الأساسي هو مقياس عددي عرّفه توماس ج. مكابي الأب في بحثه الشهير المنشور عام 1976، والمعروف بتقديمه لمفهوم التعقيد الحلقي . عرّف مكابي التعقيد الأساسي بأنه التعقيد الحلقي لمخطط تدفق التحكم المُختزل بعد استبدال (اختزال) جميع هياكل التحكم في البرمجة المهيكلة ، أي تلك التي لها نقطة دخول واحدة ونقطة خروج واحدة (مثل حلقات if-then-else و while)، بعبارات مفردة. ^{[ 1 ] : 317 [ 2 ] : 80}

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

لتجنب الخلط بين مختلف مفاهيم قابلية الاختزال إلى برامج مُهيكلة، من المهم الإشارة إلى أن ورقة مكابي تناقش بإيجاز ثم تعمل في سياق ورقة بحثية لـ س. راو كوساراجو عام 1973 ، والتي قدمت تحسينًا (أو رؤية بديلة) لنظرية البرنامج المُهيكل . أظهرت الورقة البحثية الرائدة لـ بوم وجاكوبيني عام 1966 أنه يمكن إعادة كتابة جميع البرامج باستخدام بنيات البرمجة المُهيكلة فقط (المعروفة أيضًا باسم بنيات D: التسلسل، و if-then-else، وحلقة while)، ومع ذلك، عند تحويل برنامج عشوائي إلى برنامج مُهيكل، قد يلزم إدخال متغيرات إضافية (واستخدامها في الاختبارات) وقد يتم تكرار بعض التعليمات البرمجية. ^{[ 3 ]}

في ورقتهم البحثية، افترض بوم وجاكوبيني، دون إثبات، ضرورة إدخال متغيرات إضافية لأنواع معينة من البرامج غير المهيكلة لتحويلها إلى برامج مهيكلة. ^{[ 4 ] : ​​236.} ومن الأمثلة على البرامج (التي نعرفها الآن) والتي تتطلب هذه المتغيرات الإضافية حلقة تكرارية تحتوي على شرطين للخروج. ولمعالجة فرضية بوم وجاكوبيني، عرّف كوساراجو مفهومًا أكثر تقييدًا لاختزال البرامج من مفهوم تكافؤ تورينج الذي استخدمه بوم وجاكوبيني. ويفرض مفهوم كوساراجو للاختزال، بالإضافة إلى الشرط البديهي بأن يحسب البرنامجان القيمة نفسها (أو لا ينتهيا) عند إدخال المدخلات نفسها، أن يستخدم البرنامجان نفس العمليات الأولية والمسندات، والتي تُفهم على أنها التعبيرات المستخدمة في الشروط. وبسبب هذه القيود، لا يسمح اختزال كوساراجو بإدخال متغيرات إضافية. إن إسناد قيم لهذه المتغيرات من شأنه أن يُنشئ إجراءات أولية جديدة، واختبار قيمها سيُغير المسندات المستخدمة في العبارات الشرطية. وباستخدام هذا المفهوم الأكثر تقييدًا للاختزال، أثبت كوساراجو حدسية بوم وجاكوبيني، وهي أنه لا يمكن تحويل حلقة ذات مخرجين إلى برنامج مُهيكل دون إدخال متغيرات إضافية ، بل ذهب أبعد من ذلك وأثبت أن البرامج التي تحتوي على فواصل متعددة المستويات (من الحلقات) تُشكل تسلسلًا هرميًا، بحيث يمكن دائمًا إيجاد برنامج ذي فواصل متعددة المستويات بعمق n لا يمكن اختزاله إلى برنامج ذي فواصل متعددة المستويات بعمق أقل من n ، وذلك أيضًا دون إدخال متغيرات إضافية. ^{[ 4 ] [ 5 ]}

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

على سبيل المثال، فإن جزء برنامج C التالي له تعقيد أساسي قدره 1، لأنه يمكن تقليل عبارة if الداخلية و for ، أي أنه برنامج منظم.

for ( i = 0 ; i < 3 ; i ++ ) { if ( a [ i ] == 0 ) b [ i ] += 2 ; }

يتميز جزء برنامج C التالي بتعقيد أساسي قدره أربعة؛ وقواعده الخالية من السياق غير قابلة للاختزال. يجد البرنامج أول صف من المصفوفة z يحتوي على أصفار ويضع هذا الفهرس في المتغير i؛ وإذا لم يكن هناك صف يحتوي على أصفار، فإنه يضع -1 في المتغير i.

for ( i = 0 ; i < m ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if ( z [ i ][ j ] != 0 ) goto non_zero ; } goto found ; non_zero : } i = -1 ; found :

تُستخدم فكرة اختزال مخططات تدفق التحكم (CFG) عبر الانهيارات المتتالية للرسوم البيانية الفرعية (إلى عقدة واحدة في النهاية لمخططات تدفق التحكم السليمة) في تحسين المترجمات الحديثة . مع ذلك، يُستبدل مفهوم بنية التحكم ذات المدخل الواحد والمخرج الواحد، المُستمد من البرمجة الهيكلية، بمفهوم الحلقة الطبيعية ، والتي تُعرَّف بأنها "حلقة ذات مدخل واحد ومخارج متعددة، مع فرع واحد فقط يعود إلى المدخل من داخلها". تُسمى مناطق مخطط تدفق التحكم التي لا يمكن اختزالها إلى حلقات طبيعية بالمناطق غير المناسبة ؛ وتتميز هذه المناطق بتعريف بسيط نسبيًا: مكونات مخطط تدفق التحكم ذات مداخل متعددة ومترابطة بقوة. وبالتالي، فإن أبسط منطقة غير مناسبة هي حلقة ذات نقطتي دخول. لا تُسبب المخارج المتعددة مشاكل تحليلية في المترجمات الحديثة. بينما تُسبب المناطق غير المناسبة (المداخل المتعددة للحلقات) صعوبات إضافية في تحسين الكود. ^{[ 7 ]}

• تاريخ هندسة البرمجيات
• مسار اتخاذ القرار
• تعقيد الحلقات