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

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

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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

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

الوصول إلى عنصر في مصفوفة عبر فهرسه يستغرق:

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

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

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 4 قطع، والأمثل 3
2. Bتستخدم الجشعة 3 قطع، والأمثل 3
3. Cتستخدم الجشعة 3 قطع، والأمثل 2
4. Dتستخدم الجشعة قطعتين، والأمثل 2

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتتحقق مما إذا كانت لأي حافة وزن سالب
2. Bبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة
3. Cتعدّ الدورات بالبحث بالعمق أولًا
4. Dتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات

ماذا أثبتت مبرهنة Cook–Levin؟

1. Aأن P لا تساوي NP
2. Bأن كل مسألة NP يمكن حلها في زمن أسّي
3. Cأن مسألة الإرضاء البولياني (SAT) هي NP-تامة
4. Dأن مسألة التوقف غير قابلة للحسم