الگوریتم ریش

الگوریتم Risch، به افتخار رابرت ایچ Risch به این نام نامیده شد که برای حساب دیفرانسیل و انتگرال جبر می‌باشد. این الگوریتم مسئله انتگرال را درون یک مسئله جبری تغییر شکل می‌دهد. آن مبنایی بر مشکل عملی می‌باشد که انتگرال گیری شده و مطابق بر روشهایی برای عملکرد منطقی انتگرال گیری، رادیکال، لگاریتم و تابع تشریعی می‌باشد. ریش الگوریتم را در سال ۱۹۶۸ ساخت و آنرا فرایند تصمیم‌گیری نامید. چرا که متدی است برای تصمیم اینکه آیا یک تابع، تابع اولیه‌ای دارد که انتگرال نامعین داشته باشد و همچنین اگر دارد، تعیینش می‌کند. الگوریتم Risch در الگوریتمی برای جبر کامپیوتری توسط Keith O.Geddes مختصرا توضیح داده شده است. همچنین توسط Gedde , Stephen R. Czapor و George Labah مختصرا توضیح داده شده است. الگوریتم Risch-Normal درسال ۱۹۷۶ تولید شد که سریعتر اما از نظر فنی ضعیف‌تر است.
توصیف
الگوریتم Risch برای تابع اولیه انتگرال استفاده شده است. این‌ها توابعی هستند که شامل ترکیب تابع‌های نمایی، لگاریتم‌ها، رادیکال‌ها، مثلثات و چهار عمل اصلی علم حساب (ضرب و جمع و تفریق و تقسیم) می‌باشند. لاپلاس این مسئله را برای وضعیت تابع منطقی حل کرد همانطوری که او نشان داد انتگرال نامعین یک تابع منطقی، تابعیست منطقی و یک عدد محدود از ضرب تعداد محدودی از ضرب‌های ثابت لگاریتم تابع منطقی است. الگوریتم پیشنهاد شده توسط لاپلاس معمولا در متون کتاب حساب دیفرانسیل شرح داده شده است و سرانجام در دهه ۱۹۶۰ به عنوان یک برنامه کامپیوتری پیاده‌سازی شد.
Liouville مسئله حل شده توسط الگوریتم Rischرا به صورت فرمول درآورد. Liouville به روش تحلیلی اثبات کرد که اگر یک راه حل ابتدایی یا اولیه که اسمش g باشد وجود داشته باشد، برای معادله g ′ = f آنگاه برای ثابت  i و تابع اصلی u i و v پاسخ به شکل زیر
می‌باشد.
Risch روشی ساخت که اجازه می‌داد شخص فقط نگران مجموعه‌ای محدود از توابع اولیه به صورت فرمول لیوویل باشد.
فراست الگوریتم ریش، از رفتار توابع نمایی و لگاریتمی در مشتق گیری می‌آید. برای تابع f e g که f و g توابع متغیری هستند که ما داریم
لذا اگر e g در نتیجه انتگرال نامعین بود، باید انتظار داشت که داخل انتگرال نیز باشد همانگونه که:
سپس اگر ln n g در نتیجه انتگرال باشد آنوقت فقط توان‌های کمی از لگاریتم می‌توان انتظار داشت..
مثال‌های مسئله
یافتن ضد مشتق اولیه برای جزئیاتی خیلی حساس است. به عنوان مثال تابع زیر یک ضد مشتق اولیه دارد:
یعنی
برخی از سیستم‌های جبری کامپیوتری ممکن است در اینجا یک ضد مشتق بر حسب تابع غیر اصلی برگردانند (مثل انتگرال‌های بیضی) هرچند خارج از حوزه الگوریتم ریش هستند. اما اگر ۷۱ به ۷۲ تغییر کند نمایش دادن ضد مشتق با استفاده از تابع اولیه، ممکن نیست! دلیلش این است که گروه Galois از
(D(۴ می‌باشد. مثلا توسط جایگشت‌های (۱و۲و۳و۴) و (۳و۱) تولید شده و هشت عنصر را شامل می‌شود (درx ۴ − ۲ یکسان است) در حالی که گروه Galois از
(S(۴ می‌شود، مثلا توسط جایگشت‌های (۲ ۱) و (۳ ۱) و (۴ ۱) تولید شده و شامل ۲۴ عنصر می‌باشد. تابع زیر یک مثال پیچیده‌تری است:
در واقع، ضد مشتق این تابع یک شکل نسبتا کوتاهی دارد:
پیاده‌سازی
تبدیل فرایند تصمیم ریش به یک الگوریتم که بتواند توسط کامپیوتر اجرا شود وظیفه پیچیده‌ای است که نیازمند مطالعات ابتکاری و پالایش زیاد می‌باشد. هیچ نرم‌افزاری (تا فوریه ۲۰۱۱) شناخته نشد که بتواند الگوریتم ریش را به طور کامل پیاده‌سازی کند، اگرچه چندین سیستم جبری کامپیوتری جزئی از آن را پیاده‌سازی کرده‌اند.
تصمیم پذیری
الگوریتم ریش اعمال شده به توابع اولیه عمومی یک الگوریتم نیست! بلکه یک نیمه الگوریتماست. چراکه به عنوان بخشی از عملیات خودش نیاز به بررسی دارد که آیا عبارات خاصی، برابر با صفر می‌شوند! (مسئله پایدار)، به خصوص در زمینه پایدار. برای عباراتی که فقط درگیر توابعی‌اند که معمولا برای این گرفته شده‌اند که اولیه باشند، شناخته شده نیست، خواه الگوریتم بررسی را انجام دهد یا خیر (سیستم‌های جبری کامپیوتری فعلی از روش‌های ابتکاری استفاده می‌کنند)؛ علاوه بر اون اگر کسی یک Absolute Value Function به لیست توابع اولیه بیفزاید، اینطور برداشت می‌شود که همچین الگوریتمی وجود ندارد! را ببینید.
توجه کنید که این مسئله همچنین در الگوریتم تقسیم چندجمله‌ای polynomial نیز وجود دارد؛ این الگوریتم با شکست مواجه خواهد شد اگر نتواند به درستی تعیین کند که آیا عوامل مشترک عینا به صفر می‌رسد. بنابراین، الگوریتم Risch نیاز زیادی دارد که قسمت ثابت قابل محاسبه باشد. مثلا؛ برای عناصری که به X بستگی نداشته باشند، مسئله معادله صفر (zero-equivalence) قابل تصمیم‌گیری است.
لیست انتگرال‌ها
قضیه Liouville (جبر متفاوت)
انتگرال نمادی
اصل کلی
تابع گاما ناکامل