CS353 · مراجعة شاملة

مراجعة الاختبار النهائي - الخوارزميات

يغطي منهج الاختبار من الوحدة 7 إلى 13

الوحدة 7 الوحدة 8 الوحدة 9 الوحدة 10 الوحدة 11 الوحدة 12 الوحدة 13 المعادلات مقارنة الخوارزميات خزنة الامتحان

7 التحويل والحل: الكومة واختزال المشكلات

استخدام استراتيجية التحويل والحل لتصميم خوارزميات فعالة من خلال بنية الكومة واختزال المشكلات.

7.1 تعريف الكومة وخصائصها

الكومة هي شجرة ثنائية شبه مكتملة يكون فيها مفتاح كل أب أكبر من أو يساوي مفاتيح أبنائه، مثل هرم إداري يكون فيه المدير دائماً أعلى رتبة من مرؤوسيه.

الكومة (Heap) هي شجرة ثنائية تحتوي على مفاتيح في عقدها (مفتاح واحد لكل عقدة) وتحقق شرطين أساسيين:

  1. هي شجرة شبه مكتملة (Essentially complete)، أي أن جميع مستوياتها ممتلئة باستثناء المستوى الأخير الذي قد تنقصه بعض العقد من جهة اليمين.
  2. شرط سيادة الأب: المفتاح في كل عقدة يجب أن يكون أكبر من أو يساوي جميع المفاتيح في أبنائها (وأحفادها).

من الخصائص المهمة للكومة أن الجذر يحتوي دائماً على المفتاح الأكبر، وأن كل شجرة فرعية داخل الكومة تعتبر كومة بحد ذاتها.

ارتفاع الكومة التي تحتوي على n من العقد هو h = ⌊log2 n⌋.

ارتفاع الكومة التي تحتوي على n من العقد. \[h = \lfloor \log_2 n \rfloor\]

7.2 تمثيل الكومة باستخدام المصفوفة

يمكن تخزين الكومة في مصفوفة عادية حيث يتم حساب مواقع الأبناء والآباء باستخدام عمليات حسابية بسيطة على الأدلة (Indices).

نظراً لأن الكومة شجرة شبه مكتملة، يمكن تمثيلها بسهولة وكفاءة كمصفوفة. يتم تخزين العناصر بترتيب من أعلى لأسفل ومن اليسار لليمين.

إذا افترضنا أن الفهرسة تبدأ من 1 (لتسهيل الحسابات)، فإن:

  • الابن الأيسر للعقدة j يقع في الدليل 2j.
  • الابن الأيمن للعقدة j يقع في الدليل 2j+1.
  • الأب للعقدة j يقع في الدليل ⌊j/2⌋.
  • العقد الداخلية (الآباء) تشغل المواقع الأولى حتى ⌊n/2⌋ في المصفوفة.
معادلات حساب أدلة الأبناء والآباء في المصفوفة. \[Left(j) = 2j, \quad Right(j) = 2j+1, \quad Parent(j) = \lfloor j/2 \rfloor\]

7.3 خوارزمية الترتيب بالكومة (Heapsort)

الترتيب بالكومة يحول المصفوفة إلى كومة، ثم يسحب العنصر الأكبر (الجذر) مراراً وتكراراً ويضعه في نهاية المصفوفة.

تتكون خوارزمية الترتيب بالكومة من مرحلتين:

  • المرحلة 1: بناء كومة (Max-Heap) لقائمة معطاة من n مفتاح (باستخدام طريقة Bottom-up).
  • المرحلة 2: تكرار عملية إزالة الجذر n-1 مرة. في كل مرة، يتم تبديل المفتاح في الجذر (الأكبر) مع المفتاح في آخر ورقة (أقصى اليمين). ثم يتم تقليل حجم الكومة بمقدار 1، ويتم تطبيق عملية الإصلاح (Heapify) على الجذر الجديد لدفعه للأسفل حتى يتحقق شرط الكومة مجدداً.
التعقيد الزمني للمرحلة الثانية من الترتيب بالكومة. \[C(n) = \sum_{i=1}^{n-1} 2\log_2 i \in \Theta(n \log n)\]

7.4 اختزال المشكلات (Problem Reduction)

اختزال المشكلة يعني تحويل مشكلة لا نعرف حلها إلى مشكلة أخرى نمتلك خوارزمية جاهزة لحلها.

لإثبات الحد الأدنى لمسألة P، يمكننا اختزال مسألة Q (ذات حد أدنى معروف) إلى المسألة P.

الفكرة هي: إذا كانت المسألة P صعبة على الأقل مثل المسألة Q، فإن الحد الأدنى لـ Q هو أيضاً حد أدنى لـ P.

يجب الانتباه لاتجاه الاختزال: نحن نختزل المسألة المعروفة (Q) إلى المسألة المجهولة (P).

معادلة اختزال حساب المضاعف المشترك الأصغر إلى القاسم المشترك الأكبر. \[LCM(x, y) = \frac{x \times y}{GCD(x, y)}\]

8 مقايضات المساحة والوقت

استخدام ذاكرة إضافية لتسريع تنفيذ الخوارزمية من خلال تحسين المُدخلات أو الهيكلة المسبقة.

8.1 مقايضات المساحة والوقت

استخدام ذاكرة إضافية لتسريع تنفيذ الخوارزمية، مثل حفظ إجابات مسبقة لتجنب إعادة حسابها.

في تصميم الخوارزميات، تعتبر مقايضة المساحة بالوقت تقنية شائعة جداً، وهي أكثر انتشاراً من مقايضة الوقت بالمساحة.

تنقسم هذه التقنية إلى نوعين رئيسيين: تحسين المُدخلات (Input Enhancement) حيث يتم معالجة المُدخلات مسبقاً لتخزين معلومات تُستخدم لاحقاً (مثل الفرز بالعد ومطابقة السلاسل)، والهيكلة المسبقة (Prestructuring) حيث يتم إعادة هيكلة المُدخلات لتسهيل الوصول إليها (مثل الجداول المجزأة Hashing وأشجار B-trees).

8.2 خوارزمية هورسبول

نسخة مبسطة من Boyer-Moore تقارن من اليمين لليسار وتستخدم جدول إزاحة واحد لتخطي عدة أحرف دفعة واحدة.

تعتمد خوارزمية هورسبول على تحسين المُدخلات من خلال المعالجة المسبقة للنمط لإنشاء جدول إزاحة (Shift Table).

تقارن الخوارزمية أحرف النمط مع النص من اليمين إلى اليسار. عند حدوث عدم تطابق، تحدد الخوارزمية مقدار الإزاحة بناءً على حرف النص (c) الذي تمت محاذاته مع آخر حرف في النمط، وذلك بالرجوع إلى جدول الإزاحة.

8.3 خوارزمية بوير-مور

خوارزمية مطابقة متقدمة تقارن من اليمين لليسار وتستخدم جدولين (الرمز السيئ واللاحقة الجيدة) لتحديد أقصى إزاحة ممكنة.

