منابع المپیاد دانشجویی مهندسی کامپیوتر

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

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

من سال های ۱۳۹۸ و ۱۳۹۹ در المپیاد شرکت کردم که سال اول نتیجه ام خیلی خوب نشد! و سال بعد رتبه دوم مشترک شدم.

چجوری شرکت کنم حالا؟

خب اول یه سری قوانین المپیاد رو براتون بگم که بدونید. روش ورود به المپیاد از راه کنکور و یا منطقه‌ است (البته سال ۱۳۹۹ به خاطر شرایط کرونا تغییر کرد که احتمالا دیگه مهم نیست). از کنکور ۱۵ نفر اول انتخاب میشن و از هر از منطقه ۵ نفر. ۱۰ تا منطقه در کل داریم که ۶۵ نفر در کل حضور پیدا می‌کنند.

کسایی که از سمت کنکور میرن که راهشون مشخصه! اونایی که از منطقه میخوان برن، ابتدا باید در ۵ نفر برتر دانشکده خودشون باشن و بعد میرن امتحان منطقه‌ای میدن و باید تو ۵ نفر اول منطقه باشن تا راهیابی پیدا کنن به مرحله فینال.

چون خیلی ها سوال پرسیدن این دو تا نکته رو هم بگم.

اول: المپیاد مهندسی کامپیوتر فقط واسه کسانی هست که رشته‌شون همینه. کسی که از فیزیک یا ریاضی یا هر رشته دیگه ای میاد، حتی اگر نفر یک کنکور بشه، نمیتونه شرکت کنه. (فقط مطمئن نیستم دوستان علوم کامپیوتر میتونن شرکت کنند یا نه. اگر کسی اطلاعی داره بهم بگه.)

دوم: حتما باید موقع المپیاد دانشجوی سال سوم یا چهارم کارشناسی باشید. مثلا اگر از فارغ التحصیلی کارشناسی تون یکی دوسال گذشته دیگه نمیشه.

اصلا چه فایده‌ای داره؟!

۱۵ نفر اول می‌تونن درخواست گواهی بدن و جز دانشگاه های تاپ تهران (یعنی شریف و امیرکبیر و تهران) هر جایی خواستن بدون کنکور برن و ۵ نفر اول می‌تونن به هر دانشگاهی بدون کنکور برن.

البته یک چیز درگوشی بهتون بگم که کسایی بودن که ۸ ام یا ۹ ام شدن و به امیرکبیر و حتی شریف درخواست دادن و قبولشون کردن! درسته که تو قانونش نیست ولی ممکنه!

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

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

در مورد بنیاد ملی نخبگان هم اونجوری که خودش میگه «عضو نداره» یعنی هیچکس عضو بنیاد ملی نخبگان نیست. یه سری ها یه امتیازهایی جمع میکنند و به یه حد نصابی که رسید میتونن از طرح های بنیاد استفاده کنن. مثلا در مورد سربازی امتیازتون که به ۱۳۰ رسید می‌تونید درخواست بدین که پرونده تون بررسی بشه و اگر دوست داشتن بهتون پروژه بدن. جدولش هم تو سایت اش هست.

چی بخونم حالا؟

المپیاد ۵ تا درس داره همیشه. که ۴ تاش رو باید امتحان بدین و یکیش رو باید حذف کنین. دقت کنید اون حذفی اینجوری نیست که بگین من نمی‌خوام حذف کنم. باید حذف کنین :)

از اونجایی که آدمیزاد ذاتا دنبال راه میانبره یه قانون دیگه‌اش که خیلی مهمه رو بگم که خیالتون راحت بشه. از قبل باید مشخص کنید که چه درسی رو نمی‌خواین آزمون بدین. نمیشه برین سرجلسه سوال‌ها رو ببینید و بگید من نمیخوام این رو امتحان بدم. :))

درس ها عبارتند از: نظریه زبان‌ها و ماشین‌ها، مدارمنطقی و معماری کامپیوتر، الگوریتم و ساختمان‌های داده، سیستم عامل و شبکه‌های کامپیوتری.

۱- نظریه زبان و ماشین

این رو از زبان بچه های امیرکبیر میگم. سال ۱۳۹۸ که امتحان دادم بعد امتحان نظریه کپ کرده بودم (تعجب خیلی زیاد) که این چرت و پرت‌ها چی بود اصلا! از کدوم کتاب سوال داده بودن؟ چه طرزش بود؟ اونجا بود که دوستان امیرکبیر گفتند که نظریه ۴ تا سوال داره معمولا که ۲ تا از کتاب آقای مایکل سیپسر میاد و ۲ تا هم از کتاب پیتر لینز.

