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

مراجعة الاختبار النصفي - الخوارزميات

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

الوحدة 1 الوحدة 2 الوحدة 3 الوحدة 4 الوحدة 5 الوحدة 6 المعادلات مقارنة الخوارزميات خزنة الامتحان

1 أساسيات الخوارزميات

فهم ماهية الخوارزمية، خصائصها الخمس، وخطوات تصميمها وتحليلها.

1.1 تعريف الخوارزمية وخصائصها

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

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

تتميز الخوارزمية بخمس خصائص أساسية:

  • المدخلات (Input): كميات تقدم من الخارج (صفر أو أكثر).
  • المخرجات (Output): إنتاج كمية واحدة على الأقل.
  • الوضوح (Definiteness): كل تعليمة يجب أن تكون واضحة وغير غامضة.
  • المحدودية (Finiteness): يجب أن تنتهي الخوارزمية بعد عدد محدود من الخطوات.
  • الكفاءة (Efficiency): يجب أن تكون التعليمات أساسية وتعمل في وقت قصير.

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

يمكن كتابة الخوارزميات باللغة الطبيعية، أو الكود الوهمي (Pseudocode)، أو المخططات الانسيابية (Flowcharts).

هناك ثلاث طرق رئيسية لتحديد الخوارزمية:

  1. اللغة الطبيعية (Natural Language): بسيطة وسهلة ولكنها غالباً ما تكون مختصرة وتفتقر للدقة.
  2. الكود الوهمي (Pseudocode): مزيج من اللغة الطبيعية وهياكل لغات البرمجة. هو أكثر دقة من اللغة الطبيعية وهو الطريقة السائدة حالياً. يستخدم رموزاً مثل السهم الأيسر (←) للتعيين.
  3. المخطط الانسيابي (Flowchart): تمثيل رسومي باستخدام أشكال هندسية. كان سائداً في الماضي ولكنه يعتبر غير مريح حالياً.
pseudocode 
ALGORITHM Sum(a,b)
c <- a + b
return c

1.3 خطوات تصميم وتحليل الخوارزميات

دورة حياة الخوارزمية تبدأ بفهم المشكلة وتنتهي بكتابة الكود، مروراً بالتصميم والإثبات والتحليل.

الخطوات الأساسية هي:

  1. فهم المشكلة (Understand the problem): قراءة الوصف، طرح الأسئلة، تحديد نوع المشكلة والمدخلات. تخطي هذه الخطوة يؤدي إلى إعادة العمل.
  2. اتخاذ القرارات (Decide on): تحديد قدرات الجهاز (تسلسلي أم متوازي)، الاختيار بين الحل الدقيق والتقريبي، واختيار تقنية التصميم وهياكل البيانات.
  3. تصميم الخوارزمية (Design an algorithm).
  4. إثبات الصحة (Prove correctness): غالباً باستخدام الاستقراء الرياضي.
  5. تحليل الخوارزمية (Analyze the algorithm): قياس كفاءة الوقت والمساحة.
  6. كتابة الكود (Code the algorithm): تحويلها إلى لغة برمجة مع تحسين الكود.

1.4 أنواع المشاكل الهامة

تصنف المشاكل الحسابية إلى فئات رئيسية مثل الفرز، البحث، معالجة النصوص، الرسوم البيانية، والمشاكل التوافقية.

أهم أنواع المشاكل هي:

  1. الفرز (Sorting): إعادة ترتيب العناصر بترتيب تصاعدي. الخوارزمية تكون in-place إذا لم تحتج ذاكرة إضافية، وتكون stable إذا حافظت على الترتيب النسبي للعناصر المتساوية.
  2. البحث (Searching): إيجاد قيمة معينة (مفتاح البحث).
  3. معالجة النصوص (String processing): مثل مطابقة السلاسل، مفيدة جداً في المعلوماتية الحيوية.
  4. مشاكل الرسوم البيانية (Graph problems): مثل اجتياز الرسم البياني وأقصر مسار.
  5. المشاكل التوافقية (Combinatorial problems): إيجاد كائن توافقي (تبديل/تجميع) يحقق قيوداً معينة، وهي الأصعب عملياً (مثل مشكلة البائع المتجول).
  6. المشاكل الهندسية (Geometric).
  7. المشاكل العددية (Numerical).

2 طرق تحليل الخوارزميات

تقييم كفاءة الخوارزميات رياضياً باستخدام الرموز التقاربية وعلاقات التكرار.

2.1 إطار عمل التحليل

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

يعتمد إطار عمل تحليل الخوارزميات على نوعين من الكفاءة: الكفاءة الزمنية (Time efficiency) والكفاءة المكانية (Space efficiency).

بدلاً من قياس الوقت بالثواني (والذي يختلف باختلاف الأجهزة والمترجمات)، نقوم بحساب عدد مرات تنفيذ العملية الأساسية (Basic operation) كدالة في حجم المدخلات (Input size).

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

وقت التشغيل يساوي تقريباً وقت تنفيذ العملية الأساسية مضروباً في عدد مرات تنفيذها. \[T(n) \approx c_{op} C(n)\]

2.2 حالات الكفاءة (الأسوأ، الأفضل، والمتوسط)

تختلف كفاءة الخوارزمية لنفس حجم المدخلات بناءً على طبيعة البيانات، مما يوجب دراسة الحالة الأسوأ، الأفضل، والمتوسطة.

بالنسبة لبعض الخوارزميات (مثل البحث الخطي)، لا يعتمد وقت التشغيل على حجم المدخلات $n$ فقط، بل على تفاصيل المدخلات نفسها.

الحالة الأسوأ (Worst-case): أطول وقت تشغيل ممكن لمدخلات بحجم $n$.

الحالة الأفضل (Best-case): أسرع وقت تشغيل ممكن.

الحالة المتوسطة (Average-case): الكفاءة المتوقعة لمدخلات عشوائية، وتتطلب افتراضات احتمالية حول المدخلات.

حساب الحالة المتوسطة يعتمد على احتمالية كل حالة ممكنة. \[C_{avg}(n) = \sum_{i=1}^{n} i \cdot P(i)\]

2.3 الرموز التقاربية

لغة رياضية لوصف رتبة نمو الخوارزميات عندما يؤول حجم المدخلات إلى المالانهاية (Big-O, Big-Omega, Big-Theta).

