کتاب نظریه الگوریتمی و کاربرد گراف ها

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

درباره کتاب نظریه الگوریتمی و کاربرد گراف ها

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

خلاصه کتاب نظریه الگوریتمی و کاربرد گراف ها

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

چرا باید کتاب نظریه الگوریتمی و کاربرد گراف ها را بخوانیم؟

دلایل خواندن کتاب نظریه الگوریتمی و کاربرد گرافها را می‌توان این‌طور خلاصه کرد:

• ارتباط میان اثبات قضیه و استخراج الگوریتم را توضیح می‌دهد.
• تحلیل بدترین حالت را در کنار شرح الگوریتم‌ها قرار می‌دهد.
• تمرین‌های اثباتی و مثال نقض، زمینه‌ی سنجش درک مفاهیم را فراهم می‌کنند.
• ارائه‌ی الگوریتم‌ها به دانستن زبان برنامه‌نویسی مشخصی وابسته نیست.

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

کتاب نظریه الگوریتمی و کاربرد گرافها به این گروه‌ها پیشنهاد می‌شود:

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