مقدمه

معمولاً دانش‌آموزانی که می‌خواهند المپیاد بخوانند دید روشنی نسبت به آن‌چه باید یاد بگیرند و چه‌طور باید این کار را انجام دهند ندارند. نبودِ برنامه‌ی منسجم یکی از مشکلات بزرگ برای المپیادهای علمی است. اگر برای این کار به درستی برنامه‌ریزی شود، شاهد نتایج درخشانی خواهیم بود که کمترین آن‌ها موفقیت دانش‌آموزان در مسابقات کشوری و جهانی است و المپیاد بهانه‌ای می‌شود برای دنبال کردن علاقه‌مندی‌ها و استعدادها و سرآغازی بر موفقیت‌های دیگر.

توضیحِ برنامه‌ی المپیاد کامپیوتر

المپیاد کامپیوتر شاید یکی از مفهومی‌ترین المپیادها باشد. مباحث موجود در این المپیاد معمولاً در مدرسه آموزش داده نمی‌شود. ولی برای قبولی در مرحله اول و دوم نیازی به دانش برنامه‌نویسی- کامپیوتر- نیست؛ هر چند دانستن آن کمک شایانی به درک بهتر مباحث مورد نیاز در این دو مرحله می‌کند. اغلب سؤال‌ها و مباحث مطرح شده در مرحله اول و دوم فکری و به نوعی سنجش مهارت حل مسأله است. بنابراین تقویت مهارت حل مسأله (که اغلب با حل مسأله‌های متعدد به دست می‌آید) مهم‌ترین بحث در المپیاد کامپیوتر است. یعنی در المپیاد کامپیوتر، ما درست نگاه کردن به مسئله و هجوم بردن به مسأله از زوایای متعدد را یاد می‌گیریم.در این برنامه ابتدا شما با مراحل المپیاد کامپیوتر در ایران آشنا می‌شوید و سپس مباحث و منابع پیشنهادی برای هر یک را خواهید دید.

المپیاد کامپیوتر چیست؟

یکی از المپیادهای هفت‌گانه‌ست که از ابتدا تا مسابقات جهانی، مراحل گوناگون دارد:

جدول ۱: مراحل مقدماتی المپیاد کامپیوتر

* سؤالات این آزمون دارای زیرمسئله‌های متعدد هستند.

• اعداد ستون‌های تعداد سؤال، تعداد شرکت‌کننده، تعداد قبولی و به خصوص کفِ قبولی، حدودی و برای آشنایی بیشتر هستند.
• مرحله ۱ و ۲ در تمام شهرستان‌ها برگزار می‌شود.  مرحله سوم (و مراحل بعدی) به صورت متمرکز در تهران برگزار می‌شود.
• قبولی‌های مرحله‌ی سوم به دوره‌ی تابستانه راه می‌یابند و آموزش می‌بینند. آزمون کات برنز و فاینال بخشی از این دوره هستند.

جدول ۲: مراحل نهایی المپیاد کامپیوتر

اگر به جایی نرسیدیم چه؟!

همیشه در بین دانش‌پژوهان با این سؤال مواجهیم. اولاً، تعریف به جایی نرسیدن چیست؟ طلا نشدن؟ مدال نگرفتن؟ فرض کنیم تعریف به جایی نرسیدن مدال نگرفتن باشد. آن‌گاه من افراد بسیار زیادی را می‌شناسم که با این تعریف به جایی نرسیده اند اما در دانش‌گاه از کسانی که هم سن او بودند و طلا گرفته بودند پیشی گرفته‌اند. المپیاد کامپیوتر، هنر حل مسئله را آموزش می‌دهد. شما در صورتی که این المپیاد را جدی بگیرید به یک مسئله‌حل‌کن واقعی تبدیل می‌شوید. کسی که برایش فرقی ندارد مسئله، ترکیبیات است یا برنامه‌نویسی یا یک سؤال پیش پا افتاده‌ی کنکور یا یک مسئله‌ی واقعی در زندگی.

نقش المپیاد کامپیوتر در کنکور

المپیاد کامپیوتر تاثیر به سزایی در ریاضی کنکور دارد. مباحث مرحله اول برای حل سؤالات بخش ریاضیات گسسته و احتمالات کنکور (که حدود ۱۵ سؤال از سؤالات کنکور را در بر دارد). همچنین هنر حل مسئله‌ای که از المپیاد کسب شده به حل تعداد زیادی از سؤالات دیگر نیز کمک می‌کند (مثل هندسه و دیفرانسیل). در فیزیک نیز همان هنر حل مسئله بی‌تاثیر نیست. شاید باورش سخت باشد ولی هنر حل مسئله حتی در بخش عمومی کنکور هم تاثیرات خود را دارد.

نقش المپیاد کامپیوتر در المپیاد دانش‌جویی

مباحث المپیاد کامپیوتر دانش‌آموزی کم‌ترین تفاوت با مباحث ACM(مسابقات برنامه‌نویسی دانش‌جویی) را دارند. یک دانش‌پژوه علاقه‌مند برنامه‌نویسی را کنار نمی‌گذارد و به سرعت پس از ورود به دانش‌گاه وارد این عرصه می‌شود.

نقش المپیاد کامپیوتر در کار و شغل آینده

برنامه‌نویسی و فکر کردنی که در المپیاد می‌آموزید به سادگی می‌تواند شما را وارد شرکت‌های برتر حوزه‌ی ITکند. سری به شرکت‌های مطرح این حوزه بزنید؛ کافه‌بازار، سحاب‌پرداز، فناپ، اسنپ، کوئرا و…پر هستند از المپیادی‌های دیروز.

نقشه‌ی راه

دو سرمشق کلی در المپیاد کامپیوتر وجود دارد. سرمشق اول می‌گوید:

«یک موضوع بسیار مهم این است که تا جایی که می‌توانید همه‌ی مسائل را خودتان حل کنید. حتی اگر بعد فکر کردن زیاد نتیجه‌ای حاصل نشد، آن سؤال را علامت گذاشته و بعداً به سراغ آن بروید. یک سؤال که خودتان حل کنید از ده سؤال که راهش را بلد باشید با ارزش‌تر است.»

سرمشق دوم می‌گوید:

«اگر قدری روی یک مسئله فکر کردید و به نتیجه‌ای نرسیدید مشکلی نیست اگر سؤال را سوزاندید (سؤال سوزاندن یعنی خواندن راه حل سؤال). این حداقل مقدار را با تجربه می‌توان به دست آورد. مثلاً روی یک مسئله‌ی مرحله یکی بیش از ۱۰ دقیقه وقت نگذارید. اگر حل نشد به سراغ راه‌حل بروید و خوب یاد بگیرید.»

البته هر دو سرمشق بر روی این گزاره توافق دارند:

«اگر کار کردن زیاد روز یک موضوع خسته می‌شوید و به طور نسبتاً پراکنده مسئله حل کنید. مثلاً دو مسأله از استقرا، چند مسأله از ناوردایی و … حل کنید. بازده کاری هم با این روش افزایش می‌یابد.»

پیش‌نهاد من این است که هر جفت سرمشق‌ها را امتحان کنید. البته که نظر من به سمت سرمشق دوم متمایل است. طلاهایی را دیده‌ام که هیچ‌گاه به سراغ راه حل سؤالات نرفته‌اند. از آن سو طلاهایی نیز هستند که تعداد بسیار زیادی سؤال را سوزانده‌اند. اگر سرمشق دوم را پیش می‌گیرید، کمیت را بالا ببرید. همچنین باید حافظه‌ی خوبی نیز داشته باشید. اصولاً افراد خوش‌حافظه با سرمشق دوم به نتایج فوق‌العاده‌ای می‌رسند.

برنامه‌ی پیش‌نهادی برای بخش تئوری

 برای شروع باید چیزهایی از شمارش یاد گرفت (که در مرحله اول مطرح می‌شود). کتاب نردبان المپیاد ریاضی، جلدِ ترکیبیات (آرش جلالی)، روش‌های ترکیبیات (علیپور)، ریاضیات انتخاب (نیمه‌ی اول کتاب) و الفبای المپیاد ریاضی (فصل اول) برای یادگیری شمارش مناسبند. برای تمرین بیشتر فصل‌های شمارشی کتاب ترکیبیات زرد علیپور و تمرینات آن نیز مناسبند. بعد از تمام کردن شمارش- و حل مسأله‌های کافی در این زمینه- دانش‌آموز باید مباحث اصل ناوردایی، لانه کبوتری و اکسترمال را فرا بگیرد. بهترین کتاب هم در این زمینه استراتژی‌های حل مسأله است، روش‌های ترکیبیات نیز می‌تواند مفید باشد که برای هر یک از این مباحث باید فصل مربوط به آن خوانده شود و مسائل آن هم حل شود (به جز مسأله‌هایی که خیلی زمینه‌ی ریاضی دارند، مخصوصاً مسائل فصل لانه کبوتری از کتاب استراتژی). فصل لانه کبوتری کتاب ترکیبیات زرد علیپور هم منبع بسیار مناسبی است.

