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

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

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

آموزش طراحی الگوریتم

»

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

ادامه ...

یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی معتبر همچون ACM این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟

کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده‌ی موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات که برای هر علاقه‌مند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.

ادامه ...

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

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

ادامه ...

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

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

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

ادامه ...

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

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

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

ادامه ...

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

   

 

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