الجبر الحاسوبي

نظرًا لكفاءة البرامج العددية العالية في الحسابات العددية التقريبية ، فمن الشائع في الجبر الحاسوبي التركيز على الحسابات الدقيقة باستخدام بيانات ممثلة بدقة. هذا التمثيل الدقيق يعني أنه حتى عندما يكون حجم المخرجات صغيرًا، قد تنمو البيانات الوسيطة الناتجة أثناء الحساب بطريقة غير متوقعة. يُعرف هذا السلوك باسم " تضخم التعبير" . ^{[ 7 ]} وللتخفيف من هذه المشكلة، تُستخدم طرق متنوعة في تمثيل البيانات، وكذلك في الخوارزميات التي تعالجها. ^{[ 8 ]}

تعابير الوجه

باستثناء الأرقام والمتغيرات ، يمكن اعتبار كل تعبير رياضي رمزًا لمؤثر متبوعًا بسلسلة من المعاملات. في برامج الجبر الحاسوبي، تُمثَّل التعبيرات عادةً بهذه الطريقة. يتميز هذا التمثيل بمرونة عالية، حيث يمكن تمثيل ومعالجة العديد من الأشياء التي لا تبدو تعبيرات رياضية للوهلة الأولى على هذا النحو. على سبيل المثال، يمكن اعتبار المعادلة تعبيرًا يبدأ بـ "="، ويمكن تمثيل المصفوفة تعبيرًا يبدأ بـ "matrix" وصفوفها هي المعاملات.

حتى البرامج يمكن اعتبارها وتمثيلها كتعبيرات تتضمن عامل "إجراء" ومعاملين على الأقل: قائمة المعاملات وجسم التعبير، وهو تعبير بحد ذاته يتضمن "جسم" كعامل وسلسلة من التعليمات كمعاملات. وبالمقابل، يمكن اعتبار أي تعبير رياضي برنامجًا. على سبيل المثال، يمكن اعتبار التعبير a + b برنامجًا لعملية الجمع، حيث a و b هما المعاملان. يتضمن تنفيذ هذا البرنامج تقييم التعبير لقيم معينة لـ a و b ؛ إذا لم تُعطَ أي قيم، فإن نتيجة التقييم هي ببساطة المدخلات.

تُعدّ عملية التقييم المؤجل هذه أساسية في الجبر الحاسوبي. فعلى سبيل المثال، يُشير المعامل "=" في المعادلة، في معظم أنظمة الجبر الحاسوبي، إلى اسم برنامج اختبار المساواة: عادةً، ينتج عن تقييم المعادلة معادلة أخرى، ولكن عند الحاجة إلى اختبار المساواة، سواءً طلبه المستخدم صراحةً عبر أمر "التقييم إلى قيمة منطقية"، أو بدأه النظام تلقائيًا في حالة الاختبار داخل البرنامج، يتم تنفيذ التقييم إلى نتيجة منطقية.

نظرًا لأن حجم معاملات التعبير غير قابل للتنبؤ وقد يتغير أثناء جلسة العمل، فإن تسلسل المعاملات عادة ما يتم تمثيله كسلسلة من المؤشرات (كما هو الحال في Macsyma ) ^{[ 13 ]} أو إدخالات في جدول تجزئة (كما هو الحال في Maple ).

إن التطبيق المباشر لقواعد التفاضل الأساسية بالنسبة إلى x على التعبير a ^x يعطي النتيجة

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

يُفضّل عمومًا استخدام تعبير أبسط من هذا، ويُصبح التبسيط ضروريًا عند التعامل مع التعبيرات العامة. ويتم هذا التبسيط عادةً من خلال قواعد إعادة الكتابة . ^{[ 14 ]} توجد عدة فئات من قواعد إعادة الكتابة التي يجب أخذها في الاعتبار. أبسطها هي القواعد التي تُقلّل دائمًا من حجم التعبير، مثل E − E → 0 أو sin(0) → 0. وتُطبّق هذه القواعد بشكل منهجي في أنظمة الجبر الحاسوبي.

