ورقة عمل الخوارزميات والتعقيد مع الإجابات

ما خوارزمية القوة الغاشمة؟

1. Aخوارزمية تخمّن إجابة عشوائيًا
2. Bخوارزمية تستخدم العودية دائمًا
3. Cخوارزمية تجرّب كل الحلول المرشحة الممكنة
4. Dخوارزمية تعمل على معالجات كثيرة

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالبرمجة الديناميكية
2. Bفرّق تسُد
3. Cالاختيار الجشع
4. Dالقوة الغاشمة

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aخطي
2. Bلوغاريتمي
3. Cثابت
4. Dتربيعي

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
2. Bأقصر المسارات بين كل أزواج الرؤوس في O(V³)
3. Cشجرة امتداد صغرى في O(E log V)
4. Dترتيبًا طوبولوجيًا في O(V²)

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن الفرز بالدمج O(n) أصلًا
2. Bلأن الفرز بالدمج ليس له بنية عودية
3. Cلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
4. Dلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن الفرز بالإدراج O(n log n) في أسوأ الحالات
2. Bلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
3. Cلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
4. Dلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر

أي عبارة عن P و NP صحيحة؟

1. ANP تعني «ليست كثيرة الحدود» (not polynomial)
2. Bثبت أن P ≠ NP
3. Cكل مسألة في P تنتمي أيضًا إلى NP
4. Dلا يمكن التحقق من حلول مسائل NP بسرعة

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتعدّ الدورات بالبحث بالعمق أولًا
2. Bتتحقق مما إذا كانت لأي حافة وزن سالب
3. Cبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة
4. Dتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات