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

أي ترميز يصف حدًا أعلى للنمو؟

1. AO الكبير (Big O)
2. Bثيتا الكبير (Big Theta)
3. Cأوميغا الكبير (Big Omega)
4. Dأوميغا الصغير (Little omega)

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

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

يقيس التعقيد المكاني:

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

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

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

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

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

أي أمرين يجب إثباتهما لإثبات أن مسألة القرار X هي NP-تامة؟

1. Aأن X تنتمي إلى P، وأن X تُختزل إلى SAT
2. Bأن X تنتمي إلى NP، وأن مسألة NP-تامة معروفة تُختزل إلى X في زمن كثير حدود
3. Cأن X ليس لها خوارزمية كثيرة حدود، وأن X قابلة للحسم
4. Dأن X تُختزل إلى مسألة في P، وأن X تنتمي إلى NP

لماذا قد تعطي خوارزمية Dijkstra نتائج خاطئة حين تكون بعض أوزان الحواف سالبة؟

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