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

کتاب مقدمه‌ ای بر طراحی و تحلیل الگوریتم‌ ها (جلد دوم) (Introduction to The Design and Analysis of Algorithms) نوشته‌ آنانی لویتین و با ترجمه و توضیح جعفر الماسی‌ زاده است و نشر دانشگاه اصفهان آن را منتشر کرده است. این کتاب که ویراست سوم آن در طاقچه منتشر شده، ادامه‌ی مباحث جلد اول است و روی موضوع‌هایی مانند برنامه‌ریزی پویا، مسئله‌ی کوله‌پشتی، درخت‌های دودویی جست‌وجوی بهینه، الگوریتم‌های روی گراف‌ها، روش سیمپلکس، مسائل ان‌پی‌کامل و الگوریتم‌های تقریبی تمرکز دارد. ساختار کتاب آموزشی است و فصل‌ها با مثال‌های متعدد، تمرین‌های پایانی و پیوست‌های تحلیلی همراه شده‌اند، تا هم ایده‌ی الگوریتم‌ها و هم تحلیل زمانی و فضایی آن‌ها روشن شود. نسخه‌ی الکترونیکی این اثر را می‌توانید از طاقچه خرید و دانلود کنید.

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

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

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

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

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

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

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

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

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

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

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