سبک و سیاق طراحی سوال در مسابقات برنامه نویسی
به بهانه برگزاری فینال مسابقات برنامه نویسی بیان
سومین دور از مسابقات برنامه نویسی بیان با برگزاری مرحله‌ی فینال در تاریخ ١١ اردیبهشت ٩٤ به پایان خواهد رسید. راه یافتگان این دوره از بیست کشور جهان گرد هم خواهند آمد تا در کنار ٥٠ برنامه‌نویس ایرانی مهارت‌های خود را در زمینه‌ی برنامه‌نویسی بسنجند. به بهانه‌ی برگزاری این مسابقات تصمیم گرفتیم به سبک و سیاق طراحی سوالات برنامه نویسی مطرح شده در مسابقات مختلف در سرتاسر جهان بپردازیم.
در سال‌های گذشته مسابقات برنامه‌نویسی به طور وسیع‌ای گسترش یافته‌اند و در حال حاضر دوست‌داران برنامه‌نویسی برای شرکت در این مسابقات گزینه‌های زیادی برای انتخاب دارند. بدون شک یکی از مهمترین کلید‌های موفقیت در این مسابقات تمرین مداوم و حل مسائل گوناگون است. در کنار این موضوع نکته‌ای هست که در درجه‌ی اول باید به آن توجه داشت و آن این است که اغلب مسابقات برنامه نویسی بخصوص مسابقات معتبر ICPC نه بر روی مباحث مهندسی نرم‌افزار بلکه صرفا بر روی حل مسئله تمرکز دارند. بنابراین تمرین در حوزه‌ی برنامه‌نویسی کاربردی که در دنیای واقعی توسعه نرم‌افزار با آن روبرو هستیم کمک چندانی به موفقیت در این مسابقات نخواهد کرد.
با توجه کردن به سوالاتی که تا کنون در مسابقات مختلف مطرح شده‌اند می‌توان دریافت که چه مباحثی بیشتر در حل سوالات به کار بسته می‌شوند و این اولین گام در آماده شدن برای مسابقات برنامه‌نویسی مختلف برای هر فردی، چه تازه‌کار و چه باتجربه است.
مسائل آسان
بیشتر افراد ابتدا با مسائل آسان شروع به کار می‌کنند. منظور از مسائل آسان مسائلی هستند که باید دقیقا آن‌چه را که از شما خواسته شده پیاده‌سازی کنید، به عنوان مثال پیاده‌سازی آن‌چه که به طور مستقیم در شرح سوال به آن اشاره شده. گرچه این دسته از سوالات به ندرت در مسابقات مطرح می‌شوند اما برای حل آن‌ها با مواردی روبرو خواهید شد که در حل مسائل دشوارتر به شما کمک خواهند کرد. این مسائل غالبا به کمک توانایی‌های اولیه برنامه‌نویسی قابل حل هستند و به کارگیری الگوریتم‌های پیچیده و ریاضیات عمیق را نمی‌طلبند.
ساختمان داده‌ها
پیاده سازی ساختمان داده‌های اولیه مانند پشته و صف از موارد ابتدای است که باید بتوانید انجام دهید. گرچه شاید برای شروع کار چندان هم آسان نباشد، اما درک درست ساختمان داده‌ها، تلاش برای پیاده‌سازی آن‌ها و بررسی کد‌های نوشته شده توسط دیگران شما را برای رویارویی با مسائل دشوار در مسابقات آماده خواهد کرد.
کار با رشته‌ها
رشته‌ها در اغلب مسابقات برای حل مسائل به کار برده می‌شوند. بیشتر سوالات مربوط به این مبحث الگوریتم پیچیده‌ای ندارند ولی پیاده‌سازی آن‌ها دشوار است. در این مسائل آشنایی با توابع کتابخانه‌ای و فوت و فن‌های هوشمندانه نقش مهم‌تری از دانستن الگوریتم ایفا می‌کنند. به عنوان مثال سوال اول مسابقات انتخابی بیان در سال ٩١ مربوط به کار با رشته‌ها بوده است. سوالات بیشتر در مورد کار با رشته‌ها را اینجا ببینید.
جستجو و مرتب‌سازی
به دلیل وجود الگوریتم‌های کلاسیک جستجو و مرتب‌سازی در کتابخانه‌های استاندارد اغلب زبان‌های برنامه‌نویسی، تمرکز برنامه‌نویسان غالبا بر استفاده از این الگوریتم‌هاست نه فلسفه و پیاده‌سازی آن‌ها، با این حال دانستن اساس تئوری آن‌ها، همانند ساختمان داده‌های مختلف ضروری است.
کاربرد ریاضیات
حل تعداد زیادی از سوالاتی که در مسابقات برنامه‌نویسی مطرح می‌شوند، بیش از مهارت بالا در برنامه‌نویسی نیاز به مهارت در ریاضیات نیاز دارند. ریاضیات پرکاربرد در مسابقات را می‌توان به دسته‌های زیر تقسیم کرد:
علم حساب
علم حساب در کامپیوتر دقیقا آن چیزی که در دوران دبیرستان آموخته می‌شود نیست. در واقع آن‌چه که با آن سر و کار داریم مربوط به معماری کامپیوتر است. برنامه‌نویسان باید نحوه‌ی کار کامپیوتر با اعداد صحیح و حقیقی، بیت‌ها و باینری را بلد بوده و قادر به کدنویسی برای اعداد با دقت بالا، کسر‌ها و اعداد مختلط باشند.
ترکیبیات
ترکیبیات یکی از مهمترین شاخه‌های ریاضیات بوده و در حل مسائل مربوط به شمارش و احتمال کاربرد زیادی دارد.
در کنار اصول اولیه، مطالعه‌ی فرمول‌ها و قضایا و مطالعات موردی مثل دنباله‌های مهم اعداد صحیح موجب کسب درک کافی از ترکیبیات خواهد شد.
نظریه‌ی اعداد
نظریه‌ی اعداد از محبوب‌ترین مباحثی است که در سوالات مسابقات مطرح می‌شود، نظریه‌ی اعداد موضوع عمیق و گسترده‌ای است و به همین دلیل داشتن پیش‌زمینه‌ی کافی در مورد اعداد اول، بزرگترین مقسوم علیه مشترک، هم‌نهشتی و تجانس کافی است. لیستی از سوالات مطرح شده برای نظریه‌ی اعداد را اینجا می‌توانید ببینید.
بازی‌ها
منظور از بازی‌ها بازی‌های ترکیبیاتی است. بازی‌های موردی دیگری هم در سوالات مطرح می‌شوند که به کمک ریاضیات قابل حل هستند، برخی دیگر از آن‌ها نیز با روش‌هایی چون برنامه‌نویسی پویا و الگوریتم‌های مربوط به گراف‌ها حل‌شدنی هستند. برای آشنایی با سوالات مربوط به این دسته می‌توانید اینجا را ببینید.
مفاهیم دیگر ریاضیات و الگوریتم‌ها همچون ضرب ماتریس‌ها، حذف گاوسی، جایگشت، آنالیز عددی نیز در حل سوالات کاربرد دارند.
تکنیک‌های طراحی الگوریتم
گرچه ریاضیات نقش مهمی در حل سوالات ایفا می‌کند، اما بدون مهارت در طراحی الگوریتم‌ها و آشنایی با تکنیک‌های کدنویسی نمی‌توان مسئله‌ای را حل کرد، در هر‌حال سئوالاتی که با آن‌ها روبرو می‌شویم سئوالات برنامه‌نویسی هستند، نه ریاضیات.
Brute Force
یکی از مهمترین تکنیک‌های حل مسئله تکنیک Brute Force است که بر روی بسیاری از مسائل که در آن‌ها بازده از اهمیت خاصی برخوردار نیست قابل اجراست. در کنار الگوریتم‌های ساده‌ی brute force که تنها شامل تعداد اندکی حلقه‌های تو در تو هستند، باید با پیمایش معکوس یا backtracking نیز آشنا بود.
برنامه‌نویسی پویا
برنامه‌نویسی پویا الگویی برای تحلیل مسائل و طراحی الگوریتم است. با وجود این‌که در ابتدا درک آن کار آسانی نیست، اما بعد از درک و حل تعداد بیشتری از مسائل، برنامه‌نویسی پویا یکی از کاربردی‌ترین ابزارها برای حل مسئله خواهد بود. لیستی از مسائل مربوط به برنامه‌نویسی پویا را می‌توانید از اینجا پیدا کنید.
ساختمان داده‌ها
ساختمان داده‌ها نقش مهمی را در حل مسائلی که زمان فاکتور مهمی در حل آن‌هاست ایفا می‌کنند. در بیشتر مسابقاتی که در اروپا و آسیا برگزار می‌شوند بحث ساختمان داده‌ها مکررا مطرح شده است. البته باید دانست که ساختمان داده‌ها در حل مسائل مسابقات IOI کاربرد بیشتری دارند.
نمونه‌ای از سوالاتی که در آن باید از ساختمان داده (درخت) برای حل استفاده کرد، سوال آخر مرحله‌ی حذفی بیان در سال ٩٣ بوده است. همچنین لیستی از سوالات خوب مربوط به این مبحث را اینجا می‌توانید ببینید.
تکنیک‌های طراحی الگوریتم ترکیبی
الگوریتم‌های دیگری مانند الگوریتم‌های تقسیم و حل، الگوریتم‌های حریصانه و ... نیز وجود دارند که بسیار مهم بوده و در مسابقات پرتکرار هستند. سوالات پیچیده‌تر معمولا برای حل نیاز به ترکیب و استفاده از تکنیک‌های مختلف طراحی الگوریتم دارند.
نظریه‌ی گراف‌ها
به ندرت در مسابقات مختلف سوالی از نظریه‌ی گراف مطرح نشده است. مسابقات فینال جهانی در سال‌های اخیر شامل سوالاتی از نظریه‌ی گراف بوده که تیم‌های برتر را از سایر تیم‌ها متمایز کرده است. سوالات مطرح شده در مسابقات ناحیه‌ی اروپا منبع مناسبی برای آشنایی با حل مسائل نظریه‌ی گراف هستند. در این لینک می‌توانید سوالات مطرح شده در زمینه‌ی نظریه‌ی گراف‌ها را ببینید.
هندسه
سوالاتی که مربوط به هندسه هستند اغلب پیچیده یا سخت هستند و به راحتی می‌توان در حل آن‌ها دچار مشکل شد. برخی سوالات هندسه در طول یک مسابقه غیر قابل حل به نظر می‌آیند با این حال از عهده‌ی تعداد زیادی از آن‌ها هم می‌توان برآمد. دانستن هندسه‌ی مقدماتی، هندسه‌ی تحلیلی و مثلثات برای حل این سوالات کافی است. از آنجایی که تقریبا در تمامی مسابقات افراد اجازه‌ی همراه داشتن برگه‌های پرینت شده را دارند، همراه داشتن فرمول‌ها و مواردی که به صورت روتین در حل مسائل هندسه کاربرد دارند ضروری است. برای حل مسائلی که بیشتر الگوریتم گرا هستند دانستن مفاهیم بنیادی هندسه‌ی محاسباتی نیز ضروری است. نمونه‌ای از سوالات هندسه‌ی مطرح شده در مسابقات، سوال چهارم مرحله‌ی انتخابی مسابقات بیان در سال ٩١ بوده است. برای آشنایی با سوالات این مبحث از این لینک می‌توانید استفاده کنید.
همانطور که قبلا گفته شد، مهمترین کلید موفقیت در مسابقات تمرین و حل مسائل مختلف است. منابع آنلاین متعددی وجود دارند که با مراجعه به آن‌ها می‌توانید نمونه سوالات مطرح شده در مسابقات مختلف و همچنین سوالات با تیپ‌های مشابه به سوالات مسبقات را در آن‌ها پیدا کنید. به علاوه حل مسائل کلاسیکی که در اغلب کتاب‌ها و منابع وجود دارند را نیز نباید فراموش کرد.
منبع: وبلاگینا
