السلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Divide and Conquer
الخوارزميات وبنى المعطيات –  خوارزمية فرق تسد

نتابع في هذه الحلقة حديثنا عن احد الخوارزميات الشائعة الا وهي ” خوارزمية فرق تسد” Divide and Conquer

ضمن منهج خوارزمية “فرق تسد” divide and conquer, يتم تقسم المسألة المطلوب معالجتها الى عدة مسائل جزئية, ومن ثم يتم حل كل مسألة من هذه المسائل الجزئية بشكل مستقل.
عندما نستمر بتقسيم المسائل الجزئية الى مسائل اصغر, تدريجيا سوف نصل الى مرحلة حيث لا يعود بإمكاننا تقسيم المسألة الى مسائل اصغر من ذلك.
عندها يتم حل هذه المسائل الأصغر – تدعى عادة بمصطلح atomic – ومن ثم يتم تجميع الحلول الخاصة بكل المسائل الجزئية من أجل الحصول على حل المسألة الأصلية.

بشكل عام, يمكن توضيح منهجية خوارزمية فرق تسد divide and conquer من خلال ثلاث خطوات:

1. فرق – التجزئة Divide/Break
2. السيطرة – الحل Conquer/Solve
3. الدمج – التجميع Merge/Combine

سنشرح كل خطوة من هذه الخطوات على حدا:

فرق – التجزئة Divide/Break

تتضمن هذه الخطوة عملية تقسيم المسألة الى مسائل جزئية.
حيث ان المسائل الجزئية يجب ان تمثل جزء من المسألة الاصلية.
غالبا تتخذ هذه الخطوة منحى عودي recursive approach من اجل تنفيذها وتقسيم المسألة وصولا الى اصغر مسألة جزئية  ممكنة.
في هذه المرحلة, تتحول المسائل الجزئية الى مايدعى ب atomic – مسائل صغرى من المسألة الاساسية لا يمكن الحصول على اصغر منها – ولكنها لاتزال تمثل جزء من المسألة الاساسية المطلوب حلها.

السيطرة – الحل Conquer/Solve

في هذه المرحلة يكون لدينا عدد من المسائل الصغرى من المسألة الاصلية والتي من المطلوب حلها.

عادة, وضمن هذا المستوى, يتم اعتبار المسائل “محلولة” solved نفسها بنفسها – لانها وصلت لمرحلة من الصغر والبساطة بحيث اصبح الحل ظاهريا.

الدمج – التجميع Merge/Combine

عندما يتم حل المسائل الجزئية, تقوم هذه المرحلة بشكل عودي recursively  بتجميع الحلول الجزئية وصولا لتشكيل الحل الكلي للمسألة.

يعمل منهنج هذه الخوارزمية بشكل عودي recursively.
ملاحظة:

العودية recursion: وهي طريقة ومنهج لحل المسائل وتتضمن تقسيم المسألة الى مسائل جزئية اصغر الى حين الوصول الى اصغر حجم ممكن للمسألة والتي يمكن حلها بسهولة, عادة – برمجيا – تتمثل العودية recursion عبر تابع – دالة- تقوم باستدعاء نفسها بشكل متكرر وصولا الى شرط التوقف الذي يحدد اصغر حجم ممكن للمسألة قيد الحل.

 

أمثلة:

فيما يلي عدد من خوارزميات  الكمبيوتر المبنية على اساس منهجية فرق تسد Divide and Conquer

• الفرز – الدمج Merge sort
• الفرز السريع Quick Sort
• البحث الثنائي Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)

هنالك عدد كبير من الخوارزميات التي تستخدم هذا المنهج, ولكن الامثلة المطروحة كافية وجيدة لتوضيح هذه الاستراتيجية

نلقاكم ان شاء الله بحلقة قادمة نتحدث فيها عن البرمجة الديناميكية Dynamic programming لننهي بها حديثنا عن الخوارزميات وننتقل بعدها للحديث عن بنى المعطيات

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة	المصطلح
بنى المعطيات, او هياكل المعطيات	Data Structure
الخوارزميات	Algorithm
الواجهة	Interface
التنفيذ	Implementation
العمليات	Operations
التعقيد الزمني	Time Complexity
زمن التنفيذ	Running time/execution time
البحث عن المعطيات	Data search
سرعة المعالجة	Processor speed
الطلبات المتعددة	Multiple Request
التعقيد الزمني	Time complexity
التعقيد المكاني	Space complexity
التحليل المقار	Asymptotic Analysis
أفضل حالة	Best case
الحالة الوسيطية	Average case
اسوء حالة	Worst case

 

References

https://www.tutorialspoint.com/data_structures_algorithms/index.htm