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

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

في الرياضيات وعلوم الكمبيوتر ، ^[1] الجبر الحاسوبي ، ويسمى أيضًا الحساب الرمزي أو الحساب الجبري ، هو مجال علمي يشير إلى دراسة وتطوير الخوارزميات والبرمجيات لمعالجة التعبيرات الرياضية وغيرها من الأشياء الرياضية . على الرغم من أن الجبر الحاسوبي يمكن اعتباره مجالًا فرعيًا من الحوسبة العلمية ، إلا أنهما يُعتبران عمومًا مجالات مميزة لأن الحوسبة العلمية تعتمد عادةً على الحساب العددي بأرقام تقريبية ذات فاصلة عائمة ، بينما يؤكد الحساب الرمزي على الحساب الدقيق باستخدام تعبيرات تحتوي على متغيرات ليس لها قيمة معينة ويتم معالجتها كرموز.

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

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

يميز بعض المؤلفين بين الجبر الحاسوبي والحوسبة الرمزية باستخدام الاسم الأخير للإشارة إلى أنواع من الحساب الرمزي بخلاف الحساب باستخدام الصيغ الرياضية . يستخدم بعض المؤلفين الحساب الرمزي للجانب المتعلق بعلوم الكمبيوتر من الموضوع و"الجبر الحاسوبي" للجانب الرياضي. ^[2] في بعض اللغات، لا يُعد اسم المجال ترجمة مباشرة لاسمه الإنجليزي. عادةً ما يُطلق عليه اسم calcul formel بالفرنسية، والذي يعني "الحوسبة الرسمية". يعكس هذا الاسم الروابط التي تربط هذا المجال بالطرق الرسمية .

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

لا توجد جمعية علمية متخصصة في الجبر الحاسوبي، ولكن هذه الوظيفة تتولى تنفيذها مجموعة ذات اهتمام خاص من جمعية الآلات الحاسوبية تسمى SIGSAM (مجموعة ذات اهتمام خاص بالتلاعب الرمزي والجبري). ^[3]

هناك العديد من المؤتمرات السنوية حول الجبر الحاسوبي، وأهمها ISSAC (ندوة دولية حول الحوسبة الرمزية والجبرية)، والتي ترعاها SIGSAM بانتظام. ^[4]

هناك العديد من المجلات المتخصصة في الجبر الحاسوبي، وأهمها مجلة الحوسبة الرمزية التي أسسها برونو بوخبرجر عام 1985. ^[5] وهناك أيضًا العديد من المجلات الأخرى التي تنشر بانتظام مقالات في الجبر الحاسوبي. [ ^6]

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

الأنظمة العددية المعتادة المستخدمة في الحساب العددي هي أرقام الفاصلة العائمة والأعداد الصحيحة ذات الحجم المحدود الثابت. ولا يعد أي من هذه الأنظمة مناسبًا للجبر الحاسوبي، بسبب تضخم التعبيرات. ^[9]

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

إن برمجة تنفيذ فعال للعمليات الحسابية مهمة صعبة. لذلك، تستخدم معظم أنظمة الجبر الحاسوبية المجانية وبعض الأنظمة التجارية مثل Mathematica و Maple ، ^{[10] [11]} مكتبة GMP ، والتي تعد بالتالي معيارًا فعليًا .

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

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

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

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

إن التطبيق الخام للقواعد الأساسية للتفاضل فيما يتعلق بـ x على التعبير يعطي النتيجة ${\displaystyle 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 (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$

يُنظر إليه على أنه متعدد الحدود في و${\displaystyle \sin(x+y)}$${\displaystyle \log(z^{2}-5)}$

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

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

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

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

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

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

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

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

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

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

• مُثبت النظريات الآلي
• الإثبات بمساعدة الحاسوب
• الهندسة الجبرية الحسابية
• نظام الجبر الحاسوبي
• محلل تفاضلي
• مدقق الإثبات
• فاحص النموذج
• الحساب الرمزي العددي
• محاكاة رمزية
• الذكاء الاصطناعي الرمزي

للحصول على تعريف مفصل للموضوع:

• بوخبرغر، برونو (1985). "الحوسبة الرمزية (افتتاحية)" (PDF) . مجلة الحوسبة الرمزية . 1 (1): 1-6. doi :10.1016/S0747-7171(85)80025-0.

بالنسبة للكتب المدرسية المخصصة للموضوع:

• دافنبورت، جيمس هـ .؛ سيريت، إيفون؛ تورنييه، إيفلين (1988). الجبر الحاسوبي: الأنظمة والخوارزميات للحساب الجبري . ترجمه من الفرنسية أ. دافنبورت وجيه إتش دافنبورت. أكاديميك بريس. رقم ISBN 978-0-12-204230-0.
• فون تسور جاثين، يواكيم؛ غيرهارد، يورغن (2003). جبر الكمبيوتر الحديث (الطبعة الثانية). مطبعة جامعة كامبريدج. رقم ISBN 0-521-82646-2.
• جيديس، كيه أو؛ كزابور، إس آر؛ لابان، جي. (1992). خوارزميات الجبر الحاسوبي . رمز الكتاب : 1992afca.book.....G. doi : 10.1007/b102438. رقم ISBN 978-0-7923-9259-0.
• بوخبرجر، برونو؛ كولينز، جورج إدوين؛ لوس، روديجر؛ ألبريشت، رودولف، محررون (1983). الجبر الحاسوبي: الحساب الرمزي والجبرية . ملحق الحوسبة. المجلد 4. doi :10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6. S2CID  5221892.