تظهر صعوبة في العمليات التجميعية كالجمع والضرب. الطريقة المعتادة للتعامل مع التجميعية هي اعتبار أن الجمع والضرب لهما عدد غير محدد من المعاملات؛ أي أن a + b + c يُكتب على الصورة "+"( a , b , c ) . وبالتالي، يُبسط كل من a + ( b + c ) و ( a + b ) + c إلى "+"( a , b , c ) ، والذي يُعرض على الصورة a + b + c . أما في حالة تعابير مثل a − b + c ، فإن أبسط طريقة هي إعادة كتابة −E و E − F و E / F بشكل منهجي على النحو التالي: ( −1 ) ⋅E و E + ( −1 ) ⋅F و E ⋅F − ¹ على التوالي ^. بمعنى آخر، في التمثيل الداخلي للتعبيرات، لا يوجد طرح ولا قسمة ولا طرح أحادي، خارج تمثيل الأرقام.

تكمن صعوبة أخرى في خاصية التبديل بين عمليتي الجمع والضرب. تكمن المشكلة في سرعة التعرف على الحدود المتشابهة لدمجها أو حذفها. يُعد اختبار كل زوج من الحدود مكلفًا، خاصةً مع المجاميع والمنتجات الطويلة جدًا. ولحل هذه المشكلة، يقوم برنامج Macsyma بترتيب معاملات المجاميع والمنتجات بحيث توضع الحدود المتشابهة في أماكن متتالية، مما يُسهّل اكتشافها. في برنامج Maple ، صُممت دالة تجزئة لتوليد التصادمات عند إدخال الحدود المتشابهة، مما يسمح بدمجها فور ظهورها. يتيح ذلك التعرف الفوري على التعبيرات الفرعية التي تظهر عدة مرات في عملية حسابية وتخزينها مرة واحدة فقط. يوفر هذا ذاكرة ويُسرّع الحساب بتجنب تكرار العمليات نفسها على التعبيرات المتطابقة.

