تقليل وحل (Decrease-and-Conquer)
دراسة تقنية 'تقليل وحل' في تصميم الخوارزميات، بما في ذلك التقليل بمقدار ثابت (مثل الترتيب بالإدراج)، التقليل بعامل ثابت (مثل البحث الثنائي)، والتقليل بحجم متغير (مثل خوارزمية إقليدس والفرز الطوبولوجي).
Decrease-and-Conquer
Study of the 'Decrease-and-Conquer' algorithm design technique, including decrease-by-a-constant (e.g., Insertion Sort), decrease-by-a-constant-factor (e.g., Binary Search), and variable-size-decrease (e.g., Euclid's algorithm and Topological Sorting).
أهداف التعلم
- وصف تقنية 'تقليل وحل' وأنواعها المختلفة.
- وصف خوارزمية الترتيب بالإدراج والفرز الطوبولوجي وتحليل تعقيدها.
- التعرف على خوارزميات التقليل بعامل ثابت وخوارزميات التقليل بحجم متغير.
- Describe Decrease-and-Conquer and their various types.
- Describe the insert sort, topological Sorting and analysis their complexity.
- Recognize Constant-Factor Algorithms and variable size algorithms.
1 مقدمة في تقليل وحل
1 Introduction to Decrease-and-Conquer
تقنية تعتمد على استغلال العلاقة بين حل مشكلة بحجم معين وحلها بحجم أصغر.
A technique based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.
تقنية 'تقليل وحل' (Decrease-and-Conquer) تقوم على تقليل حجم المشكلة إلى مشكلة فرعية أصغر، ثم حل المشكلة الفرعية، وأخيراً توسيع الحل ليشمل المشكلة الأصلية.
يمكن تنفيذها بطريقتين: من أعلى إلى أسفل (Top-down) باستخدام النهج العودي (Recursive)، أو من أسفل إلى أعلى (Bottom-up) باستخدام النهج التكراري (Iterative) والذي يسمى أحياناً بالنهج التزايدي (Incremental approach).
The decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.
Once established, it can be exploited either top-down (usually implemented using a recursive approach) or bottom-up (usually implemented iteratively, starting with the smallest instance, sometimes called the incremental approach).
تتفرع هذه التقنية إلى ثلاثة أنواع رئيسية:
- التقليل بمقدار ثابت (Decrease by a constant) وغالباً ما يكون 1.
- التقليل بعامل ثابت (Decrease by a constant factor) وغالباً ما يكون النصف.
- التقليل بحجم متغير (Variable size decrease) حيث يختلف نمط تقليل الحجم في كل تكرار.
There are three major variations:
- Decrease by a constant (usually by 1).
- Decrease by a constant factor (usually by half, i.e., factor of 2).
- Variable size decrease, where the size reduction pattern varies at each iteration.
لماذا يُعتبر النهج من أسفل إلى أعلى (التكراري) غالباً أكثر كفاءة من النهج من أعلى إلى أسفل (العودي)؟ Why is the bottom-up (iterative) approach often considered more efficient than the top-down (recursive) approach?
لأنه يتجنب العبء الإضافي (overhead) المرتبط باستدعاء الدوال المتكرر في الذاكرة (Call Stack).
Because it avoids the overhead associated with recursive function calls on the call stack.
2 التقليل بمقدار ثابت: الترتيب بالإدراج
2 Decrease by a Constant: Insertion Sort
خوارزمية ترتيب تقوم بإدخال عنصر جديد في مكانه الصحيح ضمن مصفوفة فرعية مرتبة مسبقاً.
A sorting algorithm that inserts a new element into its correct position within an already sorted subarray.
الترتيب بالإدراج (Insertion Sort) هو تطبيق مباشر لتقنية التقليل بمقدار ثابت (بمقدار 1).
بافتراض أن لدينا مصفوفة فرعية مرتبة A[0..n-2]، نحتاج إلى إيجاد الموضع المناسب للعنصر A[n-1] وإدراجه.
يتم ذلك بمسح المصفوفة المرتبة من اليمين إلى اليسار حتى نجد أول عنصر أصغر من أو يساوي A[n-1].
التنفيذ من أسفل إلى أعلى (التكراري) أكثر كفاءة من العودي.
Insertion sort is a direct application of decrease-by-a-constant (by 1).
Given a sorted array A[0..n-2], a new element A[n-1] needs to be inserted.
We scan the sorted subarray from right to left until the first element smaller than or equal to A[n-1] is encountered, and insert it right after.
The bottom-up iterative implementation is more efficient.
تحليل التعقيد: العملية الأساسية هي مقارنة المفاتيح A[j] > v.
في أسوأ الحالات (مصفوفة مرتبة تنازلياً)، يكون التعقيد O(n^2).
في أفضل الحالات (مصفوفة مرتبة تصاعدياً)، يتم تنفيذ المقارنة مرة واحدة لكل تكرار، مما يعطي تعقيداً O(n).
في المتوسط، تقوم بنصف عدد المقارنات مقارنة بأسوأ حالة، مما يجعلها أسرع بمرتين من أسوأ حالة وممتازة للمصفوفات شبه المرتبة.
هي أفضل من الترتيب بالاختيار (Selection Sort) والترتيب بالفقاعة (Bubble Sort).
Algorithm analysis: The basic operation is the key comparison A[j] > v.
Worst-case (decreasing array) is O(n^2).
Best-case (already sorted array) is O(n).
Average-case makes half as many comparisons as the worst case, making it twice as fast on average and excellent for almost-sorted arrays.
It is better than selection sort and bubble sort.
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لماذا يُفضل استخدام الترتيب بالإدراج عندما تكون المصفوفة 'شبه مرتبة'؟ Why is Insertion Sort preferred when an array is 'almost sorted'?
لأن الحلقة الداخلية (while) ستتوقف مبكراً جداً، مما يجعل الأداء يقترب من أفضل حالة O(n).
Because the inner while loop will terminate very early, making the performance approach the best-case O(n).
3 الفرز الطوبولوجي (Topological Sorting)
3 Topological Sorting
ترتيب رؤوس رسم بياني موجه بحيث يظهر كل رأس قبل الرؤوس التي يشير إليها.
Ordering vertices of a directed graph such that for every directed edge uv, vertex u comes before v.
الفرز الطوبولوجي يحل مشكلة ترتيب المهام المعتمدة على بعضها (مثل المقررات الدراسية ذات المتطلبات السابقة).
يجب أن يكون الرسم البياني موجهاً وخالياً من الدورات (DAG - Directed Acyclic Graph).
إذا كان الرسم البياني يحتوي على دورة موجهة (Directed Cycle)، فلا يمكن إيجاد فرز طوبولوجي له.
Topological sorting solves the problem of ordering dependent tasks (like courses with prerequisites).
The graph must be a Directed Acyclic Graph (DAG).
If a digraph has no directed cycles, the topological sorting problem for it has a solution.
خوارزمية إزالة المصدر (Source-removal algorithm): تعتمد على تحديد 'مصدر' (رأس لا توجد حواف داخلة إليه / in-degree = 0)، وحذفه مع جميع حوافه الخارجة، ثم تكرار العملية.
الترتيب الذي تُحذف به الرؤوس يمثل الفرز الطوبولوجي.
إذا كان هناك عدة مصادر، يمكن كسر التعادل بشكل عشوائي، مما يعني أنه قد يكون هناك أكثر من فرز طوبولوجي صحيح لنفس الرسم البياني.
Source-removal algorithm: Repeatedly identify a 'source' (a vertex with no incoming edges, in-degree = 0), delete it along with all its outgoing edges.
The order in which vertices are deleted yields the topological sort.
Ties among multiple sources can be broken arbitrarily, meaning multiple valid topological sorts can exist.
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ماذا يحدث إذا حاولت تطبيق خوارزمية إزالة المصدر على رسم بياني يحتوي على دورة؟ What happens if you try to apply the source-removal algorithm on a graph with a cycle?
ستتوقف الخوارزمية قبل معالجة جميع الرؤوس لأنه لن يتبقى أي رأس بدرجة دخول (in-degree) تساوي صفراً.
The algorithm will halt before processing all vertices because there will be no remaining vertices with an in-degree of 0.
4 أنواع الحواف في غابة البحث بالعمق (DFS Forest)
4 Types of Edges in a DFS Forest
أربعة أنواع من الحواف تنتج عن اجتياز الرسم البياني الموجه باستخدام البحث بالعمق (DFS).
Four types of edges resulting from traversing a directed graph using Depth-First Search (DFS).
عند استخدام خوارزمية البحث بالعمق (DFS) لاجتياز رسم بياني موجه، يمكن تصنيف الحواف إلى أربعة أنواع:
- حواف الشجرة (Tree edges): الحواف التي تشكل غابة DFS.
- الحواف الخلفية (Back edges): تتجه من رأس إلى أحد أسلافه (تشير إلى وجود دورة).
- الحواف الأمامية (Forward edges): تتجه من رأس إلى أحد أحفاده في الشجرة (غير أبنائه المباشرين).
- الحواف المتقاطعة (Cross edges): حواف لا تنتمي لأي من الأنواع السابقة (تربط بين فروع مختلفة).
When traversing a digraph using DFS, edges are classified into four types:
- Tree edges: edges that make up the DFS forest.
- Back edges: from vertices to their ancestors (indicates a directed cycle).
- Forward edges: from vertices to their descendants in the tree other than their children.
- Cross edges: none of the aforementioned types (connecting different branches).
وجود 'حافة خلفية' (Back edge) هو الدليل القاطع على وجود دورة موجهة (Directed Cycle) في الرسم البياني.
إذا كانت غابة DFS لا تحتوي على حواف خلفية، فإن الرسم البياني هو DAG، وبالتالي يمكن إجراء فرز طوبولوجي له.
The presence of a 'back edge' is the definitive proof of a directed cycle in the graph.
If a DFS forest of a digraph has no back edges, the digraph is a DAG, and thus topological sorting is possible.
كيف يمكننا استخدام DFS للتحقق مما إذا كان الفرز الطوبولوجي ممكناً؟ How can we use DFS to check if topological sorting is possible?
نقوم بتشغيل DFS؛ إذا وجدنا أي حافة خلفية (Back edge)، فهذا يعني وجود دورة والفرز الطوبولوجي غير ممكن.
Run DFS; if we encounter any back edge, it means there is a cycle and topological sorting is not possible.
5 التقليل بعامل ثابت: البحث الثنائي
5 Decrease by a Constant Factor: Binary Search
خوارزمية بحث فعالة جداً في مصفوفة مرتبة، تقوم بتقليل حجم المشكلة إلى النصف في كل خطوة.
A highly efficient search algorithm in a sorted array that reduces the problem size by half at each step.
البحث الثنائي (Binary Search) هو مثال رئيسي على خوارزمية 'التقليل بعامل ثابت' (تحديداً بعامل 2).
يعمل عن طريق مقارنة مفتاح البحث K مع العنصر الأوسط A[m].
إذا تطابقا، تتوقف الخوارزمية. وإلا، تتكرر العملية على النصف الأول إذا كان K < A[m]، أو على النصف الثاني إذا كان K > A[m].
يمكن تنفيذه بشكل عودي أو تكراري (وهو الأفضل).
Binary search is a principal example of a decrease-by-a-constant-factor algorithm (specifically by a factor of 2).
It works by comparing a search key K with the array’s middle element A[m].
If they match, it stops; otherwise, it repeats recursively for the first half if K < A[m], and for the second half if K > A[m].
It can be implemented recursively or iteratively.
تحليل الخوارزمية: في أسوأ الحالات، يتم تقليل حجم المصفوفة إلى النصف في كل تكرار، مما يعطي علاقة التكرار: C_worst(n) = C_worst(n/2) + 1.
حل هذه العلاقة يعطي تعقيداً زمنياً قدره O(log n).
التحليل الدقيق يوضح أن متوسط عدد المقارنات أصغر بقليل فقط من أسوأ حالة.
يعتبر البحث الثنائي خوارزمية بحث مثالية (Optimal) إذا اقتصرنا على المقارنات بين المفاتيح.
Algorithm analysis: In the worst case, the array size is halved each iteration, yielding the recurrence relation: C_worst(n) = C_worst(floor(n/2)) + 1.
This resolves to O(log n).
Average-case analysis shows the number of comparisons is only slightly smaller than the worst case.
Binary search is an optimal searching algorithm if restricted only to key comparisons.
ALGORITHM BinarySearch(A[0..n-1], K)
l <- 0; r <- n - 1
while l <= r do
m <- floor((l + r) / 2)
if K = A[m] return m
else if K < A[m] r <- m - 1
else l <- m + 1
return -1لماذا لا نستخدم البحث الثنائي دائماً بدلاً من البحث الخطي؟ Why don't we always use Binary Search instead of Linear Search?
لأن البحث الثنائي يتطلب أن تكون المصفوفة مرتبة مسبقاً، وعملية الترتيب نفسها مكلفة (O(n log n)).
Because Binary Search requires the array to be sorted beforehand, and sorting itself is an expensive operation (O(n log n)).
6 التقليل بحجم متغير: خوارزمية إقليدس
6 Variable-Size-Decrease: Euclid's Algorithm
خوارزمية لحساب القاسم المشترك الأكبر (GCD) حيث يختلف مقدار تقليل المشكلة في كل خطوة.
An algorithm to compute the Greatest Common Divisor (GCD) where the size reduction varies at each step.
في خوارزميات 'التقليل بحجم متغير'، يختلف نمط تقليل الحجم في كل تكرار.
مثال ممتاز على ذلك هو خوارزمية إقليدس لحساب القاسم المشترك الأكبر.
تعتمد الخوارزمية على الصيغة: gcd(m, n) = gcd(n, m mod n).
قيمة المعامل الثاني (m mod n) تكون دائماً أصغر من المعامل الأول، ولكن مقدار النقصان يختلف في كل خطوة.
In 'Variable-Size-Decrease' algorithms, the size reduction pattern varies at each iteration.
A good example is Euclid’s algorithm for computing the greatest common divisor.
It is based on the formula: gcd(m, n) = gcd(n, m mod n).
The value of the second argument is always smaller, but the reduction amount varies.
على سبيل المثال، لحساب gcd(106, 16): 106 mod 16 = 10، ثم 16 mod 10 = 6، ثم 10 mod 6 = 4، ثم 6 mod 4 = 2، ثم 4 mod 2 = 0.
النتيجة هي 2.
نلاحظ أن الحجم يقل بشكل غير ثابت (من 16 إلى 10 إلى 6 إلى 4 إلى 2).
For example, computing gcd(106, 16): 106 mod 16 = 10, then 16 mod 10 = 6, then 10 mod 6 = 4, then 6 mod 4 = 2, then 4 mod 2 = 0.
The GCD is 2.
The size decreases variably (16 -> 10 -> 6 -> 4 -> 2).
متى تتوقف خوارزمية إقليدس؟ When does Euclid's algorithm terminate?
تتوقف عندما يصبح المعامل الثاني (n) صفراً، ويكون المعامل الأول (m) هو القاسم المشترك الأكبر.
It terminates when the second argument (n) becomes zero, and the first argument (m) is the GCD.
7 مشكلة الاختيار و Quick Select
7 The Selection Problem and Quick Select
إيجاد العنصر رقم k الأصغر في مصفوفة باستخدام تقسيم عشوائي (Partitioning) دون ترتيب المصفوفة بالكامل.
Finding the k-th smallest element in an array using randomized partitioning without fully sorting the array.
مشكلة الاختيار (Selection Problem) هي إيجاد العنصر رقم k الأصغر في مصفوفة A[0..n-1].
أسهل حالة هي إيجاد الحد الأدنى (k=1) أو الأقصى (k=n)، وأصعب حالة هي إيجاد الوسيط (k=n/2).
بدلاً من ترتيب المصفوفة بالكامل (مما يستغرق وقتاً أطول)، نستخدم استراتيجية التقسيم العشوائي (Randomized Partitioning) مثل تقسيم لوموتو (Lomuto partitioning).
The Selection Problem is finding the k-th smallest element in an array A[0..n-1].
The easiest case is finding the Min (k=1) or Max (k=n), and the hardest is the Median (k=n/2).
Instead of sorting the entire list, we use randomized partitioning (like Lomuto partitioning) around a pivot value p.
خوارزمية Quickselect: بعد التقسيم، يكون المحور (pivot) في موقعه النهائي s.
إذا كان s = k-1، فقد وجدنا العنصر.
إذا كان s > k-1، نبحث في الجزء الأيسر.
إذا كان s < k-1، نبحث في الجزء الأيمن عن العنصر رقم (k-s).
تحليل التعقيد: في أفضل الحالات (والمتوسطة)، يتم حل المشكلة في O(n).
في أسوأ الحالات (تقسيم غير متوازن تماماً في كل خطوة)، يكون التعقيد O(n^2).
Quickselect algorithm: After partitioning, the pivot is at its final index s.
If s = k-1, the pivot is the k-th smallest.
If s > k-1, search the left part.
If s < k-1, search the right part for the (k-s)-th element.
Analysis: Best/Average case is O(n).
Worst case (extremely unbalanced partition every time) is O(n^2).
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)لماذا يعتبر إيجاد الوسيط (Median) هو الحالة الأصعب في مشكلة الاختيار؟ Why is finding the median considered the hardest case in the selection problem?
لأنه يتطلب الغوص في عمق المصفوفة وتقسيمها عدة مرات للوصول إلى المنتصف الدقيق، عكس الحد الأدنى أو الأقصى الذي يمكن إيجاده بمسحة واحدة.
Because it requires diving deep into the array and partitioning multiple times to reach the exact middle, unlike min/max which can be found in a single pass.
| Decrease by a constant | Decrease by a constant factor | Variable-size decrease | |
|---|---|---|---|
| مقدار التقليل Reduction Amount | ثابت (غالباً 1) Constant (usually 1) | عامل ثابت (غالباً النصف) Constant factor (usually half) | متغير في كل تكرار Varies at each iteration |
| مثال خوارزمية Algorithm Example | الترتيب بالإدراج (Insertion Sort) Insertion Sort | البحث الثنائي (Binary Search) Binary Search | خوارزمية إقليدس (Euclid's Algorithm) Euclid's Algorithm |