پیغام مدیر :
با سلام خدمت شما بازديدكننده گرامي ، خوش آمدید به سایت من . لطفا براي هرچه بهتر شدن مطالب اين وب سایت ، ما را از نظرات و پيشنهادات خود آگاه سازيد و به ما را در بهتر شدن كيفيت مطالب ياري کنید.
فاكتوريل غيربازگشتي
نوشته شده در یکشنبه 12 دی 1389
بازدید : 52
نویسنده : mahdipc
محاسبات عددي مدرن در كامپيوتر
فاكتوريل غيربازگشتي
2 رياضيدان به نام‌هاي ويلهام اكرمن و گابريل سودن كه در دانشگاه ديويد هيلبرت در رشته مباني محاسبات مطالعه و تحقيق مي‌كردند، تابعي به نام آكرمان ارائه كردند. اين تابع يك تابع بازگشتي درجه اول مثل فاكتوريل نيست، ولي آنها اثبات كردند با يك كامپيوتر، پردازشگر سريع و حافظه‌اي بزرگ مي‌توان آن را محاسبه كرد.

اين تابع به صورت زير تعريف مي‌شود.

اگر تابع را بررسي كنيم، متوجه مي‌شويم كه پس از هر مرحله براي m دو حالت اتفاق مي‌افتد:

1ـ مقدارش كم مي‌شود.

2ـ مقدار m تا زماني ثابت مي‌ماند كه مقدار n آنقدر كاهش بيابد تا به صفر برسد و از آن پس مقدار m كم مي‌شود.

پس مطمئن هستيم كه m بالاخره بعد از چند مرحله كاهش مي‌يابد تا به صفر برسد و سپس مقدار n يك واحد افزايش پيدا مي‌كند. وقتي m به صفر برسد، تابع آكرمن به جواب رسيده است. اما نكته‌ اين است كه به ازاي تمامي مقادير ورودي m ميزان رشد n يكسان نيست و براي بعضي از مقادير m ميزان رشد n بشدت زياد خواهد بود. مثلا براي مقدار 3 ورودي براي m در مرحله nام خروجي تابع برابر 3- (3+n)2 مي‌شود. براي مقادير كوچك‌تر از 3خروجي، تابع از اين مقدار نيز كمتر مي‌شود اما براي مقادير بزرگ‌تر مساوي با 4 خروجي، تابع بسيار بزرگ مي‌شود. مثلا براي ورودي m برابر 4 و n برابر 4 مقدار تابع عددي برابر

3ـ2265533 مي‌شود كه عددي بسيار بزرگ است. همان طور كه مشخص است به ازاي مقادير بزرگ‌تر مساوي 4 ، رشد n بسيار زياد است و نمي‌توان آن را حساب كرد.

تابع آكرمن تك متغير

اگر تابع آكرمن را به صورت

(Ackerman (n,n تعريف كنيم به يك تابع تك‌متغير تبديل مي‌شود كه رشد مقادير آن بسيار زياد است و نسبت به توابع ديگر تك‌متغير داراي رشد سريع‌تري است.




مطالب مرتبط با این پست
.



می توانید دیدگاه خود را بنویسید


ورود کاربران

خوش آمدید! لطفا وارد حساب خود شوید

رمز عبور را فراموش کرده‌اید؟
حساب کاربری ندارید؟

فراموشی رمز عبور

نام کاربری یا ایمیل خود را وارد کنید

یا

ثبت نام کاربران

در چند ثانیه حساب کاربری خود را بسازید

قبلا ثبت نام کرده‌اید؟

نظرات کاربران

دیدگاه خود را با ما در میان بگذارید