تستخدم الرموز التقاربية لمقارنة رتب النمو:

  1. $O$ (Big-O): يمثل الحد الأعلى التقاربي (Asymptotic upper bound). الدالة $t(n) \in O(g(n))$ إذا كانت محصورة من الأعلى بمضاعف ثابت لـ $g(n)$. مفيد لتحليل الحالة الأسوأ.
  2. $\Omega$ (Big-Omega): يمثل الحد الأدنى التقاربي (Asymptotic lower bound). مفيد لتحليل الحالة الأفضل.
  3. $\Theta$ (Big-Theta): يمثل الحد المحكم التقاربي (Asymptotic tight bound). الدالة محصورة من الأعلى والأسفل. مفيد لتحليل الحالة المتوسطة أو عندما تتطابق الحالة الأسوأ والأفضل.
تعريف الحد الأعلى التقاربي (Big-O). \[t(n) \le c \cdot g(n) \implies t(n) \in O(g(n))\]

2.4 التحليل الرياضي للخوارزميات غير التكرارية

تحليل يعتمد على إعداد مجاميع (Sums) لعدد مرات تنفيذ العملية الأساسية داخل الحلقات التكرارية (Loops).

خطة التحليل:

  1. تحديد حجم المدخلات.
  2. تحديد العملية الأساسية (غالباً في الحلقة الأعمق).
  3. التحقق مما إذا كان عدد مرات التنفيذ يعتمد فقط على حجم المدخلات أم يتطلب فصل الحالات (أسوأ، أفضل).
  4. إعداد مجموع (Sum) يعبر عن عدد مرات تنفيذ العملية الأساسية.
  5. استخدام قوانين المجاميع القياسية لإيجاد صيغة مغلقة (Closed form) أو رتبة النمو.
مجموع التكرارات المتداخلة لخوارزمية فحص تفرد العناصر. \[C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{n(n-1)}{2} \approx \frac{1}{2}n^2 \in \Theta(n^2)\]

2.5 التحليل الرياضي للخوارزميات التكرارية

تحليل يعتمد على إعداد علاقات تكرار (Recurrence Relations) وحلها باستخدام طرق مثل التعويض العكسي (Backward Substitution).

خطة التحليل:

  1. تحديد حجم المدخلات.
  2. تحديد العملية الأساسية.
  3. التحقق من الحالات (أسوأ، أفضل).
  4. إعداد علاقة تكرار (Recurrence relation) مع شرط ابتدائي (Initial condition) لعدد مرات تنفيذ العملية الأساسية.
  5. حل علاقة التكرار لتحديد رتبة النمو. طريقة التعويض العكسي هي إحدى الطرق الشائعة لحل هذه العلاقات.
علاقة التكرار لعدد عمليات الضرب في خوارزمية المضروب التكرارية. \[M(n) = M(n-1) + 1, \quad M(0) = 0\]

2.6 التحليل التجريبي للخوارزميات

بديل للتحليل الرياضي يتم من خلال تشغيل الخوارزمية فعلياً على عينات بيانات وقياس الأداء.

يُستخدم التحليل التجريبي عندما يكون التحليل الرياضي صعباً أو معقداً. الخطة العامة:

  1. فهم هدف التجربة.
  2. تحديد مقياس الكفاءة (عدد العمليات أو وقت التشغيل الفعلي).
  3. تحديد خصائص عينة المدخلات (النطاق، الحجم).
  4. كتابة برنامج ينفذ الخوارزمية.
  5. توليد عينة من المدخلات (غالباً أرقام عشوائية).
  6. تشغيل الخوارزمية وتسجيل البيانات.
  7. تحليل البيانات الناتجة.

3 القوة الغاشمة والبحث الشامل

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

3.1 استراتيجية القوة الغاشمة

نهج مباشر لحل المشكلات يعتمد على تطبيق التعريفات حرفياً، مثل شعار 'فقط افعلها'.

القوة الغاشمة هي استراتيجية تعتمد على بيان المشكلة وتعريفات المفاهيم المعنية.

على الرغم من أنها غالباً ما تكون غير فعالة (inefficient)، إلا أنها مفيدة لحل الحالات صغيرة الحجم من المشكلة، وتعتبر من أسهل الاستراتيجيات في التطبيق.

3.2 ترتيب الاختيار

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

يبدأ ترتيب الاختيار بمسح القائمة بأكملها للعثور على أصغر عنصر وتبديله مع العنصر الأول.

ثم يمسح القائمة بدءاً من العنصر الثاني للعثور على أصغر عنصر بين العناصر المتبقية (n-1) ويبدله مع العنصر الثاني.

بشكل عام، في التمريرة i، تبحث الخوارزمية عن أصغر عنصر بين آخر (n-i) عناصر وتبدله مع A[i].

عدد المقارنات في خوارزمية ترتيب الاختيار. \[C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{(n-1)n}{2}\]
pseudocode 
ALGORITHM SelectionSort(A[0..n-1])
for i <- 0 to n-2 do
  min <- i
  for j <- i+1 to n-1 do
    if A[j] < A[min] min <- j
  swap A[i] and A[min]

3.3 الترتيب الفقاعي

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

يقوم الترتيب الفقاعي بمقارنة العناصر المتجاورة في القائمة وتبديلها إذا كانت في غير ترتيبها الصحيح.

بتكرار هذه العملية، يرتفع ('bubbles up') العنصر الأكبر إلى الموضع الأخير في القائمة.

التمريرة التالية ترفع ثاني أكبر عنصر، وهكذا حتى يتم ترتيب القائمة بعد n-1 تمريرة.

