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

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

طراحی الگوریتم یکی از دروس اصلی و پایه در تمامی گرایش های مختلف رشته کامپیوتر از جمله سخت افزار، نرم افزار، هوش مصنوعی، علوم پایه و IT می باشد. کتاب "درس و کنکور طراحی الگوریتم" برمبنای سه اثر معتبر در حوزه الگوریتم نوشته شده است که عبارتند از: کتاب های نیپولیتان، هورویتز و کتاب آقای بهروز قلی زاده.

کتاب مذکور مشتمل بر 8 فصل می باشد: 1- پیچیدگی زمانی و مرتبه اجرایی 2- روابط بازگشتی 3- روش تقسیم و غلبه 4- یادآوری گراف 5- برنامه نویسی پویا 6- روش حریصانه 7- تکنیک عقبگرد 8- آشنایی با نظریه NP

6 فصل اول کتاب از اهمیت بالایی برخوردار است چرا که بیشتر تست ها از این مباحث طرح می شود؛ درحالی که از فصول بعدیِ آن، تاکنون تستی در کنکورها طرح نشده است.

فصل اول از اهمیت زمان در اجرای یک برنامه و پیچیدگی آن صحبت می کند و در فصل دوم مراتب روابط بازگشتی را به طور جامع توضیح می دهد.

در فصل سوم مخاطب را با تکنیک تقسیم و غلبه (تقسیم و حل) آشنا می کند.

در فصل چهار به علت اهمیت بالای گراف، به یادآوری گراف ها می پردازد.

فصل پنج تکنیک برنامه نویسی پویا و شباهت های آن با تقسیم و غلبه را بررسی می کند.

در فصل شش به توضیحِ الگوریتم های حریصانه یا آزمند می پردازد.

در فصل هفت روش عقب گرد با مثال های مهمی مانند وزیر و قفل رمزی را بیان می دارد و نهایتاً در فصل هشت ابتدا نظریه NP را توضیح داده و سپس نمونه کامل و سخت آن را شرح می دهد.

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

فهرست

فصل اول: پیچیدگی زمانی و مرتبه اجرایی فصل دوم: روابط بازگشتی فصل سوم: روش تقسیم و غلبه فصل چهارم: یادآوری گراف فصل پنجم: برنامه نویسی پویا فصل ششم: روش حریصانه فصل هفتم: تکنیک عقبگرد فصل هشتم: آشنایی با نظریه NP برشی از متن: فصل ششم: روش حریصانه

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

مفهوم روش حریصانه نام این روش از شخصیت معروف اسکروج گرفته شده است. اسکروج به جای آنکه به گذشته و آینده فکر کند، تنها انگیزه هر روز او به دست آوردن طلای بیشتر بود. الگوریتم حریصانه (Greedy) نیز مانند شیوه ی اسکروج می باشد. الگوریتم های حریصانه یا آزمند شبیه روش های پویا اغلب برای حل مسئله ی بهینه سازی استفاده می شوند. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیاری معین (بهترین) به نظر می رسد، بدون توجه به انتخاب هایی که قبلاً انجام شده یا در آینده انجام خواهد شد، انتخاب می شود. الگوریتم های حریصانه اغلب راه خل های ساده ای هستند. در روش حریصانه بر خلاف روش پویا، مسئله به نمونه های کوچکتر تقسیم نمی شود. با یک مثال ساده مفهوم این روش را شرح می دهیم: مثال 1: خریداری از یک فروشگاه یک جنس 64 تومانی می خرد و 100تومان به فروشنده می دهد و فروشنده باید 36 تومان به او برگرداند. اگر فروشنده سکه های 1، 5، 10، 25 و 50 تومانی (از هرکدام خداقل یک نمونه) داشته باشد چگونه می تواند بقیه پول خریدار را برگرداند به نحوی که تعداد سکه ها (در کل) کمترین مقدار ممکن باشد؟ یک راه حل حریصانه به این صورت است: در ابتدا هیچ سکه در مجموعه جواب نداریم. از بین سکه های موجود بزرگترین ممکن یعنی 25 تومانی را انتخاب می کنیم. این مرحله از الگوریتم حریصانه را روال انتخاب (selection procedure) گویند. اگر یک سکه 25 تومانی دیگر را انتخاب کنیم حاصل از 36 تونان بیشتر خواهد شد، لذا آن را کنار گذاشته و به سراغ سکه 10 تومانی می رویم. حال بررسی  می کنیم اگر این سکه 10 تومانی را به مجموعه انتخابی قبلی اضافه کنیم حاصل از 36 تومان بیشتر می شود یا خیر. این مرحله را تحقیق عملی بودن (feasibility check) می نامند. حال اگر این 10تومان را به 25 تومان اضافه کنیم جمع مجموعه انتخاب شده 35 می شود که هنوز به 36 نرسیده است. این مرحله را تحقیق حل شدن (solution check) می گوییم. در ادامه سکه های دیگر را به ترتیب مقایسه می کنیم و در نهایت با انتخاب سکه یک تومانی در کل با 3 سکه (25 تومانی و 10تومانی و یک تومانی) 36 تومان به دست می آید و این حداقل تعداد سکه ممکن است. توجه کنید در الگوریتم فوق ملاک انتخاب، برای انتخاب بهترین سکه در هر مرحله (بهینه محلی) ارزش سکه است و در هنگام انتخاب سکه  در هر مرحله به انتخاب های قبلی و بعدی کاری نداریم. در این شیوه اجازه فکر کردن درباره ی یک انتخاب انجام شده را نداریم یعنی هنگامی که سکه ای پذیرفته شد به طور دائم جزو حل به حساب می آید و هنگامی هم که سکه ای رد می شود به طور دائم از حل کنار گذاشته می شود. همانطور که مشاهده کردید این روش بسیار ساده است ولی اصلی ترین نکته آن است که آیا این روش الزاماً به یک حل بهینه می رسد؟

مؤلف: حمیدرضا مقسمی ناشر: انتشارات گسترش علوم پایه