المپیاد کامپیوتر به صورت سالانه برای ایجاد رقابت و افزایش سطح سواد، در بین دانش آموزان سال اول، دوم و سوم متوسطه برگزار می شود. این آزمون شامل 5مرحله است که فرد در صورت قبولی در آنها، موفق به دریافت مدال طلا، نقره یا برنز می شود.

در مراحل اولیه بحث برنامه نویسی مطرح نیست و بیشتر بر روی توانایی حل مسئله تاکید شده است. پس برای موفقیت در المپیاد کامپیوتر لازم است در مرحله نخست توانایی حل مسئله خود را افزایش دهید. در ادامه به بررسی جامع این المپیاد می پردازیم.

مراحل المپیاد کامپیوتر

مرحله نخست

آزمون مرحله اول در بین 10 هزار نفر برگزار می شود که تعداد 2000 نفر آنها به مرحله بعدی صعود می کنند. این آزمون به صورت چهارگزینه ای در سطح استانی برگزار می شود.

مرحله دوم

مرحله دوم المپیاد کامپیوتر در سطح کشوری برگزار می شود. ظرفیت پذیرش کاملا بستگی به ظرفیت کمپ تابستانی دارد زیرا بر اساس قوانین تعداد پذیرفته شدگان این مرحله دوبرابر ظرفیت کمپ تابستانی است. سوالات این مرحله به صورت یک آزمون تستی و یک آزمون تشریحی بوده و در دو روز برگزار می شود.

مرحله سوم

مرحله سوم به آزمون مقدماتی برنامه نویسی نیز شناخته می شود. دقت داشته باشید که شرکت در این مرحله فقط برای دانش آموزان سال دوم و سوم مجاز است و دانش آموزان سال اول نمی تونند در این مرحله شرکت کنند.

آزمون مقدماتی برنامه نویسی به صورت یک آزمون تمرینی و دو آزمون انتخابی است. در آزمون های انتخابی برای حل مسائل کامپیوتر در اختیار شما قرار خواهد گرفت و مجاز هستید برای حل مسائل از آن کمک بگیرید.

ظرفیت قبولی در این دوره 35نفر است و به مرحله بعد یعنی دوره تابستانی صعود می کنند.

مرحله چهارم

بیشتر تلاش ها برای رسیدن به این مرحله انجام می شود. از حالا به بعد مرحله چهارم را دوره تابستانی می نامیم. در دوره تابستانی علوم کامپیوتر (بسیار سطح بالاتر از کتب درسی دبیرستان)، برنامه نویسی و توانایی حل مسئله به صورت روزانه تدریس و تمرین می شود.

همچنین به صورت منظم از شما آزمون برنامه نویسی و علوم کامپیوتر گرفته می شود.

به غیر از افرادی که از طریق آزمون برنامه نویسی مقدماتی جذب شده اند، کسانی که در سال های گذشته موفق به دریافت مدال نقره المپیاد کامپیوتر شده اند نیز در دوره حضور دارند. در پایان دوره به 8نفر از کسانی که بهترین عملکرد را در آزمون ها از خود نشان داده اند مدال طلا اهدا می شود.

بقیه دانش آموزان به مدال نقره و برنز دست پیدا کرده و به تعداد کمی که از خود عملکرد مطلوبی نشان نداده اند دیپلم افتخار اهدا می شود.

مرحله پنجم

دانش آموزان تا زمانی که مجاز به شرکت در المپیاد باشند می توانند با افزایش تسلط بر مفاهیم و توانایی های خود برای ورود به تیم ملی المپیاد کامپیوتر با یکدیگر رقابت کنند.

در این دوره علاوه بر تمرین، مباحث تکمیلی تر آموزش داده می شود. در پایان 4نفر از این دوره برای تشکیل تیم ملی المپیاد کامپیوتر انتخاب می شوند.

مرحله ششم

در این مرحله افراد برای اعزام به المپیاد جهانی کامپیوتر آماده می شوند که به دوره آمادگی تیم ملی کامپیوتر معروف است.

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

ترکیبات

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

نظریه گراف

• تعاریف اولیه: راس، یال، مسیر، گشت، گذر، مؤلفه همبندی
• مسیرها
• درجه رئوس، قضیه منتل، قضیه توران و دنباله ‌های گرافیکی
• گراف های جهت ‌دار و تورنمنت ‌ها
• درخت و قضیه ‌های مربوط به آن
• گراف‌ های اویلری
• قضیه هال
• پوشش یالی، پوشش راسی، مجموعه‌های مستقل
• قضیه تات، قضیه کونیگ و قضیه پترسن
• kهمبندی عالی و راسی
• رنگ ‌آمیزی یالی و قضیه ویزینگ
• رنگ ‌آمیزی راسی و دنباله ‌های رنگ ‌آمیزی
• دورهای همیلتونی
• برش ‌های یالی و راسی

الگوریتم

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

✓ نمادهای 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و ...

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

منابع مفید برای المپیاد کامپیوتر

منابع المپیاد کامپیوتر علاوه بر گسترده بودن، مدام دستخوش تغییرات می شود و ضروری است که از لیست به روز شده منابع استفاده کنید.

• نردبان المپیاد ریاضی، ترکیبیات مرحله اول، آرش جلالی، انتشارات گچ (آیریسک)
• الفبای المپیاد ریاضی، مرتضی محمد آبادی، انتشارات دانش ‌پژوهان جوان
• روش‌های ترکیبیات، علی‌رضا علی‌پور، انتشارات فاطمی
• استراتژی ‌های حل مسئله، انتشارات مبتکران
• المپیاد های ریاضی شوروی، مترجم پرویز شهریاری
• ترکیبیات، علیرضا علیپور، انتشارات فاطمی
• المپیاد های کامپیوتر ایران از آغاز تا کنون، مراحل اول، یاسر احمدی فولادی
• المپیاد های کامپیوتر ایران از آغاز تا کنون، مراحل دوم، یاسر احمدی فولادی
• المپیاد های ریاضی لنینگراد
• نظریه گراف و کاربردهای آن، باندی مورتی
• طراحی الگوریتم با رویکردی خلاقانه، یودی منبر
• مقدمه‌ ای بر الگوریتم ‌ها، مترجم عین ‌اله جعفرنژاد قمی (CLRS)
• How To Program C++،Deitel & Deitel
• آموزش برنامه ‌نویسی باC++ ، دایتل و دایتل، مترجم: حسن محمدی، حسین محمدی
• برنامه ‌نویسی به زبان C++، عین ‌اله جعفرنژاد قمی
• آشنایی با نظریه گراف، داگلاس بی. وست، نشر گسترش علوم پایه
• مسئله‌ های الگوریتمی، دکتر محمد قدسی

سوالات متداول

چه منابعی برای موفقیت در المپیاد کامپیوتر مطالعه کنیم؟

منابع المپیاد کامپیوتر بسیار گسترده است و به صورت جامع در مقاله به آن پرداخته شده است.

المپیاد کامپیوتر چند مرحله دارد؟

المپیاد کامپیوتر از 6 مرحله تشکیل شده است.

منبع: لیست دانشگاه های بدون کنکور روانشناسی تهران