کتاب مقدمه‌ ای بر طراحی و تحلیل الگوریتم ها (جلد دوم)

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

درباره کتاب مقدمه‌ ای بر طراحی و تحلیل الگوریتم ها (جلد دوم)

کتاب مقدمه‌ای بر طراحی و تحلیل الگوریتم‌ها (جلد دوم) ادامه‌ی مستقیم کار آنانی لویتین در جلد اول است و به بخش‌هایی از طراحی الگوریتم می‌پردازد که معمولاً در مرحله‌ی پیشرفته‌تر آموزش مطرح می‌شوند. در این کتاب تمرکز از الگوریتم‌های پایه به سمت فنون تحلیلی عمیق‌تر و کلاس‌های دشوارتر مسائل حرکت کرده است و مترجم، جعفر الماسی‌زاده، در خلال ترجمه توضیح‌ها و یادداشت‌هایی برای روشن‌ترشدن استدلال‌ها افزوده است. کتاب مقدمه‌ای بر طراحی و تحلیل الگوریتم‌ها (جلد دوم) با فصل برنامه‌ریزی پویا آغاز می‌شود؛ جایی که نویسنده ابتدا با مثال‌هایی مثل دنباله‌ی فیبوناچی، مسأله‌ی ردیف سکه‌ها و مسأله‌ی جمع‌آوری سکه‌ها روی یک تخته، ایده‌ی «زیرمسائل همپوشان» و «اصل بهینگی» را قدم‌به‌قدم می‌سازد. سپس مسأله‌ی کوله‌پشتی و نسخه‌های مختلف آن، الگوریتم‌های پایین‌به‌بالا و بالابه‌پایین، مفهوم توابع حافظه‌دار و تحلیل شبه‌چندجمله‌ای‌بودن برخی الگوریتم‌ها مطرح شده است. در ادامه‌ی کتاب مقدمه‌ای بر طراحی و تحلیل الگوریتم‌ها (جلد دوم) فصل‌هایی درباره‌ی درخت‌های دودویی جستجوی بهینه، الگوریتم‌های کلاسیک روی گراف‌ها مانند وارشال، فلوید، پریم، کراسکال، دایکسترا و درخت‌های هافمن آمده است. سپس مباحثی مانند روش سیمپلکس و تفسیر هندسی برنامه‌ریزی خطی، جریان بیشینه، تطابق بیشینه، مسأله‌ی ازدواج پایدار، توان محدود الگوریتم‌ها، درخت‌های تصمیم، مسائل پی و ان‌پی و ان‌پی‌کامل، عقبگرد، شاخه‌وکران، الگوریتم‌های تقریبی و حل معادلات غیرخطی بررسی شده‌اند. در پایان نیز پیوست‌هایی برای فرمول‌های تحلیلی، رابطه‌های بازگشتی و مراجع آمده تا خواننده ابزار لازم برای تحلیل دقیق‌تر الگوریتم‌ها را در اختیار داشته باشد.

خلاصه کتاب مقدمه‌ ای بر طراحی و تحلیل الگوریتم ها (جلد دوم)

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

چرا باید کتاب مقدمه‌ ای بر طراحی و تحلیل الگوریتم ها (جلد دوم) را بخوانیم؟

این کتاب تصویری نسبتاً کامل از بخش پیشرفته‌ی طراحی الگوریتم ارائه کرده است؛ از برنامه‌ریزی پویا و کوله‌پشتی تا ان‌پی‌کامل و الگوریتم‌های تقریبی. خواننده با مثال‌های عددی، تمرین‌های متنوع و پیوست‌های تحلیلی، هم شیوه‌ی ساخت الگوریتم را می‌بیند و هم یاد می‌گیرد چگونه کارایی زمانی و فضایی آن را با دقت بررسی کند و مرزهای حل‌پذیری را تشخیص دهد.

خواندن این کتاب را به چه کسانی پیشنهاد می‌کنیم؟

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