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

ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟

1. Aأنها تعالج عنصرًا واحدًا بالضبط في كل ثانية من زمن التشغيل
2. Bأنها تستغرق ثانية واحدة بالضبط دائمًا
3. Cأن زمن تنفيذها لا ينمو مع حجم المدخلات
4. Dأنها لا يمكن تنفيذها إلا مرة واحدة

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز السريع (Quicksort)
2. Bالفرز الفقاعي
3. Cالفرز بالإدراج
4. Dالفرز بالدمج

ما الخوارزمية؟

1. Aسلسلة منتهية من الخطوات المحددة جيدًا تحل مسألة
2. Bلغة برمجة مصممة لكتابة الصيغ الرياضية
3. Cبنية بيانات تخزّن الأعداد
4. Dأي برنامج حاسوبي له واجهة رسومية

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(log n)

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

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

ما حل علاقة التكرار T(n) = 2T(n/2) + O(1)؟

1. AO(n²)
2. BO(n log n)
3. CO(log n)
4. DO(n)

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

1. Aتصبح كل الخوارزميات ذات الزمن الأسّي خطية فورًا
2. Bيمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
3. Cتنتقل تلك المسألة وحدها إلى P
4. Dتصبح مسألة التوقف قابلة للحسم

أي تعريف للفئة NP صحيح؟

1. Aالمسائل غير كثيرة الحدود
2. Bالمسائل التي لا يمكن حلها في زمن كثير حدود
3. Cالمسائل التي لا تستطيع أي خوارزمية حلها
4. Dمسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة