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

أي من أزمنة التنفيذ هذه كثير حدود؟

1. AO(nⁿ)
2. BO(n!)
3. CO(2ⁿ)
4. DO(n³)

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(V²)
2. BO(E log V)
3. CO(V + E)
4. DO(V × E)

أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟

1. Aالفرز بالدمج (Merge sort)
2. Bالفرز الفقاعي (Bubble sort)
3. Cالفرز بالكومة (Heap sort)
4. Dالفرز السريع (Quicksort)

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

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

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

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

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

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

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأنها تعمل فقط عندما W = 0
2. Bلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
3. Cلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
4. Dلأن n صغيرة دائمًا

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. Aإرضاء الدارات
2. B2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
3. C3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
4. DSAT العامة على صيغ في الصيغة العادية العطفية