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

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

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

کتاب «طراحی الگوریتم» در حجمی مناسب طراحی شده که در طی یک ترم بتوان همگی مطالب آن را تدریس نمود و در عین حال برای دانشجویان گرامی نیز ارزان باشد. این اثر ارزشمند بسیار کاربردی بوده و شامل مثال ها و تمرین های متعددی می باشد و جواب کلیدی تمرین ها در آخر کتاب آورده شده است. جواب تشریحی تمرین ها و هم چنین پاورپوینت و فیلم آموزشی تدریس این کتاب، توسط مؤلفین آماده شده که متقاضیان می توانند از طریق راه های ذکر شده در ابتدای کتاب، به آن ها دسترسی داشته باشند.

کتاب "طراحی الگوریتم" مشتمل بر چهار فصل می باشد: 1- پیچیدگی زمانی و مرتبه اجرایی 2- روش تقسیم و غلبه 3- برنامه نویسی پویا 4- روش حریصانه

 

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

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

• برای آن که احتمال تولید لیست تهی توسط تابع Partition کمتر شود، در هر بار اجرای آن می توان عنصر محور (لولا) را به صورت تصادفی انتخاب کرد که به این روش مرتب سازی Randomized Quick Sort می گویند. هم چنین می توان قبل از اجرای الگوریتم مرتب سازی سریع، لیست ورودی را به صورت تصادفی به هم ریخت.
• می توان یک مقدار آستانه جهت فراخوانی بازگشتی Quick Sort تعیین نمود تا اگر طول آرایه ورودی آن از آستانه کمتر باشد، از یک روش مرتب سازی دیگر (اغلب مرتب سازی درجی) استفاده شود.
• در هر بار اجرای تابع Partition یک عنصر در جای صحیح خود قرار می گیرد (همان عنصر لولا)، بنابراین اگر تابع Partition را روی آرایه ای اجرا کنیم و عنصر محوری در مکان k ام قرار گیرد، نتیجه می گیریم که این عنصر لولا، k امین کوچکترین عنصر لیست بوده است.
• مرتب سازی سریع از همان آرایه ی اصلی جهت مرتب کردن داده ها استفاده می کند ولی باید توجه داشته باشید که به علت بازگشتی بودن به حافظه پشته نیاز دارد. اثبات می شود در بدترین حالت عمق پشته بازگشتی از مرتبه خواهد بود  و در حالت متوسط فضای مورد نیاز پشته  است.
• اگر تمام عناصر آرایه با هم برابر باشند در واقع آرایه مرتب بوده و زمان Quick Sort بدترین حالت یعنی می شود.

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

• برای آن که احتمال تولید لیست تهی توسط تابع Partition کمتر شود، در هر بار اجرای آن می توان عنصر محور (لولا) را به صورت تصادفی انتخاب کرد که به این روش مرتب سازی Randomized Quick Sort می گویند. هم چنین می توان قبل از اجرای الگوریتم مرتب سازی سریع، لیست ورودی را به صورت تصادفی به هم ریخت.
• می توان یک مقدار آستانه جهت فراخوانی بازگشتی Quick Sort تعیین نمود تا اگر طول آرایه ورودی آن از آستانه کمتر باشد، از یک روش مرتب سازی دیگر (اغلب مرتب سازی درجی) استفاده شود.
• در هر بار اجرای تابع Partition یک عنصر در جای صحیح خود قرار می گیرد (همان عنصر لولا)، بنابراین اگر تابع Partition را روی آرایه ای اجرا کنیم و عنصر محوری در مکان k ام قرار گیرد، نتیجه می گیریم که این عنصر لولا، k امین کوچکترین عنصر لیست بوده است.
• مرتب سازی سریع از همان آرایه ی اصلی جهت مرتب کردن داده ها استفاده می کند ولی باید توجه داشته باشید که به علت بازگشتی بودن به حافظه پشته نیاز دارد. اثبات می شود در بدترین حالت عمق پشته بازگشتی از مرتبه خواهد بود  و در حالت متوسط فضای مورد نیاز پشته  است.
• اگر تمام عناصر آرایه با هم برابر باشند در واقع آرایه مرتب بوده و زمان Quick Sort بدترین حالت یعنی می شود.

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

فهرست

فصل اول: پیچیدگی زمانی و مرتبه اجرایی فصل دوم: روش تقسیم و غلبه فصل سوم: برنامه نویسی پویا فصل چهارم: روش حریصانه پاسخ نهایی  تمرین ها    

• نویسندگان: حمیدرضا مقسّمی - مریم غلامی - پریسا دانشجو
• انتشارات: گسترش علوم پایه