فصل هفتم (جلسه آخر):

مقدمه ای بر پیچیدگی محاسباتی:

 مسئله مرتب سازی

1- 7 پیچیدگی محاسباتی

- پیچیدگی محاسباتی عبارت از مطالعه تمام الگوهای امکن پذیر برای حل یک مسئله مفروض است.

- در تحلیل پیچیدگی محاسباتی کوشش می کنیم تا حد پایینی کارایی همه ی الگوریتم ها را برای یک مسئله مفروض به دست آوریم.

- تحلیل پیچیدگی محاسباتی را با مطالعه مسئله مرتب سازی معرفی می کنیم.

- این انتخاب دو دلیل دارد:

 1- چند الگوریتم ابداع شده اند که که مسئله را حل می کنند.

 2- مسئله مرتب سازی یکی از معدود مسائلی است که در بسط الگوریتم هایی با پیچیدگی زمانی نزدیک به حد پایینی برای آن موفق بوده ایم.

2-7 مرتب سازی درجی و مرتب سازی انتخابی

 ..... 

فصل ششم:

راهبرد شاخه و حد

- راهبرد شاخه و حد ازآن لحاظ به عقبگرد شبا هت دارد که

 درآن، بریا حل مسئله از درخت فضای حالت استفاده می شود.

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

- الگوریتم شاخه و حد ، در هر گره عددی را ( حدی ) رامحاسبه می کند تاتعیین شود که آیا این گره امید بخش هست یا خیر.

- اگر آن حد بهتر از مقدار بهترین حلی که تاکنون یافته شده ، نباشد، گره غیر امید بخش است. در غیر این صورت ، امید بخش است.

        ......

فصل پنجم:

راهبرد عقبگرد

- از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که این دنباله ، ملا کی را در بر می گیرد.

- یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.

- هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

- عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.

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

 .......

فصل چهارم:

روش حریصانه در طراحی الگوریتم

الگوریتم حریصانه ، به ترتیب عناصر را گرفته ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

الگوریتم حریصانه ، همانند برنامه نویسی پویا غالبا برای حل مسائل بهینه سازی به کار می روند، ولی روش حریصانه صراحت بیشتری دارد.

در روش حریصانه ، تقسیم به نمونه های کوچک تر صورت نمی پذیرد.

.....

فصل سوم:

برنامه نویسی پویا

برنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش ، نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.

مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:

 ......
 

فصل دوم:

روش تقسیم و حل

روش تقسیم و حل یک روش بالا به پایین است.

حل یک نمونه سطح بالای مسئله با رفتن به جزء و بدست آوردن حل نمونه های کوچکتر حاصل می شود.

هنگام پی ریزی یک الگوریتم بازگشتی ، باید:

.....

فصل اول:

کارایی ، تحلیل و مرتبه الگوریتم ها

این کتاب در باره تکنیک های مربوط به حل مسائل است.

تکنیک ، روش مورد استفاده در حل مسائل است.