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

ما الخوارزمية؟

1. Aسلسلة منتهية من الخطوات المحددة جيدًا تحل مسألة
2. Bأي برنامج حاسوبي له واجهة رسومية
3. Cبنية بيانات تخزّن الأعداد
4. Dلغة برمجة مصممة لكتابة الصيغ الرياضية

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز بالدمج
2. Bالفرز بالإدراج
3. Cالفرز الفقاعي
4. Dالفرز السريع (Quicksort)

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

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

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

أي عبارة صحيحة عن دالة عودية ليس لها حالة أساس قابلة للبلوغ؟

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

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

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

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

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

أي عبارة عن P و NP صحيحة؟

1. Aلا يمكن التحقق من حلول مسائل NP بسرعة
2. Bثبت أن P ≠ NP
3. CNP تعني «ليست كثيرة الحدود» (not polynomial)
4. Dكل مسألة في P تنتمي أيضًا إلى NP