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

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز الفقاعي
2. Bالفرز بالدمج
3. Cالفرز بالإدراج
4. Dالفرز السريع (Quicksort)

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

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

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

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

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

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

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aشجرة امتداد صغرى في O(E log V)
2. Bأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
3. Cترتيبًا طوبولوجيًا في O(V²)
4. Dأقصر المسارات بين كل أزواج الرؤوس في O(V³)

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

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

لإثبات أن مسألة جديدة X هي NP-صعبة، ماذا يجب أن تفعل؟

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

هل 2²ⁿ تنتمي إلى O(2ⁿ)؟

1. Aنعم، لأن المعاملات الثابتة في الأس تُهمَل دائمًا في O الكبير
2. Bنعم، لأن كلتيهما أسيتان
3. Cلا، لأن 2²ⁿ = 4ⁿ و4ⁿ / 2ⁿ = 2ⁿ تنمو بلا حد
4. Dلا، لأن 2²ⁿ تنمو أبطأ من 2ⁿ