المصفوفات matrices هي إحدى مفاهيم الجبر الخطي، ولها تطبيقات في الكثير من المجالات، وسوف نستعرض في هذه المقالة خوَارزميتان من خوارزميات المصفوفات.
طباعة المصفوفات
سنبدأ بخوارزمية بسيطة لطباعة المصفوفات. تأخذ الخوارزمية مصفوفة ثنائية الأبعاد وتطبع عناصرها الواحد تلو الآخر وفق ترتيب خاص، وإليك مثال على ذلك:
Input: الدخل 14 15 16 17 18 21 19 10 20 11 54 36 64 55 44 23 80 39 91 92 93 94 95 42 Output: الخرج print value in index // اطبع القيم 14 15 16 17 18 21 36 39 42 95 94 93 92 91 64 19 10 20 11 54 80 23 44 55 or print index // أو اطبع الفهارس 00 01 02 03 04 05 15 25 35 34 33 32 31 30 20 10 11 12 13 14 24 23 22 21
هذه شيفرة عامة للخوارزمية:
function noOfLooping(m,n) { if(m > n) { smallestValue = n; } else { smallestValue = m; } if(smallestValue % 2 == 0) { return smallestValue/2; } else { return (smallestValue+1)/2; } } function squarePrint(m,n) { var looping = noOfLooping(m,n); for(var i = 0; i < looping; i++) { for(var j = i; j < m - 1 - i; j++) { console.log(i+''+j); } for(var k = i; k < n - 1 - i; k++) { console.log(k+''+j); } for(var l = j; l > i; l--) { console.log(k+''+l); } for(var x = k; x > i; x--) { console.log(x+''+l); } } } squarePrint(6,4);
ضرب المصفوفات
ضرب المصفوفات هي إحدى العمليات الأساسية على المصفوفات، ولها تطبيقات عديدة، مثل حلّ نِظمات المعادلات التفاضلية الخطية وغيرها، سوف نستعرض في هذه الفقرة أحد تطبيقات ضرب المصفوفات، وهو حساب أعداد فيبوناتشي.
نعلم أنّ العثور على العنصر رقم n في متتالية فيبوناتشي سهل للغاية عندما يكون n صغيرًا نسبيًا، إذ يكفي أن نستخدم منظورًا عوديًا بسيطًا، حيث أنّ f(n)=f(n-1)+f(n-2)، أو يمكننا استخدام منظور البرمجة الديناميكية لتجنب تكرار الحسابات. لكنّ هذه الطرق لا تنفع لحل المشاكل المعقّدة، فماذا ستفعل مثلًا إن طُلِب منك حلّ هذه المشكلة:
اقتباسليكن 0 < n < 10^9، احسب قيمة f(n) mod 999983
حيث تمثّل mod عملية حساب الباقي.
لن تنجح البرمجة الديناميكية هنا، لذا علينا أن نبحث عن حل أفضل لهذه المشكلة، وإحدى الحلول الممكنة لهذه المشكلة هي استخدام ضرب المصفوفات لتمثيل العلاقة العَودية.
قبل أن نواصل، يُستحبّ أن تكون لك معرفة أولية بالمفاهيم الرياضية الآتية.
- لتكن A و B مصفوفتين، يجب أن تكون قادرًا على حساب ضرب هاتين المصفوفتين، أي BxA.
- لتكن A و B مصفوفتين، يجب أن تكون قادرًا على إيجاد المصفوفة T التي تحقق B = TxA.
-
لتكن A مصفوفة أبعادها d X d، يجب أن تكون قادرًا على إيجاد قوّتها إلى n (في مدّة
O(d3log(n))).
سنحتاج في البداية إلى إنشاء مصفوفة M تمثّل العلاقة العَودية، بحيث يمكننا انطلاقًا منها حساب الحالة / القيمة المطلوبة انطلاقًا من الحالات / القيم المعروفة سلفًا من المتتالية.
لنفترض أنّنا نعرف قيمة k حالة سابقة من المتتالية العودية، نريد أن نحسب قيمة الحالة رقم (k +1) من المتتالية انطلاقًا من الحالات المعروفة. لتكن M مصفوفة حجمها k X k، سنبني مصفوفة A حجمها k X 1 تحتوى الحالات المعروفة لعلاقة العوديّة، وسننشئ أيضًا مصفوفة B حجمها k X 1 تحتوي قيم الحالات الموالية، أي تحقق MXA = B:
| f(n) | | f(n+1) | | f(n-1) | | f(n) | M X | f(n-2) | = | f(n-1) | | ...... | | ...... | | f(n-k) | | f(n-k+1) |
إن استطعنا تصميم المصفوفة M وفقًا لهذه الخاصيات، فسنكون قادرين على حل المشكلة بيُسر. سنجرّب هذه الطريقة على عدةّ أنواع من علاقات العوديّة.
النوع 1
لنبدأ بالحالة الأبسط: f(n) = f(n-1) + f(n-2)، سنحصل على: f(n+1) = f(n) + f(n-1).
لنفترض أنّنا نعرف قيمتي f(n) و f(n-1)، ونريد أن نحسب قيمة f(n+1) انطلاقًا من القيمتين السابقتين. نبدأ بإنشاء المصفوفتين A و B كما وضّحنا سابقًا:
Matrix A Matrix B | f(n) | | f(n+1) | | f(n-1) | | f(n) |
لاحظ أن المصفوفة A تُصمّم بحيث تحتوي كل الحالات التي تعتمد عليها f(n+1)، وعلينا الآن تصميم مصفوفة M حجمها 2X2 تحقّق MxA = B.
العنصر الأول من B هو f(n+1)، ويساوي f(n) + f(n-1) بحسب علاقة العوديّة. نحن نعلم أنّ العنصر الأول من B يساوي الصف الأول من M مضروبًا في A حسبَ قواعد ضرب المصفوفات، أي أنّ f(n)*a + f(n-1)*b = f(n+1)، حيث [a b] يمثّل الصف الأول من المصفوفة M، من جهة أخرى نعلم من علاقة التعود أنّ f(n+1)=f(n)+f(n-1)، لهذا نستنتج أنّ الصفّ الأول من M سيكون [1 1].
| 1 1 | X | f(n) | = | f(n+1) | | ----- | | f(n-1) | | ------ |
ملاحظة: يشير الرمز ----- إلى عدم اهتمامنا بهذه القيمة حاليًا.
يساوي العنصر الثاني من B القيمة f(n)، والتي يمكن الحصول عليها عن طريق العملية f(n) x 1، ومن ثم فإنّ الصف الثاني من M هو [1 0].
| ----- | X | f(n) | = | ------ | | 1 0 | | f(n-1) | | f(n) |
لقد حصلنا الآن على المصفوفة M المطلوبة.
| 1 1 | X | f(n) | = | f(n+1) | | 1 0 | | f(n-1) | | f(n) |
النوع 2
سنحاول الآن حساب: f(n) = a X f(n-1) + b X f(n-2)، حيث a و b ثابتتان.
تكافئ الصيغة أعلاه المعادلة: f(n+1) = a X f(n) + b X f(n-1).
قد تعلم الآن أنّه ينبغي أن تتساوي أبعاد المصفوفات مع عدد التبعيات، والتي تساوي 2 في هذا المثال، لذا سنبني المصفوفتين A و B، وكلاهما من الحجم 2x1:
Matrix A Matrix B | f(n) | | f(n+1) | | f(n-1) | | f(n) |
نحتاج أن تكون [a, b] في الصفّ الأول من المصفوفة M بالنسبة لـ f(n+1) = a X f(n) + b X f(n-1)، وبالنسبة للعنصر الثاني فيB، أي f(n)، فهو موجود في المصفوفة A، لذلك سنأخذه، ولهذا نضع [1 0] في الصف الثاني من M لنحصل على:
| a b | X | f(n) | = | f(n+1) | | 1 0 | | f(n-1) | | f(n) |
النوع 3
نأخذ الآن الحالة التالية: احسب قيمة f(n) = a x f (n-1) + c x f (n-3).
لقد كانت الحالات -القيم السابقة التي تُحسب العودية انطلاقًا منها- في المثالين السابقين متجاورات، أمّا هنا فهي غير متجاورة، فالحالة f (n-2) مفقودة، فكيف نتعامل مع هذا؟
يمكننا تحويل علاقة العودية إلى العلاقة التالية:
f(n) = a X f(n-1) + 0 X f (n-2) + c X f (n-3) // أو f(n + 1) = a X f(n) + 0 X f (n-1) + c X f (n-2)
شبه هذه الصيغةُ صيغةَ النوع 2.
هذه هي المصفوفة M، والتي ستكون من الحجم 3x3. لقد حسبنا المصفوفة M بطريقة مشابهة للطريقة التي استخدمناها في النوع 2، ويمكنك تجربتها بالورقة والقلم إن وجدت صعوبة في فهمها.
| a 0 c | | f(n) | | f(n+1) | | 1 0 0 | X | f(n-1) | = | f(n) | | 0 1 0 | | f(n-2) | | f(n-1) |
النوع 4
نأخذ الآن مثالًا أكثر تعقيدًا: f(n) = f(n-1) + f(n-2) + c، حيث تكون c ثابتًا ما. يختلف هذا المثال عن سابقيه، فقد كنا نحوّل في السابق كل حالة في A إلى الحالة التالية في B عبر عملية الضرب.
f(n) = f(n-1) + f(n-2) + c f(n+1) = f(n) + f(n-1) + c f(n+2) = f(n+1) + f(n) + c ................................
أما هنا فلا تصلح الطريقة التي اعتمدنَاها سابقًا، وعلينا أن نبحث في طريقة أخرى. ماذا لو جرّبنا إضَافة c كحالة على النحو التالي:
| f(n) | | f(n+1) | M X | f(n-1) | = | f(n) | | c | | c |
يمكننا الآن إنشاء M بسهولة:
| 1 1 1 | | f(n) | | f(n+1) | | 1 0 0 | X | f(n-1) | = | f(n) | | 0 0 1 | | c | | c |
النوع 5
لنأخذ الآن مثالًا آخر:
f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e
هذا تمرين لك، حاول أولاً تحديد حالات العوديّة، وأنشئ المصفوفتين A و B، ثمّ احسب المصفوفة M:
هذه قيمة M:
| a 0 c d 1 | | 1 0 0 0 0 | | 0 1 0 0 0 | | 0 0 1 0 0 | | 0 0 0 0 1 |
النوع 6
هناك أشكال كثيرة من العودية، منها الشكل التالي:
f(n) = f(n-1) -> if n is odd // في الحالات الفردية f(n) = f(n-2) -> if n is even // في الحالات الزوجية
أو باختصار:
f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)
يمكننا تقسيم الدوال على أساس الفردية أو الزوجية، وإنشاء مصفوفتين تمثّل إحداهما الفردية، وتمثّل الأخرى الزوجية، ثمّ نحُسب كل واحدة منهما على حدة.
النوع 7
قد تحتاج أحيانًا إلى الحفاظ على أكثر من علاقة عودية واحدة كما في المثال التالي:
g(n) = 2g(n-1) + 2g(n-2) + f(n)
لاحظ أنّ قيمة g (n) تعتمد على f(n).
يمكننا استخدام ضرب المصفوفات كما في الأمثلة السابقة ولكن بأبعاد أكبر. ننشئ أولا المصفوفتين A و B.
Matrix A Matrix B | g(n) | | g(n+1) | | g(n-1) | | g(n) | | f(n+1) | | f(n+2) | | f(n) | | f(n+1) |
لدينا: g(n+1) = 2g(n-1) + f(n+1) و f(n+2) = 2f(n+1) + 2f(n). لننشئ المصفوفة M بالطريقة نفسها التي استخدمناها آنفًا:
| 2 2 1 0 | | 1 0 0 0 | | 0 0 2 2 | | 0 0 1 0 |
ترجمة -بتصرّف- للفصلين 51 و 52 من الكتاب Algorithms Notes for Professionals.
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.