عدد المقارنات في الترتيب الفقاعي في أسوأ الحالات. \[C(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 = \frac{(n-1)n}{2} \in O(n^2)\]
pseudocode 
ALGORITHM BubbleSort(A[0..n-1])
for i <- 0 to n-2 do
  for j <- 0 to n-2-i do
    if A[j+1] < A[j] swap A[j] and A[j+1]

3.5 مطابقة السلاسل النصية بالقوة الغاشمة

محاذاة النمط مع النص ومقارنة الحروف واحداً تلو الآخر، وإزاحة النمط بمقدار حرف واحد عند عدم التطابق.

المشكلة: إيجاد سلسلة فرعية في نص (طوله n) تطابق نمطاً (طوله m).

الخوارزمية تضع النمط فوق بداية النص وتقارن الحروف.

إذا حدث عدم تطابق، يتم إزاحة النمط بمقدار حرف واحد إلى اليمين وتتكرر العملية.

الهدف هو إيجاد الفهرس i لأول حرف في النص يبدأ منه التطابق.

عدد المقارنات في أسوأ حالة لمطابقة السلاسل النصية. \[m(n - m + 1) \in O(nm)\]
pseudocode 
ALGORITHM BruteForceStringMatch(T[0..n-1], P[0..m-1])
for i <- 0 to n-m do
  j <- 0
  while j < m and P[j] == T[i+j] do
    j <- j + 1
  if j == m return i
return -1

3.6 مشكلة أقرب زوج من النقاط

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

لحل المشكلة بكفاءة، نقسم النقاط إلى مجموعتين (يسار ويمين) بخط عمودي x=c.

نجد أقرب زوج في كل مجموعة بشكل عودي (d1 و d2).

نأخذ المسافة الأصغر d = min(d1, d2).

ثم نفحص شريطاً عمودياً عرضه 2d حول خط التقسيم للبحث عن نقاط قد تكون أقرب.

عدد مرات حساب المسافة بين النقاط. \[C(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \frac{(n-1)n}{2} \in O(n^2)\]
pseudocode 
ALGORITHM BruteForceClosestPair(P)
d <- infinity
for i <- 1 to n-1 do
  for j <- i+1 to n do
    d <- min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
return d

3.8 مشكلة البائع المتجول (TSP)

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

تطلب المشكلة إيجاد أقصر جولة عبر مجموعة من n مدينة تزور كل مدينة مرة واحدة بالضبط قبل العودة إلى مدينة البداية.

يمكن نمذجتها بواسطة رسم بياني موزن، حيث تمثل الرؤوس المدن وأوزان الحواف تمثل المسافات.

المشكلة تعادل إيجاد أقصر 'دائرة هاميلتونية' (Hamiltonian circuit) في الرسم البياني.

عدد المسارات الممكنة في مشكلة البائع المتجول. \[\frac{(n-1)!}{2}\]

3.9 مشكلة حقيبة الظهر

اختيار مجموعة من العناصر لتعظيم القيمة الإجمالية دون تجاوز سعة الحقيبة.

بوجود n عنصر بأوزان وقيم معروفة، وحقيبة ظهر بسعة W، المطلوب إيجاد المجموعة الفرعية الأكثر قيمة من العناصر التي تتسع في الحقيبة.

نهج البحث الشامل يولد جميع المجموعات الفرعية (Subsets) الممكنة، يحسب الوزن الإجمالي لكل منها لتحديد المجموعات الممكنة (Feasible)، ثم يختار المجموعة ذات القيمة الأعلى.

التعقيد الزمني للبحث الشامل لمشكلة حقيبة الظهر. \[O(2^n)\]

3.10 مشكلة التعيين

تعيين n شخص لـ n وظيفة بحيث تكون التكلفة الإجمالية أقل ما يمكن.

يوجد n شخص يجب تعيينهم لتنفيذ n وظيفة (شخص واحد لكل وظيفة).

التكلفة C[i,j] معروفة لتعيين الشخص i للوظيفة j.

المشكلة هي إيجاد تعيين بأقل تكلفة إجمالية.

الحلول الممكنة تمثل كـ n-tuples (j1, ..., jn) حيث يشير المكون i إلى الوظيفة المعينة للشخص i.

التعقيد الزمني للبحث الشامل لمشكلة التعيين. \[O(n!)\]

4 تقليل وحل (Decrease-and-Conquer)

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

4.1 مقدمة في تقليل وحل

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

تقنية 'تقليل وحل' (Decrease-and-Conquer) تقوم على تقليل حجم المشكلة إلى مشكلة فرعية أصغر، ثم حل المشكلة الفرعية، وأخيراً توسيع الحل ليشمل المشكلة الأصلية.

يمكن تنفيذها بطريقتين: من أعلى إلى أسفل (Top-down) باستخدام النهج العودي (Recursive)، أو من أسفل إلى أعلى (Bottom-up) باستخدام النهج التكراري (Iterative) والذي يسمى أحياناً بالنهج التزايدي (Incremental approach).

4.2 التقليل بمقدار ثابت: الترتيب بالإدراج

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

الترتيب بالإدراج (Insertion Sort) هو تطبيق مباشر لتقنية التقليل بمقدار ثابت (بمقدار 1).

بافتراض أن لدينا مصفوفة فرعية مرتبة A[0..n-2]، نحتاج إلى إيجاد الموضع المناسب للعنصر A[n-1] وإدراجه.

يتم ذلك بمسح المصفوفة المرتبة من اليمين إلى اليسار حتى نجد أول عنصر أصغر من أو يساوي A[n-1].

التنفيذ من أسفل إلى أعلى (التكراري) أكثر كفاءة من العودي.

عدد المقارنات في أسوأ حالة للترتيب بالإدراج. \[C_{worst}(n) = \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} \in O(n^2)\]
pseudocode 
ALGORITHM InsertionSort(A[0..n-1])
for i <- 1 to n - 1 do
    v <- A[i]
    j <- i - 1
    while j >= 0 and A[j] > v do
        A[j + 1] <- A[j]
        j <- j - 1
    A[j + 1] <- v

4.3 الفرز الطوبولوجي (Topological Sorting)

ترتيب رؤوس رسم بياني موجه بحيث يظهر كل رأس قبل الرؤوس التي يشير إليها.

الفرز الطوبولوجي يحل مشكلة ترتيب المهام المعتمدة على بعضها (مثل المقررات الدراسية ذات المتطلبات السابقة).

يجب أن يكون الرسم البياني موجهاً وخالياً من الدورات (DAG - Directed Acyclic Graph).

إذا كان الرسم البياني يحتوي على دورة موجهة (Directed Cycle)، فلا يمكن إيجاد فرز طوبولوجي له.

pseudocode 
Algorithm Topological sort
Mark each vertex in V as unvisited
Find indegree[v] for each vertex v in V
for each vertex v in V do
    if indegree[v] = 0 then
        Q.Enqueue(v)
        Mark v as visited
while Q is not empty do
    u <- Q.Dequeue()
    T.AddLast(u)
    for each vertex w in V adjacent to u do
        if w is unvisited then
            indegree[w] <- indegree[w] - 1
            if indegree[w] = 0 then
                Q.Enqueue(w)
                Mark w as visited
return T

4.4 أنواع الحواف في غابة البحث بالعمق (DFS Forest)

أربعة أنواع من الحواف تنتج عن اجتياز الرسم البياني الموجه باستخدام البحث بالعمق (DFS).

عند استخدام خوارزمية البحث بالعمق (DFS) لاجتياز رسم بياني موجه، يمكن تصنيف الحواف إلى أربعة أنواع:

  1. حواف الشجرة (Tree edges): الحواف التي تشكل غابة DFS.
  2. الحواف الخلفية (Back edges): تتجه من رأس إلى أحد أسلافه (تشير إلى وجود دورة).
  3. الحواف الأمامية (Forward edges): تتجه من رأس إلى أحد أحفاده في الشجرة (غير أبنائه المباشرين).
  4. الحواف المتقاطعة (Cross edges): حواف لا تنتمي لأي من الأنواع السابقة (تربط بين فروع مختلفة).

4.6 التقليل بحجم متغير: خوارزمية إقليدس

خوارزمية لحساب القاسم المشترك الأكبر (GCD) حيث يختلف مقدار تقليل المشكلة في كل خطوة.

في خوارزميات 'التقليل بحجم متغير'، يختلف نمط تقليل الحجم في كل تكرار.

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

تعتمد الخوارزمية على الصيغة: gcd(m, n) = gcd(n, m mod n).

قيمة المعامل الثاني (m mod n) تكون دائماً أصغر من المعامل الأول، ولكن مقدار النقصان يختلف في كل خطوة.

صيغة خوارزمية إقليدس. \[\gcd(m, n) = \gcd(n, m \bmod n)\]

4.7 مشكلة الاختيار و Quick Select

إيجاد العنصر رقم k الأصغر في مصفوفة باستخدام تقسيم عشوائي (Partitioning) دون ترتيب المصفوفة بالكامل.

مشكلة الاختيار (Selection Problem) هي إيجاد العنصر رقم k الأصغر في مصفوفة A[0..n-1].

أسهل حالة هي إيجاد الحد الأدنى (k=1) أو الأقصى (k=n)، وأصعب حالة هي إيجاد الوسيط (k=n/2).

بدلاً من ترتيب المصفوفة بالكامل (مما يستغرق وقتاً أطول)، نستخدم استراتيجية التقسيم العشوائي (Randomized Partitioning) مثل تقسيم لوموتو (Lomuto partitioning).

التعقيد الزمني لأسوأ حالة لخوارزمية Quickselect. \[C_{worst}(n) = (n-1) + (n-2) + \dots + 1 = \frac{(n-1)n}{2} \in O(n^2)\]
pseudocode 
ALGORITHM Quickselect(A[l..r], k)
s <- LomutoPartition(A[l..r])
if s = k - 1 return A[s]
else if s > l + k - 1 Quickselect(A[l..s - 1], k)
else Quickselect(A[s + 1..r], k - 1 - s)

5 خوارزميات فرّق تسد

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

5.1 استراتيجية فرّق تسد

استراتيجية لحل المشكلات تعتمد على تقسيم المشكلة إلى أجزاء أصغر، حلها، ثم دمج الحلول.

تتكون خطة 'فرّق تسد' من ثلاث خطوات رئيسية:

  1. التقسيم (Divide): تقسيم المشكلة إلى عدة مشاكل فرعية من نفس النوع، ويفضل أن تكون متساوية الحجم.
  2. الفتح/الحل (Conquer): حل المشاكل الفرعية بشكل عودي (Recursively).
  3. الدمج (Combine): دمج حلول المشاكل الفرعية للحصول على حل للمشكلة الأصلية.
معادلة التكرار العامة لخوارزميات فرّق تسد، حيث a هو عدد المشاكل الفرعية، و b هو عامل التقسيم، و f(n) هو وقت التقسيم والدمج. \[T(n) = aT(n/b) + f(n)\]

5.2 الترتيب بالدمج

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

الترتيب بالدمج هو مثال مثالي لتطبيق 'فرّق تسد'.

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

عملية الدمج تستخدم مؤشرين يقارنان العناصر ويضعان الأصغر في المصفوفة الجديدة.

الحل الدقيق لأسوأ حالة لعدد المقارنات في الترتيب بالدمج. \[C_{worst}(n) = n \log_2 n - n + 1\]

5.3 الترتيب السريع

خوارزمية ترتيب تقسم المصفوفة بناءً على قيمة 'محور' (Pivot)، بحيث تكون العناصر الأصغر يساره والأكبر يمينه.

على عكس الترتيب بالدمج الذي يقسم حسب الموقع، الترتيب السريع يقسم حسب القيمة.

يتم اختيار عنصر كمحور (Pivot)، ويتم إعادة ترتيب المصفوفة (Partitioning) بحيث تصبح جميع العناصر التي تسبق المحور أصغر منه أو تساويه، والعناصر التي تليه أكبر منه أو تساويه.

ثم يتم ترتيب الجزأين بشكل مستقل.

عدد المقارنات في أسوأ حالة للترتيب السريع. \[C_{worst}(n) = \frac{(n+1)(n+2)}{2} - 3 \in O(n^2)\]

5.4 اجتياز الأشجار الثنائية

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

هناك ثلاثة أنواع كلاسيكية لاجتياز الشجرة الثنائية:

  1. الاجتياز المسبق (Preorder): زيارة الجذر، ثم الشجرة الفرعية اليسرى، ثم اليمنى.
  2. الاجتياز الداخلي (Inorder): زيارة الشجرة الفرعية اليسرى، ثم الجذر، ثم اليمنى.
  3. الاجتياز اللاحق (Postorder): زيارة الشجرة الفرعية اليسرى، ثم اليمنى، ثم الجذر.

5.5 ضرب الأعداد الصحيحة الكبيرة

استخدام 'فرّق تسد' لتقليل عدد عمليات الضرب الفردية عند ضرب أعداد ضخمة (مثل التشفير).

الطريقة المدرسية التقليدية لضرب عددين من n خانة تتطلب O(n^2) عملية ضرب.

باستخدام 'فرّق تسد'، يمكننا تقسيم كل عدد إلى نصفين. الطريقة الساذجة (First Cut) تعطي 4 عمليات ضرب وتبقى O(n^2).

لكن الطريقة المحسنة (Second Cut) تستخدم خدعة جبرية لتقليل عمليات الضرب إلى 3 فقط.

التعقيد الزمني لخوارزمية ضرب الأعداد الكبيرة المحسنة. \[T(n) = 3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}\]