به نظرم اگر خواستید شرکت کنید تمرین های کتاب پیتر لینز رو حل کنید. یه پیش بینی هم می‌کنم که یه سوال هم حتما از یکی از لم‌های تزریق میاد! زمان ما اومد.

۲- معماری کامپیوتر و مدارمنطقی

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

برای کنکور به نظرم فیلم‌های پروفسور نوابی یه کم زیاده ولی برای المپیاد به هیچ وجه زیاد نیست! حتما همش رو ببینید. از اون به بعد برای هر دو درس به تعداد زیادی سوال نیاز دارید که یه منبعش نمونه سوالات کنکور هست که توصیه می‌کنم و دیگری هم یه کتابی که از انتشارات نص برای معماری کامپیوتر گرفتم به نام «رهیافت حل المسائل در معماری کامپیوتر» ترجمه مریم تقی زاده است.

۳- سیستم عامل

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

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

۴-ساختمان داده و الگوریتم

مهم ترین کتابی که به نظرم باید مطالعه بشه کتاب داده ساختار ها و الگوریتم دکتر قدسی و البته کتاب ۶۰۰ مسئله دکترقدسی است.

من خودم برای یادگیری نحوه پیاده سازی الگوریتم ها و درک بهترشون فیلم های ماش همدانی (The ultimate algorithm and data structure course) رو هم دیدم. به نظرم خیلی خوب بودن.

یادتون باشه که در سوالات ممکنه ازتون بخوان که کد بنویسید و باید بتونید حداقل یه شبه کد مثل امتحان الگوریتم که احتمالا دادین، بنویسید!

۵- شبکه های کامپیوتری

کتاب مرجع کراس راسه. قدیم (البته منظورم ۱۰۰ سال پیش نیست همین ۳ ۴ سال پیش) رفرنس کتاب آقای تننباوم بود که خیلی هم کتاب خوبیه.

سال ۹۸ یه سوال داده بودن ببینید چه جالب بود: گفته بودن پروتکل MPLS را به طور کامل شرح دهید و مزایا و معایبش رو هم بنویسید و شکل هم بکشید و خلاصه تاریخچه اش رو هم بگید. یعنی اینجور چیزهایی هم کاملا ممکنه حتی. فکر نکنید همش حل مسئله اس.

به نظرت کدوم رو حذف کنیم؟

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

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

قبلا هر درس ۴ ۵ تا سوال میومد ولی امسال (۱۴۰۰) که برنامه رو دیدم به نظرم اومد چون تو یک روز برگزار میشه (مثل امتحانی که ما تو ۱۳۹۹ دادیم) تعداد سوال ۳ یا حداکثر ۴ تاس.

حال و هوای سوالات چطوره؟

سوالات بیشتر جنبه اثباتی و تشریحی دارن. ازتون میخوان که جواب رو تشریحی و کامل بنویسید و توضیح بدید و اثبات کنید. مثلا دو صفحه اثبات نوشتن در یک سوال خیلی عادیه و اصلا عجیب نیست. در ضمن سوالات هر دو مرحله تشریحی هست.

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

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

نتایج از کجا اعلام میشه؟

نتایج دانشگاه رو که معمولا استاد مسئول استعداد درخشان دانشکده اعلام می‌کنه و ارسال می‌کنه. نتایج المپیاد منطقه‌ای رو هم همون استاد بهتون میگه و بعضی وقت‌ها تو سایت خود دانشگاه میذارن. نتایج مرحله نهایی رو فقط و فقط از سایت المپیاد می‌تونید نگاه کنید. بعدشم اگر رتبه ۱ تا ۱۵ شده باشید یه درخواست رتبه می‌دید و یه گواهی براتون ارسال می‌کنند.

چند تا سوال نمونه از المپیاد ۱۳۹۸ که یادمه!

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

نظریه

سوالات نظریه سخت بود و تمام سوالات از جنس اثبات بود. هیج کدوم از سوالات از جنس حل کردن نبودن.

سوال اول گفته بود: اگر یک زبان مستقل از متن بر روی الفبای تک حرفی مثلا a داشته باشیم. آیا این زبان لزوما منظم است؟ اثبات کنید!

