سِفر یادگیری

... محلی برای تفکر و شناخت ... جایی برای دقیق و عمیق نگریستن

سِفر یادگیری

... محلی برای تفکر و شناخت ... جایی برای دقیق و عمیق نگریستن

استقرا

سه شنبه, ۲۳ ارديبهشت ۱۳۹۳، ۰۵:۴۱ ب.ظ

نویسنده : محمد مطیعی


استقرا کِی به درد می خوره؟
معمولا وقتی ما می خوایم یه حکمی رو راجع به یه مساله ثابت بکنیم و اندازه ورودی مساله خیلی بزرگه (مثلا میخوایم یه حکمی رو راجع به یه جدول 2009*2009 ثابت کنیم) یا اینکه اندازه ورودی مساله نامعلومه (مثلا میخوایم یه حکمی رو راجع به n تا خط ثابت کنیم) یکی از روش هایی که می تونه تو اثبات اون حکم کمک ما کنه استقراست.

 


خب حالا استقرا چیکار میکنه؟
 فرض کنید من میخوام از همکف دانشکده با پله ها برم طبقه 3. چیکار باید بکنم؟
خب من الان جلوی اولین پله یا در حقیقت روی 0مین پله ایستادم (یه حقیقت اولیه و ساده!  پایه استقرا) .
من هر لحظه روی هر پله که وایساده باشم می تونم با یه قدم برم روی پله بعدی. همین کافیه دیگه! چون من اگه پله اول باشم با یه قدم میرم پله دوم، بعد چون تو پله دوم هستم طبق اون جمله می تونم برم پله سوم... و وقتی پله iم باشم می تونم برم پله i+1م ... پس می تونم برسم طبقه سوم!

 

کل این پاراگراف قبلی از توضیحات من شبیه گام استقرا می مونه! تو گام استقرا من میام فرض می کنم که تا پله iم تونستم بیام، ( به این میگن فرض استقرا) حالا میخوام برم روی پله i+1م ( به اینم میگم حکم استقرا، چیزی که میخوام بهش برسم!). تنها چیزی که این وسط باید اثبات کنم همون رسیدن از پله iم  به پله i+1مه! که اثبات اصلی توی روش استقراست! اگه اینو اثبات کنم... همه چی حله! چون اولش روی پله صفر هستم پس i=0 رو دارم (پس فرضم برقراره) پس به i=1 میتونم برسم، پس حالا i=1 رو دارم... پس دوباره فرضم برقراره پس به i=2 می تونم برسم... و همین طور می تونم به هرعددی=i برسم!
 

 

 

 

 



خب حالا با یه مساله، یه مقداری فرمال تر این موضوع رو مطرح می کنم.

مثال)

ثابت کنید هر جدول  رو که یه گوشه-ش حذف شده میشه با تری مینو پوشوند. (تری مینو یه مربع 2*2 ـه که یه گوشه-ش حذف شده)

 

تری مینو ها رو میتونید هرطوری میخواید بچرخونید و بعد روی اون جدولتون قرار بدید!

خب اول از همه برای اینکه این مساله رو حل کنید باید ببینید که استقرا رو روی چی بزنیم؟ چه چیزی متغیره ؟ حالا توی این مساله که واضحه مساله کلا یه متغیر بیشتر نداره... n ! ولی بعضی وقتا مساله چند تا متغیر داره... و شما مثلا می تونید روی یکی از اون متغیرها... یا حتی مجموع اون متغیرها استقرا بزنید... اما چیزی که مهمه اینه که ببینید کدوم حالت طوریه که می تونید اون اثبات گامش رو راحت تر انجام بدید.

خب حالا حالت پایه رو چی بگیریم؟
یه حالت ساده و کوچیک i=1! بدیهیه که یه جدول 2*2 که یه گوشه-ش حذف شده رو میشه یه دونه تری مینو گذاشت روش و اون رو پوشوند!

حالا برای گام استقرا باید چیکار کنیم؟ باید فرض و حکم رو مشخص کنیم و از فرض برسیم به حکم!

فرض استقرا: فرض می کنم که تونستم یه جدول  رو بپوشونم.

