5- الخوارزميات وبنى المعطيات – خوارزمية فرق تسد Algorithms and Data Structure – Divide and Conquer Algorithm
السلام عليكم ورحمة الله وبركاته
Algorithms and Data Structure – Divide and Conquer
الخوارزميات وبنى المعطيات – خوارزمية فرق تسد
نتابع في هذه الحلقة حديثنا عن احد الخوارزميات الشائعة الا وهي ” خوارزمية فرق تسد” Divide and Conquer
ضمن منهج خوارزمية “فرق تسد” divide and conquer, يتم تقسم المسألة المطلوب معالجتها الى عدة مسائل جزئية, ومن ثم يتم حل كل مسألة من هذه المسائل الجزئية بشكل مستقل.
عندما نستمر بتقسيم المسائل الجزئية الى مسائل اصغر, تدريجيا سوف نصل الى مرحلة حيث لا يعود بإمكاننا تقسيم المسألة الى مسائل اصغر من ذلك.
عندها يتم حل هذه المسائل الأصغر – تدعى عادة بمصطلح atomic – ومن ثم يتم تجميع الحلول الخاصة بكل المسائل الجزئية من أجل الحصول على حل المسألة الأصلية.
بشكل عام, يمكن توضيح منهجية خوارزمية فرق تسد divide and conquer من خلال ثلاث خطوات:
- فرق – التجزئة Divide/Break
- السيطرة – الحل Conquer/Solve
- الدمج – التجميع 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 |