سوال دوم بدین صورت بود که گفته بود عبارت منظمی رو در نظر بگیرین. اگر زبان ال پریم رو بصورت زیر تعریف کنیم، زبان ال پریم مستقل از متن است یا خیر و منظم است یا خیر. ادعای های خود را ثابت کنید.(زبان ال پریم میشه مجموعه رشته هایی که تعداد صفر ها و یک هاشون حداقل با یه عضو مجموعه ال که همون زبان منظم اولیه باشه برابرن. )

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

سوال اخر به این صورت بود که گفته بود اگر یه زبان بر روی ماشین تورینگ قطعی به اسم p داشته باشیم و زبانی هم بر روی ماشین تورینگ غیرقطعی به اسم NP داشته باشیم. اثبات کنید زبان P بر روی عملگر بستار بسته است. و اثبات کنید زبان NP بر روی عملگر بستار بسته است که به نظر من دومی اشتباه هست. اثبات هاش هم بلد نبودم.

سیستم عامل

سوالات درس سیستم عامل به نظر از کتاب سیلبرشاتس بود‌. جمعا ۵ سوال داشت و به نسبت نظریه آسون‌تر بود.

سوال اول یه مساله ارایشگر خواب الود بود و به جای ارایشگر TA قرار داشت. میگفت این TA روی بچه ها میان بیدار میکنن و اگر کسی بود رو صندلی می شینن منتهی حداکثر تعداد صندلی ۳ تا هست. اگر جا نبود میرن بعدش بیان. گفته بود که کدش رو بنویسید.

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

Movl fg, %da

Cal printf

Push %c

Move global, %d

سوال سوم فرض کنید در شرکتی کار میکنید که سیستم عامل ان ویندوز NT است. شرکت میخواد به لینوکس مهاجرت کنه. برای شرکت نمی صرفه که برنامه ها رو دوباره run and compile کنه. برای شرکت راه حل بدین و مزایا و معایبش رو بگین. قسمت اولش بود تازه. حالا شبه کد هم براش بنویسین‌.

سوال چهارم در مورد Earlieat deadline first بود که گفته بود cpu load چقدره.

سوال پنجم تعداد خط پرینت hello os شده در یه فور بود که داخلش دستور فورک داشت. گفته بود فرض کنین دستور فورک خطا نمیده. حالا بگین چند بار عبارت چاپ میشه.البته تابع پرینت اف خارج فور بود.

شبکه

سوالات شبکه راحت بودن.

اولین سوالش MPLS بود. گفته بود پروتکل رو توضیح بدین. بگین چجوری با هم سر شماره لینک هماهنگ میشن و کلا مزایا و معایبو خلاصه هر چی میدونین بگین‌ دو صفحه هم جا گذاشته بود که هر چی خواستیم بنویسیم.

سوال دوم درباره پروتکل SR و GBN بود و گقته بود اگر یه پیغام به طول فلان داشته باشیم و هر بسته هم یه سایز مشخص داشته باشه و پکت ۱۰ و ۱۲ گم بشه کلا بگین چه اتفاقی میفته که باید کنترل ازدحام TCP و تایم اوت و این چیزا رو بلد میبودین. میفهمیدین سایز پنجره و شماره اک هر بسته چقدر میشه. لاگ کامل خواسته بود. با جدول میشد کشید.

برای حل کردن سوال ۳ و۴ باید بلد میبودین که اگر بسته ها یکی یکی از مسیریاب اول به دوم برسن کی میرسن چقدر منتظر میمونن. اینا یعنی با هزینه لینک متفاوت چقدر داده ها تو صف میمونن.

سوال اخر گفته بود اگر یه فایل html و ۵ تا فایل داشتیم ۲ تا فایل روی یه سرور و ۳ تا روی یه سرور دیگه‌. بگین چقدر طول میکشه. هزینه لینک ها و مشخصات لینک ها رو هم داده بود. صرفا یه جمع و تفریق ساده بود. گفته بود حالا اگر مثلا هر دو با هم به لینک بفرستن هزینه لینک تغییر کنه و بشه انقدر چقدر طول میکشه.

الگوریتم

ننوشتم. یادم نیست.

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

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

از وقتی که گذاشتید و مطالعه کردین، ممنونم. در ضمن در وبلاگ اصلی‌ام بعضی سوال‌هایی که ازم بصورت ایمیل پرسیده شده رو جواب دادم.