تعتمد خوارزمية Boyer-Moore على فكرتين: مقارنة الأحرف من اليمين إلى اليسار، وحساب الإزاحة مسبقاً في جدولين.

جدول الرمز السيئ (Bad-symbol table) يحدد الإزاحة بناءً على حرف النص الذي تسبب في عدم التطابق.

جدول اللاحقة الجيدة (Good-suffix table) يحدد الإزاحة بناءً على الجزء الذي تطابق بنجاح من النمط (اللاحقة)، مستفيداً من البنية الدورية للنمط.

الخوارزمية تختار الإزاحة الأكبر بين الجدولين.

معادلة حساب الإزاحة النهائية في خوارزمية بوير-مور. \[d = \max \{d_1, d_2\}\]

9 الوحدة 9: مقايضات المساحة والوقت (التهشير وأشجار B)

استخدام التهشير وأشجار B كأدوات قوية لفهرسة البيانات والوصول السريع إليها.

9.1 أساسيات التهشير (Hashing)

التهشير هو طريقة فعالة لتنفيذ قاموس باستخدام دالة رياضية لتعيين المفاتيح إلى مواقع في جدول.

تعتمد فكرة التهشير على تعيين مفاتيح ملف بحجم $n$ إلى جدول بحجم $m$ (يسمى جدول التهشير) باستخدام دالة محددة مسبقاً تسمى دالة التهشير $h(K)$.

يجب أن تكون دالة التهشير الجيدة سهلة الحساب وتوزع المفاتيح بالتساوي تقريباً في جميع أنحاء الجدول.

من التطبيقات المهمة للتهشير: جداول الرموز وقواعد البيانات.

دالة التهشير الشائعة حيث m هو عدد صحيح. \[h(K) = K \bmod m\]

9.2 التصادمات والتهشير المفتوح

يحدث التصادم عندما يتم تعيين مفتاحين لنفس الموقع. التهشير المفتوح يحل ذلك بتخزين المفاتيح في قوائم مرتبطة خارج الجدول.

إذا كان $h(K_1) = h(K_2)$، فهناك تصادم. حتى مع الدوال الجيدة، يُتوقع حدوث تصادمات (مفارقة عيد الميلاد).

في التهشير المفتوح (السلسلة المنفصلة)، يتم تخزين المفاتيح في قوائم مرتبطة خارج جدول التهشير، حيث تعمل عناصر الجدول كرؤوس لهذه القوائم.

إذا وزعت الدالة المفاتيح بشكل موحد، فإن متوسط طول القائمة المرتبطة سيكون $\alpha = n/m$ (عامل التحميل).

لا يزال التهشير المفتوح يعمل حتى لو كان عدد المفاتيح أكبر من حجم الجدول ($n > m$).

متوسط عدد الفحوصات في عمليات البحث غير الناجحة للتهشير المفتوح. \[U = \alpha\]

9.3 أشجار B وخصائصها

شجرة B هي شجرة بحث متوازنة تسمح بتخزين مفاتيح متعددة في نفس العقدة، وهي مثالية لفهرسة البيانات على الأقراص.

أشجار B هي أداة رئيسية لتنظيم مجموعات البيانات كفهرس. تسمح بأكثر من مفتاح واحد في نفس العقدة.

في إصدار B-tree، يتم تخزين جميع سجلات البيانات في الأوراق بترتيب تصاعدي. العقد الأبوية تُستخدم للفهرسة وتحتوي على $n-1$ مفاتيح مرتبة.

خصائص شجرة B من الرتبة $m \ge 2$:

  • الجذر إما ورقة أو له بين 2 و $m$ أبناء.
  • كل عقدة (باستثناء الجذر والأوراق) لها بين $\lceil m/2 \rceil$ و $m$ أبناء.
  • الشجرة متوازنة تماماً (جميع الأوراق في نفس المستوى).
التعقيد الزمني الإجمالي للبحث في شجرة B باستخدام البحث الثنائي. \[O(\log_2 t \log_t n)\]

10 البرمجة الديناميكية

تقسيم المسألة إلى مشاكل فرعية متداخلة وحلها من الأسفل للأعلى مع تخزين الحلول لتجنب الحساب المتكرر.

10.1 أساسيات البرمجة الديناميكية

تقنية لتصميم الخوارزميات تعتمد على تقسيم المسألة إلى مشاكل فرعية متداخلة وحلها من الأسفل للأعلى.

البرمجة الديناميكية (Dynamic Programming) هي تقنية عامة لتصميم الخوارزميات تُستخدم لحل المسائل التي يمكن تعريفها بعلاقات تكرارية (recurrences) مع وجود مشاكل فرعية متداخلة (overlapping subproblems).

تم اختراعها بواسطة عالم الرياضيات الأمريكي ريتشارد بيلمان في الخمسينيات.

الفكرة الأساسية هي إعداد علاقة تكرارية تربط حل المسألة الأكبر بحلول المسائل الأصغر، ثم حل المسائل الأصغر مرة واحدة فقط وتسجيل حلولها في جدول (Bottom-up fashion)، واستخراج الحل النهائي من هذا الجدول.

علاقة التكرار لأرقام فيبوناتشي كمثال على البرمجة الديناميكية. \[F(n) = F(n-1) + F(n-2)\]

10.2 مسألة حقيبة الظهر باستخدام البرمجة الديناميكية

إيجاد المجموعة الفرعية الأكثر قيمة من العناصر التي يمكن وضعها في حقيبة ذات سعة محدودة.

في مسألة حقيبة الظهر (Knapsack Problem)، يُعطى عدد n من العناصر، لكل عنصر وزن صحيح w وقيمة v، وحقيبة بسعة صحيحة W.

الهدف هو إيجاد المجموعة الفرعية الأكثر قيمة التي تتسع في الحقيبة.

باستخدام البرمجة الديناميكية، نعرّف F[i, j] كأقصى قيمة يمكن الحصول عليها باستخدام أول i عناصر وسعة j.

يتم بناء جدول حيث يتم ملؤه صفاً بصف أو عموداً بعمود.

علاقة التكرار لمسألة حقيبة الظهر. \[F(i, j) = \max\{F(i - 1, j), v_i + F(i - 1, j - w_i)\}\]

10.3 خوارزمية فلويد (أقصر المسارات)

خوارزمية لإيجاد أقصر مسافة بين كل زوج من العقد في رسم بياني موزون.

تحل خوارزمية فلويد مسألة أقصر المسارات بين جميع الأزواج (All-pairs shortest paths) في رسم بياني موزون (بدون دورات ذات وزن سالب).

تستخدم نفس فكرة وارشال: بناء الحل عبر سلسلة من المصفوفات D(0), ..., D(n) باستخدام مجموعات متزايدة من العقد المسموح بها كعقد وسيطة.