تؤدي بعض قواعد إعادة الصياغة أحيانًا إلى زيادة حجم التعبيرات التي تُطبق عليها، وأحيانًا أخرى إلى تقليله. وينطبق هذا على قانون التوزيع أو المتطابقات المثلثية . فعلى سبيل المثال، يسمح قانون التوزيع بإعادة الصياغة.${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$و${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$نظرًا لعدم وجود طريقة عامة جيدة لاتخاذ قرار بشأن تطبيق قاعدة إعادة الكتابة هذه أو عدم تطبيقها، فإن إعادة الكتابة لا تتم إلا عند استدعائها صراحةً من قِبل المستخدم. بالنسبة لقانون التوزيع، تُسمى دالة الحاسوب التي تُطبق قاعدة إعادة الكتابة هذه عادةً "توسيع". أما قاعدة إعادة الكتابة العكسية، والتي تُسمى "تحليل"، فتتطلب خوارزمية معقدة، ولذلك فهي دالة أساسية في أنظمة الجبر الحاسوبي (انظر تحليل كثيرات الحدود ).

هناك مفهومان للمساواة في التعبيرات الرياضية . المساواة التركيبية هي تطابق تمثيلها في الحاسوب، ويسهل اختبارها في برنامج حاسوبي. أما المساواة الدلالية فهي عندما يُمثل تعبيران نفس الكائن الرياضي، كما في

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

من المعروف من نظرية ريتشاردسون أنه قد لا توجد خوارزمية تحدد ما إذا كان تعبيران يمثلان أعدادًا متساويين دلاليًا إذا سُمح باستخدام الدوال الأسية واللوغاريتمية في التعبيرين. وبناءً على ذلك، لا يمكن اختبار المساواة (الدلالية) إلا على فئات معينة من التعبيرات مثل كثيرات الحدود والكسور النسبية .

لاختبار تساوي تعبيرين، بدلاً من تصميم خوارزميات محددة، من المعتاد وضع التعبيرات في شكل معياري أو وضع الفرق بينهما في شكل طبيعي ، واختبار المساواة النحوية للنتيجة.

في الجبر الحاسوبي، لا يُعدّ مصطلحا "الصيغة القانونية" و"الصيغة العادية" مترادفين. ^{[ 15 ]} الصيغة القانونية هي صيغة يكون فيها تعبيران متطابقين دلاليًا إذا وفقط إذا كانا متطابقين نحويًا، بينما الصيغة العادية هي صيغة يكون فيها التعبير صفرًا دلاليًا فقط إذا كان صفرًا نحويًا. بعبارة أخرى، للصفر تمثيل فريد كتعبير في الصيغة العادية.

تُفضّل الأشكال المعيارية عادةً في الجبر الحاسوبي لعدة أسباب. أولًا، قد تكون الأشكال القانونية أكثر تكلفةً حسابيًا من الأشكال المعيارية. على سبيل المثال، لوضع متعددة حدود في شكل قانوني، يجب توسيع كل ناتج باستخدام قانون التوزيع ، بينما لا يكون ذلك ضروريًا مع الشكل المعياري (انظر أدناه). ثانيًا، قد يكون الأمر، كما هو الحال مع التعبيرات التي تتضمن جذورًا، أن الشكل القانوني، إن وُجد، يعتمد على بعض الخيارات العشوائية، وقد تختلف هذه الخيارات بين تعبيرين تم حسابهما بشكل مستقل. هذا قد يجعل استخدام الشكل القانوني غير عملي.

اعتمدت أنظمة الجبر الحاسوبية المبكرة، مثل جهاز ENIAC في جامعة بنسلفانيا ، على المبرمجين لإعادة برمجته بين العمليات الحسابية، والتحكم في وحداته المادية المتعددة (أو لوحاته)، وتزويد قارئ بطاقات IBM الخاص به بالبيانات. ^{[ 16 ]} تولت الرياضياتيات الجزء الأكبر من برمجة ENIAC، حيث قادت كل من جين جينينغز ، ومارلين ويسكوف ، وروث ليخترمان ، وبيتي سنايدر ، وفرانسيس بيلاس ، وكاي ماكنولتي هذه الجهود. ^{[ 17 ]}

في عام 1960، استكشف جون مكارثي توسيعًا للدوال التكرارية الأولية لحساب التعبيرات الرمزية من خلال لغة برمجة ليسب أثناء عمله في معهد ماساتشوستس للتكنولوجيا . ^{[ 18 ]} على الرغم من أن سلسلته حول "الدوال التكرارية للتعبيرات الرمزية وحسابها بواسطة الآلة" ظلت غير مكتملة، ^{[ 19 ]} فقد ساهم مكارثي ومساهماته في برمجة الذكاء الاصطناعي والجبر الحاسوبي عبر ليسب في تأسيس مشروع ماك في معهد ماساتشوستس للتكنولوجيا والمنظمة التي أصبحت فيما بعد مختبر ستانفورد للذكاء الاصطناعي (SAIL) في جامعة ستانفورد ، والتي سهّلت منافستها تطورًا كبيرًا في الجبر الحاسوبي طوال أواخر القرن العشرين.

واجهت الجهود المبكرة في مجال الحوسبة الرمزية، في الستينيات والسبعينيات من القرن العشرين، تحديات تتعلق بعدم كفاءة الخوارزميات المعروفة منذ زمن طويل عند نقلها إلى أنظمة الجبر الحاسوبي. ^{[ 20 ]} سعت المشاريع السابقة لمشروع MAC، مثل ALTRAN ، إلى التغلب على القيود الخوارزمية من خلال تطوير الأجهزة والمترجمات، بينما اتجهت الجهود اللاحقة نحو تحسين البرمجيات. ^{[ 21 ]}

انصبّ جزء كبير من عمل الباحثين في هذا المجال على إعادة النظر في الجبر الكلاسيكي لتعزيز فعاليته ، مع تطوير خوارزميات فعّالة لاستخدامها في الجبر الحاسوبي. ومن أمثلة هذا النوع من العمل حساب القواسم المشتركة الكبرى لكثيرات الحدود ، وهي مهمة ضرورية لتبسيط الكسور ومكوّن أساسي في الجبر الحاسوبي. وقد أثبتت الخوارزميات الكلاسيكية لهذا الحساب، مثل خوارزمية إقليدس ، عدم كفاءتها على الحقول اللانهائية؛ وواجهت خوارزميات الجبر الخطي صعوبات مماثلة. ^{[ 22 ]} ولذلك، اتجه الباحثون إلى اكتشاف طرق لاختزال كثيرات الحدود (مثل تلك الموجودة على حلقة من الأعداد الصحيحة أو مجال تحليل فريد ) إلى صيغة قابلة للحساب بكفاءة باستخدام خوارزمية إقليدس.