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

ماذا يتطلب البحث الثنائي في مدخلاته؟

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

ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟

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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

1. Aالزمن الذي تستغرقه على أصغر مدخل
2. Bالزمن الذي تستغرقه على حاسوب بطيء
3. Cالزمن المتوقع الذي تستغرقه على مدخل عشوائي بحجم n
4. Dأقصى زمن تستغرقه على كل المدخلات ذات الحجم n

ترتب مصفوفة من n عنصر مرة واحدة ثم تجيب عن k استعلام عضوية بالبحث الثنائي. ما الكلفة الكلية؟

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

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 1,000
2. Bنحو 20
3. Cنحو 100
4. Dنحو 500,000

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

1. Aضعف حجم الغطاء الرأسي الأصغر على الأكثر
2. Bغطاء رأسي أصغر دائمًا
3. Cجودته مجهولة مقارنةً بالأمثل
4. Dlog n ضعف الأصغر على الأكثر

لإثبات أن مسألة جديدة X هي NP-صعبة، ماذا يجب أن تفعل؟

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