5.6 خوارزمية شتراسن لضرب المصفوفات

خوارزمية لضرب المصفوفات تقلل عدد عمليات الضرب من 8 إلى 7 لمصفوفات 2x2.

ضرب مصفوفتين 2x2 بالطريقة التقليدية يتطلب 8 عمليات ضرب.

اكتشف شتراسن طريقة لحساب الناتج باستخدام 7 عمليات ضرب فقط، مع زيادة في عمليات الجمع والطرح.

يتم تطبيق هذه الفكرة بشكل عودي على مصفوفات بحجم n x n.

التعقيد الزمني لخوارزمية شتراسن. \[M(n) = 7^{\log_2 n} = n^{\log_2 7} \approx n^{2.807}\]

5.7 مشكلة أقرب زوج

إيجاد النقطتين الأقرب لبعضهما في مستوى ثنائي الأبعاد باستخدام تقسيم النقاط بخط عمودي.

لحل المشكلة بكفاءة، نقسم النقاط إلى مجموعتين (يسار ويمين) بخط عمودي x=c. نجد أقرب زوج في كل مجموعة بشكل عودي (d1 و d2). نأخذ المسافة الأصغر d = min(d1, d2). ثم نفحص شريطاً عمودياً عرضه 2d حول خط التقسيم للبحث عن نقاط قد تكون أقرب.

