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

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

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

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

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالبرمجة الديناميكية
2. Bفرّق تسُد
3. Cالقوة الغاشمة
4. Dالاختيار الجشع

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aنعم، لكن فقط إذا كانت n أصغر من 100
2. Bلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
3. Cنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
4. Dلا، لأن n³ أصغر من n² عندما تكون n كبيرة

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

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

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

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(n³)
2. BO(n!)
3. CO(2^n²)
4. DO(n² 2ⁿ)

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

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