الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب تکنیک‌های طراحی الگوریتم نوشته‌ها با برچسب تکنیک‌های طراحی الگوریتم - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

تکنیک‌های طراحی الگوریتم

»

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

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

ادامه ...

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه‌ی تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

1- داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه‌ی چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.

ادامه ...

یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش Divide and Conquer است که در زبان فارسی به صورت تقسیم و حل یا تقسیم و غلبه ترجمه شده است.

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

برای آشنایی بیشتر، چند الگوریتم که با روش حل و تقسیم پیاده‌سازی شده‌اند معرفی می‌شوند.

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
»  کتاب Competetive Programming
معرفی کتاب Competitive Programming برای علاقه‌مندان به شرکت در مسابقات برنامه‌نویسی و المپیاد کامپیوتر با قابلیت دانلود نسخه‌ی الکترونیکی
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  کتاب طراحی الگوریتم با رویکردی خلاقانه
معرفی کتاب Introduction to Algorithms: A Creative Approach  با قابلیت دانلود نسخه‌ی الکترونیکی
»  کتاب مقدمه‌ای بر الگوریتم‌ها
معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها با قابلیت دانلود
»  کتاب چالش‌های برنامه‌نویسی
معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود کتاب، فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
»  کتاب هنر مسابقات برنامه‌نویسی
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
برچسب‌ها
#تمرین المپیاد کامپیوتر #ترجمه فارسی سوالات کتاب Programming Challenges #ترجمه‌ی فارسی سوالات برنامه‌نویسی #نمونه سوال فارسی مسابقات ACM #منبع آموزشی #نمونه سوال مسابقه ACM #مسابقه برنامه نویسی #الگوریتم‌های مرتب‌سازی #سوالات برنامه‌نویسی #تکنیک‌های طراحی الگوریتم #آمادگی المپیاد کامپیوتر #آموزش برنامه‌نویسی ++C #ماتریس #Python #الگوریتم‌های حریصانه #الگوریتم دایکسترا #آموزش طراحی الگوریتم #درخت پوشا #الگوریتم‌های گراف #حل سوالات ACM-ICPC #پیمایش گراف #الگوریتم #آمادگی مسابقه ACM #نمونه سوالات مسابقه برنامه‌نویسی #سوالات UVa Online Judge #سوالات مسابقات برنامه‌نویسی بیان #جستجوی اول عمق #مسئله‌های برنامه‌نویسی #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #الگوریتم‌های عقبگرد #برنامه‌نویسی #سوالات چالشی برنامه‌نویسی #ویدئوی آموزشی #مسئله‌ی کوله‌پشتی #تمرین طراحی الگوریتم #ترجمه‌ی فارسی سوالات ACM #معرفی وب‌سایت #کتاب الگوریتم #وبلاگ #الگوریتم فلوید-وارشال #جستجوی اول سطح #مسابقات برنامه‌نویسی ACM #نمونه سوال فارسی مسابقه‌ی ACM #الگوریتم‌های بازگشتی #صف #حل مسئله‌‌ی الگوریتمی #نکات برنامه‌نویسی #ساختمان داده #الگوریتم‌های کوتاهترین مسیر #دانلود کتاب #الگوریتم‌های تقسیم و غلبه #کتاب مسابقات برنامه‌نویسی #مسابقه برنامه‌نویسی #کتاب الکترونیکی #آمادگی مسابقه برنامه‌نویسی #محاسبات ریاضی #حل سوالات Timus Online Judge #مسئله‌های الگوریتمی #الگوریتم‌های برنامه‌نویسی پویا #کتابخانه قالب استاندارد ++C #آموزش الگوریتم #مسأله‌های برنامه‌نویسی #حل سوالات مسابقات برنامه‌نویسی #درخت‌ها #حل سوالات UVa Online Judge #آموزش ساختمان داده‌ها #الگوریتم‌های مسیریابی #مسأله‌های الگوریتمی #گراف #تمرین مسابقه برنامه‌نویسی #ترجمه‌ی فارسی سوالات UVa Online Judge #نمونه سوال فارسی مسابقات برنامه‌نویسی #سوالات مسابقات ACM-ICPC #برنامه‌نویسی ++C #مسابقات برنامه‌نویسی