خوارزمية جوسبر

في الرياضيات ، تُعرف خوارزمية جوسبر ، نسبةً إلى بيل جوسبر ، بأنها إجراء لإيجاد مجاميع الحدود فوق الهندسية التي هي نفسها حدود فوق هندسية. أي: لنفترض أن لدينا a (1)  +  ...  + a ( n ) = S ( n ) - S (0)، حيث S ( n ) حد فوق هندسي (أي أن S ( n + 1)/ S ( n ) دالة كسرية لـ n )؛ عندئذٍ يكون a ( n ) بالضرورة حدًا فوق هندسيًا، وبمعرفة صيغة a ( n )، تجد خوارزمية جوسبر أن S ( n ) = 0.     

الخطوة 1: أوجد متعددة حدود p بحيث يكون، عند كتابة b ( n ) = a ( n )/ p ( n )، أن النسبة b ( n )/ b ( n - 1) تأخذ الشكل q ( n )/ r ( n ) حيث q و r متعددتا حدود، ولا يوجد لـ q ( n ) عامل غير تافه يحقق r ( n + j ) لـ j = 0، 1، 2، ... . (هذا ممكن دائمًا، سواء كانت المتسلسلة قابلة للجمع في صيغة مغلقة أم لا).        

الخطوة الثانية: إيجاد دالة كثيرة الحدود ƒ بحيث يكون S ( n ) = q ( n  +  1)/ p ( n ) ƒ ( n ) a ( n ). إذا كانت المتسلسلة قابلة للجمع بصيغة مغلقة، فمن الواضح أن دالة كسرية ƒ بهذه الخاصية موجودة؛ في الواقع، يجب أن تكون دائمًا كثيرة حدود، ويمكن إيجاد حد أعلى لدرجتها. تحديد ƒ (أو إثبات عدم وجود دالة ƒ كهذه ) هو مسألة حل نظام من المعادلات الخطية. ^{[ 1 ]}

يمكن استخدام خوارزمية جوسبر لاكتشاف أزواج ويلف-زيلبرجر ، إن وُجدت. لنفترض أن F ( n  +  1, k ) − F ( n , k ) = G ( n , k + 1) − G ( n , k ) حيث F معلومة و G غير معلومة. ثم نُدخل a ( k ) := F ( n + 1, k ) − F ( n , k ) في خوارزمية جوسبر. (نتعامل مع هذا كدالة لـ k ومعاملاتها دوال لـ n وليست أعدادًا؛ كل شيء في الخوارزمية يعمل في هذا السياق). إذا نجحت الخوارزمية في إيجاد S ( k ) بحيث S ( k ) − S ( k - 1) = a ( k )، فقد انتهينا: هذه هي G المطلوبة . وإذا لم تنجح، فلا توجد G.                     

تجد خوارزمية جوسبر (حيثما أمكن) صيغة مغلقة فوق هندسية للمجموع غير المحدد للحدود فوق الهندسية. قد يحدث ألا توجد مثل هذه الصيغة المغلقة، ولكن يكون للمجموع على جميع قيم n ، أو لمجموعة معينة من قيم n ، صيغة مغلقة. يكون هذا السؤال ذا معنى فقط عندما تكون المعاملات نفسها دوالًا لمتغير آخر. لذا، لنفترض أن a ( n , k ) حد فوق هندسي في كل من n و k : أي أن a ( n , k )/ a ( n - 1, k ) و a ( n , k )/ a ( n , k - 1) دالتان كسريتان لـ n و k . عندئذٍ، يمكن استخدام خوارزمية زيلبرجر وخوارزمية بيتكوفشيك لإيجاد صيغ مغلقة للمجموع على k لـ a ( n , k ).        

اكتشف بيل جوسبر هذه الخوارزمية في السبعينيات أثناء عمله على نظام الجبر الحاسوبي Macsyma في SAIL و MIT .

• جوسبر الابن، رالف ويليام "بيل" (يناير 1978) [26-09-1977]. "إجراء اتخاذ القرار للجمع الهندسي الفائق غير المحدد" (ملف PDF) . وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية . الرياضيات. 75 (1). زيروكس، مركز أبحاث بالو ألتو، بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: 40-42 . رمز Bibcode : 1978PNAS...75...40G . doi : 10.1073/pnas.75.1.40 . PMC 411178. PMID 16592483. مؤرشف (ملف PDF) من الأصل في 12-04-2019 . تم الاسترجاع في 10-01-2020 . الخوارزمية / متطابقات معاملات ذات الحدين / الصيغة المغلقة / الحساب الرمزي / التكرارات الخطية