معادلة التكرار والتعقيد الزمني لمشكلة أقرب زوج باستخدام فرّق تسد. \[T(n) = 2T(n/2) + O(n) \implies O(n \log n)\]

6 التحويل والحل (Transform-and-Conquer)

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

6.1 استراتيجية التحويل والحل

تقنية تعتمد على تحويل المشكلة إلى شكل أسهل قبل حلها، مثل ترتيب الأوراق قبل البحث عن اسم معين.

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

هناك ثلاثة أنواع رئيسية:

  1. تبسيط النسخة (Instance Simplification) مثل الفرز المسبق.
  2. تغيير التمثيل (Representation Change) مثل استخدام هياكل بيانات مختلفة كأشجار AVL.
  3. اختزال المشكلة (Problem Reduction) بتحويلها لمشكلة يوجد لها خوارزمية جاهزة.

6.2 الفرز المسبق (Presorting)

ترتيب البيانات أولاً لجعل العمليات اللاحقة (مثل البحث أو إيجاد العناصر المكررة) أسرع بكثير.

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

أمثلة:

  1. البحث: فرز ثم بحث ثنائي بكفاءة O(n log n).
  2. تفرد العناصر (Element Uniqueness): بدلاً من مقارنة كل زوج بكفاءة O(n^2)، نقوم بالفرز O(n log n) ثم فحص العناصر المتجاورة O(n)، لتصبح الكفاءة الكلية O(n log n).
الكفاءة الزمنية لمشكلة تفرد العناصر باستخدام الفرز المسبق. \[\Theta(n \log n) + O(n) = \Theta(n \log n)\]
pseudocode 
ALGORITHM PresortElementUniqueness(A[0..n-1])
  // Sorts the array first, then checks for uniqueness
  sort the array A
  for i <- 0 to n - 2 do
    if A[i] == A[i + 1] return false
  return true

6.3 الحذف الغاوسي (Gaussian Elimination)

تحويل نظام من المعادلات الخطية المعقدة إلى مصفوفة مثلثية عليا يسهل حلها من الأسفل للأعلى.

الحذف الغاوسي هو مثال على 'تبسيط النسخة'.

لحل نظام من n معادلة خطية، نقوم بتحويل مصفوفة المعاملات إلى نظام مكافئ بمصفوفة مثلثية عليا (المرحلة 1: الحذف الأمامي).

بعد ذلك، نقوم بحل النظام باستخدام التعويض العكسي (المرحلة 2: Back substitution) بدءاً من المعادلة الأخيرة صعوداً إلى الأولى.

الكفاءة الزمنية الكلية لخوارزمية الحذف الغاوسي. \[\Theta(n^3) + \Theta(n^2) = \Theta(n^3)\]
pseudocode 
// Stage 1: Reduction to upper-triangular matrix
for i <- 1 to n-1 do
  for j <- i+1 to n do
    for k <- i to n+1 do
      A[j, k] <- A[j, k] - A[i, k] * A[j, i] / A[i, i]

// Stage 2: Back substitutions
for j <- n down to 1 do
  t <- 0
  for k <- j+1 to n do
    t <- t + A[j, k] * x[k]
  x[j] <- (A[j, n+1] - t) / A[j, j]

6.4 أشجار البحث الثنائية (BST)

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

شجرة البحث الثنائية ترتب المفاتيح بحيث تحقق 'خاصية شجرة البحث الثنائية'.

تدعم عمليات القاموس: البحث (مباشر)، الإدراج (البحث عن المفتاح وإدراجه كعقدة ورقية)، والحذف (3 حالات: ورقة، عقدة بطفل واحد، عقدة بطفلين).

تعتمد كفاءة هذه العمليات على ارتفاع الشجرة h، حيث log_2(n) <= h <= n-1.

حدود ارتفاع شجرة البحث الثنائية. \[\lfloor \log_2 n \rfloor \le h \le n-1\]

6.5 أشجار AVL (AVL Trees)

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

شجرة AVL هي شجرة بحث ثنائية حيث يكون 'عامل التوازن' (Balance Factor) لكل عقدة هو إما -1، 0، أو 1.

عامل التوازن يُحسب كـ (ارتفاع الشجرة الفرعية اليسرى - ارتفاع الشجرة الفرعية اليمنى). ارتفاع الشجرة الفارغة يُعرّف بأنه -1.

هذا التوازن الصارم يضمن أن عمليات البحث والإدراج والحذف تتم في وقت O(log n) في أسوأ الحالات.

الحد الأقصى لارتفاع شجرة AVL، مما يثبت كفاءتها اللوغاريتمية. \[h \le 1.4404 \log_2(n + 2) - 1.3277\]

6.6 دورانات شجرة AVL

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

