آشنایی با المپیاد کامپیوتر – برنامهریزی و معرفی کتاب های المپیاد کامپیوتر
مقدمه
اگر هنوز با المپیادهای علمی و ادبی در ایران آشنا نیستید، حتما به اینجا سر بزنید و مطالب مقدماتی را مطالعه کنید. معمولاً دانشآموزانی که میخواهند المپیاد بخوانند دید روشنی نسبت به آنچه باید یاد بگیرند و چهطور باید این کار را انجام دهند ندارند. نبودِ برنامهی منسجم یکی از مشکلات بزرگ برای المپیادهای علمی است. اگر برای این کار به درستی برنامهریزی شود، شاهد نتایج درخشانی خواهیم بود که کمترین آنها موفقیت دانشآموزان در مسابقات کشوری و جهانی است و المپیاد بهانهای میشود برای دنبال کردن علاقهمندیها و استعدادها و سرآغازی بر موفقیتهای دیگر.
توضیحِ برنامهی المپیاد کامپیوتر
المپیاد کامپیوتر شاید یکی از مفهومیترین المپیادها باشد. مباحث موجود در این المپیاد معمولاً در مدرسه آموزش داده نمیشود. ولی برای قبولی در مرحله اول و دوم نیازی به دانش برنامهنویسی- کامپیوتر- نیست؛ هر چند دانستن آن کمک شایانی به درک بهتر مباحث مورد نیاز در این دو مرحله میکند. اغلب سؤالها و مباحث مطرح شده در مرحله اول و دوم فکری و به نوعی سنجش مهارت حل مسأله است. بنابراین تقویت مهارت حل مسأله (که اغلب با حل مسألههای متعدد به دست میآید) مهمترین بحث در المپیاد کامپیوتر است. یعنی در المپیاد کامپیوتر، ما درست نگاه کردن به مسئله و هجوم بردن به مسأله از زوایای متعدد را یاد میگیریم.در این برنامه ابتدا شما با مراحل المپیاد کامپیوتر در ایران آشنا میشوید و سپس مباحث و منابع پیشنهادی برای هر یک را خواهید دید.
المپیاد کامپیوتر چیست؟
یکی از المپیادهای هفتگانهست که در مجموع ۹ مرحله دارد:
جدول 1: مراحل مقدماتی المپیاد کامپیوتر
| مرحلهی آزمون | تعداد سؤال | سبک | زمان برگزاری | کفِ قبولی
(تقریبی) |
تعداد تقریبی شرکتکننده | تعداد تقریبی قبولی | توضیحات | |
| مرحله اول | ۳۰ | تستی | بهمن | %30 | ۱۰۰۰۰ | ۱۰۰۰ | سؤالات بیشتر جنبهی شمارشی دارند | |
| مرحله دوم | روز ۱ | ۲۵ | تستی | اردیبهشت | %35 | ۱۰۰۰ | ۲۰۰ | علاوه بر شمارش، الگوریتم، احتمال پیشرفته نیز اضافه میشوند
ضریب این آزمون در نتیجهی کلی مرحله دوم ۵۰٪است. |
| روز ۲ | ۴* | تشریحی | 35 تا 50% | ۲۰۰ | ۸۰ | استقرا، لانهکبوتری، الگوریتمهای سازنده (constructive algorithms)، بازیها، احتمال پیشرفته، گراف پیشرفته نیز اضافه میشوند
ضریب این آزمون در نتیجهی کلی مرحله دوم ۵۰٪است. منظور از کف نیز کفِ مجموع نمرات بخش تستی و تشریحیست |
||
| مرحله سوم | ۳* | برنامهنویسی | تیر | %55 | ۸۰ | ۴۰ | برنامهنویسی، برنامهنویسی پویا، جستوجوی حالتها، ترکیبیات شمارشی، نظریهاعداد شمارشی الگوریتمهای ابتدایی اضافه میشوند
نتیجهی آزمون مرحله دوم ۶۰٪در نتیجهی این آزمون تاثیر دارد. منظور از کف نیز کفِ مجموع نمرات مرحله دوم و سوم است |
|
* سؤالات این آزمون دارای زیرمسئلههای متعدد هستند.
+ اعداد ستونهای تعداد سؤال، تعداد شرکتکننده، تعداد قبولی و به خصوص کفِ قبولی، حدودی و برای آشنایی بیشتر هستند.
+ مرحله ۱ و ۲ در تمام شهرستانها برگزار میشود. مرحله سوم (و مراحل بعدی) به صورت متمرکز در تهران برگزار میشود.
+ قبولیهای مرحلهی سوم به دورهی تابستانه راه مییابند و آموزش میبینند. آزمون کات برنز و فاینال بخشی از این دوره هستند.
جدول 2: مراحل نهایی المپیاد کامپیوتر
| مرحلهی آزمون | تعداد سؤالات | نوع آزمون | زمانِ تقریبی | توضیحات | |
| کات برنز | آزمونهای متعدد برگزار میشود | تشریحی و برنامهنویسی | مرداد | بخشی دیگر از الگوریتمها اضافه میشوند
در صورت نرسیدن نمره به حد نصاب یا افتادن دو درس دانشپژوه از دوره تابستانی حذف میشود و مدال برنز به او تعلق میگیرد |
|
| فاینال | تئوری | ۳ یا ۴ آزمون ۳ سؤاله* | تشریحی | دهه آخر شهریور | مباحث پیشرفتهتری از گراف، احتمالات، نظریهی زبانها و ماشینها و …اضافه میشود.
ضریب این آزمون در نتیجهی کلی هنگام تقسیم مدال ۴۰٪است. |
| عملی | ۳ یا ۴ آزمون ۳ سؤاله* | برنامهنویسی | دهه آخر شهریور | الگوریتمهای پیشرفتهتر اضافه میشوند
ضریب این آزمون در نتیجهی کلی هنگام تقسیم مدال ۶۰٪است. |
|
| دوره انتخابی تیم | آزمونهای متعدد برگزار میشود | برنامهنویسی | آبان تا اسفند سال بعد | الگوریتمهای پیشرفتهتر اضافه میشوند | |
| المپیاد جهانی | برنامهنویسی | مرداد سال بعد | الگوریتمهای پیشرفتهتر اضافه میشوند | ||
اگر به جایی نرسیدیم چه؟!
همیشه در بین دانشپژوهان با این سؤال مواجهیم. اولاً، تعریف به جایی نرسیدن چیست؟ طلا نشدن؟ مدال نگرفتن؟ فرض کنیم تعریف به جایی نرسیدن مدال نگرفتن باشد. آنگاه من افراد بسیار زیادی را میشناسم که با این تعریف به جایی نرسیده اند اما در دانشگاه از کسانی که هم سن او بودند و طلا گرفته بودند پیشی گرفتهاند. المپیاد کامپیوتر، هنر حل مسئله را آموزش میدهد. شما در صورتی که این المپیاد را جدی بگیرید به یک مسئلهحلکن واقعی تبدیل میشوید. کسی که برایش فرقی ندارد مسئله، ترکیبیات است یا برنامهنویسی یا یک سؤال پیش پا افتادهی کنکور یا یک مسئلهی واقعی در زندگی.
نقش المپیاد کامپیوتر در کنکور
المپیاد کامپیوتر تاثیر به سزایی در ریاضی کنکور دارد. مباحث مرحله اول برای حل سؤالات بخش ریاضیات گسسته و احتمالات کنکور (که حدود ۱۵ سؤال از سؤالات کنکور را در بر دارد). همچنین هنر حل مسئلهای که از المپیاد کسب شده به حل تعداد زیادی از سؤالات دیگر نیز کمک میکند (مثل هندسه و دیفرانسیل). در فیزیک نیز همان هنر حل مسئله بیتاثیر نیست. شاید باورش سخت باشد ولی هنر حل مسئله حتی در بخش عمومی کنکور هم تاثیرات خود را دارد.
نقش المپیاد کامپیوتر در المپیاد دانشجویی
مباحث المپیاد کامپیوتر دانشآموزی کمترین تفاوت با مباحث ACM(مسابقات برنامهنویسی دانشجویی) را دارند. یک دانشپژوه علاقهمند برنامهنویسی را کنار نمیگذارد و به سرعت پس از ورود به دانشگاه وارد این عرصه میشود.
نقش المپیاد کامپیوتر در کار و شغل آینده
برنامهنویسی و فکر کردنی که در المپیاد میآموزید به سادگی میتواند شما را وارد شرکتهای برتر حوزهی ITکند. سری به شرکتهای مطرح این حوزه بزنید؛ کافهبازار، سحابپرداز، فناپ، اسنپ، کوئرا و…پر هستند از المپیادیهای دیروز.
نقشهی راه
دو سرمشق کلی در المپیاد کامپیوتر وجود دارد.
سرمشق اول میگوید:
«یک موضوع بسیار مهم این است که تا جایی که میتوانید همهی مسائل را خودتان حل کنید. حتی اگر بعد فکر کردن زیاد نتیجهای حاصل نشد، آن سؤال را علامت گذاشته و بعداً به سراغ آن بروید. یک سؤال که خودتان حل کنید از ده سؤال که راهش را بلد باشید با ارزشتر است.»
سرمشق دوم میگوید:
«اگر قدری روی یک مسئله فکر کردید و به نتیجهای نرسیدید مشکلی نیست اگر سؤال را سوزاندید (سؤال سوزاندن یعنی خواندن راه حل سؤال). این حداقل مقدار را با تجربه میتوان به دست آورد. مثلاً روی یک مسئلهی مرحله یکی بیش از ۱۰ دقیقه وقت نگذارید. اگر حل نشد به سراغ راهحل بروید و خوب یاد بگیرید.»
البته هر دو سرمشق بر روی این گزاره توافق دارند:
«اگر کار کردن زیاد روز یک موضوع خسته میشوید و به طور نسبتاً پراکنده مسئله حل کنید. مثلاً دو مسأله از استقرا، چند مسأله از ناوردایی و … حل کنید. بازده کاری هم با این روش افزایش مییابد.»
پیشنهاد من این است که هر جفت سرمشقها را امتحان کنید. البته که نظر من به سمت سرمشق دوم متمایل است. طلاهایی را دیدهام که هیچگاه به سراغ راه حل سؤالات نرفتهاند. از آن سو طلاهایی نیز هستند که تعداد بسیار زیادی سؤال را سوزاندهاند. اگر سرمشق دوم را پیش میگیرید، کمیت را بالا ببرید. همچنین باید حافظهی خوبی نیز داشته باشید. اصولاً افراد خوشحافظه با سرمشق دوم به نتایج فوقالعادهای میرسند.
برنامهی پیشنهادی برای بخش تئوری
برای شروع باید چیزهایی از شمارش یاد گرفت (که در مرحله اول مطرح میشود). کتاب نردبان المپیاد ریاضی، جلدِ ترکیبیات (آرش جلالی)، روشهای ترکیبیات (علیپور)، ریاضیات انتخاب (نیمهی اول کتاب) و الفبای المپیاد ریاضی (فصل اول) برای یادگیری شمارش مناسبند. برای تمرین بیشتر فصلهای شمارشی کتاب ترکیبیات زرد علیپور و تمرینات آن نیز مناسبند. بعد از تمام کردن شمارش- و حل مسألههای کافی در این زمینه- دانشآموز باید مباحث اصل ناوردایی، لانه کبوتری و اکسترمال را فرا بگیرد. بهترین کتاب هم در این زمینه استراتژیهای حل مسأله است، روشهای ترکیبیات نیز میتواند مفید باشد که برای هر یک از این مباحث باید فصل مربوط به آن خوانده شود و مسائل آن هم حل شود (به جز مسألههایی که خیلی زمینهی ریاضی دارند، مخصوصاً مسائل فصل لانه کبوتری از کتاب استراتژی). فصل لانه کبوتری کتاب ترکیبیات زرد علیپور هم منبع بسیار مناسبی است.
بعد از این مباحث به یکی از مهمترین مباحث مطرح در المپیاد کامپیوتر میرسیم، یعنی استقرا. که باید وقت کافی بر روی آن گذاشته شود. تقریباً نیمی (شاید هم بیشتر) از مسألههای مرحله دو از مبحث استقراست. برای شروع فصل آخر کتاب الفبای المپیاد ریاضی یکی از کاملترین منابع است. روشهای ترکیبیات، فصل استقرای کتاب زرد ترکیبیات علیپور و همچنین کتاب استراتژیهای حل مسأله هم مسألههای خوبی دارند.
وقتی مباحث اولیه تمام شد وقت مسئله حل کردن است. بیشترین وقت در این قسمت باید صرف شود. کتاب المپیادهای ریاضی شوروی یک منبع خوب مسأله است. البته فقط سؤالات ترکیباتی آن. کتاب المپیادهای ریاضی لنینگراد هم بعضاً مسألههای خوبی دارد. انتهای کتاب مسألههای الگوریتمی هم حاوی مسائل مناسبی است که کمی سخت و پیشرفتهاند. نکته مهم در این بخش حل مسألههای زیاد است. از روشهای ترکیبیات، نمونه سؤالات سالهای قبل مرحله دوم نیز غافل نشوید.
هم زمان با ترکیبیات باید مقدمات نظریه گراف نیز فرا گرفته شود. برای نظریه گراف کتاب «نظریه گراف» نوشته داگلاس بیوست بهترین کتاب موجود است که ترجمه آن هم در بازار هست. فصلهای 1 ، 2 و 3 کتاب وست برای یادگیری کلی گراف کافیست. این کتاب همچنین مسألههای خوبی دارد که حتماً باید حل شود. دانشآموز باید با توجه به سرعتش در حل مسائلی برنامهای بریزد که تا قبل مرحله دو حداقل 2 فصل از کتاب وست (و همچنین قضیههای مهم بخش تطابق) را بخواند.
نکته:
دانشآموز باید قبل از مرحله اول سؤالات دورههای پیشین را از خود امتحان بگیرد. قبل از مرحله دوم نیز (از یک ماه و نیم قبل) آزمونهای مرحله ۲ سالهای پیش را امتحان بدهد و بررسی کند (این ۶۰٪آمادگی مرحله دو است). قبل از مرحله ۳ نیز (از ۳ هفته قبل) مرحله ۳های سالهای گذشته را امتحان بدهد و بررسی کند. اگر دانشآموز احساس کرد که در بحث تئوری قوی شده میتواند به سراغ سؤالات فاینال تئوری دورههای قبل برود. البته سراغ هر سؤال باید وقتی رفت که بتوان آن را حل کرد. سؤالات فاینال تئوری سالهای پیش هم برای آمادگی برای مرحله دو و قویتر شدن حل مسئله مناسب است. بعد از مرحله دو اگر دانشآموز احساس میکند میتواند قبول شود تا تابستان وقت خود را روی برنامهنویسی (و فقط برنامهنویسی) بگذارد.
برنامهی پیشنهادی برای بخش عملی
پیش بردن بخش عملی به صورت فردی بسیار سخت است. هر ساله مباحث عملی در المپیاد کامپیوتر دستخوش تغییراتی میشود و دانشپژوه نیازمند راهنماییست که این مباحث را به او آموزش دهد. نمیتوان با خواندن کتاب انتظار پیشرفت در بخش عملی داشت. هر چند بخش بزرگی از قویشدن در بخش عملی تمرین کردن است، اما همین که چه تمرینهایی حل شوند و مباحث به چه ترتیبی یاد گرفته شوند خود نیازمند استاد است. پیشنهاد میشود دانشپژوه در این حوزه از یک معلم یا حداقل یک راهنما استفاده کند، اما به صورت کلی میتوانید از لیست ارائه شده در انتهای مطلب نیز استفاده کنید.
سرفصلهای المپیاد کامپیوتر
مباحث تئوری:
❖ ترکیبات:
- شمارش: اصول جمع و ضرب، جایگشتها، ترکیب و تبدیل
- احتمال و امیدریاضی
- اصل اکسترمال
- اصل ناوردایی
- رنگآمیزی
- اصل استقرا: استقرای ضعیف، استقرای قوی، استقرای قهقرایی
- دو گونه شمردن (شمارش مضاعف)
- اصل لانه کبوتری
- رابط بازگشتی
❖ نظریه گراف:
- تعاریف اولیه: راس، یال، مسیر، گشت، گذر، مؤلفه همبندی
- مسیرها
- درجه رئوس، قضیه منتل، قضیه توران و دنبالههای گرافیکی
- گرافهای جهتدار و تورنمنتها
- درخت و قضیههای مربوط به آن
- گرافهای اویلری
- قضیه هال
- پوشش یالی، پوشش راسی، مجموعههای مستقل
- قضیه تات، قضیه کونیگ و قضیه پترسن
- kهمبندی عالی و راسی
- رنگآمیزی یالی و قضیه ویزینگ
- رنگآمیزی راسی و دنبالههای رنگآمیزی
- دورهای همیلتونی
- برشهای یالی و راسی
v الگوریتم:
مباحث الگوریتم و برنامهنویسی هر ساله تغییرات نسبتاً زیادی در المپیاد ایران دارند. پیشنهاد میشود از یک استاد خبره و آشنا با دورهی تابستانی کمک بگیرید. اما برخی از مباحث در لیست زیر آمدهاند. لیست زیر حاوی مباحث ۴ سال پیش است، تغییرات بسیار زیادی در المپیاد ایران از آن دوره اتفاق افتاده است.
-
تحلیل الگوریتمها:
✓ نمادهای O، امگا و تتا
✓ روش جایگذاری
✓ درخت بازگشتی
✓ فرمول اصلی
✓ تحلیل سرشکن شده
-
آشنایی با الگوریتم:
✓ مسأله ستارهی مشهور
✓ مسأله نمای افقی
✓ الگوریتم هورنر
-
ساختمانهای دادهای:
✓ آرایهها
✓ لیست پیوندی
✓ بردار (آرایهی پویا)
✓ پشته
✓ صف
✓ درخت دودویی جستوجو
✓ هیپ (هرم)
✓ Disjoint set
✓ طراحی ساختمانهای دادهای
-
مرتبسازی:
✓ مرتبسازی درجی
✓ مرتبسازی هرمی
✓ مرتبسازی سریع
✓ مرتبسازیهای غیر مقایسهای
✓ مرتبهی آماری و الگوریتم Select
✓ یافتن بیشینه و کمینه
✓ اعداد تصادفی
-
الگوریتمهای دنبالهها (غیر از مرتبسازی):
✓ جستوجوی دودویی و انواع آن
✓ تطابق رشتهای: الگوریتمهای KMPو Hash
✓ کد هافمن
✓ فاصلهویرایشی دو دنباله
✓ یافتن اکثریت
✓ بزرگترین زیر دنبالهصعودی(LIS)
-
الگوریتمهای گراف:
✓ ذخیرهسازی گراف
✓ DFS
✓ BFS
✓ ساخت درخت DFSو BFS
✓ ترتیب توپولوژیک
✓ درخت پوشای کمینه
✓ الگوریتم دایسترا
✓ الگوریتم فلوید
✓ تجزیه گراف به مؤلفههای قویا همبند
✓ تجزیه به مؤلفههای دو همبند
✓ تطابق دو بخشی
✓ LCA(اولین جد مشترک)
✓ پیدا کردن راسهای و یالهای برشی
-
برنامهریزی پویا:
✓ بزرگترین زیر دنباله مشترک (LCS)
✓ ضرب زنجیر ماتریسها
✓ عناصر روش برنامهریزی پویا
✓ روش از بالا به پایین و روش پایین به بالا
✓ گراف زیرمسئلهها
✓ مسئله کولهپشتی
-
الگوریتمهای حریصانه:
✓ اثباتهای حریصانه بودن
✓ رنگآمیزی بازهها
✓ کولهپشتی کسری
✓ مسئله انتخاب فعالیت
-
الگوریتمهای هندسی:
✓ ضرب خارجی و ضرب داخلی دو بردار
✓ محاسبه طول پارهخط
✓ محل برخورد دو پارهخط
✓ مساحت چند ضلعی
✓ مسئله نقطه و چند ضلعی
✓ پوش محدب
✓ دایره و پارهخط
-
NPکامل:
✓ اثباتهای NP- کامل بودن
✓ تحویل مسألهها به همدیگر
برنامه نویسی:
❖ زبان C++:
- برنامهنویسی چیست؟
- سرفایلها
- متغیرها و عملیات ریاضی
- دستورات ورودی/ خروجی
- دستورهای کنترلی:
✓ دستور شرطی if
✓ حلقههای forو while
✓ عملگرهای منطقی
✓ Continue, break, goto
- توابع:
✓ توابع ریاضی cmath
✓ تعریف توابع
✓ تابع بازگشتی
✓ فراخوانی با ارجاع و مقدار
- آرایهها و اشارهگرها:
✓ آرایههای یک بعدی و چند بعدی
✓ رفتار آرایهها
✓ متغیرهای اشارهگر
✓ اشارهگرهای رشتهای
✓ توابع پردازش رشته
- کلاس stringو توابع مفید
- عملگرهای بیتی، structها
- پیش پردازنده
- کتابخانه قالب استاندارد (STL):
✓ Vector
✓ Set
✓ Map
✓ Priority- queue
✓ Bitset
✓ الگوریتمهای مهم STL: sort, max, minو …
- مفهوم کلاس و استفاده از آن
❖ تمرین عملی
منابع مفید المپیاد کامپیوتر
1) نردبان المپیاد ریاضی، ترکیبیات مرحله اول، آرش جلالی، انتشارات گچ
2) الفبای المپیاد ریاضی، مرتضی محمدآبادی، انتشارات دانشپژوهان جوان
3) روشهای ترکیبیات، علیرضا علیپور، انتشارات فاطمی
4) استراتژیهای حل مسئله، انتشارات مبتکران
5) المپیادهای ریاضی شوروی، مترجم پرویز شهریاری
6) ترکیبیات، علیرضا علیپور، انتشارات فاطمی
7) المپیادهای کامپیوتر ایران از آغاز تا کنون، مراحل اول، یاسر احمدی فولادی
8) المپیادهای کامپیوتر ایران از آغاز تا کنون، مراحل دوم، یاسر احمدی فولادی
9) المپیادهای ریاضی لنینگراد
10) نظریه گراف و کاربردهای آن، باندی مورتی
11) طراحی الگوریتم با رویکردی خلاقانه، یودی منبر
12) مقدمهای بر الگوریتمها، مترجم عیناله جعفرنژاد قمی (CLRS)
13) How To Program C++،Deitel & Deitel
فروشگاه اینترنتی سیجاب یکی از فروشگاه های آنلاین ایران است که در زمینه :
فعالیت میکند.
فروشگاه اینترنتی سیجاب
با گسترهای از کالاهای متنوع برای تمام اقشار جامعه و هر ردهی سنی، برای کاربران خود «تجربهی لذتبخش یک خرید اینترنتی» را تداعی میکند.«ارسال سریع»، «ضمانت بهترین قیمت» و «تضمین اصل بودن کالا» سه اصل اولیه است .
تمامی افراد به راحتی می توانند محصولات مورد نظر خود را از فروشگاه اینترنتی سیجاب سفارش دهند و با بهترین قیمت و امکان پرداخت بصورت آنلاین و یا ” پرداخت هنگام تحویل کالا ” محصولات خود را سفارش دهند.
