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

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

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

تستغرق خوارزمية O(n²) ثانية واحدة عند n = 1000. كم تستغرق تقريبًا عند n = 2000؟

1. Aثانية واحدة
2. B4 ثوانٍ
3. C8 ثوانٍ
4. Dثانيتين

ما التذكير (Memoisation)؟

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

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟

1. Aالبحث بالعمق أولًا (DFS)
2. Bخوارزمية ديكسترا (Dijkstra)
3. Cخوارزمية بيلمان–فورد مطلوبة في جميع الحالات
4. Dخوارزمية كروسكال (Kruskal)

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

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

هل 2²ⁿ تنتمي إلى O(2ⁿ)؟

1. Aلا، لأن 2²ⁿ = 4ⁿ و4ⁿ / 2ⁿ = 2ⁿ تنمو بلا حد
2. Bنعم، لأن كلتيهما أسيتان
3. Cنعم، لأن المعاملات الثابتة في الأس تُهمَل دائمًا في O الكبير
4. Dلا، لأن 2²ⁿ تنمو أبطأ من 2ⁿ