سلسلة تعلم الخوارزميات: ما هي خوارزميات البرمجة الديناميكية؟
ما هي الخورازميات العودية «Recursion Algorithms» ؟
سلسلة تعلم الخوارزميات: ما هي الخوارزميات العودية؟ نوصف الشيء بأنه ذو بنية عودية إذا كان مؤلفًا من مكونات بعضها معرف تعريف الشيء الأصلي أو الأساسي.
إن مفهوم العودية ذائع الصيت في المجال الرياضي إذ يستخدم في التعريفات الرياضية وحل كثير من المسائل فيها كمسائل المضاريب و”متسلسلة فيبوناتشي” ومسألة “برج هانوي” وغيرها من المشاكل ذات التعريف العودي.
دعنا نوضح الفكرة الرئيسية لاستخدام الخوارزميات العودية المسائل كالتالي: لحل مسألة ما، سنقوم بتحليل المسألة الرئيسية إلى مسائل فرعية لنفس المسألة الأصلية ومن ثم ّ استخدام حلول المسائل الفرعية للوصل إلى الحل النهائي للمسألة الرئيسية.
يستخدم مفهوم الخوارزميات العودية في حسابات المضاريب «factorials» في الرياضيات فلكي نتمكن من حساب مضروب عدد ما يجب معرفة مضروب العدد السابق وهكذا حتى نصل إلى العدد 1 .
فمثلًا إذا كان لدينا عدد نرمز له بالرمز n وأردنا حساب مضروبه- دعنا نرمز لمضروبه بالرمز!n -والذي يمثل في هذه الحالة المسألة الأصلية- سنحتاج إذن إلى حساب المسائل الفرعية المتفرعة من هذه المسألة الأصلية أي سنقوم بحساب «(n-1)!» و«(n-2)!» وهكذا. لنفترض أننا نريد حساب مضروب العدد 4 ففي هذه الحالة سيتعين علينا إجراء العملية الحسابية كالتالي:
4!= 4 x (4 -1)! =4 x 3! = 4 x 3 x (3-1)! = 4 x 3 x 2! =4 x 3 x 2 x (2-1)! = 4 x 3 x 2 x 1! = 4 x 3 x 2 x 1x (1-1)! =4 x 3 x 2 x 1 x 0!
كما نرى في مثالنا السابق قمنا بتقسيم المسألة الرئيسية إلى عدة مسائل فرعية فلحساب مضروب العدد 4 قمنا بحساب مضروب العدد 3 ثم مضروب العد 2 وهكذا حتى وصلنا للرقم 0 والذي مضروبه يساوي 1 (0! =1). إذن مضروب العدد 4 يساوي
4! = 4 x 3 x 2 x 1 x 1 =24
محتويات المقال :
يجب أن تحتوي جميع الخوارزميات العودية على ما يلي:
إنّ الأداة اللازمة والكافية للتعبير عن برنامج معيّن تعبيراً عودياًّ هي «الإجرائية-Procedure» أو «الدالة-Function» لأنها تسمح بإعطاء اسم معين لمجموعة تعليمات، وهذا ما يسمح باستدعاء هذه التعليمات استدعاءً عوديّاً. يمكن التمييز بين نوعين من الإجرائيات العوديّة:
– الإجرائيات ذات العوديّة المباشرة «direct recursion»: نقول عن إجرائية P إنها عوديّة مباشرة إذا كانت تحوي استدعاءً صريحاً لنفسها.
– الإجرائيات ذات العوديّة غير المباشرة «indirect recursion»: نقول عن إجرائية P إنها عوديّة غير مباشرة إذا كانت تستدعي إجرائية أخرى Q تستدع P بطريقة مباشرة أو غير مباشرة.
في عام 1202 توصل فيبوناتشي إلى اكتشاف أجمل السلاسل العددية على الإطلاق وذلك أثناء بحثه حول سرعة تكاثر الأرانب في الظروف المثالية وقد صاغ فرضياته على النحو التالي:
إذن كم زوجًا من الأرانب سيكون لدينا بعد عام؟ هذا السؤال الذي طرحه العالم فيبوناتشي وتمكن آنذاك من صياغة متسلسلته الشهيرة على النحو التالي
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,……
إذا دققت النظر إلى هذه المتسلسلة ستجد أن كل رقم هو ناتج عن جمع الرقمين السابقين له، فالرقم 89 هو ناتج جمع الرقمين 55 و 34 والرقم 55 هو ناتج جمع الرقمين السابقين له 34 و 21 وهكذا. إذاً لدينا حالتان بدائيتان (0 و 1) بينما من أجل أي عدد آخر لا يمكن حساب القيمة إلا بالاعتماد على القيم المسبقة، هذا يعني أنه لدينا تكرار حساب دالة فيبوناتشي ولكن في كل مرة لأعداد أصغر حتى نصل إلى أبسط قيم ممكنة أي 0 و 1.
بذلك يمكننا القول بأن متسلسلة فيبوناتشي معرفة تعريفًا عوديًا. الجدير بالذكر أن هذه المتسلسة تظهر بشكلٍ متكرر في الطبيعة لتبدو وكأنها مؤشر على بعض جوانب النمو. على سبيل المثال، يُمكنك إيجادها في حلقات الحلزونات الطبيعية، وفي النباتات، وفي أزهار عباد الشمس وفي شجرة عائلة النحل، وترتبط هذه السلسلة برقمٍ شهير يُعرف بالنسبة الذهبية «golden ratio» إذ أن النسبة بين أي رقمين متتالين -أي رقمين بعد الرقم 2 في المتسلسلة- تقترب من النسبة الذهبية كلما تقدمنا أكثر في المتسلسلة فالنسبة بين 5 و 3 تساوي 1.666 والنسبة بين 8 و 5 يساوي 1.6 وهكذا حتى نصل إلى العدد 40 والأعداد التالية ستجد بأن النسبة تساوي تقريبا النسبة الذهبية والتي تقدر قيمتها ب 1.618033988749895 .
توزع حلزونات البذور على نمط متسلسة فيبوناتشي في زهور عباد الشمس
نستفيد من الخوارزميات العودية عندما نتعامل مع مسائل معقدة حيث تقوم العودية بتقسيم هذه الحالة إلى حالات أبسط على التوالي حتى إن تصل إلى حالة بدائية. ومن ثم تعود خطوةً خطوةً وتعوض القيم الناتجة إلى أن تصل إلى الحالة الأصلية فنحصل على الناتج النهائي.
لكن الاستدعاءات العودية تسبب ضياعاً في الوقت وتستهلك ذاكرة إضافية لذا لا تستخدم في الواقع العملي في كل المسائل فذواكر الحواسيب التي تعمل على معالجة البيانات محددة الحجم وقد لا تكفي لكل وسائط الاستدعاء. يمكنك متابعة المقالات السابقة في سلسلة تعلم الخورزميات من هنا وهنا.
المصادر
لا تزال أفكار نيتشه الفلسفية يتردد صداها في المجتمع المعاصر، وتتحدى فهمنا للأخلاق ومكانتها في…
تخيل فريقًا من العلماء الرواد يعملون بلا كلل لكشف أسرار الدماغ البشري. إنهم في سعيهم…
في عالم وسائل التواصل الاجتماعي، تظهر الصيحات وتختفي، لكن بعضها يجعلك تتساءل: ما السبب وراء…
الصداع تجربة إنسانية عالمية، وعلى الرغم من انتشاره إلا أن الأسباب الكامنة وراءه لا تزال…
إن فهم كيف بدأت الحياة وتطورت على الأرض هو السؤال الذي أذهل البشر على مر…
يصادف في شهر أغسطس الذكرى السنوية الثالثة لانسحاب الولايات المتحدة من أفغانستان وعودة طالبان إلى…
View Comments