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

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

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالاختيار الجشع
2. Bفرّق تسُد
3. Cالبرمجة الديناميكية
4. Dالقوة الغاشمة

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟

1. Aاختر النشاط الذي يبدأ أبكر
2. Bاختر أقصر نشاط أولًا
3. Cاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة
4. Dاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

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

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

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

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

1. AΘ(n² log n)
2. BΘ(n^{log₂ 7})، أي نحو n^2,81
3. CΘ(n²)
4. DΘ(n³)