کتاب طراحی الگوریتم ها - نقیب زاده

کتاب طراحی الگوریتم ها (تحلیل، طراحی و ارزیابی کارایی) تألیف دکتر محمود نقیب زاده توسط انتشارات به نشر به چاپ رسیده است.

الگوریتم به روش خاص حل هر دسته از مسائل گفته می شود. امروزه واژه ی الگوریتم در علوم و مهندسی کامپیوتر معادل روش حل مسئله است که پس از پیاده سازی برای کامپیوتر قابل کاربرد باشد. الگوریتم به این منظور طراحی می شود که پس از تبدیل آن به یک زبان برنامه نویسی برای اجرا به کامپیوتر داده شود. عوامل متعددی روی سرعت اجرای الگوریتم ها تأثیر می گذارند که از این عوامل می توان به سرعت کامپیوتر، میزان حافظه اصلی و از همه مهم تر کیفیت الگوریتم اشاره کرد. کتاب حاضر با هدف آموزش طراحی الگوریتم های کیفی تدوین شده است. زمینه های مورد بحث منطبق بر آخرین مواد درسی طراحی الگوریتم ها برای دوره های علوم مهندسی کامپیوتر می باشد. علاوه بر این، مطالعه ی اثر پیش رو برای آمادگی مسابقه ی جهانی ای. سی. ام و امتحانات سراسری ورود به دوره ی کارشناسی ارشد و دکترای کامپیوتر نیز توصیه می شود. هم چنین موضوعات مختلفی در کتاب آورده شده که یادگیری آن ها می تواند برای حل مسائل بی شمار دیگری به شما کمک نماید. "دکتر محمود نقیب زاده" مطالب کتاب را با تعاریف زیر بنایی و بیان اهمیت تحلیل، طراحی و پیاده سازی الگوریتم های کیفی آغاز نموده و آن ها را با مثال های مختلفی ساده سازی و قابل فهم می نماید.

کتاب "طراحی الگوریتم ها (تحلیل، طراحی و ارزیابی کارایی)" مشتمل بر یازده فصل می باشد: 1- مبانی تحلیل، طراحی و ارزیابی کارایی الگوریتم ها 2- ساختمان داده ها و الگوریتم های پایه آنها 3- بازگشت پذیری و الگوریتم های بازگشتی 4- روش تقسیم و حل 5- روش حریصانه 6- روش برنامه سازی پویا 7- جستجو در درخت ها و گراف ها 8- روش بازگشت به عقب 9- انشعاب و تحدید 10- مسائل رام نشدنی 11- الگوریتم های موازی

برشی از متن کتاب

فصل 1: مبانی تحلیل، طراحی و ارزیابی کارایی الگوریتم ها   ارزیابی کارایی الگوریتم ها: برای اکثر مسائل قابل حل الگوریتم های متفاوتی وجود دارد. حتی اگر مسئله ای تنها یک راه حل داشته باشد می‌توان الگوریتم‌هایی ساخت که در جزئیات با یک دیگر متفاوت باشند. طبق تعریف همه الگوریتم هایی که برای حل یک دسته از مسائل تولید می شوند پس از اجرا باید ما را به جواب مورد نظر برسانند. سوال این است که معیار برتری یک الگوریتم نسبت به الگوریتم دیگر چیست؟ برای مقایسه کارایی الگوریتم هایی که برای حل مسئله ای واحد تولید شده‌ اند در این جا دو معیار مطرح می ‌باشد. الف) زمان لازم برای اجرای کامل الگوریتم ب) میزان حافظه لازم در زمان اجرای الگوریتم در این معیارها به زمان صرف شده برای تولید الگوریتم و رفع اشکال های آن و زمان تبدیل آن به برنامه توجه نشده است. علت این امر آن است که این دو مورد هر یک یک بار انجام می ‌شود ولی اجرای الگوریتم های واقعی به دفعات زیاد و گاهی میلیاردها بار انجام می ‌شود و توجه اصلی باید به کارایی الگوریتم در زمان اجرا باشد. معیارهای بالا اگرچه عوامل اصلی در مقایسه الگوریتم ها را مشخص می نمایند اما در عمل قابل استفاده نیستند. واضح است که اگر یک الگوریتم را به وسیله دو کامپیوتر متفاوت با توانایی و سرعت غیر یکسان اجرا کنیم دو زمان اجرای متفاوت خواهیم داشت. بنابراین زمان لازم برای اجرای کامل یک الگوریتم به کامپیوتری که آن را اجرا می ‌کند بستگی دارد. پس برای مقایسه کارآیی دو الگوریتم باید شرایط یکسانی را فراهم کرد. فصل 2: ساختمان داده ها و الگوریتم های پایه آن ها  لیست پیوندی: در برخی کاربردها اندازه ی داده ها از قبل مشخص نیست بنابراین چنان چه آرایه ای برای نگهداری داده ها در نظر بگیریم تعداد مولفه های آن نامشخص خواهد بود. در این گونه موارد اگر اجباری در به کارگیری آرایه باشد باید تعداد مولفه های آن را آن قدر بزرگ در نظر بگیریم که در بدترین شرایط پاسخگوی نگه داری همه مولفه ها باشد. در این صورت در بقیه موارد اتلاف حافظه خواهیم داشت. اتلاف حافظه مربوط به مولفه هایی از آرایه است که برای آن ها جا پیش بینی شده اما در عمل وجود ندارند. ساختارهای پیوندی هیچ یک از نقاط ضعف اصلی آرایه ها را ندارد. عمل حذف و اضافه در یک ساختار پیوندی به جابجایی بقیه مولفه ها نیاز ندارد و در ساختارهای پیوندی دقیقاً به تعداد مولفه ‌ها جا اشغال می گردد اما آنچه باعث می گردد برخی منابع ساختارهای پیوندی را ساختارهای پویا نام گذاری کنند این است که حافظه لازم برای هر مولفه ساختار در زمان اجرا و در موقع نیاز تسخیر می گردد و در هر زمان به حافظه تخصیص داده شده نیاز نباشد و آزاد گردد می تواند بلافاصله و به هر منظوری مورد استفاده مجدد قرار گیرد. هر مؤلفه یک ساختار پیوندی دارای دو بخش است. بخش اول محل ذخیره داده ها است و بخش دوم محل ذخیره پیوندها. البته هر بخش می تواند دارای چند فیلد باشد.

فهرست

پیشگفتار فصل 1: مبانی تحلیل، طراحی و ارزیابی کارایی الگوریتم ها فصل 2: ساختمان داده ها و الگوریتم های پایه آنها فصل 3: بازگشت پذیری و الگوریتم های بازگشتی فصل 4: روش تقسیم و حل فصل 5: روش حریصانه فصل 6: روش برنامه سازی پویا فصل 7: جستجو در درخت ها و گراف ها فصل 8: روش بازگشت به عقب فصل 9: انشعاب و تحدید فصل 10: مسائل رام نشدنی فصل 11: الگوریتم های موازی پیوست نمایه موضوعی منابع

• ویــراست سـوم
• تحلیـل - طراحـی - ارزیابـی کارایـی
• نویسنده: دکتر محمود نقیب زاده
• انتشارات: به نشر