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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو أبطأ من g تمامًا
2. Bأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
3. Cأن f تنمو أسرع من g تمامًا
4. Dأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

1. Aلم يكن بالإمكان حلها إلا بتجربة كل الاحتمالات
2. Bأمكن حلها في زمن كثير حدود
3. Cلم يكن لها حل
4. Dأمكن حلها في زمن ثابت

ما التعقيد الزمني للفرز بالإدراج في أفضل الحالات، على مصفوفة مرتبة مسبقًا؟

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

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

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

الخوارزمية الجشعة (Greedy):

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

لإثبات أن مسألة جديدة X هي NP-صعبة، ماذا يجب أن تفعل؟

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

ما الفرق بين مسألة غير قابلة للحسم ومسألة غير قابلة للمعالجة؟

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