زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 استقراي قوي – قسمت اول - «تابع آكرمن» (زنگ تفريح شماره‌ي 33)
استقراي قوي – قسمت اول - «تابع آكرمن» (زنگ تفريح شماره‌ي 33)زنگ تفريح كامپيوتر
بازگشت و ماشين تورينگ

استقراي قوي – قسمت اول

«تابع آكرمن» (Ackermann's Function)







چكيده
در اين زنگ تفريح بنا داريم دانش دانش‌اموزان را در حوزه‌ي شناختي بالا ببريم. بنا داريم ضمن افزايش «دانش اصطلاح‌ها» و «واقعيت‌هاي مشخص» از «دانش امور جزوي»، دانش طبقه‌بندي‌ها و طبقه‌ها» از «دانش راه‌ها و وسايل برخورد با امور جزوي» را نيز بيافزاييم.

دانش‌اموزان پس از مطالعه‌ي اين زنگ تفريح به امور ذيل قادر خواهند شد:

- «استقراي رياضي» و «استقراي قوي» را تعريف كنند
- تفاوت دو استقراي مذكور را بيان كنند.
- «تابع آكرمن» از توابع بازگشتي را بشناسند.



استقرا
يكي از روش‌هاي قدرتمند اثبات در رياضيات و كامپيوتر «استقرا» است. «استقراي رياضي» (Mathematical Induction) مي‌گويد: فرض كنيد مجموعه‌اي از اعداد طبيعي و عدد «صفر» را دراختيار داريد. فرض كنيد هرگاه عدد ، عضو مجموعه باشد عدد  نيز عضوي از آن مجموعه باشد. بنابراين همه‌ي اعداد طبيعي عضو اين مجموعه هستند.

اگر بخواهيم غيررسمي‌تر مطلب را توضيح دهيم مي‌گوييم: فرض كنيد مجموعه‌اي از اعداد را گردهم آورده‌ايد و در اين مجموعه «صفر» نيز قرار دارد. اما متوجه مي‌شويد به‌ازاي هر  كه در اين مجموعه قرار دارد عدد  موجود است. بدين‌ترتيب شما مجموعه‌اي بزرگ از «اعداد طبيعي» را در اختيار داريد.

اساساً «استقراي رياضي» بر اين روش استوار است كه از عدد «صفر» آغاز كنيد و هر بار يك عدد 1 به آن اضافه كنيد. سرانجام براي همه‌ي اعداد به‌دست خواهيد آورد.

«استقراي رياضي» مفهومي بي‌نهايت مهمي است به‌خاطر آن‌كه امكان مي‌دهد نتايج بي‌شماري به‌دست آمده، اثبات‌هاي مشكل يا غيرممكن توسط روش‌هاي ديگر به‌آساني ميسر شود. كاربرد عمومي «استقراي رياضي» زماني است كه بخواهيم صحت جمله‌اي را براي همه‌ي اعداد طبيعي اثبات كنيم. اين در حالي است كه ممكن است اثبات مستقيم عبارت مذكور كاملاً سخت باشد اما جمله‌اي كه به‌ازاي  اثبات شود به‌ازاي  نيز به‌راحتي اثبات خواهد شد.

موارد ذيل در «استقراي رياضي» نشان داده مي‌شود:

- جمله به‌ازاي  صحيح است

- اگر جمله براي عدد  صادق باشد براي عدد بعدي  نيز صدق خواهد كرد:







(رابطه‌‌ي 1)

اگر بتوانيم دو گزاره‌ي بالا را ثابت كنيم براساس «استقراي رياضي»، جمله براي تمام اعداد طبيعي نيز صادق خواهد بود زيرا گزاره‌ي اول مي‌گويد: مجموعه‌ي  براي عضو «صفر» از مجموعه صادق است. گزاره‌ي دوم نيز مي‌گويد وقتي جمله براي عدد  صادق است  نيز در آن مجموعه جاي خواهد داشت؛ بنابراين مجموعه‌ي مذكور شامل همه‌ي اعداد طبيعي و صفر است.




«استقراي قوي» (Strong Induction)
نتيجه‌ي منطقي از «استقراي رياضي»، «استقراي قوي» (Strong Induction) است كه گاهي از آن با نام‌هاي ذيل نيز ياد مي‌شود:

- «استقراي كامل» (Complete Induction)
- «استقراي ميدان مقادير» (Course of Value Induction).

مطابق «استقراي قوي» اگر بدانيم عدد  در مجموعه‌ي مذكور است هرگاه  در آن مجموعه باشد هر عددي نيز در آن مجموعه خواهد بود.

ياداوري – چون هيچ عددي كوچك‌تر از «صفر» در مجموعه نيست «صفر» بايد در مجموعه وجود داشته باشد.







(رابطه‌‌ي 2)

براي اثبات «استقراي قوي» (Strong Induction) چنين گفته‌اند: اگر زيرمجموعه‌اي از مجموعه‌ي مذكور را به‌گونه‌اي تعريف كنيم كه شامل اعدادي باشد كه براي هر عدد، عدد بعدي نيز وجود داشته باشد، «صفر» قطعاً عضو اين زيرمجموعه خواهد بود. اگر  را به‌عنوان عضوي از اين مجموعه فرض كنيم همه‌ي اعداد بعد از آن نيز در مجموعه‌‌ي اصلي وجود دارد؛ از طرفي طبق فرض، نيز در اين زيرمجموعه وجود دارد. بنابراين زيرمجموعه شامل تمام اعدادي خواهد بود كه مجموعه‌ي اصلي شامل آن است!


تفاوت «استقراي رياضي» و «استقراي قوي»
براي بيان تفاوت «استقراي رياضي» با «استقراي قوي» مي‌توانيم به مواردي نظير ذيل اشاره كنيم:

الف – «استقراي قوي» بيان مي‌دارد براي همه‌ي اعداد ، گزاره‌ي  صادق است:




(رابطه‌‌ي 3)





به مثال ذيل توجه كنيد:

- همه‌ي كلاغ‌هاي مشاهده شده سياه هستند
بنابراين:

همه‌ي كلاغ‌ها سياه هستند.

اين مثالي از اثبات به‌طريق «استقراي قوي» است؛ به‌عبارت ديگر در اين روش از وضعيت جزو، وضعيت كل نتيجه مي‌شود. اما به هر حال نسبت به نتيجه مطمئن نيستيم مگر آن‌كه احتمال ديگر رنگ‌ها را از كلاغ منتفي كنيم. بنابراين نتيجه ممكن است عملاً غلط باشد.

به‌عنوان مثال: شخصي ممكن است با مطالعه بر روي ژنوم پرنده، پرنده‌اي بدون جهش يا تغيير طولاني‌مدت در نتيجه‌ي توليد نسل با رنگ غيرسياه توليد كند. حتي ممكن است كلاغ‌هاي بي‌رنگ يافته و بدين‌ترتيب بتوانيم كلاغ‌هايي با رنگ روشن توليد كنيم.

حتي اگر تعريف «كلاغ» براي سياهي رنگ تغيير دهيم ممكن است بي‌رنگي و در نتيجه كلاغ با رنگ روشن را بيابيم.

ب – در «استقراي رياضي» براي اعداد ، صدق گزاره‌ي  ثابت مي‌شود.




به مثال ذيل توجه كنيد:

- من هميشه تصاوير را بر روي ميخ نصب مي‌كنم
بنابراين:

همه‌ي تصاوير بر روي ميخ نصب مي‌شوند.

اين مثالي از اثبات به‌طريق «استقراي رياضي» است. فرض كنيد گزاره‌ي اول صحيح باشد در اين مثال گزاره‌ي «من هميشه تصاوير را بر روي ميخ نصب مي‌كنم» به «همه‌ي تصاوير بر روي ميخ نصب مي‌شوند» تعميم يافته است. اما به هر حال رابطه‌ي بين «شرط استقرا» با «نتيجه» ضعيف است. هيچ دليلي وجود ندارد اعتقاد داشته باشيم چون يك نفر تصاوير را بر روي ميخ آويزان مي‌كند راه‌هاي ديگري براي آويزان كردن تصاوير وجود نداشته باشد يا اين‌كه افراد نمي‌توانند كارهاي ديگري با تصاوير انجام دهند.

به‌علاوه همه‌ي تصاوير از ميخ آويزان نمي‌شوند. هم‌چنين همه‌ي تصاوير آويزان نمي‌گردند. «نتيجه» نمي‌تواند با قوت از «شرط» استقرا به‌دست آيد.

اين در حالي است كه با جستجوي اطلاعات ديگر به‌راحتي مي‌بينيم كه اين مثال استقرا ما را به نتيجه‌اي به‌وضوح نادرست هدايت كرده است. نتايج به‌دست آمده از «استقراي رياضي» معمولاً افراطي است.

به مثال ذيل توجه فرماييد:

- همه‌ي جوايز حساب‌هاي قر‌ض‌الحسنه‌ي بانك‌ها به نوجوانان اهدا مي‌شود.
بنابراين:

همه‌ي نوجوانان خوش‌شانس هستند.

در اين مثال، «شرط استقرا» برپايه‌ي يقين به‌دست آمده است. اما به هر حال، نتيجه از اين فرض به‌دست نمي‌آيد. مشاهده شده است كه همه‌ي نوجوانان خوش‌شانس هستند. به‌عبارت ديگر، برعكس جمله‌ي «خورشيد هر صبح بالا مي‌آيد»، مثال‌هاي بي‌شماري از نوجوانان وجود دارد كه موفق به برنده شدن در قرعه‌كشي نشده‌اند.

در هر دو مثال اخير، ارتباط منطقي بين «شرط» و «نتيجه» (با كلمه‌ي «بنابراين») ناقص است و براي ما حكمي منطقي و در عين حال استقرايي قوي فراهم نمي‌كند.



بازگشت (Recursion)
«بازگشت» (Recursion) - كه در مباحث كامپيوتر به‌نام «تفرقه بيانداز و حكومت كن!» (Divide and Conquer)‌ مطرح مي‌شود – روشي است كه در آن يك مسأله‌ به بخش‌هايي كوچك‌تر تقسيم مي‌شود كه حل كردن آن‌ها ساده‌تر است.

اگر بتوانيم مسأله‌اي را به بخش‌هاي كوچك‌تر تقسيم كنيم و بخش‌هاي كوچك‌تر حل‌شدني باشند روشي براي حل آن مسأله يافته‌ايم و فرقي ندارد كه مسأله چقدر بزرگ باشد. اين امر را به‌وسيله‌ي «استقرا» انجام مي‌دهند. بنابراين بحث «استقرا» در علوم كامپيوتر در مبحث «بازگشت» (Recursion) مطرح مي‌شود.

به‌عنوان مثال، فرض كنيم مختصات رؤوس يك چندضلعي داده شده است (همان‌طور كه بديهي است چندضلعي از چند رأس متمايز تشكيل شده كه اضلاع آن يكديگر را قطع نمي‌كنند)؛ مي‌خواهيد چندضلعي را به چند مثلث تقسيم كنيم. اگر بتوانيم برنامه‌اي بنويسيم كه يك چندضلعي بزرگ را به دو چندضلعي كوچك‌تر تقسيم كند خواهيم فهميد كه مي‌توانيم همه‌ي چندضلعي‌ها را به مثلث‌هايي تقسيم كند. بدين‌ترتيب چندضلعي بزرگ‌تر را به دو چندضلعي كوچك‌تر تقسيم كرده و سپس اين فرايند را تكرار مي‌كنيم تا چندضلعي‌هاي كوچك‌تري به‌دست آيد.



«تابع آكرمن» (Ackermann's Function)
«تابع آكرمن» (Ackermann's Function) نمونه‌اي از توابع «بازگشتي» (Recursive) و شامل زوج‌هاي اعداد طبيعي به‌شكل ذيل است:





(رابطه‌‌ي 4)

براي مقادير كوچك  نظير: 1، 2 يا 3، «تابع آكرمن» با سرعت نسبتاً كمي نسبت به  (حداقل به‌صورت تابع نمايي) رشد مي‌كند. اما به هر حال براي سريع‌تر رشد مي‌يابد به‌طوري كه داريم:



(رابطه‌ي 5)

اين در حالي است كه بسط  برمبناي ده، بسيار بزرگ است.

برخي از بسط‌هاي «تابع آكرمن» (Ackermann's Function) ذيلاً تقديم شده است:

بسط  به‌شكل ذيل است:










(رابطه‌ي 6)

بسط  به‌شكل ذيل است:










































(رابطه‌ي 7)

از طرفي پس از جستجو، مقدار  قبلاً به‌صورت ذيل محاسبه شده است:


(رابطه‌ي 8)

همان‌طور كه مشاهده مي‌كنيد  عدد بسيار بزرگي است.

در جدول 1 بعضي از مقادير «تابع آكرمن» (Ackermann's Function) ذكر شده است.

جدول 1 – بعضي از مقادير «تابع آكرمن» (Ackermann's Function).

/

0

1

2

3

4

0

1

2

3

4

5

1

2

3

4

5

6

2

3

5

7

9

11

3

5

16

29

61

125

4

13

65532

5

65532

همان‌طور كه ملاحظه مي‌كنيد محاسبه‌ي مقادير اين تابع به‌سادگي ميسر نمي‌شود. اگرچه اين نوع بازگشت محدود است به‌خاطر آن‌كه يا  كاهش مي‌يابد يا ثابت باقي مي‌ماند و  نيز كاهش مي‌يابد. هر بار كه  به «صفر» مي‌رسد  نيز سرانجام به «صفر» مي‌رسد. اما به هر حال، زماني كه  كاهش مي‌يابد كران بالايي براي چگونگي افزايش  وجود نداشته اغلب خيلي زياد افزايش مي‌يابد.

اگر تابعي نظير  تعريف كنيم كه در آن هم  و هم  با هم افزايش يابند تابعي يك متغيره خواهيم داشت كه در زمره‌ي «توابع بازگشتي اوليه‌ي» (Primitive Recursive Function) كوتاه محسوب مي‌شوند. از اين جمله مي‌توان به توابع ذيل اشاره كرد:

- تابع نمايي
- تابع فاكتوريل
- سوپرفاكتوريل‌ها
- و ...

به‌علت رشد بسيار بزرگ «تابع آكرمن» (Ackermann's Function)، واضح است كه در ماشين‌هاي محاسبه‌اي با حافظه‌اي نامحدود نظير: «ماشين تورينگ» (Turing Machine) محاسبه‌پذير بوده لذا «تابع محاسبه‌اي» (Computable Function) هستند. از طرفي به‌علت رشد بسيار سريعي كه نسبت به «تابع بازگشتي اوليه» (Primitive Recursive Function) دارند «بازگشتي اوليه» (Primitive Recursive) محسوب نمي‌شوند لذا اغلب به‌عنوان مثالي براي كم‌ارزش كردن اين فرضيه به‌كار مي‌رود كه مي‌گويد: «همه‌ي توابع ساده يا مفيد «بازگشتي اوليه» (Primitive Recursive) هستند». در عين حال نبايد «توابع بازگشتي اوليه» (Primitive Recursive Function) را با «بازگشت اوليه» (Primitive Recursion) اشتباه كرد.

لازم به‌ذكر است نظريه‌پردازان زبان‌هاي برنامه‌نويسي علاقه‌مند به برنامه‌هايي هستند كه از ويژگي‌هاي «بازگشت اوليه» (Primitive Recursion) برخوردار باشد يعني انتها داشته باشد.




«ويلهلم آكرمن»
(Wilhelm Ackermann)



تاريخچه‌ي «تابع آكرمن» (Ackermann's Function)
در اواخر دهه‌ي 1300 (1920 ميلادي)، «گابريل سودان» (Gabriel Sudan) و «ويلهلم آكرمن» (Wilhelm Ackermann) دانشجويان «ديويد هيلبرت» (David Hilbert) مطالعه بر روي «محاسبه‌ها» (Computation) را آغاز كردند. «گابريل سودان» (Gabriel Sudan) با كشف تابع غيرمشهور «سودان» (Sudan Function) شهرت يافت؛ اين تابع اولين «تابع بازگشتي» (Recursive) نام گرفت كه «اوليه» (Primitive) محسوب نمي‌شد.

كمي بعد و به‌طور مستقل «ويلهلم آكرمن» (Wilhelm Ackermann) تابع بازگشتي خود را منتشر كرد كه آن هم «اوليه» (Primitive) نبود. وي ابتدا تابع سه‌متغيره‌ي  را به‌صورت ذيل تعريف كرد:


(رابطه‌ي 9)

«ويلهلم آكرمن» (Wilhelm Ackermann) ثابت كرد تابع  يك «تابع بازگشتي» (Recursive) بوده و يك كامپيوتر با حافظه‌ي نامحدود مي‌تواند آن را محاسبه كند اما يك «تابع بازگشتي اوليه» (Primitive Recursive Function) (نظير: جمع، فاكتوريل و ...)‌ محسوب نمي‌شود.


«ديويد هيلبرت»
(D
avid Hilbert)



«ديويد هيلبرت» (David Hilbert)
فرض كرد «تابع آكرمن» بازگشتي اوليه نيست ولي «ويلهلم آكرمن» (Wilhelm Ackermann) دانشجوي سابقش به‌طور عملي در مقاله‌اي با عنوان: «درباره‌ي ساختار هيلبرت از اعداد حقيقي» (On Hilbert's Construction of Real Numbers) اين مسأله را ثابت كرد. نهايتاً هيلبرت در مقاله‌اي بسيار مهم اساس «اعداد نامحدود» (Transfinite Numbers) را براساس روش‌هاي محدود بنا نهاد.

تابعي كه با نام «تابع آكرمن» (Ackermann's Function) مي‌شناسيم توسط «روزا پيتر» (Rozsa Peter) و «رافائل رابينسون» (Raphael Robinson) تعريف شده است.




 





ماشين تورينگ» (Turing Machine)
«ماشين تورينگ» (Turing Machine) ابزاري «پايه‌اي مجرد براي دستكاري نمادها» (Basic Abstract Symbol Manipulating) است كه با وجود سادگي‌اش مي‌تواند با شبيه‌سازي منطق هر كامپيوتري سازگاري دارد. در سال 1315 (1936 ميلادي) توسط «آلن متيسون تورينگ» (Alan Turing) توصيف شد.

مفهوم «ماشين تورينگ» (Turing Machine) از آن‌جا ناشي شد كه بايد رويه‌اي كاملاً تعريف‌شده‌‌اي را با تغيير در محتواي يك نوار كاغذي نامحدود اجرا كرد. نوار كاغذي به مربع‌هايي تقسيم شده كه هر مربع شامل مجموعه‌اي از نمادها است. لازم است يكي از مجموعه‌هاي محدود از وضعيت‌ها و رويه‌ها به‌صورت رابطه‌اي از مراحل بسيار پايه‌اي به‌صورتي نظير ذيل به‌ياد آورده شود:

- اگر در وضعيت 42 هستيد نماد مشاهده شده «صفر» است

- سپس اين نماد را با «1» عوض كنيد و يك نماد به‌سمت راست آن اضافه كرده مثلاً: وضعيت 17 را به‌عنوان وضعيت جديد فرض كنيد.

يك «ماشين تورينگ» (Turing Machine) از بخش‌هاي ذيل تشكيل شده است:

- نوار (Tape)
يك نوار كه به سلول‌هايي تقسيم شده است. هر سلول شامل نمادي از بعضي از حروف الفبايي است. حروف الفبايي شامل نمادهاي ويژه‌ي خالي هستند (مثلاً: B) و يك يا بيش از يك نماد.

فرض مي‌شود كه نوار به‌طور دلخواه به‌سمت راست يا چپ مي‌تواند حركت كند؛ به‌عنوان مثال: «ماشين تورينگ» (Turing Machine) هميشه مملو از نوارهايي براي محاسبه‌ است.

سلول‌هايي كه قبلاً بر روي آن‌ها مطلبي نوشته نشده است با نمادهاي خالي پُر شده‌اند.

در بعضي مدل‌ها، در انتهاي سمت چپ نوار نماد ويژه‌اي حك شده است. نوار به‌سمت راست به‌صورتي نامحدود گسترش‌پذير است. نمادها بعضي اوقات به رنگ‌هايي رجوع داده مي‌شوند.

- هد (Head)
«هد» (Head) مي‌تواند نمادها را خوانده و يا بنويسد و در هر بار بر روي نوار به‌سمت چپ يا راست تنها و تنها يك خانه حركت مي‌كند. در بعضي مدل‌ها، «هد» (Head) حركت مي‌كند و «نوار» (Tape) ثابت است.

- «جدول» (Table) (جدول عملكرد يا تابع انتقال)
جدول چهارتايي يا پنج‌تايي در داخل نوار قرار دارد و نماد در داخل خانه‌ها قرار مي‌گيرد. نماد داخل جدول يكي از عمليات ذيل را از ماشين خواستار مي‌شود:
الف - نمادي را نوشته يا پاك كند.
ب - «هد» (Head) را به‌سمت راست (R) يا چپ (L) حركت دهد.
ج - همان وضعيت يا وضعيت جديد تجويز مي‌شود.
در مدل‌هايي كه از جدول چهارتايي تشكيل شده‌اند علاوه بر عمليات سه‌گانه‌ي فوق، هيچ دو عملياتي با هم اجراشدني نيست. در بعضي مدل‌ها، داده‌هاي ورودي‌اي در جدول براي تركيبي از نمادهاي حاضر موجود نيست؛ پس ماشين متوقف مي‌شود. در بعضي مدل‌ها لازم است تمام داده‌هاي ورودي پُر شده باشند.
- «ثبت‌كننده‌ي وضعيت» (State Register)
«ثبت‌كننده‌ي وضعيت» (State Register) وضعيت جدول تورينگ را ذخيره مي‌كند. تعداد وضعيت‌هاي مختلف هميشه محدود بوده و يك وضعيت «شروع» - كه در آن «ثبت‌ وضعيت» آغاز مي‌شود – وجود دارد.

«تورينگ» (Turing) به‌عنوان «يادداشت دستورالعمل‌ها» براي نگهداري محاسبه‌ي «كامپيوتر» (يا فردي) تعريف مي‌شود كه در يك «حالت درهم و برهم» (Desultory Manner) كار مي‌كند.

به‌ياد داشته باشيد كه هر بخش از «ماشين تورينگ» [مجموعه‌هاي نمادها و وضعيت‌ها و عملياتي نظير: پرينت، پاك كردن، ضبط حركت و ...] محدود، مجزا و تميزدادني است. بالقوه مقدار نامحدودي از «نوار» (Tape) وجود دارد كه مقادير نامحدودي «فضاي ذخيره‌اي» (Storage Space) دراختيار مي‌گذارد.


1386/10/6 لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاين كاربران غيرعضو آنلاين:   2644
  كاربران عضو آنلاين:   0
  کل كاربران آنلاين:   2644