إذا أدى إدراج مفتاح إلى الإخلال بشرط التوازن، يتم تحويل الشجرة الفرعية باستخدام أحد الدورانات الأربعة:

  1. دوران أحادي لليمين (R-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليسرى للابن الأيسر.
  2. دوران أحادي لليسار (L-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليمنى للابن الأيمن.
  3. دوران مزدوج يسار-يمين (LR-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليمنى للابن الأيسر.
  4. دوران مزدوج يمين-يسار (RL-rotation): يُنفذ عند الإدراج في الشجرة الفرعية اليسرى للابن الأيمن.

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

المعادلة / المفهوم الوحدة LaTeX / Notation
وقت التشغيل يساوي تقريباً وقت تنفيذ العملية الأساسية مضروباً في عدد مرات تنفيذها. M2 \(T(n) \approx c_{op} C(n)\)
حساب الحالة المتوسطة يعتمد على احتمالية كل حالة ممكنة. M2 \(C_{avg}(n) = \sum_{i=1}^{n} i \cdot P(i)\)
تعريف الحد الأعلى التقاربي (Big-O). M2 \(t(n) \le c \cdot g(n) \implies t(n) \in O(g(n))\)
مجموع التكرارات المتداخلة لخوارزمية فحص تفرد العناصر. M2 \(C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{n(n-1)}{2} \approx \frac{1}{2}n^2 \in \Theta(n^2)\)
علاقة التكرار لعدد عمليات الضرب في خوارزمية المضروب التكرارية. M2 \(M(n) = M(n-1) + 1, \quad M(0) = 0\)
عدد المقارنات في خوارزمية ترتيب الاختيار. M3 \(C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{(n-1)n}{2}\)
عدد المقارنات في الترتيب الفقاعي في أسوأ الحالات. M3 \(C(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 = \frac{(n-1)n}{2} \in O(n^2)\)
عدد المقارنات في أسوأ حالة لمطابقة السلاسل النصية. M3 \(m(n - m + 1) \in O(nm)\)
عدد مرات حساب المسافة بين النقاط. M3 \(C(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \frac{(n-1)n}{2} \in O(n^2)\)
عدد المسارات الممكنة في مشكلة البائع المتجول. M3 \(\frac{(n-1)!}{2}\)
التعقيد الزمني للبحث الشامل لمشكلة حقيبة الظهر. M3 \(O(2^n)\)
التعقيد الزمني للبحث الشامل لمشكلة التعيين. M3 \(O(n!)\)
التعقيد الزمني لـ DFS باستخدام قائمة التجاور. M3 \(O(|V| + |E|)\)
التعقيد الزمني لـ BFS باستخدام مصفوفة التجاور. M3 \(O(|V|^2)\)
عدد المقارنات في أسوأ حالة للترتيب بالإدراج. M4 \(C_{worst}(n) = \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} \in O(n^2)\)
عدد المقارنات في أسوأ حالة للبحث الثنائي. M4 \(C_{worst}(n) \approx \log_2 n + 1\)
صيغة خوارزمية إقليدس. M4 \(\gcd(m, n) = \gcd(n, m \bmod n)\)
التعقيد الزمني لأسوأ حالة لخوارزمية Quickselect. M4 \(C_{worst}(n) = (n-1) + (n-2) + \dots + 1 = \frac{(n-1)n}{2} \in O(n^2)\)
معادلة التكرار العامة لخوارزميات فرّق تسد، حيث a هو عدد المشاكل الفرعية، و b هو عامل التقسيم، و f(n) هو وقت التقسيم والدمج. M5 \(T(n) = aT(n/b) + f(n)\)
الحل الدقيق لأسوأ حالة لعدد المقارنات في الترتيب بالدمج. M5 \(C_{worst}(n) = n \log_2 n - n + 1\)
عدد المقارنات في أسوأ حالة للترتيب السريع. M5 \(C_{worst}(n) = \frac{(n+1)(n+2)}{2} - 3 \in O(n^2)\)
التعقيد الزمني لخوارزمية ضرب الأعداد الكبيرة المحسنة. M5 \(T(n) = 3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}\)
التعقيد الزمني لخوارزمية شتراسن. M5 \(M(n) = 7^{\log_2 n} = n^{\log_2 7} \approx n^{2.807}\)
معادلة التكرار والتعقيد الزمني لمشكلة أقرب زوج باستخدام فرّق تسد. M5 \(T(n) = 2T(n/2) + O(n) \implies O(n \log n)\)
الكفاءة الزمنية لمشكلة تفرد العناصر باستخدام الفرز المسبق. M6 \(\Theta(n \log n) + O(n) = \Theta(n \log n)\)
الكفاءة الزمنية الكلية لخوارزمية الحذف الغاوسي. M6 \(\Theta(n^3) + \Theta(n^2) = \Theta(n^3)\)
حدود ارتفاع شجرة البحث الثنائية. M6 \(\lfloor \log_2 n \rfloor \le h \le n-1\)
الحد الأقصى لارتفاع شجرة AVL، مما يثبت كفاءتها اللوغاريتمية. M6 \(h \le 1.4404 \log_2(n + 2) - 1.3277\)

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

الحل الدقيق مقابل الحل التقريبي

المعيار Exact Algorithm Approximation Algorithm
النتيجة ينتج النتيجة الصحيحة والدقيقة تماماً ينتج نتيجة قريبة من الحل الصحيح ضمن حد خطأ مسموح
حالة الاستخدام المشاكل القابلة للحل في وقت معقول المشاكل المعقدة جداً (مثل استخراج الجذور، التكاملات)

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

المعيار Big-O (O) Big-Omega (Ω) Big-Theta (Θ)
نوع الحد حد أعلى (Upper Bound) حد أدنى (Lower Bound) حد محكم (Tight Bound)
الاستخدام الشائع تحليل الحالة الأسوأ تحليل الحالة الأفضل تحليل الحالة المتوسطة / الدقيقة

مقارنة حالات الكفاءة

المعيار Worst-case Best-case Average-case
التعريف أطول وقت تشغيل لمدخل بحجم n أقصر وقت تشغيل لمدخل بحجم n الوقت المتوقع لمدخلات عشوائية

مقارنة بين DFS و BFS

المعيار Depth-First Search (DFS) Breadth-First Search (BFS)
بنية البيانات المستخدمة المكدس (Stack - LIFO) الطابور (Queue - FIFO)
طريقة الاستكشاف التعمق في مسار واحد حتى النهاية ثم التراجع استكشاف متمركز (مستوى بمستوى)
التعقيد الزمني (قائمة التجاور) O(|V| + |E|) O(|V| + |E|)

ترتيب الاختيار مقابل الترتيب الفقاعي

المعيار Selection Sort Bubble Sort
آلية العمل يبحث عن الأصغر ويضعه في البداية يقارن المتجاورين ويرفع الأكبر للنهاية
عدد التبديلات (Swaps) تبديل واحد لكل تمريرة O(n) تبديلات متعددة لكل تمريرة O(n^2)

مقارنة بين أنواع تقليل وحل

المعيار Decrease by a constant Decrease by a constant factor Variable-size decrease
مقدار التقليل ثابت (غالباً 1) عامل ثابت (غالباً النصف) متغير في كل تكرار
مثال خوارزمية الترتيب بالإدراج (Insertion Sort) البحث الثنائي (Binary Search) خوارزمية إقليدس (Euclid's Algorithm)

الترتيب بالدمج مقابل الترتيب السريع

المعيار Merge Sort Quick Sort
طريقة التقسيم حسب الموقع (النصف) حسب القيمة (المحور)
أسوأ حالة للتعقيد الزمني O(n log n) O(n^2)
متطلبات المساحة الإضافية كبيرة O(n) صغيرة (In-place)

القوة الغاشمة مقابل الفرز المسبق (تفرد العناصر)

المعيار Brute Force Presorting
الكفاءة الزمنية O(n^2) O(n log n)
النهج مقارنة كل زوج من العناصر الفرز أولاً ثم فحص العناصر المتجاورة

شجرة البحث الثنائية مقابل شجرة AVL

المعيار Standard BST AVL Tree
كفاءة البحث في أسوأ حالة O(n) O(log n)
التوازن غير مضمون (قد تصبح كقائمة مرتبطة) مضمون بصرامة (فرق الارتفاع <= 1)
تعقيد الإدراج/الحذف بسيط معقد (يتطلب دورانات متكررة)

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

🎯 اختبر نفسك

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

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

أهلاً بكم يا أبنائي وبناتي طلاب مقرر CS353 في ليلة الاختبار النصفي. لقد وصلنا إلى هذه المحطة الهامة بعد رحلة علمية شيقة ومكثفة، وأنا فخور جداً بما أنجزتموه حتى الآن. في هذه الليلة الحاسمة، أريدكم أن تسترخوا وتتأملوا كيف تترابط الوحدات الست التي درسناها لتشكل خريطة طريق متكاملة لحل المشكلات البرمجية. بدأنا في الوحدة الأولى بفهم جوهر الخوارزميات، وتعرفنا على خصائصها الخمس الأساسية والخطوات المنهجية لتصميمها وتحليلها. هذا الفهم النظري قادنا مباشرة إلى الوحدة الثانية، حيث تسلحنا بالأدوات الرياضية القوية مثل الرموز التقاربية (Asymptotic Notations) وعلاقات التكرار (Recurrence Relations) لتقييم كفاءة الخوارزميات بدقة. هنا يكمن الفخ الأول في الاختبار: لا تخلطوا بين تعقيد الحالة الأسوأ والحالة المتوسطة، وتأكدوا من إتقان حل علاقات التكرار لأنها الأساس لتقييم الخوارزميات العودية. بعد إرساء الأساس، انتقلنا في الوحدة الثالثة إلى استراتيجية القوة الغاشمة والبحث الشامل (Brute Force). ورغم أنها طريقة مباشرة ومضمونة لحل المشكلات التوافقية المعقدة، إلا أننا أدركنا قصورها في التعامل مع البيانات الضخمة. هذا القصور كان الدافع للانتقال إلى استراتيجيات أكثر ذكاءً. في الوحدة الرابعة، تعلمنا تقنية التقليل والقهر (Decrease-and-Conquer)، حيث نستغل العلاقة بين المشكلة الأصلية ونسخة أصغر منها. احذروا في الاختبار من الخلط بين هذه التقنية وبين تقنية فرق تسد (Divide-and-Conquer) التي درسناها في الوحدة الخامسة؛ فالأولى تقلل حجم المشكلة بمقدار ثابت أو نسبة معينة، بينما الثانية تقسم المشكلة إلى عدة مشكلات فرعية، تحلها عودياً، ثم تدمج النتائج. الفخ الثاني هنا هو نسيان خطوة الدمج (Combine) وتكلفتها عند حساب التعقيد الزمني في خوارزميات فرق تسد. أخيراً، توجنا هذه الاستراتيجيات في الوحدة السادسة بتقنية التحويل والقهر (Transform-and-Conquer)، والتي علمتنا أن نعمل بذكاء أكبر من خلال تحويل المشكلة المعقدة إلى شكل أبسط أو بنية بيانات أسهل قبل حلها. في الاختبار، ركزوا على كيفية اختيار الاستراتيجية الأنسب لكل مشكلة، وكيفية كتابة علاقة التكرار الصحيحة لها. تذكروا أن كل وحدة تبني على ما قبلها؛ فلا يمكنكم تحليل خوارزمية فرق تسد بدون أدوات الوحدة الثانية. خذوا نفساً عميقاً، راجعوا بهدوء، وتجنبوا السهر الطويل. أنتم مستعدون تماماً لتجاوز هذا الاختبار النصفي بنجاح وتفوق. بالتوفيق!

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

26 نقطة حرجة
💡 سر الامتحان M4
في الفرز الطوبولوجي، إذا كان هناك أكثر من رأس بدرجة دخول صفر (in-degree = 0) في نفس الوقت، يمكنك اختيار أي منها. هذا يعني أن الرسم البياني الواحد قد يكون له عدة حلول صحيحة للفرز الطوبولوجي.
⚠️ فخ M1
الاعتقاد بأن الخوارزمية صحيحة إذا كانت تعمل 'في معظم الأوقات'. الخوارزمية الصحيحة يجب أن تعمل بشكل صحيح لجميع المدخلات المشروعة.
💡 سر الامتحان M2
في التحليل الرياضي، نحن لا نهتم بالثوابت (Constants) أو الحدود ذات الرتب الأقل، لأننا ندرس 'رتبة النمو' عندما يؤول حجم المدخلات (n) إلى المالانهاية.
💡 سر الامتحان M1
المخططات الانسيابية (Flowcharts) أصبحت تقنية قديمة وغير مريحة، ونادراً ما تستخدم اليوم مقارنة بالكود الوهمي (Pseudocode) الذي يهيمن على المجال.
⚠️ فخ M3
الاعتقاد بأن DFS و BFS لهما تعقيد زمني مختلف. كلاهما يمتلك نفس التعقيد: O(|V|^2) لمصفوفة التجاور و O(|V| + |E|) لقائمة التجاور.
💡 سر الامتحان M5
في خوارزمية شتراسن، على الرغم من أن عدد عمليات الجمع يزداد بشكل كبير، إلا أن التعقيد الزمني الكلي ينخفض لأن عمليات الضرب هي التي تهيمن على وقت التنفيذ (Asymptotic growth).
🔑 مفهوم أساسي M6
عامل التوازن في شجرة AVL يُحسب دائماً كـ (ارتفاع اليسار - ارتفاع اليمين). إذا تجاوزت هذه القيمة 1 أو قلت عن -1، فالشجرة تحتاج إلى دوران.
⚠️ فخ M5
الخلط بين طريقة التقسيم في Merge Sort و Quick Sort. الترتيب بالدمج يقسم حسب 'الموقع' (النصف الأيمن والأيسر)، بينما الترتيب السريع يقسم حسب 'القيمة' (أكبر وأصغر من المحور).
⚠️ فخ M6
الخلط بين اتجاه الدوران ومكان الإدراج. الدوران لليمين (R-rotation) يُستخدم لإصلاح شجرة ثقيلة من جهة اليسار (إدراج في يسار-اليسار)، وليس العكس!
💡 سر الامتحان M3
في البحث المتسلسل، إضافة 'حارس' (Sentinel) لا يغير التعقيد الزمني O(n)، ولكنه يسرع التنفيذ الفعلي بتقليل عدد العمليات داخل الحلقة.
⚠️ فخ M2
الخطأ الشائع: الاعتقاد بأن الحالة المتوسطة (Average-case) هي ببساطة (الحالة الأفضل + الحالة الأسوأ) / 2. الحقيقة: تتطلب الحالة المتوسطة معرفة التوزيع الاحتمالي للمدخلات.
⚠️ فخ M4
الاعتقاد بأن الترتيب بالإدراج (Insertion Sort) دائماً بطيء (O(n^2)). في الواقع، هو سريع جداً O(n) إذا كانت المصفوفة شبه مرتبة، مما يجعله مفضلاً في بعض الحالات العملية على خوارزميات أكثر تعقيداً.
⚠️ فخ M2
الخلط بين Big-O و Big-Theta. Big-O يعطيك فقط سقفاً (قد يكون فضفاضاً جداً، مثل القول أن n ينتمي لـ O(n^3))، بينما Big-Theta يعطيك وصفاً دقيقاً ومحكماً لنمو الدالة.
🔑 مفهوم أساسي M3
البحث الشامل (Exhaustive Search) ليس استراتيجية جديدة، بل هو مجرد تطبيق لمبدأ 'القوة الغاشمة' على المشكلات التوافقية (التي تتطلب توليد تباديل أو مجموعات فرعية).
🔑 مفهوم أساسي M1
المشاكل التوافقية (مثل مشكلة البائع المتجول) هي الأصعب عملياً في الحوسبة بسبب الانفجار التوافقي للاحتمالات.
🔑 مفهوم أساسي M2
العملية الأساسية (Basic Operation) هي المفتاح. ابحث دائماً عن العملية الموجودة في الحلقة الأعمق (Innermost loop) لأنها ستنفذ أكبر عدد من المرات وتهيمن على وقت التشغيل.
💡 سر الامتحان M6
في الحذف الغاوسي، التعقيد الزمني O(n^3) يأتي بالكامل من مرحلة الحذف الأمامي (بسبب الحلقات الثلاث المتداخلة). مرحلة التعويض العكسي سريعة جداً وتستغرق O(n^2) فقط.
⚠️ فخ M3
الخلط بين التعقيد الزمني لمشكلة البائع المتجول (TSP) وحقيبة الظهر (Knapsack). TSP تعقيدها عاملي O(n!) بينما حقيبة الظهر تعقيدها أسي O(2^n).
⚠️ فخ M5
الاعتقاد بأن الترتيب السريع (Quick Sort) دائماً أسرع من الترتيب بالدمج. في أسوأ الحالات (مصفوفة مرتبة مسبقاً)، ينحدر الترتيب السريع إلى O(n^2) بينما يحافظ الترتيب بالدمج على O(n log n).
🔑 مفهوم أساسي M1
المعادلة الذهبية: الخوارزميات + هياكل البيانات = البرامج (Algorithms + Data Structures = Programs).
⚠️ فخ M4
محاولة تطبيق الفرز الطوبولوجي على رسم بياني يحتوي على دورة (Cycle). الخوارزمية ستفشل ولن تتمكن من معالجة جميع الرؤوس. الفرز الطوبولوجي يعمل *فقط* على DAG.
🔑 مفهوم أساسي M5
السر في كفاءة خوارزمية 'أقرب زوج' هو خطوة الدمج. بدلاً من مقارنة كل نقطة بالنقاط الأخرى (O(n^2))، نكتفي بفحص 6 نقاط كحد أقصى لكل نقطة داخل الشريط العمودي، مما يجعل خطوة الدمج O(n).
🔑 مفهوم أساسي M4
خوارزمية Quickselect لا تقوم بترتيب المصفوفة بالكامل. إنها تستخدم التقسيم (Partitioning) لتجاهل جزء كبير من المصفوفة في كل خطوة، مما يجعلها أسرع بكثير من الترتيب الكامل لإيجاد الوسيط.
⚠️ فخ M6
الاعتقاد بأن شجرة البحث الثنائية (BST) تضمن دائماً وقت بحث O(log n). هذا فخ! في أسوأ الحالات (مثل إدراج عناصر مرتبة)، تصبح الشجرة خطية ويكون وقت البحث O(n).
🔑 مفهوم أساسي M4
الفرق الجوهري بين 'تقليل وحل' و 'فرق تسد' هو أن 'تقليل وحل' يقلل المشكلة إلى مشكلة فرعية *واحدة* فقط، بينما 'فرق تسد' يقسمها إلى *عدة* مشاكل فرعية.
🔑 مفهوم أساسي M6
الفرز المسبق (Presorting) يغير عنق الزجاجة في الخوارزمية. بدلاً من حل المشكلة بطريقة القوة الغاشمة البطيئة O(n^2)، نقوم بالفرز O(n log n) ثم نحل المشكلة في وقت خطي O(n).