حکم استقرا: میخوام با استفاده از فرض استقرا ثابت کنم که میتونم یه جدول   رو هم با تریمینو ها بپوشنم!


خب چه طوری اینو اثبات کنم؟ واضحه که باید یه استفاده ای از فرضم بکنم! اگه مستقیم برسم سراغ جدول  و زور بزنم که با تریمینو بپوشنمش هرگز موفق نمیشم چون اصن انگار نه انگار که دارم استقرا میزنم! انگار میخوام خود مساله رو مستقیم حل کنم!

خب پس چه طوری می تونم از فرضم کمک بگیرم؟
باید یه طوری جدولم رو تبدیل کنم به جدول فرضم یعنی  و بعد با توجه به اینکه فرض کردم که اون جدول رو میتونم بپوشونم... این رو هم بپوشونم! 

چه طوری میتونم این تبدیل رو انجام بدم؟ خب اگه نگاه کنیم، هربار داره به توان 2 یکی اضافه میشه... یعنی هربار انگار داره ضلع جدولمون دو برابر میشه پس میتونیم جدول حکم رو به چهار تا جدول فرض تقسیم کنیم. و میدونیم جدول فرض رو میتونیم پر کنیم، پس هرکدوم ازون چهار قسمت رو (چون  هستن ) میتونیم پر شده فرض کنیم، اما هنوز کار تموم نشده... مشکل اون خونه های گوشه هست که خالی هستن هنوز!

حالا این مشکل رو چه طوری میتونیم حل کنیم؟ 

ازین سه تا یکیش که توی جدول اصلی (  ) هم خالیه! ولی اون سه تای دیگه رو باید یه طوری پرشون کنیم! اما اینا که مجاور نیستن! خب راهکار اینه که اونا رو دوران میدیم!

حالا این وسط رو با یه تریمینو جدید میپوشونیم! 

الان دیگه اثبات کامل شد! یعنی چی؟ یعنی به ازای n مساوی با هر عددی، ثابت کردیم میتونیم یه جدول   رو با تریمینو پر کنیم! 

 

 


این چیزایی که تا این جا گفتیم همه-ش استقرای ضعیف بود! یعنی از فرض کردن n=i میخواستیم ثابت کنیم حکم برای n=i+1 هم برقراره! تو استقرای قوی میایم میگیم، وقتی ما ثابت کردیم یه حکمی به ازای 1... 2...3 ... i برقراره، می تونیم اگه لازم بود مساله رو به جای اینکه از n=i نتیجه بگیریم، از ترکیب یه سری حالت n=k که k<i نتیجه بگیریم... چرا چون میدونیم به ازای همه حالت های کوچکتر از i ثابت کردیم! یعنی میتونیم مثلا مساله رو بشکوینم به حالت n=3 و n=i-2 و خب با ترکیب اون دو حالت و یه سری اثبات بگیم که n=i+1 هم حکم براش درسته!
کلا انگار استقرای قوی داره این شکلی عمل میکنه: (قبل فلش فرضمون هست و بعدش حکممون! یعنی مثلا تو خط اول با درست بودن حالت پایه حالت n=2 رو ثابت می کنه و همین طور همه حالت ها ثابت میشن!)

1 -> 2
1 و 2 -> 3
1 و 2 و 3 -> 4
1 و 2 و 3 و 4 -> 5
...
1 و 2 و 3 و ... و i+1 <- i


خب یه مثال از استقرای قوی بزنیم!

مثال)

در یک nضلعی محدب با هر گونه رسم قطرهای نامتقاطع به طوری که داخل nضلعی را به مثلث ها افراز می کنند،  تعداد قطرها n-3 تا میباشد. 

پایه: برای پایه به سادگی یک 3ضلعی محدب که خود یک مثلث میباشد را در نظر میگیرم در این حالت تعداد قطرها 3-3=0 میباشد پس حکم برقرار است.
گام استقرا:
فرض میکنیم حکم به ازای n=3 تا n=i-1 برقرار باشد، (فرض استقرا) اکنون ثابت میکنیم حکم به ازای n=i نیز برقرار است (حکم استقرا).

