الوحدة الخامسة: خوارزميات فرّق تسد
تغطي هذه الوحدة استراتيجية 'فرّق تسد' في تصميم الخوارزميات، بما في ذلك خوارزميات الترتيب (الدمج والسريع)، اجتياز الأشجار الثنائية، ضرب الأعداد الكبيرة، خوارزمية شتراسن لضرب المصفوفات، ومشكلة أقرب زوج.
Module 5: Divide-and-Conquer
This module covers the Divide-and-Conquer algorithm design technique, including sorting algorithms (Merge and Quick sort), binary tree traversals, large integer multiplication, Strassen's matrix multiplication, and the closest-pair problem.
أهداف التعلم
- وصف استراتيجية 'فرّق تسد' وأنواعها المختلفة.
- شرح خوارزميتي الترتيب بالدمج والترتيب السريع وتحليل تعقيدهما.
- التعرف على طرق اجتياز الأشجار الثنائية والخصائص المتعلقة بها.
- تطبيق ضرب الأعداد الصحيحة الكبيرة وخوارزمية شتراسن لضرب المصفوفات.
- توضيح مشكلة أقرب زوج باستخدام 'فرّق تسد' وتحليلها.
- Describe Divide-and-Conquer and their various types.
- Describe the Mergesort, Quicksort and analysis their complexity.
- Recognize Binary Tree Traversals and Related Properties.
- Apply multiplication of large Integers and Strassen’s Matrix Multiplication.
- Demonstrate the Closest-Pair Problem by Divide-and-Conquer and its analysis.
1 استراتيجية فرّق تسد
1 Divide-and-Conquer Paradigm
استراتيجية لحل المشكلات تعتمد على تقسيم المشكلة إلى أجزاء أصغر، حلها، ثم دمج الحلول.
A problem-solving strategy that divides a problem into smaller subproblems, solves them, and combines the results.
تتكون خطة 'فرّق تسد' من ثلاث خطوات رئيسية:
- التقسيم (Divide): تقسيم المشكلة إلى عدة مشاكل فرعية من نفس النوع، ويفضل أن تكون متساوية الحجم.
- الفتح/الحل (Conquer): حل المشاكل الفرعية بشكل عودي (Recursively).
- الدمج (Combine): دمج حلول المشاكل الفرعية للحصول على حل للمشكلة الأصلية.
The divide-and-conquer plan consists of three steps:
- Divide: a problem is divided into several subproblems of the same type, ideally of about equal size.
- Conquer: the subproblems are solved recursively.
- Combine: the solutions to the subproblems are combined to get a solution to the original problem.
تعتبر هذه الخوارزميات أكثر كفاءة من حلول القوة الغاشمة (Brute-force).
كما أن هذه التقنية مناسبة جداً للحوسبة المتوازية (Parallel computations) المستخدمة في حل المشاكل المعقدة.
A divide-and-conquer algorithm is necessarily more efficient than even a brute-force solution.
The technique is also well-suited for parallel computations used for solving complex problems.
لماذا يُشترط غالباً أن تكون المشاكل الفرعية من نفس نوع المشكلة الأصلية في استراتيجية فرّق تسد؟ Why is it often required that subproblems be of the same type as the original problem in Divide-and-Conquer?
للسماح باستخدام الاستدعاء الذاتي (Recursion) لحل المشاكل الفرعية بنفس الخوارزمية.
To allow the use of recursion, enabling the same algorithm to solve the subproblems.
2 الترتيب بالدمج
2 Merge Sort
خوارزمية ترتيب تقسم المصفوفة إلى نصفين، ترتب كل نصف، ثم تدمجهما معاً.
A sorting algorithm that divides the array into two halves, sorts each, and merges them back together.
الترتيب بالدمج هو مثال مثالي لتطبيق 'فرّق تسد'.
يقوم بترتيب مصفوفة عن طريق تقسيمها إلى نصفين، ثم ترتيب كل نصف بشكل عودي، وأخيراً دمج المصفوفتين المرتبتين في مصفوفة واحدة.
عملية الدمج تستخدم مؤشرين يقارنان العناصر ويضعان الأصغر في المصفوفة الجديدة.
Mergesort is a perfect example of a successful application of the divide-and-conquer technique.
It sorts an array by dividing it into two halves, sorting each recursively, and then merging the two smaller sorted arrays into a single sorted one.
The merging process uses two pointers to compare elements and copy the smaller one to a new array.
معادلة التكرار هي C(n) = 2C(n/2) + C_merge(n).
في أسوأ الحالات، التعقيد الزمني هو O(n log n).
العيب الرئيسي لهذه الخوارزمية هو حاجتها لمساحة تخزين إضافية كبيرة (Extra storage requirement) لعملية الدمج.
The recurrence relation is C(n) = 2C(n/2) + C_merge(n).
In the worst case, the time complexity is O(n log n).
Its principal drawback is a significant extra storage requirement for the merging phase.
| الترتيب بالدمجMerge Sort | الترتيب السريعQuick Sort | |
|---|---|---|
| طريقة التقسيمDivision Method | حسب الموقع (النصف)By position (halves) | حسب القيمة (المحور)By value (pivot) |
| أسوأ حالة للتعقيد الزمنيWorst-case Time Complexity | O(n log n)O(n log n) | O(n^2)O(n^2) |
| متطلبات المساحة الإضافيةExtra Space Requirement | كبيرة O(n)Significant O(n) | صغيرة (In-place)Minimal (In-place) |
لماذا يحتاج الترتيب بالدمج إلى مساحة تخزين إضافية O(n)؟ Why does Merge Sort require O(n) extra storage space?
لأنه لا يمكن دمج المصفوفتين في نفس المكان (in-place) بكفاءة؛ نحتاج إلى مصفوفة مؤقتة لتخزين العناصر المرتبة أثناء الدمج.
Because merging two arrays in-place efficiently is difficult; a temporary array is needed to hold the sorted elements during the merge step.
3 الترتيب السريع
3 Quick Sort
خوارزمية ترتيب تقسم المصفوفة بناءً على قيمة 'محور' (Pivot)، بحيث تكون العناصر الأصغر يساره والأكبر يمينه.
A sorting algorithm that partitions an array around a 'pivot' value, placing smaller elements to its left and larger to its right.
على عكس الترتيب بالدمج الذي يقسم حسب الموقع، الترتيب السريع يقسم حسب القيمة.
يتم اختيار عنصر كمحور (Pivot)، ويتم إعادة ترتيب المصفوفة (Partitioning) بحيث تصبح جميع العناصر التي تسبق المحور أصغر منه أو تساويه، والعناصر التي تليه أكبر منه أو تساويه.
ثم يتم ترتيب الجزأين بشكل مستقل.
Unlike Mergesort which divides by position, Quicksort divides by value.
A partition is an arrangement where all elements to the left of a pivot A[s] are less than or equal to it, and all elements to the right are greater than or equal to it.
The two subarrays are then sorted independently.
في أفضل الحالات والمتوسطة، التعقيد هو O(n log n).
لكن في أسوأ الحالات (مثلاً إذا كانت المصفوفة مرتبة تصاعدياً وتم اختيار العنصر الأول كمحور)، ينحدر التعقيد إلى O(n^2).
خوارزمية تقسيم Hoare تستخدم مؤشرين يتحركان باتجاه بعضهما البعض.
In the best and average cases, complexity is O(n log n).
In the worst case (e.g., strictly increasing array with the first element as pivot), it degrades to O(n^2).
Hoare partitioning uses two pointers scanning from both ends towards the middle.
كيف يمكننا تجنب أسوأ حالة في الترتيب السريع؟ How can we avoid the worst-case scenario in Quick Sort?
عن طريق اختيار المحور بشكل عشوائي، أو استخدام طريقة 'وسيط الثلاثة' (Median of Three) لاختيار المحور.
By choosing the pivot randomly, or using the 'Median of Three' method to select the pivot.
4 اجتياز الأشجار الثنائية
4 Binary Tree Traversals
طرق لزيارة كل عقدة في الشجرة الثنائية بالضبط مرة واحدة باستخدام الاستدعاء الذاتي.
Methods to visit every node in a binary tree exactly once using recursion.
هناك ثلاثة أنواع كلاسيكية لاجتياز الشجرة الثنائية:
- الاجتياز المسبق (Preorder): زيارة الجذر، ثم الشجرة الفرعية اليسرى، ثم اليمنى.
- الاجتياز الداخلي (Inorder): زيارة الشجرة الفرعية اليسرى، ثم الجذر، ثم اليمنى.
- الاجتياز اللاحق (Postorder): زيارة الشجرة الفرعية اليسرى، ثم اليمنى، ثم الجذر.
There are three classic traversals:
- Preorder: root is visited before left and right subtrees.
- Inorder: root is visited after left subtree but before right subtree.
- Postorder: root is visited after left and right subtrees.
تعتبر هذه الاجتيازات تطبيقات مباشرة لاستراتيجية 'فرّق تسد' لأن الشجرة الثنائية معرّفة بشكل عودي (Recursive definition).
التعقيد الزمني لجميع هذه الاجتيازات هو O(n) حيث n هو عدد العقد.
These traversals are direct applications of divide-and-conquer because a binary tree is recursively defined.
The time complexity for all traversals is O(n) where n is the number of nodes.
أي نوع من الاجتيازات يعطينا عناصر شجرة البحث الثنائية (BST) بترتيب تصاعدي؟ Which traversal gives the elements of a Binary Search Tree (BST) in ascending order?
الاجتياز الداخلي (Inorder traversal).
Inorder traversal.
5 ضرب الأعداد الصحيحة الكبيرة
5 Multiplication of Large Integers
استخدام 'فرّق تسد' لتقليل عدد عمليات الضرب الفردية عند ضرب أعداد ضخمة (مثل التشفير).
Using divide-and-conquer to reduce the number of single-digit multiplications when multiplying huge numbers (e.g., in cryptography).
الطريقة المدرسية التقليدية لضرب عددين من n خانة تتطلب O(n^2) عملية ضرب.
باستخدام 'فرّق تسد'، يمكننا تقسيم كل عدد إلى نصفين. الطريقة الساذجة (First Cut) تعطي 4 عمليات ضرب وتبقى O(n^2).
لكن الطريقة المحسنة (Second Cut) تستخدم خدعة جبرية لتقليل عمليات الضرب إلى 3 فقط.
The grade-school algorithm for multiplying two n-digit numbers requires O(n^2) multiplications.
Using divide-and-conquer, we split each number in half. The naive approach (First Cut) requires 4 multiplications, still yielding O(n^2).
The optimized approach (Second Cut) uses an algebraic trick to reduce it to 3 multiplications.
بتقليل عدد عمليات الضرب إلى 3، تصبح معادلة التكرار T(n) = 3T(n/2).
باستخدام النظرية الرئيسية، يصبح التعقيد الزمني O(n^1.585)، وهو تحسن كبير جداً للأعداد الضخمة على حساب زيادة طفيفة في عمليات الجمع والطرح.
By reducing multiplications to 3, the recurrence becomes T(n) = 3T(n/2).
Using the Master Theorem, the time complexity drops to O(n^1.585), a significant improvement for huge numbers at the cost of a few extra additions/subtractions.
لماذا نفضل زيادة عمليات الجمع لتقليل عمليات الضرب في الخوارزميات؟ Why do we prefer increasing additions to reduce multiplications in algorithms?
لأن عملية الضرب مكلفة حسابياً (تأخذ وقتاً أطول في المعالج) مقارنة بعملية الجمع.
Because multiplication is computationally more expensive (takes more CPU cycles) than addition.
6 خوارزمية شتراسن لضرب المصفوفات
6 Strassen’s Matrix Multiplication
خوارزمية لضرب المصفوفات تقلل عدد عمليات الضرب من 8 إلى 7 لمصفوفات 2x2.
A matrix multiplication algorithm that reduces the number of multiplications from 8 to 7 for 2x2 matrices.
ضرب مصفوفتين 2x2 بالطريقة التقليدية يتطلب 8 عمليات ضرب.
اكتشف شتراسن طريقة لحساب الناتج باستخدام 7 عمليات ضرب فقط، مع زيادة في عمليات الجمع والطرح.
يتم تطبيق هذه الفكرة بشكل عودي على مصفوفات بحجم n x n.
Multiplying two 2x2 matrices traditionally requires 8 multiplications.
Strassen discovered a way to compute the product using only 7 multiplications, with an increase in additions/subtractions.
This idea is applied recursively to n x n matrices.
معادلة التكرار لعمليات الضرب هي M(n) = 7M(n/2)، مما يعطي تعقيداً زمنياً O(n^2.807)، وهو أفضل من O(n^3) للطريقة التقليدية.
على الرغم من زيادة عمليات الجمع A(n) = 7A(n/2) + 18(n/2)^2، إلا أن التعقيد الكلي يبقى محكوماً بعمليات الضرب.
The recurrence for multiplications is M(n) = 7M(n/2), yielding a time complexity of O(n^2.807), which is better than the brute-force O(n^3).
Although additions increase (A(n) = 7A(n/2) + 18(n/2)^2), the overall asymptotic complexity is still dominated by the multiplications.
هل خوارزمية شتراسن دائماً أسرع من الطريقة التقليدية في الواقع؟ Is Strassen's algorithm always faster than the traditional method in practice?
لا، بسبب العبء الإضافي (Overhead) لعمليات الجمع والاستدعاء الذاتي، الطريقة التقليدية أسرع للمصفوفات الصغيرة.
No, due to the overhead of extra additions and recursion, the traditional method is faster for small matrices.
7 مشكلة أقرب زوج
7 The Closest-Pair Problem
إيجاد النقطتين الأقرب لبعضهما في مستوى ثنائي الأبعاد باستخدام تقسيم النقاط بخط عمودي.
Finding the two closest points in a 2D plane by dividing the points with a vertical line.
لحل المشكلة بكفاءة، نقسم النقاط إلى مجموعتين (يسار ويمين) بخط عمودي x=c.
نجد أقرب زوج في كل مجموعة بشكل عودي (d1 و d2).
نأخذ المسافة الأصغر d = min(d1, d2).
ثم نفحص شريطاً عمودياً عرضه 2d حول خط التقسيم للبحث عن نقاط قد تكون أقرب.
To solve efficiently, divide points into two subsets (left and right) by a vertical line x=c.
Recursively find the closest pairs in each subset (d1 and d2).
Let d = min(d1, d2).
Then, inspect a vertical strip of width 2d around the dividing line for potentially closer points.
السر في كفاءة الخوارزمية هو أنه داخل الشريط العمودي، لكل نقطة في الجهة اليسرى، نحتاج فقط لفحص 6 نقاط كحد أقصى في الجهة اليمنى.
هذا يجعل خطوة الدمج O(n)، وتصبح معادلة التكرار T(n) = 2T(n/2) + O(n)، مما يعطي تعقيداً نهائياً O(n log n).
The key to efficiency is that within the vertical strip, for each point on the left, we only need to inspect a maximum of 6 points on the right.
This makes the combine step O(n), leading to the recurrence T(n) = 2T(n/2) + O(n), which resolves to O(n log n).
لماذا نحتاج لفحص 6 نقاط كحد أقصى فقط في الشريط العمودي؟ Why do we only need to check a maximum of 6 points in the vertical strip?
لأن أي نقاط في نفس الجهة يجب أن تكون المسافة بينها على الأقل d، هندسياً لا يمكن وضع أكثر من 6 نقاط في مستطيل أبعاده d x 2d دون أن تقل المسافة بين نقطتين عن d.
Because points on the same side must be at least distance 'd' apart. Geometrically, you cannot fit more than 6 points in a d x 2d rectangle without two points being closer than 'd'.