Algorithm Design Techniques

الفصل الثاني عشر: استراتيجيات تصميم الخوارزميات

الهدف: تعلم كيف تفكر كمهندس برمجيات لحل المشاكل المعقدة بذكاء.
1

Greedy Algorithms (الخوارزميات الجشعة)

المبدأ:

اتخذ القرار الذي يبدو أفضل حالياً (Locally Optimal) في كل خطوة، على أمل أن يؤدي ذلك إلى الحل الأفضل كلياً (Globally Optimal).

أمثلة ناجحة:

  • Change Making Problem: (في معظم العملات) لإعطاء باقي، اختر أكبر قطعة نقدية ممكنة أولاً.
  • Huffman Coding: لضغط الملفات.
  • Dijkstra & Prim: خوارزميات الرسوم البيانية تعتمد على مبدأ الجشع.
متى تفشل؟

في بعض أنظمة العملات (مثلاً عملات 1، 3، 4). لجمع 6:
Greedy: 4 + 1 + 1 (3 قطع).
Optimal: 3 + 3 (قطعتان!).
هنا الجشع لا يعطي الحل الأمثل .

2

Divide and Conquer (فرق تسد)

المبدأ:

قسّم المشكلة إلى مشاكل فرعية (Subproblems) أصغر، حلها (عادةً بالاستدعاء الذاتي Recursion)، ثم ادمج (Combine) الحلول.

Mergesort $T(N) = 2T(N/2) + O(N)$
Quicksort $T(N) = 2T(N/2) + O(N)$
Binary Search $T(N) = T(N/2) + O(1)$

معادلات التكرار (Recurrence Relations) تحدد التعقيد الزمني .

3

Dynamic Programming (البرمجة الديناميكية)

المبدأ:

حل المشاكل الفرعية مرة واحدة فقط، واحفظ نتيجتها في جدول (Table) لاستخدامها لاحقاً.
تستخدم عندما تكون المشاكل الفرعية متداخلة (Overlapping Subproblems).

مثال: فيبوناتشي (Fibonacci)

  • Recursion (Naive): يحسب $Fib(3)$ عدة مرات. التعقيد $O(2^N)$.
  • DP (Smart): يحسب $Fib(0), Fib(1), \dots$ بالترتيب ويخزنهم في مصفوفة. التعقيد $O(N)$ فقط!
int[] memo = new int[N+1];
memo[0] = 0; memo[1] = 1;
for(i=2; i<=N; i++)
  memo[i] = memo[i-1] + memo[i-2];

هذا يحول خوارزمية أسية (مستحيلة) إلى خوارزمية خطية (سريعة جداً).

🛡️ EXAM VAULT (خزنة الاختبار)
DISTINCTION / فرق جوهري

Divide & Conquer vs Dynamic Programming

D&C: المشاكل الفرعية مستقلة (Disjoint). (مثل MergeSort، النصف اليمين لا علاقة له باليسار).
DP: المشاكل الفرعية متداخلة (Overlapping). (مثل Fibonacci، حساب 5 يحتاج 4 و 3، وحساب 4 يحتاج 3 و 2... الـ 3 تكررت!).

TRAP / فخ

Greedy is not always Optimal

لا تنجرف لاستخدام الحل الجشع دائماً.
يجب إثبات أن الحل المحلي يؤدي للحل الكلي.
مشكلة 0/1 Knapsack (حقيبة الظهر) لا يمكن حلها بالجشع، وتتطلب Dynamic Programming للحصول على الحل الأمثل.

→ السابق (Ch 11) الفصل التالي (Ch 13) ←