یک i-ضلعی محدب دلخواه که قطربندی شده و ناحیه هایش به تعدادی مثلث افراز شده را در نظر بگیرید، یکی از قطرهای آن را به دلخواه در نظر بگیرید و شکل را از آن قطر به دو چندضلعی محدب جدا تبدیل کنید، اکنون یک a+1-ضلعی محدب که مثلث بندی شده و یک 1+(i-a) ضلعی محدب که مثلث بندی شده داریم،(1 واحدی که اضافه کرده ایم به خاطر همان وتری است که از آن چندضلعی را بریده ایم و حالا تبدیل به یکی از ضلع های هر کدام از قسمت ها شده!) هر دو 1+a+1 , i-a از i کوچکتر هستند، پس طبق فرض استقرا تعداد قطرهای استفاده شده در آنها به ترتیب: a+1-3  و i-a+1-3 میباشد. یعنی به تریب a-2 و i-a-2.
حالا با چسباندن آن دو چندضلعی به هم تشکیل چند ضلعی اولیه تعداد وترها برابر میشود با تعداد وترهای هرکدام از آن دو قسمت به اضافه یک (همان وتری که از آن شکل را تقسیم کرده ایم) پس می شود: i-a-2+a-2 +1 = i-3.
همان طور که میبینید حکم ثابت شد.

 

اشتباهات رایج در استقرا:
1- پایه استقرا اگرچه ممکنه که بخش ساده ای از اثبات باشه اما خیلی خیلی مهمه! چرا؟ چون اگه یادتون بره مطرح کنید یا وجودش رو اثبات کنید، عملا هیچ چیزی رو اثبات نکردید (اون پله اول وجود نداره که بخواید از وجودش دومی رو اثبات کنید و همین طور برید تا n امی!)

2- هیچ وقت فرض استقرا رو در نظر نگیرید و با اضافه کردن یه سری چیز بهش به حکم برسید! مثلا سعی نکنید تو سوال دوم از درست بودن حکم برای k-ضلعی، یه k-ضلعی بگیرید و یه طوری تبدیلش کنید به k+1 ضلعی و بعد نشون بدید که برای اون هم حکم برقراره!
چرا؟ چون این طوری شما باید یه چیز دیگه رو هم که اثباتش معمولا خیلی سخته اثبات کنید! اونم اینه که همه‌ی حالت های k+1 رو شما میتونید با این کارتون تولید کنید! و اگه حالتی باشه که توضیح گام استقرای شما اونو تولید نکنه اثباتتون کلا غلط میشه! (چون ازون به بعد فرضتون دیگه برقرار نیست!) 
چاره چیه؟ اول حکمتون رو در نظر بگیرید یعنی مثلا یه iضلعی محدب! بعد تبدیلش کنید به یه سری حالت از حالت های فرضتون (همون کاری که من با شکوندن چندضلعی از یه وتر دلخواه انجام دادم!)  این طوری دیگه هر iضلعی که به شما بدن رو میتونید این شکستن رو روش انجام بدید و در نتیجه اثبات شما همه ی حالت های i رو شامل میشه! پس:
از حالتی که میخواید اثباتش کنید حالت فرضتون رو تولید کنید.

3- حواستون به این باشه که وقتی دارید نتیجه گیری نهایی برای درست بودن حکم رو انجام میدید، باید همه ویژگی هایی که تو روند اثباتتون ازش استفاده کردید رو هم ثابت کنید حکمتون داره. (وگرنه نمیشه اون روند توالی رو حفظ کرد یعنی مثلا به محض اینکه از پله اول به پله دوم رفتید دیگه پله دوم همه ویژگی ها رو نداره که بشه ازش به پله سوم رفت!)

 


آخر سر هم اینکه استقرا یکی از قسمت هایی هست که بعدتر هم زیاد به دردتون میخوره! توی طراحی الگوریتم توی هوش مصنوعی با تسلط به استقرا، شهودتون نسبت به کاری که خیلی از الگوریتم ها دارن انجام میدن خیلی خیلی بیشتر میشه... پس سعی کنید این یه مبحث رو خوب یاد بگیرید! و از همه مهم تر هم حل کردن مساله به مقدار زیاد میتونه این کار رو برای شما انجام بده! :)


موفق باشید!

 

 

 

نظرات (۱)

عالی بود 

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">