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

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

ماذا يعني أن لمسألة بنية فرعية مثلى؟

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

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن الفرز بالدمج ليس له بنية عودية
2. Bلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
3. Cلأن الفرز بالدمج O(n) أصلًا
4. Dلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
2. Bلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
3. Cلأن n صغيرة دائمًا
4. Dلأنها تعمل فقط عندما W = 0

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. Aإرضاء الدارات
2. B2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
3. CSAT العامة على صيغ في الصيغة العادية العطفية
4. D3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط