6- الخوارزميات وبنى المعطيات – البرمجة الديناميكية Algorithms and Data Structure – Dynamic Programming

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

Algorithms and Data Structure – Dynamic Programming
الخوارزميات وبنى المعطيات –  البرمجة الديناميكية

حديثنا في هذه الحلقة عن البرمجة الديناميكية dynamic programming

يعتبر منهنج البرمجة الديناميكية dynamic programming مقاربا لمنهج فرق تسد divide and conquer من حيث تقسيم المسألة قيد الحل الى مسائل جزئية.

ولكن على خلاف منهج فرق تسد divide and conquer, فإن لا يتم حل المسائل الجزئية بشكل مستقل. وانما يتم الاحتفاظ بحلول هذه المسائل الجزئية واستخدامه من اجل حل المسائل المشابهه او المترابطة.

 

يستخدم منهج البرمجة الديناميكية dynamic programming approach عندما يكون لدينا مسائل يمكن تقسيمها الى مسائل جزئية متشابهه, وبالتالي فإنه يمكن اعادة استخدام النتائج.
في الغالب, يتم استخدام هذا المنهج في مسائل الأمثلة optimization problems.
قبل البدء بحل مسألة جزئية من المسألة الاصلية, تقوم الخوارزمية الديناميكية بالبحث عن نتائج حلول سابقة لمسائل جزئية مماثلة.
يتم دمج حلول المسائل الجزئية من أجل الوصول الى أفضل حل.
بإمكاننا القول بأن:

• يجب أن تكون المشكلة قابلة للتقسيم إلى مسائل جزئية متداخلة.
• يمكن الوصول الى حل مثالي عبر استخدام الحلول المثالية للمسائل الجزئية الاصغر
• تستخدم الخوارزميات الديناميكية Dynamic algorithms خاصية التذكر memorization.

 

المقارنة Comparison

على نقيض الخوارزميات الجشعة greedy algorithms, حيث تكون الحلول الامثلية المحلية مرغوبة, فإن الخوارزميات الديناميكية تسعى نحو حل مثال للمسألة ككل.

على نقيض خوارزميات فرق تسد divide and conquer, حيث يتم تجميع الحلول الجزئية من اجل الوصول الى حل المسألة الكاملة, فإن منهج الخوارزميات الديناميكية يتسخدم خرج output المسائل الجزئية الصغيرة من اجل امثلة optimize  حلول المسائل الجزئية الأكبر.

تستخدم الخوارزميات الديناميكية خاصية التذكر memorization من اجل تذكر نتائج الحلول المسائل الجزئية لكي يتم استخدامها لاحقا في امثلة حلول المسائل الجزئية الاكبر.

امثلة:

فيما يلي قائمة بعدد من مسائل الكمبيوتر التي من الممكن حلها عن طريق منهج البرمجة الديناميكية

• سلسلة فيبوناشي Fibonacci number series
• مسألة حقيبة الظهر Knapsack problem
• All pair shortest path by Floyd-Warshall
• Shortest path by Dijkstra
• جدولة المشاريع Project scheduling

يمكن استخدام البرمجة الديناميكية بطريقتين
top-down and bottom-up
تعتبر عملية استخدام الحلول السابقة للمسائل الجزئية من اجل تحسين وتسهيل الحصول على حلول جيدة للمسائل الاكبر ارخص من عملية اعادة حساب الحل من الصفر, وذلك من حيث عدد دورات المعالج CPU.

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

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

مع تحيات:

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

 

الترجمة	المصطلح
بنى المعطيات, او هياكل المعطيات	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