علاقة التكرار لخوارزمية فلويد. \[D^{(k)}[i,j] = \min \{D^{(k-1)}[i,j], D^{(k-1)}[i,k] + D^{(k-1)}[k,j]\}\]

10.4 أشجار البحث الثنائية المثلى (OBST)

بناء شجرة بحث ثنائية بحيث تكون العناصر الأكثر بحثاً قريبة من الجذر، لتقليل متوسط وقت البحث.

أحد التطبيقات الرئيسية لـ OBST هو تنفيذ قاموس (Dictionary).

المشكلة: بالنظر إلى n مفاتيح مرتبة واحتمالات البحث عنها، أوجد شجرة بحث ثنائية (BST) بمتوسط عدد مقارنات أدنى في البحث الناجح.

نظراً لأن عدد الأشجار الممكنة ينمو بشكل أسي (أرقام كاتالان)، فإن القوة الغاشمة غير فعالة.

نستخدم البرمجة الديناميكية لحلها.

علاقة التكرار لحساب التكلفة المثلى لشجرة البحث الثنائية. \[C[i,j] = \min_{i \le k \le j} \{ C[i,k-1] + C[k+1,j] \} + \sum_{s=i}^j p_s\]

11 التقنية الجشعة

بناء الحلول خطوة بخطوة باتخاذ الخيار الأمثل محلياً دون تراجع، مما يوفر سرعة فائقة ولكنه لا يضمن الحل الأمثل دائماً.

11.1 نظرة عامة على التقنية الجشعة

استراتيجية تبني الحل خطوة بخطوة باختيار الأفضل محلياً في كل مرحلة، مثل شخص يجمع أكبر الفئات النقدية أولاً.

تقوم التقنية الجشعة ببناء حل لمشكلة تحسين (optimization problem) قطعة بقطعة من خلال سلسلة من الخيارات التي يجب أن تكون:

  1. ممكنة (feasible)،
  2. مثالية محلياً (locally optimal)،
  3. لا رجعة فيها (irrevocable).

بالنسبة لبعض المشاكل، تعطي هذه التقنية حلاً مثالياً دائماً، ولكن في معظم المشاكل لا تفعل ذلك، بل تُستخدم للحصول على تقريبات سريعة (fast approximations).

11.2 مشكلة الصرافة (إرجاع الباقي)

إعطاء الباقي بأقل عدد ممكن من العملات المعدنية.

بافتراض وجود كميات غير محدودة من العملات بفئات معينة، الهدف هو إعطاء الباقي لمبلغ n بأقل عدد من العملات.

الحل الجشع يعمل بشكل مثالي مع الفئات 'التقليدية' (مثل 25، 10، 5، 1). لكنه يفشل مع بعض الفئات غير التقليدية.

على سبيل المثال، إذا كانت الفئات هي 1، 3، 4 والمبلغ المطلوب هو 6، الخوارزمية الجشعة ستختار 4، 1، 1 (3 عملات)، بينما الحل الأمثل هو 3، 3 (عملتان فقط).

11.3 شجرة الامتداد الصغرى (MST)

ربط جميع النقاط في شبكة بأقل تكلفة ممكنة وبدون تكوين أي حلقات.

شجرة الامتداد (Spanning tree) لرسم بياني متصل هي رسم بياني فرعي متصل وخالٍ من الحلقات (acyclic) يتضمن جميع رؤوس الرسم البياني الأصلي.

شجرة الامتداد الصغرى (MST) هي شجرة امتداد لرسم بياني متصل وموزون بحيث يكون مجموع أوزان حوافها هو الأقل الممكن.

البحث الشامل (Exhaustive search) لإيجادها غير فعال بسبب العدد الهائل للأشجار الممكنة.

