به بهانه برگزاری فینال مسابقات برنامه نویسی بیان
سبک و سیاق طراحی سوال در مسابقات برنامه نویسی
نوشته سعید چوبانی • 02 ارديبهشت 1394
سومین دور از مسابقات برنامه نویسی بیان با برگزاری مرحلهی فینال در تاریخ ١١ اردیبهشت ٩٤ به پایان خواهد رسید. راه یافتگان این دوره از بیست کشور جهان گرد هم خواهند آمد تا در کنار ٥٠ برنامهنویس ایرانی مهارتهای خود را در زمینهی برنامهنویسی بسنجند. به بهانهی برگزاری این مسابقات تصمیم گرفتیم به سبک و سیاق طراحی سوالات برنامه نویسی مطرح شده در مسابقات مختلف در سرتاسر جهان بپردازیم.
در سالهای گذشته مسابقات برنامهنویسی به طور وسیعای گسترش یافتهاند و در حال حاضر دوستداران برنامهنویسی برای شرکت در این مسابقات گزینههای زیادی برای انتخاب دارند. بدون شک یکی از مهمترین کلیدهای موفقیت در این مسابقات تمرین مداوم و حل مسائل گوناگون است. در کنار این موضوع نکتهای هست که در درجهی اول باید به آن توجه داشت و آن این است که اغلب مسابقات برنامه نویسی بخصوص مسابقات معتبر ICPC نه بر روی مباحث مهندسی نرمافزار بلکه صرفا بر روی حل مسئله تمرکز دارند. بنابراین تمرین در حوزهی برنامهنویسی کاربردی که در دنیای واقعی توسعه نرمافزار با آن روبرو هستیم کمک چندانی به موفقیت در این مسابقات نخواهد کرد.
با توجه کردن به سوالاتی که تا کنون در مسابقات مختلف مطرح شدهاند میتوان دریافت که چه مباحثی بیشتر در حل سوالات به کار بسته میشوند و این اولین گام در آماده شدن برای مسابقات برنامهنویسی مختلف برای هر فردی، چه تازهکار و چه باتجربه است.
مسائل آسان
بیشتر افراد ابتدا با مسائل آسان شروع به کار میکنند. منظور از مسائل آسان مسائلی هستند که باید دقیقا آنچه را که از شما خواسته شده پیادهسازی کنید، به عنوان مثال پیادهسازی آنچه که به طور مستقیم در شرح سوال به آن اشاره شده. گرچه این دسته از سوالات به ندرت در مسابقات مطرح میشوند اما برای حل آنها با مواردی روبرو خواهید شد که در حل مسائل دشوارتر به شما کمک خواهند کرد. این مسائل غالبا به کمک تواناییهای اولیه برنامهنویسی قابل حل هستند و به کارگیری الگوریتمهای پیچیده و ریاضیات عمیق را نمیطلبند.
ساختمان دادهها
پیاده سازی ساختمان دادههای اولیه مانند پشته و صف از موارد ابتدای است که باید بتوانید انجام دهید. گرچه شاید برای شروع کار چندان هم آسان نباشد، اما درک درست ساختمان دادهها، تلاش برای پیادهسازی آنها و بررسی کدهای نوشته شده توسط دیگران شما را برای رویارویی با مسائل دشوار در مسابقات آماده خواهد کرد.
کار با رشتهها
رشتهها در اغلب مسابقات برای حل مسائل به کار برده میشوند. بیشتر سوالات مربوط به این مبحث الگوریتم پیچیدهای ندارند ولی پیادهسازی آنها دشوار است. در این مسائل آشنایی با توابع کتابخانهای و فوت و فنهای هوشمندانه نقش مهمتری از دانستن الگوریتم ایفا میکنند. به عنوان مثال سوال اول مسابقات انتخابی بیان در سال ٩١ مربوط به کار با رشتهها بوده است. سوالات بیشتر در مورد کار با رشتهها را اینجا ببینید.
جستجو و مرتبسازی
به دلیل وجود الگوریتمهای کلاسیک جستجو و مرتبسازی در کتابخانههای استاندارد اغلب زبانهای برنامهنویسی، تمرکز برنامهنویسان غالبا بر استفاده از این الگوریتمهاست نه فلسفه و پیادهسازی آنها، با این حال دانستن اساس تئوری آنها، همانند ساختمان دادههای مختلف ضروری است.
کاربرد ریاضیات
حل تعداد زیادی از سوالاتی که در مسابقات برنامهنویسی مطرح میشوند، بیش از مهارت بالا در برنامهنویسی نیاز به مهارت در ریاضیات نیاز دارند. ریاضیات پرکاربرد در مسابقات را میتوان به دستههای زیر تقسیم کرد:
علم حساب
علم حساب در کامپیوتر دقیقا آن چیزی که در دوران دبیرستان آموخته میشود نیست. در واقع آنچه که با آن سر و کار داریم مربوط به معماری کامپیوتر است. برنامهنویسان باید نحوهی کار کامپیوتر با اعداد صحیح و حقیقی، بیتها و باینری را بلد بوده و قادر به کدنویسی برای اعداد با دقت بالا، کسرها و اعداد مختلط باشند.
ترکیبیات
ترکیبیات یکی از مهمترین شاخههای ریاضیات بوده و در حل مسائل مربوط به شمارش و احتمال کاربرد زیادی دارد.
در کنار اصول اولیه، مطالعهی فرمولها و قضایا و مطالعات موردی مثل دنبالههای مهم اعداد صحیح موجب کسب درک کافی از ترکیبیات خواهد شد.
نظریهی اعداد
نظریهی اعداد از محبوبترین مباحثی است که در سوالات مسابقات مطرح میشود، نظریهی اعداد موضوع عمیق و گستردهای است و به همین دلیل داشتن پیشزمینهی کافی در مورد اعداد اول، بزرگترین مقسوم علیه مشترک، همنهشتی و تجانس کافی است. لیستی از سوالات مطرح شده برای نظریهی اعداد را اینجا میتوانید ببینید.
بازیها
منظور از بازیها بازیهای ترکیبیاتی است. بازیهای موردی دیگری هم در سوالات مطرح میشوند که به کمک ریاضیات قابل حل هستند، برخی دیگر از آنها نیز با روشهایی چون برنامهنویسی پویا و الگوریتمهای مربوط به گرافها حلشدنی هستند. برای آشنایی با سوالات مربوط به این دسته میتوانید اینجا را ببینید.
مفاهیم دیگر ریاضیات و الگوریتمها همچون ضرب ماتریسها، حذف گاوسی، جایگشت، آنالیز عددی نیز در حل سوالات کاربرد دارند.
تکنیکهای طراحی الگوریتم
گرچه ریاضیات نقش مهمی در حل سوالات ایفا میکند، اما بدون مهارت در طراحی الگوریتمها و آشنایی با تکنیکهای کدنویسی نمیتوان مسئلهای را حل کرد، در هرحال سئوالاتی که با آنها روبرو میشویم سئوالات برنامهنویسی هستند، نه ریاضیات.
Brute Force
یکی از مهمترین تکنیکهای حل مسئله تکنیک Brute Force است که بر روی بسیاری از مسائل که در آنها بازده از اهمیت خاصی برخوردار نیست قابل اجراست. در کنار الگوریتمهای سادهی brute force که تنها شامل تعداد اندکی حلقههای تو در تو هستند، باید با پیمایش معکوس یا backtracking نیز آشنا بود.
برنامهنویسی پویا
برنامهنویسی پویا الگویی برای تحلیل مسائل و طراحی الگوریتم است. با وجود اینکه در ابتدا درک آن کار آسانی نیست، اما بعد از درک و حل تعداد بیشتری از مسائل، برنامهنویسی پویا یکی از کاربردیترین ابزارها برای حل مسئله خواهد بود. لیستی از مسائل مربوط به برنامهنویسی پویا را میتوانید از اینجا پیدا کنید.
ساختمان دادهها
ساختمان دادهها نقش مهمی را در حل مسائلی که زمان فاکتور مهمی در حل آنهاست ایفا میکنند. در بیشتر مسابقاتی که در اروپا و آسیا برگزار میشوند بحث ساختمان دادهها مکررا مطرح شده است. البته باید دانست که ساختمان دادهها در حل مسائل مسابقات IOI کاربرد بیشتری دارند.
نمونهای از سوالاتی که در آن باید از ساختمان داده (درخت) برای حل استفاده کرد، سوال آخر مرحلهی حذفی بیان در سال ٩٣ بوده است. همچنین لیستی از سوالات خوب مربوط به این مبحث را اینجا میتوانید ببینید.
تکنیکهای طراحی الگوریتم ترکیبی
الگوریتمهای دیگری مانند الگوریتمهای تقسیم و حل، الگوریتمهای حریصانه و … نیز وجود دارند که بسیار مهم بوده و در مسابقات پرتکرار هستند. سوالات پیچیدهتر معمولا برای حل نیاز به ترکیب و استفاده از تکنیکهای مختلف طراحی الگوریتم دارند.
نظریهی گرافها
به ندرت در مسابقات مختلف سوالی از نظریهی گراف مطرح نشده است. مسابقات فینال جهانی در سالهای اخیر شامل سوالاتی از نظریهی گراف بوده که تیمهای برتر را از سایر تیمها متمایز کرده است. سوالات مطرح شده در مسابقات ناحیهی اروپا منبع مناسبی برای آشنایی با حل مسائل نظریهی گراف هستند. در این لینک میتوانید سوالات مطرح شده در زمینهی نظریهی گرافها را ببینید.
هندسه
سوالاتی که مربوط به هندسه هستند اغلب پیچیده یا سخت هستند و به راحتی میتوان در حل آنها دچار مشکل شد. برخی سوالات هندسه در طول یک مسابقه غیر قابل حل به نظر میآیند با این حال از عهدهی تعداد زیادی از آنها هم میتوان برآمد. دانستن هندسهی مقدماتی، هندسهی تحلیلی و مثلثات برای حل این سوالات کافی است. از آنجایی که تقریبا در تمامی مسابقات افراد اجازهی همراه داشتن برگههای پرینت شده را دارند، همراه داشتن فرمولها و مواردی که به صورت روتین در حل مسائل هندسه کاربرد دارند ضروری است. برای حل مسائلی که بیشتر الگوریتم گرا هستند دانستن مفاهیم بنیادی هندسهی محاسباتی نیز ضروری است. نمونهای از سوالات هندسهی مطرح شده در مسابقات، سوال چهارم مرحلهی انتخابی مسابقات بیان در سال ٩١ بوده است. برای آشنایی با سوالات این مبحث از این لینک میتوانید استفاده کنید.
همانطور که قبلا گفته شد، مهمترین کلید موفقیت در مسابقات تمرین و حل مسائل مختلف است. منابع آنلاین متعددی وجود دارند که با مراجعه به آنها میتوانید نمونه سوالات مطرح شده در مسابقات مختلف و همچنین سوالات با تیپهای مشابه به سوالات مسبقات را در آنها پیدا کنید. به علاوه حل مسائل کلاسیکی که در اغلب کتابها و منابع وجود دارند را نیز نباید فراموش کرد.
جشن اختتامیه مسابقات برنامه نویسی بیان روز ۱۲ اردیبهشت در سالن همایشهای برج میلاد برگزار میشود و شرکت برای تمامی علاقهمندان آزاد است. برای ثبت نام میتوانید از این لینک استفاده کنید.
این مطلب توسط “ندا ضیا” تهیه و برای وبلاگینا ارسال شده است.
چیا چاره خواه
سلام. مطلب بسیار خوب و مفیدی بود. ممنون
سید امیر سجادی
مطلب بسیار خوبی بود. ممنون از شما
مسعود دانشی کهن
سلام
چرا سایت اینقدر بی برنامه شده ؟؟ دیگه مرتب بروز نمیشه
طراحی سایت
سلام
من فکر میکنم روز 11 اردیبهشت یک روز خوب باشه
تیم آسیا آی تی منتظر حضور شما هستش
دوربین مداربسته
مطلب خوبی بود.
ممنون
کرکره برقی
ممنون میشم بازم در این خصوص بنویسید.
شرکت دوربین مداربسته
متشکرم
راهبند
با سپاس
green card
نشکر
shikano
خیلی خوب بود ممنون از شما
شرکتها
کار جالبیه ممنون.
چاپ کارت ویزیت
خیلی عالی بود. برنامه نویس ها باید ذهن قوی داشته باشن واقعا.
بسم الله
سلام
بنده خدا
ممنون
استفاده کردیم
خوب بود
طراحی سایت
جالب بود . ممنوون
طراحی وب سایت
نتایج این مسابقه کی اعلام میشه
تور هند
خیی اطلاعت خوبی راجب مسابقات بودمن خودم خیلی دنیال همچین مسابقاتی هستم
ممنون از زحمتاتون
نمایندگی پنل پیامک
ممنون از اطلاعات مفیدتون
ایران اپس
مسابقه خیلی خوبی بود بین برنامه نویس ها. سایتتون خیلی خوبه ولی چرا دیر آپدیت می کنین؟!
آژانس های مسافرتی
بسیار عالی
ورسای
جالب بود
تور استانبول
بسیار خوب ، ممنون از مطلبتون
قالب وردپرس
با هال بود
تور تایلند
مرسی خیلی مطلب خوبی بود تشکر
تور تایلند
مرسی خیلی مطلب خوبی بود تشکر
پارک ریجنس
ممنونم
مونوپاد
ممنونم از سایت خوبتون موفق باشید
صبا
من یک بار در این مسابقات شرکت داشتم سطح خوبی داره
طراحی سایت
منم در این مسایفات شرکت کردم ، مسابقات خوبیه
فروش عمده روغن خوراکی
خیلی جالب بود برام
mybano.com
با سلام دستتون درد نکنه واقعا ممنون و متشکر
مدیریت سایت www.mybano.com
دوربین مداربسته
ممنونم
سفارش گل
خیلی خوب بود
سئو سایت
عالی بود .
سپاسگزارم .
طراحی سایت
ممنون از مطالب و سایت خوبتون.
طراحی سایت
با تشکر از سایت خوبتون.
طراحی لوگو
ممنون از به اشتراک گداری مطالب خوبتون/.
قاب گوشی
ممنونم عالی بود مرسی
فروشگاه عروسک
اطلاعات مفید و کارایی بود اگر می شه فیلم و یا کلیپ یکی از این مسابقات هم بگذارید ممنون از سایت خوبتون
دارا رامینی
این مسابقه میتونه یه نقطه پیشرفت و ارتباط ایرانیها با جهانیان باشه، امیدوارم بیان این مسابقه رو ادامه بده. راستی جناب زاد چرا وبلاگینارو ول کردین؟
تیغه کرکره بررقی
همیشه برام سوال بود تو اینطورر مسابقات چه نوع سوالاتی طرح می شود. ممنون از اطلاع رسانی شما.
برنامه نویسی اندروید
با سلام
ممنون از سایت خوبتون.
تور لحظه آخری
جالبههههه
طراحی سایت
با سلام و عرض ادب
خواستم تشکر کنم بابت مطالب خوب شما
لطفا به این رویه ادامه بدید و بیشتر مطالب بذارید.
تشکر
کامبوچا
خوب بود
طراحی سایت
بسیار عالی بود
موفق باشید
سمیه
مرسی
عالی
ملایی
سلام
خوب بود
برنامه نویسی اندروید
با سلام
ممنون از سایت خوبتون.
طراحی سایت
با سلام
ممنون از سایت خوبتون.
ماكاس
بيشتر به جاي برنامه نويسي بايد نخبه رشته علوم كامپيوتر باشي توي اين مسابقات ظاهرا
طراحي سايت
نمونه سوالاتش موجود نبود ؟
خانه ی وب سایت
البته اینجور هم که میگید نیست !
به این سادگیا !
ولی خوب بود مقالتون
ممنون خانوم ضیاء
وکیل کانادا
ممنونم عالی بود مرسی
چسب بتن
جالب بود ممنون
پمپ ایران
با سلام و سپاس بسیار عالی بود مرسی
دوربین مداربسته
سلام
ممنون از مطالب خوبتون , امیدوارم همیشه موفق باشید
پوسته وردپرس
عالب بود
طراحی لوگو
عالی مثل همیشه…لطفا مطلب راجع به برنامه نویسی بیشتر بزارید ممنوووون
مدیریت زمان
عال بود موفق باشید
بابک
ممنون.مطالب مفیدی بود.
طراحی سایت
مقاله خوبی بود
طراحی سایت
ممنون از مطلب مفیدتون
موفق باشید
طراحی سایت
ممنون از اطلاع رسانیتون . مفید بود
یو پی اس
عالی بود، موفق باشید
http://finetco.ir
عینک آفتابی
سلام
ممنون از مطلب خوب تون .
تور دبی
بسیار عالی بود ممنونم
احمد
ممنون
قالبسازی
ممنون بسیار عالی بود
یو پی اس
سلام خوب بود
اگه میشه در مورد طراحی و سئو بیشتر مطلب بزارین ممنون
فروشگاه خرید کبریت دائمی
سلام عالی بود مرسی
فروشگاه خرید کبریت دائمی
سلام عالی بود مرسی