یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی (مانند ACM-ICPC) این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟
کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی به چنین سوالاتی نیز پاسخ داده است. این کتاب با بحث
در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده موثر از
مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان
مسابقات که برای هر علاقه‌مند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید
است.
در قسمتی از کتاب نویسنده به مباحثی اشاره می‌کند که
آشنایی و تسلط بر آنها برای کسب موفقیت در مسابقات برنامه‌نویسی بسیار کارآمد است.
در ادامه قسمتی از این مباحث شرح داده شده است. بیشتر این مباحث در کتاب به صورت
مبسوط بررسی شده‌اند.
اعداد اول، پیمانه‌ها و سایر مفاهیم نظریه
اعداد
[برگرد بالا]
مباحث مربوط به نظریه اعداد از جمله مباحث ظریف در
طراحی سوالات مسابقات برنامه‌نویسی هستند. تعاریف و قضایای بسیاری در نظریه اعداد
وجود دارند که بسیاری از محاسبات حجیم را ساده کرده و از صرف هزینه در محاسبات
جلوگیری می‌کنند.
فاکتوریل، مفاهیم شمارش و اصول
ترکیبیات
[برگرد بالا]
مباحث شمارشی یکی از مباحث کاربردی ریاضیات است که در
سوالات مسابقات برنامه‌نویسی در شکل‌های مختلف استفاده می‌شوند. رابطه‌های مربوط به
جایگشت و ترکیب عناصر به صورت ساده، حلقوی و مسائلی از این دست بیشترین کاربرد و
جلوه را در مسائل مختلف دارند. مسئله مربی ناامید نمونه‌ای از این مسائل است.
دنباله‌های اعداد
[برگرد بالا]
از جمله دنباله‌های عددی پرکاربرد مسائل
شمارشی دنباله اعداد فیبوناچی و دنباله اعداد کاتالان هستند که کاربرد و روش‌های محاسبه جملات آنها در
مطالب قبلی ارائه شده است.
مسئله طولانی‌ترین زیردنباله مشترک
(LCS)
[برگرد بالا]
در این مسئله هدف یافتن طولانی‌ترین زیردنباله مشترک
بین دو دنباله است. در این زیردنباله متوالی بودن عناصر اهمیتی نداشته و تنها ترتیب
آنها مهم است. به عنوان مثال، برای دو دنباله ABCDEFGH و EDAGBCFH زیردنباله
ABCFH طولانی‌ترین زیردنباله مشترک است. برای حل این مسئله راه‌های مختلفی وجود
دارد که استفاده از روش برنامه‌نویسی پویا یکی از آنها است.
مسئله طولانی‌ترین زیردنباله
مرتب
[برگرد بالا]
در این مسئله هدف یافتن طولانی‌ترین زیردنباله از یک
دنباله است که عناصر آن به صورت صعودی (LIS) یا نزولی (LDS) مرتب باشند. برای حل
این مسئله نیز می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
مسئله فاصله ویرایش یا حجم ویرایش (Edit
Distance)
[برگرد بالا]
هدف از این مسئله یافتن حداقل تعداد عملیاتی است که طی آن
می‌توان یک دنباله را به دنباله دیگری تبدیل کرد. این عملیات عموما اعمال درج،
حذف و جابجایی هستند که ممکن است اعمال دیگری نیز اضافه شود. روش برنامه‌نویسی پویا
در این مورد نیز کاربرد دارد.
مسئله کوله‌پشتی صفر و یک
[برگرد بالا]
این مسئله از جمله مسائل مشهور طراحی الگوریتم‌ها است که
در مورد روش‌های مختلف حل آن بحث‌های بسیاری شده است. در این مسئله هدف یافتن
بهترین انتخاب برای پر کردن یک کوله‌پشتی با لوازم با ارزشی از وزن‌های مختلف است،
به طوری که وزن لوازم بیشتر از قدرت تحمل کوله‌پشتی نبوده و در عین حال ارزش آنها
بیشینه باشد. روش حریصانه اولین ایده‌ای است که به ذهن می‌رسد؛ اما در مورد
مسئله کوله‌پشتی صفر و یک همواره بهترین پاسخ توسط این روش تولید نمی‌شود. روش
برنامه‌نویسی پویا در این مسئله هم به کار می‌آید.
مسئله خرد کردن پول
[برگرد بالا]
در این مسئله هدف تولید مبلغ مشخصی پول با حداقل استفاده
از سکه‌ها و اسکناس‌های موجود است. در مورد این مسئله نیز راهکارهایی با استفاده از
روش‌های حریصانه و برنامه‌نویسی پویا ارائه شده است که روش اول لزوما به جواب بهینه
ختم نمی‌شود.
[برگرد بالا]
ضرب چندین ماتریس در یکدیگر خاصیت شرکت‌پذیری داشته و
می‌توان به روش‌های مختلف این عملیات را انجام داد. بهترین ترتیب ضربی که حداقل
تعداد عملیات ضرب را داشته باشد هدف اصلی این مسئله است.
[برگرد بالا]
هدف از این مسئله یافتن یک زیردنباله متوالی از یک
دنباله است که حداکثر مجموع ممکن را داشته باشند. نمونه دو بعدی آن در مورد
ماتریس‌ها و زیرماتریس‌های بیشینه در مطالب قبلی بررسی شده است.
گراف، پیمایش‌ها و عملیات جستجو
[برگرد بالا]
گراف‌ها و انواع آن از جمله ابزارهای بسیار پرکاربرد در
حل مسائل برنامه‌نویسی هستند. در این میان روش‌های پیمایش و جستجوی گراف قسمت مهمی
را به خود اختصاص می‌دهند. در یک گراف - که ممکن است وزن‌دار و جهت‌دار نیز باشد -
روش‌های پیمایش و جستجوی مختلفی وجود دارد که قسمت عمده‌ای از آنها در مباحث طراحی
الگوریتم و هوش مصنوعی مورد بررسی قرار می‌گیرند. چنین عملیاتی کاربرد بسیار وسیعی
در حل مسائل الگوریتمی و یافتن جواب مطلوب از میان جواب‌های مختلف دارد. جستجوهای
ناآگاهانه‌ای مانند جستجوی اول عمق (DFS)، جستجوی اول عمق عمیق‌شونده تکراری
(DF-ID)، جستجوی اول سطح (BFS)، جستجو با هزینه یکنواخت (UCS)، جستجوی
عمق محدود (DLS) و جستجوهای آگاهانه‌ای مانند جستجوی اولین بهترین حریصانه (Greedy
Best First) و جستجوی *A از جمله روش‌های جستجوی مشهور در این حوزه هستند.
مسئله کوتاهترین مسیر در گراف
[برگرد بالا]
یافتن کوتاهترین مسیر بین دو گره از یک گراف از جمله
مسائل کلاسیک و پرکاربرد طراحی الگوریتم‌ها است. اگر گراف پیوسته و بدون جهت باشد،
به طور حتم کوتاهترین مسیر بین دو گره وجود خواهد داشت. الگوریتم فلوید-وارشال یک الگوریتم مبتنی بر روش برنامه‌نویسی
پویا است که با مرتبه اجرایی چندجمله‌ای اطلاعات کوتاهترین مسیر بین هر دو گره
دلخواه گراف را تولید می‌کند. الگوریتم دایکسترا روش دیگری است که برای محاسبه کوتاهترین
مسیر از مبدأ ثابت به سایر گره‌های گراف مناسب است. مسئله آسانسورها نمونه‌ای از سوالات مسابقه ACM با راهکاری
از این حوزه است.
مسئله درخت پوشای کمینه (MST)
[برگرد بالا]
منظور از درخت پوشا درختی است که با تعدادی از یال‌های
گراف، تمامی گره‌ها را به یکدیگر متصل می‌کند. هر گراف ممکن است شامل چندین درخت
پوشا باشد. اگر گراف وزن‌دار باشد، درختی که مجموع وزن یال‌های آن حداقل مقدار ممکن
را داشته باشد، درخت پوشای کمینه نامیده می‌شود. الگوریتم‌های پریم و کروسکال
روش‌های مشهور تولید درخت پوشای کمینه با مرتبه‌های چندجمله‌ای هستند که با استفاده
از روش حریصانه چنین درختی را تولید می‌کنند.
توجه: آنچه که مطرح شد تمام مباحث مورد
نیاز جهت آمادگی برای چنین مسابقاتی نیست. اگرچه در ظاهر بعضی از این مسائل کاربرد
چندانی نداشته یا قابل توسعه نیستند؛ اما درک مفهوم و روش حل آنها دید وسیعتری را
برای حل مسائل الگوریتمی فراهم می‌کند.