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

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

1. Aثيتا الكبير (Big Theta)
2. Bأوميغا الصغير (Little omega)
3. CO الكبير (Big O)
4. Dأوميغا الكبير (Big Omega)

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

ما قيمة log₂ 1024؟

1. A10
2. B512
3. C12
4. D32

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

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

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

1. AO(n log n)
2. BO(n²)
3. CO(dn log k)
4. DO(d(n + k))

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

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

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

أي تعريف للفئة P صحيح؟

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