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

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

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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(E log V)
2. BO(V²)
3. CO(V × E)
4. DO(V + E)

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة
2. Bتحذف أغلى حافة حتى لا تبقى دورات
3. Cتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
4. Dتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 1,000
2. Bنحو 20
3. Cنحو 500,000
4. Dنحو 100

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

كيف تُصنَّف مسألة البائع المتجول؟

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

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

1. Aيمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
2. Bتنتقل تلك المسألة وحدها إلى P
3. Cتصبح مسألة التوقف قابلة للحسم
4. Dتصبح كل الخوارزميات ذات الزمن الأسّي خطية فورًا