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

ما قيمة log₂ 1024؟

1. A512
2. B10
3. C12
4. D32

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

1. AΩ (أوميغا الكبير)
2. Bo (o الصغير)
3. CΘ (ثيتا الكبير)
4. DO (O الكبير)

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

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

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

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

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
2. Bتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
3. Cتحذف أغلى حافة حتى لا تبقى دورات
4. Dترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

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

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

1. AΘ(n)
2. BΘ(n log² n)
3. CΘ(n log n)
4. DΘ(n²)