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

يقيس التعقيد المكاني:

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو أسرع من g تمامًا
2. Bأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا
3. Cأن f تنمو أبطأ من g تمامًا
4. Dأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

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

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

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

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

ماذا يقيس التحليل المستهلَك (amortised)؟

1. Aكلفة الخوارزمية على أفضل مدخل
2. Bمتوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
3. Cالكلفة المتوقعة على مدخلات عشوائية
4. Dكلفة أغلى عملية منفردة في أي موضع من السلسلة

ما زمن تنفيذ خوارزمية Dijkstra مع كومة ثنائية على رسم بياني فيه V رأسًا وE حافة؟

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

ما الفرق بين مسألة غير قابلة للحسم ومسألة غير قابلة للمعالجة؟

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