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

تستغرق خوارزمية O(n) ثلاث ثوانٍ عند n = مليون. كم تستغرق تقريبًا عند n = مليونين؟

1. A6 ثوانٍ
2. B12 ثانية
3. C3 ثوانٍ
4. D9 ثوانٍ

ما التذكير (Memoisation)؟

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

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

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

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

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

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

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

تكون المسألة NP-كاملة (NP-complete) إذا كانت:

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

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

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