الخوارزميات، المسارات والأدلة على الصحة
مُقدَّم| English | المعنى |
|---|---|
| algorithm/ˈælɡərɪθəm/ | الخوارزمية |
| boundary test/ˈbaʊndəri test/ | اختبار الحدود |
ما الذي يفسر هذه الملاحظة؟
- يمكن للخوارزمية أن تعمل في مثال واحد وتنهار عند حدّ ما. يجب تصميم الاختبارات بناءً على المواصفات، وليس فقط المسار السعيد (happy path).
- ابدأ بتوقع. حدد الكميات أو الخصائص التي ستقارنها، ثم حدد الدليل الذي يمكنه التمييز بين تفسيرين.
بناء النموذج
- الخوارزمية هي إجراء محدود وغير غامض لمهمة معينة. يسجل التتبع تغيرات الحالة. ثبات الحلقة يصف خاصية يحافظ عليها كل تكرار ويساعد في تبرير الصحة.
- الخوارزمية: إجراء محدود يحل مهمة مُصاغة؛ اختبار الحدود: اختبار عند حد نطاق الإدخال المسموح به.
ما الذي يجب توفره قبل تطبيق البحث الثنائي العادي على قائمة؟
Difficulty 1/5 · 100 coins + a small bonus on first completion today
يبحث الثنائي عن نصف القائمة بالمقارنة مع المنتصف، وهذا يعمل فقط إذا كانت القائمة مرتبة وفقاً لقاعدة المقارنة. القيم المكررة مقبولة، ويعمل مع أي طول.
طابق كل مصطلح تقني مع معناه الدقيق.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
استخدم التعريفات للتمييز بين الكميات والعمليات ذات الصلة.
اختر دليلاً لاختبار الفرضية
- حدد شروط الإدخال والمخرجات المتوقعة. استخدم الحالات الحدية، المجموعات الفارغة حيث يُسمح، المكررات والقيم غير الصالحة. ميّز بين الخوارزمية الخاطئة والتنفيذ الخاطئ أو المتطلبات غير المكتملة.
- تتبع عملية البحث في قائمة وهمية صغيرة مرتبة. حدد نظام الترقيم. بالنسبة للبحث الثنائي، حدّث الحدود بحيث ينكمش الفترة المتبقية ورفض المدخلات غير المرتبة إلا إذا كان الفرز جزءاً من المهمة.
أي عادة من العادتين تجعل التحقيق أو النموذج في هذه الحالة أكثر قابلية للدفاع؟
Difficulty 2/5 · 140 coins + a small bonus on first completion today
توضيح الشروط والافتراضات يسمح للآخرين بتكرار العمل بدقة، وتسجيل الأدلة الداعمة يتيح لهم التحقق من الاستنتاج. إخفاء النتائج المتعارضة يزيل الأدلة التي قد تتحدى استنتاجًا خاطئًا، ولا يمكن لقياس واحد أن يثبت ادعاءً أوسع.
اعتمد على كميات معروفة
- أدر القيم المعروفة ووحداتها. اختر العلاقة لأن افتراضاتها تتناسب مع هذه الحالة، ثم أعد ترتيب المعادلة قبل التعويض.
- معلوم: يمكن أن يتطلب البحث الخطوي في قائمة مكونة من ثماني عناصر ثماني مقارنات عندما يكون العنصر المطلوب أخيراً أو غائباً. مضاعفة طول القائمة تضاعف عدد المقارنات في أسوأ حالة تحت هذا النموذج. يقلل البحث الثنائي الفترة بنحو النصف في كل خطوة لكنه يتطلب هيكلاً مرتباً مناسباً.
يبحث البحث الخطوي عبر جميع 14 عناصر دون إيجاد تطابق. كم عدد مقارنات العناصر التي تحدث؟ استخدم نفس التسلسل: الكميات المعلومة → النموذج → العلاقة → التعويض → الوحدة والتفسير.
البحث الخطي يفحص جميع 14 عناصر دون العثور على تطابق. كم عدد عمليات مقارنة العناصر التي تحدث؟
Difficulty 2/5 · 140 coins + a small bonus on first completion today
النتيجة هي 14 مقارنة. المعطيات: بحث خطي عبر 14 عنصر بدون تطابق. يجب مقارنة كل عنصر قبل التأكد من عدم وجوده، لذا المقارنات = 14. البحث الفاشل يكلف دائماً الطول الكامل.
تحقق من الاستنتاج وحدوده
- لا يثبت اختبار عينة ناجح الصحة لجميع المدخلات الصالحة. لا تستورد صيغة شبه الكود الخاصة بكامبريدج إلى منهج IB بدون مصدر للمنهج.
- عُد إلى الملاحظة الأصلية. اشرح ما يدعمه النتيجة، وما هي الشروط التي تفترضها، وطريقة واحدة لاختبار تفسير منافس.
يعمل اختبار عينة واحد بنجاح على إثبات صحة الخوارزمية لجميع المدخلات الصالحة. هذا الادعاء خاطئ: اختبار واحد ناجح يظهر أن الخوارزمية تعمل على تلك المدخلات فقط. تتطلب الصحة استدلالًا على جميع المدخلات الصالحة أو برهانًا - فحالات الحواف مثل القوائم الفارغة والقيم الحدودية هي بالضبط حيث تفشل الكود غير المختبر.
الخوارزميات والتتبع وأدلة الصحة: حدد شروط الإدخال والمخرجات المتوقعة. استخدم الحالات الحدية، المجموعات الفارغة حيث يُسمح، المكررات والقيم غير الصالحة. ميّز بين الخوارزمية الخاطئة والتنفيذ الخاطئ أو المتطلبات غير المكتملة.
عينة اختبار واحدة ناجحة تثبت صحة الخوارزمية لجميع المدخلات الصالحة.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
اختبار واحد ناجح يظهر أن الخوارزمية تعمل على ذلك الإدخال فقط. الصواب يتطلب استنتاجاً شاملاً لجميع المدخلات الصالحة أو إثباتاً - فالحالات الحدية مثل القوائم الفارغة والقيم الحدودية هي بالضبط حيث تفشل الكود غير المختبر.
إجراء محدود يحل مهمة محددة: اكتب المصطلح التقني.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
الخوارزمية تعني إجراء محدود يحل مهمة مُحدَّدة.