بعد از این مباحث به یکی از مهم‌ترین مباحث مطرح در المپیاد کامپیوتر می‌رسیم، یعنی استقرا. که باید وقت کافی بر روی آن گذاشته شود. تقریباً نیمی (شاید هم بیشتر) از مسأله‌های مرحله دو از مبحث استقراست. برای شروع فصل آخر کتاب الفبای المپیاد ریاضی یکی از کامل‌ترین منابع است. روش‌های ترکیبیات، فصل استقرای کتاب زرد ترکیبیات علیپور و هم‌چنین کتاب استراتژی‌های حل مسأله هم مسأله‌های خوبی دارند.

وقتی مباحث اولیه تمام شد وقت مسئله حل کردن است. بیشترین وقت در این قسمت باید صرف شود. کتاب المپیادهای ریاضی شوروی یک منبع خوب مسأله است. البته فقط سؤالات ترکیباتی آن. کتاب المپیادهای ریاضی لنینگراد هم بعضاً مسأله‌های خوبی دارد. انتهای کتاب مسأله‌های الگوریتمی هم حاوی مسائل مناسبی است که کمی سخت و پیشرفته‌اند. نکته مهم در این بخش حل مسأله‌های زیاد است. از روش‌های ترکیبیات، نمونه سؤالات سال‌های قبل مرحله دوم نیز غافل نشوید.

هم‌ زمان با ترکیبیات باید مقدمات نظریه گراف نیز فرا گرفته شود. برای نظریه گراف کتاب «نظریه گراف» نوشته داگلاس بی‌وست بهترین کتاب موجود است که ترجمه آن هم در بازار هست. فصل‌های ۱ ، ۲ و ۳ کتاب وست برای یادگیری کلی گراف کافی‌ست. این کتاب هم‌چنین مسأله‌های خوبی دارد که حتماً باید حل شود. دانش‌آموز باید با توجه به سرعتش در حل مسائلی برنامه‌ای بریزد که تا قبل مرحله دو حداقل ۲ فصل از کتاب وست (و همچنین قضیه‌های مهم بخش تطابق) را بخواند.

نکته: دانش‌آموز باید قبل از مرحله اول سؤالات دوره‌های پیشین را از خود امتحان بگیرد. قبل از مرحله دوم نیز (از یک ماه و نیم قبل) آزمون‌های مرحله ۲ سال‌های پیش را امتحان بدهد و بررسی کند (این ۶۰٪آمادگی مرحله دو است). قبل از مرحله ۳ نیز (از ۳ هفته قبل) مرحله ۳های سال‌های گذشته را امتحان بدهد و بررسی کند. اگر دانش‌آموز احساس کرد که در بحث تئوری قوی شده می‌تواند به سراغ سؤالات فاینال تئوری دوره‌های قبل برود. البته سراغ هر سؤال باید وقتی رفت که بتوان آن را حل کرد. سؤالات فاینال تئوری سال‌های پیش هم برای آمادگی برای مرحله دو و قوی‌تر شدن حل مسئله مناسب است. بعد از مرحله دو اگر دانش‌آموز احساس می‌کند می‌تواند قبول شود تا تابستان وقت خود را روی برنامه‌نویسی (و فقط برنامه‌نویسی) بگذارد.

برنامه‌ی پیش‌نهادی برای بخش عملی

پیش بردن بخش عملی به صورت فردی بسیار سخت است. هر ساله مباحث عملی در المپیاد کامپیوتر دست‌خوش تغییراتی می‌شود و دانش‌پژوه نیازمند راه‌نمایی‌ست که این مباحث را به او آموزش دهد. نمی‌توان با خواندن کتاب انتظار پیش‌رفت در بخش عملی داشت. هر چند بخش بزرگی از قوی‌شدن در بخش عملی تمرین کردن است، اما همین که چه تمرین‌هایی حل شوند و مباحث به چه ترتیبی یاد گرفته شوند خود نیازمند استاد است. پیش‌نهاد می‌شود دانش‌پژوه در این حوزه از یک معلم یا حداقل یک راه‌نما استفاده کند، اما به صورت کلی می‌توانید از لیست ارائه شده در انتهای مطلب نیز استفاده کنید.

