یکی از سوالات رایج علاقمندان شرکت در مسابقات برنامه‌نویسی معتبر همچون ACM، این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟
کتاب Art ofProgramming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات، که برای هر علاقمند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.
در قسمتی از کتاب، نویسنده به مباحثی اشاره می‌کند که آشنایی و تسلط بر آنها برای کسب موفقیت در مسابقات برنامه‌نویسی بسیار کارآمد است. در ادامه قسمتی از این مباحث شرح داده شده است. بیشتر این مباحث در کتاب به صورت مبسوط بررسی شده‌اند.
1- اعداد اول، پیمانه‌ها و سایر مفاهیم نظریه اعداد: مباحث مربوط به نظریه اعداد از جمله مباحث ظریف در طراحی سوالات مسابقات برنامه‌نویسی هستند. تعاریف و قضایای بسیاری در نظریه اعداد وجود دارند که بسیاری از محاسبات حجیم را ساده کرده و از صرف هزینه در محاسبات جلوگیری می‌کنند.
2- فاکتوریل، مفاهیم شمارش و اصول ترکیبیات: مباحث شمارشی یکی از مباحث کاربردی ریاضیات است که در سوالات مسابقات برنامه‌نویسی در شکل‌های مختلف استفاده می‌شوند. رابطه‌های مربوط به جایگشت و ترکیب عناصر به صورت ساده، حلقوی و مسائلی از این دست بیشترین کاربرد و جلوه را در مسائل مختلف دارند. مساله مربی ناامید نمونه‌ای از این مسائل است که در مطالب قبلی بررسی شده است.
3- دنباله‌های اعداد: از جمله دنباله‌های عددی پرکاربرد مسائل شمارشی، دنباله اعداد فیبوناچی و دنباله اعداد کاتالان هستند که کاربرد و روش‌های محاسبه جملات آنها در مطالب قبلی ارائه شده است.
4- مساله طولانی‌ترین زیردنباله مشترک (LCS): در این مساله هدف یافتن طولانی‌ترین زیردنباله مشترک بین دو دنباله است. در این زیردنباله متوالی بودن عناصر اهمیتی نداشته و تنها ترتیب آنها مهم است. به عنوان مثال، LCS برای دو دنباله ABCDEFGH و EDAGBCFH زیر دنباله ABCFH است. برای حل این مساله راه‌های مختلفی وجود دارد که استفاده از روش برنامه‌نویسی پویا یکی از آنها است.
5- مساله طولانی‌ترین زیردنباله مرتب: در این مساله هدف یافتن طولانی‌ترین زیردنباله از یک دنباله است که عناصر آن به صورت صعودی (LIS) یا نزولی (LDS) مرتب باشند. برای حل این مساله نیز می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
6- مساله فاصله ویرایش یا حجم ویرایش (Edit Distance): هدف از این مساله، یافتن حداقل تعداد عملیاتی است که طی آن می‌توان یک دنباله را به یک دنباله دیگر تبدیل کرد. این عملیات عموما اعمال درج، حذف و جابجایی است که ممکن است اعمال دیگری نیز اضافه شود. روش برنامه‌نویسی پویا در این مورد نیز کاربرد دارد.
7- مساله کوله‌پشتی صفر و یک: این مساله از جمله مسائل مشهور طراحی الگوریتم‌ها است که در مورد روش‌های مختلف حل آن بحث‌های بسیاری شده است. در این مساله هدف یافتن بهترین انتخاب برای پر کردن یک کوله‌پشتی با لوازم با ارزشی از وزن‌های مختلف است، به طوری که وزن لوازم بیشتر از قدرت تحمل کوله‌پشتی نبوده و در عین حال ارزش آنها بیشینه باشد. روش حریصانه اولین ایده‌ای است که به ذهن می‌رسد. اما در مورد مساله کوله‌پشتی صفر و یک همواره بهترین پاسخ توسط این روش تولید نمی‌شود. روش برنامه‌نویسی پویا در این مساله هم به کار می‌آید.
8- مساله خرد کردن پول: در این مساله هدف تولید مبلغ مشخصی پول با حداقل استفاده از سکه‌ها و اسکناس‌های موجود است. در مورد این مساله نیز راهکارهایی با استفاده از روش‌های حریصانه و برنامه‌نویسی پویا ارائه شده است، که روش اول لزوما به جواب بهینه ختم نمی‌شود.
9- مساله ضرب زنجیره‌ای ماتریس‌ها: ضرب چندین ماتریس در یکدیگر خاصیت شرکت‌پذیری داشته، و می‌توان به روش‌های مختلف این عملیات را انجام داد. بهترین ترتیب ضربی که حداقل تعداد عملیات ضرب را داشته باشد هدف اصلی این مساله است.
10- مساله حداکثر مجموع: هدف از این مساله یافتن یک زیردنباله متوالی از اعداد یک دنباله است که حداکثر مجموع ممکن را داشته باشند. نمونه دو بعدی آن در مورد ماتریس‌ها و زیرماتریس‌های بیشینه در مطالب قبلی بررسی شده است.
11- گراف، پیمایش‌ها و عملیات جستجو: گراف‌ها و انواع آن از جمله ابزارهای بسیار پرکاربرد در حل مسائل برنامه‌نویسی هستند. در این میان روش‌های پیمایش و جستجوی گراف قسمت مهمی را به خود اختصاص می‌دهند. در یک گراف - که ممکن است وزن‌دار و جهت‌دار نیز باشد - روش‌های پیمایش و جستجوی مختلفی وجود دارد که قسمت عمده‌ای از آنها در مباحث طراحی الگوریتم و هوش مصنوعی مورد بررسی قرار می‌گیرند. چنین عملیاتی کاربرد بسیار وسیعی در حل مسائل الگوریتمی و یافتن جواب مطلوب از میان جواب‌های مختلف دارد. جستجوهای ناآگاهانه‌ای مانند جستجوی اول عمق (DFS)، جستجوی اول عمق عمیق‌شونده تکراری (DF-ID)، جستجوی اول سطح (BFS)، جستجو با هزینه یکنواخت (UCS)، جستجوی عمق محدود (DLS)، و جستجوهای آگاهانه‌ای مانند جستجوی اولین بهترین حریصانه (Greedy Best First) و جستجوی *A از جمله روش‌های جستجوی مشهور در این حوزه هستند.
12- مساله کوتاهترین مسیر در گراف: یافتن کوتاهترین مسیر بین دو راس از یک گراف از جمله مسائل کلاسیک و پرکاربرد طراحی الگوریتم‌ها است. اگر گراف پیوسته باشد به طور حتم کوتاهترین مسیر بین دو راس وجود خواهد داشت. الگوریتم فلوبد-وارشال یک الگوریتم مبتنی بر روش برنامه‌نویسی پویا است که با مرتبه اجرایی چندجمله‌ای اطلاعات کوتاهترین مسیر بین هر دو راس دلخواه گراف (با وزن‌های نامنفی) را تولید می‌کند.
13- مساله درخت پوشای کمینه (MST): منظور از درخت پوشا درختی است که با تعدادی از یال‌های گراف، تمامی رئوس را به یکدیگر متصل می‌کند. هر گرافی ممکن است شامل چندین درخت پوشا باشد. اگر گراف وزن‌دار باشد، درختی که مجموع وزن یال‌های آن حداقل مقدار ممکن را داشته باشد، درخت پوشای کمینه نامیده می‌شود. الگوریتم‌های پریم و کروسکال روش‌های مشهور تولید درخت پوشای کمینه با مرتبه‌های چندجمله‌ای هستند که با استفاده از روش حریصانه چنین درختی را تولید می‌کنند.
توجه: آنچه که مطرح شد تمام مباحث مورد نیاز جهت آمادگی برای چنین مسابقاتی نیست. اگرچه در ظاهر بعضی از این مسائل کاربرد چندانی نداشته، یا قابل توسعه نیستند؛ اما درک مفهوم و روش حل آنها دید وسیعتری را برای حل مسائل الگوریتمی فراهم می‌کند.
منبع: http://www.algorithmha.ir