11.4 خوارزمية برايم (Prim's Algorithm)

تنمو الشجرة عقدة تلو الأخرى باختيار أقرب عقدة متصلة بالشجرة الحالية.

تبدأ الخوارزمية بشجرة تتكون من رأس واحد (أي رأس)، وتنمو الشجرة بإضافة رأس واحد في كل مرة لإنتاج MST.

في كل تكرار، يتم إضافة الرأس غير الموجود في الشجرة والذي يكون أقرب (بأقل وزن حافة) إلى الرؤوس الموجودة بالفعل في الشجرة (هذه هي الخطوة الجشعة!).

تتوقف الخوارزمية عند تضمين جميع الرؤوس. تتطلب طابور أولوية (priority queue / min-heap) لتحديد أقرب رأس بكفاءة.

pseudocode 
ALGORITHM Prim(G)
VT <- {v0}
ET <- empty set
for i <- 1 to |V| - 1 do
    find a minimum-weight edge e* = (v*, u*) among all edges (v, u)
    such that v is in VT and u is in V - VT
    VT <- VT U {u*}
    ET <- ET U {e*}
return ET

11.5 خوارزمية كروسكال (Kruskal's Algorithm)

ترتب جميع الحواف وتختار الأقصر دائماً، بشرط ألا تصنع حلقة مغلقة.

تنظر خوارزمية Kruskal إلى شجرة الامتداد الصغرى كرسم بياني فرعي خالٍ من الحلقات يحتوي على |V|-1 من الحواف بأقل مجموع أوزان. الخطوات:

  1. ترتيب الحواف ترتيباً تصاعدياً حسب الطول.
  2. بناء الشجرة حافة تلو الأخرى من خلال سلسلة من الغابات (forests).
  3. في كل تكرار، إضافة الحافة التالية في القائمة المرتبة ما لم تؤدِ إلى تكوين حلقة (إذا كانت ستكون حلقة، يتم تخطيها).
pseudocode 
ALGORITHM Kruskal(G)
sort E in nondecreasing order of the edge weights
ET <- empty set; ecounter <- 0
k <- 0
while ecounter < |V| - 1 do
    k <- k + 1
    if ET U {e_k} is acyclic
        ET <- ET U {e_k}; ecounter <- ecounter + 1
return ET

11.6 خوارزمية ديكسترا (Dijkstra's Algorithm)

تجد أقصر طريق من نقطة بداية واحدة إلى جميع النقاط الأخرى، مثل تطبيق خرائط جوجل.

تحل مشكلة أقصر مسار من مصدر واحد (Single Source Shortest Paths Problem).

مشابهة لخوارزمية Prim، ولكن بطريقة مختلفة لحساب التسميات الرقمية: من بين الرؤوس غير الموجودة في الشجرة، تجد الرأس u الذي يمتلك أصغر مجموع (d_v + w(v,u))، حيث d_v هو طول أقصر مسار تم إيجاده من المصدر إلى v، و w(v,u) هو وزن الحافة من v إلى u.

لا تعمل الخوارزمية مع الرسوم البيانية ذات الأوزان السالبة.

تحديث المسافة الأقصر للعقدة u عبر العقدة v. \[d_u = \min (d_v + w(v,u))\]
pseudocode 
ALGORITHM Dijkstra(G, s)
Initialize(Q)
for every vertex v in V:
    dv <- infinity; pv <- null
    Insert(Q, v, dv)
ds <- 0; Decrease(Q, s, ds)
VT <- empty set
for i <- 0 to |V| - 1 do
    u* <- DeleteMin(Q)
    VT <- VT U {u*}
    for every vertex u in V - VT adjacent to u* do
        if du* + w(u*, u) < du
            du <- du* + w(u*, u); pu <- u*
            Decrease(Q, u, du)

11.7 أشجار وأكواد هوفمان (Huffman Trees and Codes)

طريقة لضغط البيانات بإعطاء الحروف المتكررة أكواداً قصيرة، والحروف النادرة أكواداً طويلة.

الترميز (Coding) هو تعيين سلاسل بتات (bit strings) لحروف الأبجدية. كود Huffman هو مخطط ترميز متغير الطول (variable-length) وخالٍ من البادئة (prefix-free)، مما يعني أنه لا يوجد كود يمثل بادئة لكود آخر. يتم بناء شجرة Huffman جشعياً:

  1. تهيئة n أشجار ذات عقدة واحدة بأوزان تساوي تكرار الحروف.
  2. دمج الشجرتين ذواتي الأوزان الأصغر في شجرة واحدة وزنها مجموع الوزنين، وتكرار ذلك n-1 مرة.

يتم تمييز الحواف بـ 0 و 1.

12 حدود قوة الخوارزميات

فهم الحدود النظرية للخوارزميات وتصنيف المسائل إلى قابلة للحل (P) ومستعصية (NP-Complete) لتحديد متى يجب التوقف عن البحث عن حل مثالي سريع.

12.1 الحدود الدنيا (Lower Bounds)

الحد الأدنى هو تقدير لأقل قدر من العمل المطلوب لحل مسألة معينة.

الحد الأدنى يحدد أفضل كفاءة ممكنة لأي خوارزمية تحل مسألة معينة. يمكن أن يكون عددًا دقيقًا أو فئة كفاءة (Ω).

نقول أن الحد الأدنى 'محكم' (Tight) إذا كانت هناك خوارزمية موجودة بالفعل تمتلك نفس كفاءة الحد الأدنى.

من طرق إيجاد الحد الأدنى: الحدود البديهية (Trivial)، الحجج النظرية للمعلومات (أشجار القرار)، وحجج الخصم، واختزال المسائل.

تمثيل فئة الكفاءة للحد الأدنى. \[\Omega(f(n))\]

12.2 أشجار القرار (Decision Trees)

نموذج يمثل الخوارزميات التي تعتمد على المقارنات، حيث تمثل العقد الداخلية المقارنات وتمثل الأوراق النتائج النهائية.

تُستخدم أشجار القرار لإنشاء حدود دنيا نظرية للمعلومات (Information-theoretic lower bounds)، خاصة لخوارزميات الفرز والبحث.

أي خوارزمية فرز تعتمد على المقارنة يمكن تمثيلها بشجرة قرار.

لفرز n من العناصر، يجب أن تحتوي الشجرة على الأقل على n! (مضروب n) من الأوراق، لأن هناك n! ترتيب محتمل.

ارتفاع هذه الشجرة الثنائية يمثل أسوأ حالة لعدد المقارنات.

الحد الأدنى لعدد المقارنات المطلوبة لفرز n من العناصر. \[\lceil \log_2 n! \rceil \approx n \log_2 n\]

12.3 الحدود الدنيا بواسطة اختزال المسائل (Lower Bounds by Problem Reduction)

تحويل مسألة لا نعرف مدى صعوبتها إلى مسألة نعرف صعوبتها مسبقاً، لإثبات أن المسألة الجديدة صعبة على الأقل بنفس المقدار.

لإثبات الحد الأدنى لمسألة P، يمكننا اختزال مسألة Q (ذات حد أدنى معروف) إلى المسألة P. الفكرة هي: إذا كانت المسألة P صعبة على الأقل مثل المسألة Q، فإن الحد الأدنى لـ Q هو أيضاً حد أدنى لـ P. يجب الانتباه لاتجاه الاختزال: نحن نختزل المسألة المعروفة (Q) إلى المسألة المجهولة (P).

اختزال مسألة Q إلى P يثبت أن P لها نفس الحد الأدنى لـ Q. \[Q[\Omega(f)] \rightarrow P[\Omega(?)] \implies P = \Omega(f)\]

12.4 أنواع المسائل: التحسين والقرار (Problem Types: Optimization and Decision)

مسائل التحسين تبحث عن 'أفضل' حل، بينما مسائل القرار تبحث عن إجابة 'نعم/لا'.

في نظرية التعقيد، يتم تصنيف المسائل إلى مسائل قابلة للحل عملياً (Tractable) وغير قابلة للحل عملياً (Intractable).

المسألة القابلة للحل عملياً هي التي توجد لها خوارزمية تحلها في وقت كثير الحدود O(p(n)).

لتسهيل التحليل الرياضي، يتم تحويل مسائل التحسين (Optimization) التي تبحث عن الحد الأقصى أو الأدنى إلى مسائل قرار (Decision) تجيب بنعم أو لا.

12.5 الفئات P و NP (Classes P and NP)

الفئة P هي المسائل التي يسهل 'حلها'، بينما الفئة NP هي المسائل التي يسهل 'التحقق من صحة حلها'.

الفئة P تتضمن مسائل القرار التي يمكن حلها في وقت كثير الحدود O(p(n))، مثل البحث، فرادة العناصر، واختبار الأولية.

الفئة NP (كثيرة الحدود غير الحتمية) تتضمن مسائل القرار التي يمكن 'التحقق' من صحة حلولها المقترحة في وقت كثير الحدود.

يتم ذلك عبر خوارزمية غير حتمية تقوم بتخمين حل عشوائي ثم تتحقق من صحته في وقت كثير الحدود.

الفئة P هي مجموعة فرعية من الفئة NP. \[P \subseteq NP\]

12.6 المسائل الكاملة غير الحتمية (NP-Complete)

مسائل NP-Complete هي 'أصعب' المسائل في فئة NP. إذا وجدت حلاً سريعاً لواحدة منها، فقد وجدت حلاً سريعاً لجميع مسائل NP.

تكون مسألة القرار D من فئة NP-Complete إذا كانت:

  1. أولاً، تنتمي إلى فئة NP.
  2. ثانياً، كل مسألة أخرى في فئة NP يمكن اختزالها إلى D في وقت كثير الحدود.

هذا يعني أن D صعبة على الأقل مثل أي مسألة أخرى في NP.

أول مسألة تم إثبات أنها NP-Complete كانت مسألة CNF-sat عبر نظرية كوك (Cook's Theorem) عام 1971.

كل مسألة في NP تختزل في وقت كثير الحدود إلى D. \[\forall Q \in NP, Q \le_p D \implies D \text{ is NP-Hard}\]

13 التعامل مع قيود قوة الخوارزميات

استخدام تقنيات الحل الدقيق (التراجع والتفرع والحد) للمسائل الصغيرة، واللجوء إلى خوارزميات التقريب للحصول على حلول شبه مثالية سريعة للمسائل الكبيرة.

13.1 التراجع (Backtracking)

تقنية تبني شجرة فضاء الحالة وتقوم بـ 'تقليم' الفروع التي لا تؤدي إلى حل، مثل المشي في متاهة والعودة فوراً عند الوصول لطريق مسدود.

التراجع هو استراتيجية حل دقيقة تبني شجرة فضاء الحالة (State-Space Tree) حيث تمثل العقد حلولاً جزئية وتمثل الحواف الخيارات المتاحة.

تستكشف الخوارزمية الشجرة باستخدام بحث العمق أولاً (DFS). عندما تكتشف الخوارزمية أن عقدة معينة لا يمكن أن تؤدي إلى حل صحيح (عقدة غير واعدة)، فإنها تقوم بـ 'تقليم' (Pruning) الشجرة الفرعية وتتراجع إلى العقدة الأب لمواصلة البحث.

من الأمثلة الشهيرة: مشكلة ن-ملكة (n-Queens) ومشكلة الدائرة الهاملتونية (Hamiltonian Circuit).

13.2 التفرع والحد (Branch-and-Bound)

تحسين لخوارزمية التراجع مخصص لمشاكل التحسين، يستخدم 'حدوداً' لتقليم الفروع التي لا يمكن أن تقدم حلاً أفضل من الحل الحالي.

التفرع والحد هو تقنية تستخدم لحل مشاكل التحسين (Optimization Problems).

لكل عقدة (حل جزئي) في شجرة فضاء الحالة، تقوم الخوارزمية بحساب 'حد' (Bound) لقيمة دالة الهدف لجميع أحفاد تلك العقدة. يتم استخدام هذا الحد لاستبعاد العقد 'غير الواعدة' وتقليم الشجرة؛ فإذا كان حد العقدة ليس أفضل من أفضل حل تم العثور عليه حتى الآن، يتم تجاهل تلك العقدة.

مثال كلاسيكي هو مشكلة التعيين (Assignment Problem) حيث يتم حساب الحد الأدنى (Lower Bound) للتكلفة.

13.3 خوارزميات التقريب (Approximation Algorithms)

خوارزميات سريعة تجد حلولاً قريبة من الحل الأمثل للمشاكل الصعبة (NP-hard) عندما يكون إيجاد الحل الدقيق مستحيلاً في وقت معقول.

نظراً لأن المشاكل من فئة NP-hard لا تمتلك خوارزميات دقيقة تعمل في وقت متعدد الحدود (Polynomial time)، نلجأ إلى خوارزميات التقريب. هذه الخوارزميات تضمن إيجاد حل تقريبي (Sub-optimal) بسرعة.

يتم قياس جودة هذه الخوارزميات باستخدام 'نسبة الدقة' (Accuracy Ratio) و'نسبة الأداء' (Performance Ratio).

نسبة الدقة: تقسم القيمة الأكبر على الأصغر لضمان أن النسبة دائماً $\ge 1$. \[r(s_a) = \frac{f(s_a)}{f(s^*)} \text{ (Minimization)} \quad | \quad r(s_a) = \frac{f(s^*)}{f(s_a)} \text{ (Maximization)}\]

13.4 خوارزميات التقريب لمشكلة البائع المتجول (TSP Approximations)

طرق سريعة لإيجاد مسار قصير للبائع المتجول، مثل الذهاب لأقرب مدينة أو استخدام شجرة الامتداد الأصغر.

هناك عدة خوارزميات تقريب لمشكلة البائع المتجول (TSP):

  1. الجار الأقرب (Nearest-Neighbor): يذهب دائماً إلى أقرب مدينة غير مزورة. نسبة أدائها غير محدودة ($R_A = \infty$).
  2. الخوارزمية متعددة الأجزاء (Multifragment-Heuristic): ترتب الحواف تصاعدياً وتضيفها للمسار بشرط عدم تكوين رأس بدرجة 3 أو دورة غير مكتملة. تميل لإنتاج مسارات أفضل من الجار الأقرب.
  3. الدوران حول الشجرة مرتين (Twice-Around-the-Tree): تبني شجرة امتداد أصغر (MST)، ثم تقوم بجولة حول الشجرة مرتين وتختصر الرؤوس المكررة.
نسبة الأداء غير محدودة للحالات العامة لمشكلة البائع المتجول. \[R_A = \infty \text{ (for general TSP)}\]

13.5 التقريب لمشكلة حقيبة الظهر وتعبئة الصناديق

استخدام الخوارزمية الجشعة بناءً على نسبة القيمة للوزن لحقيبة الظهر، وخوارزمية التوافق الأول لتعبئة الصناديق.

مشكلة حقيبة الظهر (Knapsack): الخوارزمية الجشعة تحسب نسبة القيمة إلى الوزن ($v_i/w_i$) لكل عنصر، ترتبها تنازلياً، وتضيف العناصر حتى تمتلئ الحقيبة. نسبة الأداء لها غير محدودة في النسخة المنفصلة (0/1)، لكنها تعطي حلاً دقيقاً للنسخة المستمرة (Continuous version).

مشكلة تعبئة الصناديق (Bin Packing): خوارزمية التوافق الأول (First-Fit) ترتب العناصر تنازلياً وتولد مجموعات فرعية. دقتها محددة بـ $f(s^*) / f(s_a) \le 1 + 1/k$ وتعمل في وقت $O(kn^{k+1})$.

دقة خوارزمية التوافق الأول لمشكلة تعبئة الصناديق. \[f(s^*) / f(s_a) \le 1 + \frac{1}{k}\]

تعقيدات الخوارزميات

المعادلة / المفهوم الوحدة LaTeX / Notation
ارتفاع الكومة التي تحتوي على n من العقد. M7 \(h = \lfloor \log_2 n \rfloor\)
معادلات حساب أدلة الأبناء والآباء في المصفوفة. M7 \(Left(j) = 2j, \quad Right(j) = 2j+1, \quad Parent(j) = \lfloor j/2 \rfloor\)
التعقيد الزمني للمرحلة الثانية من الترتيب بالكومة. M7 \(C(n) = \sum_{i=1}^{n-1} 2\log_2 i \in \Theta(n \log n)\)
معادلة اختزال حساب المضاعف المشترك الأصغر إلى القاسم المشترك الأكبر. M7 \(LCM(x, y) = \frac{x \times y}{GCD(x, y)}\)
معادلة حساب الإزاحة النهائية في خوارزمية بوير-مور. M8 \(d = \max \{d_1, d_2\}\)
دالة التهشير الشائعة حيث m هو عدد صحيح. M9 \(h(K) = K \bmod m\)
متوسط عدد الفحوصات في عمليات البحث غير الناجحة للتهشير المفتوح. M9 \(U = \alpha\)
التعقيد الزمني الإجمالي للبحث في شجرة B باستخدام البحث الثنائي. M9 \(O(\log_2 t \log_t n)\)
علاقة التكرار لأرقام فيبوناتشي كمثال على البرمجة الديناميكية. M10 \(F(n) = F(n-1) + F(n-2)\)
علاقة التكرار لمسألة حقيبة الظهر. M10 \(F(i, j) = \max\{F(i - 1, j), v_i + F(i - 1, j - w_i)\}\)
علاقة التكرار لخوارزمية فلويد. M10 \(D^{(k)}[i,j] = \min \{D^{(k-1)}[i,j], D^{(k-1)}[i,k] + D^{(k-1)}[k,j]\}\)
علاقة التكرار لحساب التكلفة المثلى لشجرة البحث الثنائية. M10 \(C[i,j] = \min_{i \le k \le j} \{ C[i,k-1] + C[k+1,j] \} + \sum_{s=i}^j p_s\)
تحديث المسافة الأقصر للعقدة u عبر العقدة v. M11 \(d_u = \min (d_v + w(v,u))\)
تمثيل فئة الكفاءة للحد الأدنى. M12 \(\Omega(f(n))\)
الحد الأدنى لعدد المقارنات المطلوبة لفرز n من العناصر. M12 \(\lceil \log_2 n! \rceil \approx n \log_2 n\)
اختزال مسألة Q إلى P يثبت أن P لها نفس الحد الأدنى لـ Q. M12 \(Q[\Omega(f)] \rightarrow P[\Omega(?)] \implies P = \Omega(f)\)
الفئة P هي مجموعة فرعية من الفئة NP. M12 \(P \subseteq NP\)
كل مسألة في NP تختزل في وقت كثير الحدود إلى D. M12 \(\forall Q \in NP, Q \le_p D \implies D \text{ is NP-Hard}\)
نسبة الدقة: تقسم القيمة الأكبر على الأصغر لضمان أن النسبة دائماً $\ge 1$. M13 \(r(s_a) = \frac{f(s_a)}{f(s^*)} \text{ (Minimization)} \quad | \quad r(s_a) = \frac{f(s^*)}{f(s_a)} \text{ (Maximization)}\)
نسبة الأداء غير محدودة للحالات العامة لمشكلة البائع المتجول. M13 \(R_A = \infty \text{ (for general TSP)}\)
دقة خوارزمية التوافق الأول لمشكلة تعبئة الصناديق. M13 \(f(s^*) / f(s_a) \le 1 + \frac{1}{k}\)

مقارنة الخوارزميات

الكومة مقابل شجرة البحث الثنائية (AVL)

المعيار Heap AVL Tree
الترتيب من أعلى لأسفل (الأب ≥ الأبناء) من اليسار لليمين (اليسار < الأب < اليمين)
الوصول للعنصر الأكبر O(1) - دائماً في الجذر O(log n) - أقصى اليمين
البحث عن عنصر عشوائي O(n) - يتطلب بحث خطي O(log n)

تحسين المُدخلات مقابل الهيكلة المسبقة

المعيار Input Enhancement Prestructuring
الهدف الأساسي استخراج وتخزين معلومات إضافية من المُدخلات تغيير هيكل البيانات لتسهيل الوصول
أمثلة الفرز بالعد، خوارزميات مطابقة السلاسل الجداول المجزأة (Hashing)، أشجار B

هورسبول مقابل بوير-مور

المعيار Horspool's Algorithm Boyer-Moore Algorithm
عدد الجداول المستخدمة جدول واحد (الإزاحة / الرمز السيئ) جدولان (الرمز السيئ واللاحقة الجيدة)
التعقيد الزمني (أسوأ حالة) O(mn) O(n+m)

التهشير المفتوح مقابل التهشير المغلق

المعيار Open Hashing (Separate Chaining) Closed Hashing (Open Addressing)
مكان تخزين المفاتيح خارج الجدول (قوائم مرتبطة) داخل الجدول نفسه
العمل عندما n > m نعم، يعمل لا يعمل
استخدام المؤشرات يستخدم المؤشرات يتجنب المؤشرات
سهولة الحذف مباشر وسهل غير مباشر (معقد)

البرمجة الديناميكية مقابل فرق تسد

المعيار Dynamic Programming Divide and Conquer
طبيعة المشاكل الفرعية متداخلة (Overlapping) مستقلة (Independent)
اتجاه الحل من الأسفل للأعلى (Bottom-up) من الأعلى للأسفل (Top-down)

خوارزمية وارشال مقابل خوارزمية فلويد

المعيار Warshall's Algorithm Floyd's Algorithm
الهدف الأساسي الانغلاق المتعدي (وجود مسار) أقصر المسارات بين جميع الأزواج
العمليات المستخدمة منطقية (AND / OR) حسابية (Min / +)

مقارنة بين خوارزميات Prim و Kruskal و Dijkstra

المعيار Prim's Algorithm Kruskal's Algorithm Dijkstra's Algorithm
الهدف (المشكلة التي يحلها) شجرة الامتداد الصغرى (MST) شجرة الامتداد الصغرى (MST) أقصر مسار من مصدر واحد
طريقة الاختيار الجشع أقرب عقدة للشجرة الحالية (وزن الحافة فقط) أقصر حافة في الرسم البياني بأكمله (لا تكون حلقة) العقدة ذات أقل مسافة متراكمة من المصدر
بنية البيانات الأساسية طابور أولوية (Min-Heap) الاتحاد والبحث (Union-Find) طابور أولوية (Min-Heap)

مسائل التحسين مقابل مسائل القرار

المعيار Optimization Problem Decision Problem
الهدف إيجاد أفضل حل (أقصى/أدنى) الإجابة بنعم أو لا
الاستخدام في نظرية التعقيد معقد للتحليل الرياضي الرسمي مفضل ومناسب للتحليل الرسمي

مقارنة بين فئات P و NP و NP-Complete

المعيار Class P Class NP NP-Complete
الحل في وقت كثير الحدود نعم غير معروف (ربما لا) غير معروف (مستبعد جداً)
التحقق في وقت كثير الحدود نعم نعم نعم
أمثلة البحث، الفرز TSP، التلوين CNF-Sat

استراتيجيات الحل الدقيق مقابل خوارزميات التقريب

المعيار Exact Solutions (Backtracking, B&B) Approximation Algorithms
جودة الحل حل أمثل ودقيق 100% حل شبه أمثل (تقريبي)
وقت التشغيل أسوأ حالة تكون أسية (Exponential) وقت متعدد الحدود (Polynomial time) وسريع

التراجع مقابل التفرع والحد

المعيار Backtracking Branch-and-Bound
نوع المشاكل مشاكل البحث عن حلول (مثل n-Queens) مشاكل التحسين (Optimization)
آلية التقليم (Pruning) بناءً على قيود المشكلة (عقد غير واعدة) بناءً على حساب حدود دالة الهدف (Bounds)

🃏 البطاقات التعليمية

🎯 اختبر نفسك

1 / 372 🎯 نتيجتك: 0

حديث البروفيسور

أهلاً بكم يا أبنائي وبناتي في ليلة الامتحان النهائي لمقرر CS353. الليلة هي ليلة ربط الخيوط ورؤية الصورة الكاملة لما درسناه في النصف الثاني من هذا المقرر، من الوحدة السابعة وحتى الثالثة عشرة. دعونا نسترجع معاً كيف تتكامل هذه المفاهيم لتكوين ترسانة خوارزمية متكاملة. بدأنا بالوحدة السابعة مع استراتيجية التحويل والحل (Transform-and-Conquer)، حيث تعلمنا كيف نعيد صياغة المشكلة أو نستخدم هياكل بيانات متقدمة مثل الأكوام (Heaps) وتقليل المشكلات (Problem Reduction) لتسهيل الحل. تذكروا في الامتحان ألا تخلطوا بين هذه الاستراتيجية وبين استراتيجية التقسيم والحل؛ فالتحويل يغير طبيعة المشكلة لتصبح أسهل. بعد ذلك، انتقلنا في الوحدتين الثامنة والتاسعة إلى مبدأ مقايضة المساحة والوقت (Space and Time Trade-Offs). هنا، الفخ الشائع في الامتحان هو نسيان متى وكيف نستخدم الذاكرة الإضافية لتسريع وقت التنفيذ. لقد رأينا كيف أن تحسين المدخلات والهيكلة المسبقة، بالإضافة إلى استخدام الجداول المجزأة (Hashing) وأشجار (B-Trees)، تعتبر أدوات جبارة لفهرسة البيانات والوصول السريع إليها. اقرأوا السؤال جيداً لتعرفوا ما إذا كان المطلوب هو تحسين الوقت على حساب المساحة. ثم وصلنا إلى قلب تصميم الخوارزميات في الوحدتين العاشرة والحادية عشرة. البرمجة الديناميكية (Dynamic Programming) في الوحدة العاشرة تعتمد على تقسيم المشكلة إلى مشكلات فرعية متداخلة وحلها من الأسفل للأعلى مع تخزين الحلول لتجنب الحسابات المتكررة. الفخ الأكبر هنا هو محاولة استخدام البرمجة الديناميكية لمشكلات لا تحتوي على تداخل في المشكلات الفرعية! في المقابل، الخوارزميات الجشعة (Greedy Technique) في الوحدة الحادية عشرة تبني الحل خطوة بخطوة عبر خيارات محلية مثلى لا رجعة فيها. تذكروا دائماً: الخوارزمية الجشعة سريعة جداً لكنها لا تضمن دائماً الحل الأمثل الشامل، وهذا موضع سؤال كلاسيكي للمقارنة بينها وبين البرمجة الديناميكية. أخيراً، واجهنا الواقع العملي والنظري في الوحدتين الثانية عشرة والثالثة عشرة. في الوحدة 12، درسنا حدود قوة الخوارزميات وصنفنا المشكلات إلى قابلة للحل في وقت معقول (P) ومستعصية (NP-Complete). إياكم أن تظنوا أن المشكلات المستعصية تعني الاستسلام ونهاية المطاف! ففي الوحدة 13، تعلمنا كيف نتعامل مع هذه القيود بذكاء باستخدام تقنيات الحل الدقيق مثل التراجع (Backtracking) والتفرع والحد (Branch-and-Bound) للحالات الصغيرة، أو اللجوء إلى خوارزميات التقريب (Approximation Algorithms) للحصول على حلول قريبة من الأمثل في وقت سريع عندما تكون البيانات ضخمة. ركزوا على هذه الروابط، وتجنبوا الفخاخ التي ذكرتها، وأنا واثق تماماً من تفوقكم غداً. أتمنى لكم كل التوفيق والنجاح!

خزنة الامتحان | النقاط الحرجة

33 نقطة حرجة
🔑 مفهوم أساسي M7
الترتيب بالكومة (Heapsort) يجمع بين أفضل ميزتين: كفاءة الوقت Θ(n log n) مثل Mergesort، وكفاءة الذاكرة (In-place) مثل Quicksort. عيبه الوحيد أنه غير مستقر.
⚠️ فخ M10
الخلط بين خوارزمية وارشال وفلويد: تذكر أن وارشال تتعامل مع 'وجود مسار' (قيم منطقية 0/1)، بينما فلويد تتعامل مع 'أقصر مسار' (أوزان ومسافات).
💡 سر الامتحان M7
في تمثيل المصفوفة، يمكنك معرفة ما إذا كانت العقدة ورقة (Leaf) أم لا بمجرد النظر إلى دليلها. أي عقدة دليلها أكبر من ⌊n/2⌋ هي حتماً ورقة.
💡 سر الامتحان M13
في خوارزمية الجار الأقرب (Nearest-Neighbor)، نسبة الأداء غير محدودة (∞) لأن الخيار الجشع في البداية قد يجبرك على اتخاذ مسار كارثي في النهاية للعودة لنقطة البداية.
💡 سر الامتحان M10
في خوارزميتي وارشال وفلويد، لست بحاجة إلى الاحتفاظ بـ n مصفوفات في الذاكرة. يمكنك تحديث نفس المصفوفة ثنائية الأبعاد في مكانها (In-place)، مما يجعل كفاءة المساحة ممتازة.
🔑 مفهوم أساسي M10
في أشجار البحث الثنائية المثلى (OBST)، يتم ملء الجداول بشكل قطري (Diagonal) وليس صفاً بصف، لأن حساب تكلفة شجرة بحجم معين يتطلب معرفة تكاليف جميع الأشجار الأصغر منها.
🔑 مفهوم أساسي M11
في ترميز Huffman، خاصية 'خالٍ من البادئة' (Prefix-free) هي ما يسمح للكمبيوتر بقراءة سلسلة طويلة من الأصفار والآحاد وفك تشفيرها فوراً دون الحاجة لمسافات أو فواصل بين الحروف.
⚠️ فخ M11
استخدام خوارزمية Dijkstra مع رسوم بيانية تحتوي على أوزان سالبة. الخوارزمية ستفشل لأنها تفترض أن المسافات لا يمكن أن تقل بعد زيارة العقدة.
🔑 مفهوم أساسي M12
اتجاه الاختزال (Reduction Direction): لإثبات أن مسألة جديدة P صعبة، يجب أن تختزل مسألة معروفة بصعوبتها Q إلى P. (Q -> P). إذا فعلت العكس، فلن تثبت شيئاً عن صعوبة P.
💡 سر الامتحان M8
في خوارزمية هورسبول، عند بناء جدول الإزاحة، نتجاهل الحرف الأخير من النمط عمداً. إذا لم نفعل ذلك، قد تكون قيمة الإزاحة صفراً، مما يؤدي إلى حلقة لا نهائية.
🔑 مفهوم أساسي M13
التراجع (Backtracking) يبحث عن أي حل صحيح، بينما التفرع والحد (Branch-and-Bound) يبحث عن الحل الأمثل (Optimization).
💡 سر الامتحان M9
في التهشير المغلق، لا يمكنك ببساطة 'حذف' عنصر بجعل خليته فارغة، لأن ذلك سيكسر سلسلة الفحص الخطي للعناصر التي اصطدمت به. يجب استخدام علامة خاصة (Tombstone).
💡 سر الامتحان M12
لماذا نستخدم مسائل القرار بدلاً من مسائل التحسين في نظرية التعقيد؟ لأن إجابة 'نعم/لا' تجعل من السهل جداً بناء نماذج رياضية دقيقة (مثل آلات تورينج) لمقارنة صعوبة المسائل دون القلق بشأن تنسيق المخرجات المعقدة.
⚠️ فخ M7
الخلط بين بناء الكومة من الأعلى للأسفل (Top-down) ومن الأسفل للأعلى (Bottom-up). طريقة Bottom-up أسرع بكثير وتستغرق O(n)، بينما الإدراج المتتالي (Top-down) يستغرق O(n log n).
⚠️ فخ M11
الخلط بين معيار الاختيار في Prim و Dijkstra. تذكر: Prim تهتم فقط بوزن الحافة الجديدة (لبناء الشجرة)، بينما Dijkstra تهتم بالمسافة الكلية من نقطة البداية (لإيجاد المسار).
🔑 مفهوم أساسي M9
عامل التحميل (Load Factor α = n/m) هو المؤشر الحاسم لأداء جدول التهشير. إبقاؤه صغيراً (حوالي 1 في التهشير المفتوح، وأقل بكثير في المغلق) يضمن أداء O(1).
⚠️ فخ M13
احذر: خوارزميات التقريب لا تعطي الحل الأمثل! إنها تعطي حلاً 'جيداً بما فيه الكفاية' في وقت سريع (متعدد الحدود).
🔑 مفهوم أساسي M11
الخاصية 'لا رجعة فيها' (Irrevocable) هي سلاح ذو حدين للخوارزمية الجشعة: هي سبب سرعتها الفائقة (لا يوجد تراجع)، وهي سبب فشلها في بعض المشاكل (لا يمكن تصحيح خطأ سابق).
🔑 مفهوم أساسي M12
أشجار القرار تثبت رياضياً أنه لا توجد خوارزمية فرز تعتمد على المقارنة يمكن أن تكون أسرع من O(n log n). هذا يجعل خوارزمية الدمج (Mergesort) خوارزمية مثالية من حيث التعقيد الزمني.
🔑 مفهوم أساسي M10
مبدأ الأمثلية لبيلمان هو حجر الزاوية في البرمجة الديناميكية: لا يمكنك استخدام هذه التقنية إلا إذا كان الحل الأمثل للمسألة الكبيرة يتضمن بالضرورة حلولاً أمثلة لمشاكلها الفرعية.
⚠️ فخ M10
استخدام 'فرق تسد' بدلاً من 'البرمجة الديناميكية' لمشاكل مثل فيبوناتشي سيؤدي إلى تعقيد زمني أسي بسبب إعادة حساب نفس المشاكل الفرعية المتداخلة مراراً وتكراراً.
🔑 مفهوم أساسي M8
الفرق الجوهري بين تحسين المُدخلات والهيكلة المسبقة: الأول يستخرج معلومات إضافية (مثل جداول الإزاحة)، بينما الثاني يغير بنية البيانات بالكامل (مثل تحويل مصفوفة إلى شجرة B).
⚠️ فخ M13
لا تخلط بين النسخة المنفصلة (0/1) والمستمرة لحقيبة الظهر. الخوارزمية الجشعة تحل النسخة المستمرة بشكل دقيق 100%، لكنها تفشل في ضمان الحل الأمثل للنسخة المنفصلة.
⚠️ فخ M8
جمع قيمتي الإزاحة في خوارزمية Boyer-Moore. الخوارزمية لا تجمع إزاحة الرمز السيئ مع اللاحقة الجيدة، بل تأخذ القيمة القصوى (Max) بينهما لضمان أطول قفزة آمنة.
🔑 مفهوم أساسي M7
في اختزال المشكلات (P ≤ Q)، نحن لا نثبت أن P هي جزء من Q، بل نثبت أن خوارزمية Q قوية بما يكفي لحل P بعد إجراء تحويل بسيط على المدخلات.
🔑 مفهوم أساسي M8
الفرز بالعد والمقارنة ليس فعالاً من حيث المساحة. رغم أنه يوضح مفهوم مقايضة المساحة بالوقت، إلا أن حاجته لمساحة إضافية O(n) تجعله أقل عملية من خوارزميات الفرز الموضعي (In-place).
💡 سر الامتحان M11
الخوارزميات الجشعة لا تضمن دائماً الحل الأمثل (مثل مشكلة البائع المتجول أو الصرافة بفئات غريبة)، لكنها تُستخدم بكثرة لأنها توفر 'تقريبات سريعة' (Fast approximations) لمشاكل معقدة جداً.
⚠️ فخ M9
الخلط بين خصائص العقد في شجرة B. تذكر: الجذر يمكن أن يكون له ابنان فقط، لكن العقد الداخلية الأخرى يجب أن تكون ممتلئة على الأقل بنسبة النصف (⌈m/2⌉ أبناء).
⚠️ فخ M9
الاعتقاد بأن التهشير المغلق (Closed Hashing) يمكن أن يعمل إذا كان عدد العناصر أكبر من حجم الجدول. الحقيقة: يجب أن يكون m ≥ n دائماً.
🔑 مفهوم أساسي M13
نسبة الدقة $r(s_a)$ مصممة لتكون دائماً $\ge 1$. لذلك في مشاكل التقليل نقسم التقريبي على الأمثل، وفي مشاكل التعظيم نقسم الأمثل على التقريبي.
⚠️ فخ M8
الاعتقاد بأن خوارزمية هورسبول تقارن الأحرف من اليسار إلى اليمين. الحقيقة أنها تقارن من اليمين إلى اليسار، وهذا هو سر سرعتها في تخطي الأحرف.
⚠️ فخ M12
الاعتقاد بأن NP تعني 'Non-Polynomial' (غير كثيرة الحدود). هذا خطأ شائع! NP تعني 'Nondeterministic Polynomial' (كثيرة الحدود غير حتمية)، وهي تعني أن التحقق من الحل يتم في وقت كثير الحدود.
⚠️ فخ M7
الاعتقاد بأن عناصر الكومة مرتبة من اليسار إلى اليمين. هذا خطأ شائع! الكومة مرتبة فقط من الأعلى إلى الأسفل (الأب أكبر من أبنائه)، ولا توجد علاقة ترتيب بين الأبناء في نفس المستوى.