کلاس‌های حضوری و آنلاین آیریسک و تالار گفتمان المپیادی‌ها (gap.irysc.com( می‌تواند راه‌نمای شما در این بخش باشد.

سرفصل‌های المپیاد کامپیوتر

مباحث تئوری:

❖        ترکیبات:

1. شمارش: اصول جمع و ضرب، جایگشت‌ها، ترکیب و تبدیل
2. احتمال و امیدریاضی
3. اصل اکسترمال
4. اصل ناوردایی
5. رنگ‌آمیزی
6. اصل استقرا: استقرای ضعیف، استقرای قوی، استقرای قهقرایی
7. دو گونه شمردن (شمارش مضاعف)
8. اصل لانه کبوتری
9. رابط بازگشتی

❖         نظریه گراف:

1.  تعاریف اولیه: راس، یال، مسیر، گشت، گذر، مؤلفه همبندی
2. مسیرها
3. درجه رئوس، قضیه منتل، قضیه توران و دنباله‌های گرافیکی
4. گراف‌های جهت‌دار و تورنمنت‌ها
5. درخت و قضیه‌های مربوط به آن
6. گراف‌های اویلری
7. قضیه هال
8. پوشش یالی، پوشش راسی، مجموعه‌های مستقل
9. قضیه تات، قضیه کونیگ و قضیه پترسن
10. K همبندی عالی و راسی
11. رنگ‌آمیزی یالی و قضیه ویزینگ
12. رنگ‌آمیزی راسی و دنباله‌های رنگ‌آمیزی
13. دورهای همیلتونی
14. برش‌های یالی و راسی

v     الگوریتم:

مباحث الگوریتم و برنامه‌نویسی هر ساله تغییرات نسبتاً زیادی در المپیاد ایران دارند. پیش‌نهاد می‌شود از یک استاد خبره و آشنا با دوره‌ی تابستانی کمک بگیرید. اما برخی از مباحث در لیست زیر آمده‌اند. لیست زیر حاوی مباحث ۴ سال پیش است، تغییرات بسیار زیادی در المپیاد ایران از آن دوره اتفاق افتاده است.

۱.    تحلیل الگوریتم‌ها:

• نمادهای O، امگا و تتا
• روش جایگذاری
• درخت بازگشتی
• فرمول اصلی
• تحلیل سرشکن شده

۲.      آشنایی با الگوریتم:

• مسأله‌ ستاره‌ی مشهور
• مسأله نمای افقی
• الگوریتم هورنر

۳.      ساختمان‌های داده‌ای:

• آرایه‌ها
• لیست پیوندی
• بردار (آرایه‌ی پویا)
• پشته
• صف
• درخت دودویی جست‌وجو
• هیپ (هرم)
• Disjoint set
• طراحی ساختمان‌های داده‌ای

۴.      مرتب‌سازی:

• مرتب‌سازی درجی
• مرتب‌سازی هرمی
• مرتب‌سازی سریع
• مرتب‌سازی‌های غیر مقایسه‌ای
• مرتبه‌ی آماری و الگوریتم Select
• یافتن بیشینه و کمینه
• اعداد تصادفی

۵.      الگوریتم‌های دنباله‌ها (غیر از مرتب‌سازی):

• جست‌وجوی دودویی و انواع آن
• تطابق رشته‌ای: الگوریتم‌های KMPو Hash
• کد هافمن
• فاصله ویرایشی دو دنباله
• یافتن اکثریت
• بزرگ‌ترین زیر دنباله صعودی(LIS)

۶.      الگوریتم‌‌های گراف:

• ذخیره‌سازی گراف
• DFS
• BFS
• ساخت درخت DFSو BFS
• ترتیب توپولوژیک
• درخت پوشای کمینه
• الگوریتم دایسترا
• الگوریتم فلوید
• تجزیه گراف به مؤلفه‌های قویا همبند
• تجزیه به مؤلفه‌های دو همبند
• تطابق دو بخشی
•  LCA (اولین جد مشترک)
• پیدا کردن راس‌های و یال‌های برشی

۷.      برنامه‌ریزی پویا:

• بزرگ‌ترین زیر دنباله مشترک: LCS
• ضرب زنجیر ماتریس‌ها
• عناصر روش برنامه‌ریزی پویا
• روش از بالا به پایین و روش پایین به بالا
• گراف زیرمسئله‌ها
• مسئله کوله‌پشتی

۸.      الگوریتم‌های حریصانه:

• اثبات‌های حریصانه بودن
• رنگ‌آمیزی بازه‌ها
• کوله‌پشتی کسری
• مسئله انتخاب فعالیت

۹.      الگوریتم‌های هندسی:

• ضرب خارجی و ضرب داخلی دو بردار
• محاسبه طول پاره‌خط
• محل برخورد دو پاره‌خط
• مساحت چند ضلعی
• مسئله نقطه و چند ضلعی
• پوش محدب
• دایره و پاره‌خط

۱۰.  NPکامل:

• اثبات‌های NP– کامل بودن
• تحویل مسأله‌ها به همدیگر

برنامه نویسی:

❖       زبان C++:

1. برنامه‌نویسی چیست؟
2. سرفایل‌ها
3. متغیرها و عملیات ریاضی
4. دستورات ورودی/ خروجی
5. دستورهای کنترلی:
   1. دستور شرطی if
   2. حلقه‌های forو while
   3. عملگرهای منطقی
   4.  Continue, break, goto
6. توابع:
   1. توابع ریاضی cmath
   2. تعریف توابع
   3. تابع بازگشتی
   4. فراخوانی با ارجاع و مقدار
   5. آرایه‌ها و اشاره‌گرها:
   6. آرایه‌های یک بعدی و چند بعدی
   7. رفتار آرایه‌ها
   8. متغیرهای اشاره‌گر
   9. اشاره‌گرهای رشته‌ای
   10. توابع پردازش رشته
   11. کلاس stringو توابع مفید
   12. عملگرهای بیتی، structها
7. پیش پردازنده
8. کتابخانه قالب استاندارد (STL):
   1. Vector
   2.  Set
   3. Map
   4.  Priority- queue
   5.  Bitset
   6.  الگوریتم‌های مهم STL: sort, max, minو …

• مفهوم کلاس و استفاده از آن

❖       تمرین عملی

1. نردبان المپیاد ریاضی، ترکیبیات مرحله اول / آرش جلالی / انتشارات گچ / خرید اینترنتی [+] ، دانلود از کتابراه [+]
2. روش‌های ترکیبیات جلد ۱ / علیرضا علیپور / انتشارات فاطمی / خرید اینترنتی [+]
3. روش‌های ترکیبیات جلد ۲ / علیرضا علیپور / انتشارات فاطمی / خرید اینترنتی [+]
   
4. آنالیز ترکیبی / عباس ثروتی / انتشارات خوشخوان / خرید اینترنتی [+]
5. آنالیز ترکیبی / علیرضا علیپور / انتشارات الگو / خرید اینترنتی [+]
6. مبانی احتمال / سعید قهرمانی / انتشارات دانشگاه صنعتی شریف / فصل اول تا چهارم
7. الفبای المپیاد ریاضی و کامپیوتر / مرتضی محمدآبادی / انتشارات دانش‌پژوهان جوان / خرید اینترنتی [+]
8. روش‌های احتمالی در المپیاد ریاضی و کامپیوتر / حمید کاملی / انتشارات خوشخوان / خرید اینترنتی [+]
9. استراتژی‌های حل مسئله، انتشارات مبتکران
10. المپیادهای ریاضی شوروی، مترجم پرویز شهریاری
11. ترکیبیات، علیرضا علیپور / انتشارات فاطمی / خرید اینترنتی [+]
12. المپیادهای کامپیوتر ایران از آغاز تا کنون، مراحل اول، یاسر احمدی فولادی
13. المپیادهای کامپیوتر ایران از آغاز تا کنون، مراحل دوم، یاسر احمدی فولادی
14. المپیادهای ریاضی لنینگراد
15. نظریه گراف و کاربردهای آن، باندی مورتی
16. طراحی الگوریتم با رویکردی خلاقانه، یودی منبر
17. مقدمه‌ای بر الگوریتم‌ها، مترجم عین‌اله جعفرنژاد قمی (CLRS)
18. How To Program C++،Deitel & Deitel
19. آموزش برنامه‌نویسی باC++ ، دایتل و دایتل، مترجم: حسن محمدی، حسین محمدی
20. برنامه‌نویسی به زبان C++، عین‌اله جعفرنژاد قمی
21. آشنایی با نظریه گراف، داگلاس بی. وست، نشر گسترش علوم پایه
22. مسئله‌های الگوریتمی، دکتر محمد قدسی
23. quera.ir
24. codeforces.com

گردآوری و ویرایش:

• امیررضا پوراخوان
• مرتضی خلینا