Summer of code
الگوریتم
توضیح دوره
در این دوره، با آشنایی با الگوریتمهای ابتدایی و پرورش تفکر الگوریتمی، داوطلبان برای مسابقاتی مانند ICPC و راندهای الگوریتمی مسابقههای استخدامی آماده میشوند. با مسابقاتی که در طول دوره برگزار میشوند، داوطلبان میتوانند درک بهتری از برنامهنویسی مسابقهای و فضای رقابتی داشته باشند.
سرفصلها
📝 آزمون ابتدایی:
یک آزمون یک و نیم ساعته در کوئرا که نیازمند هیچگونه دانش قبلی نسبت به الگوریتم نداشته و صرفا به منظور ایجاد آمادگی ذهنی شرکتکنندگان طراحی شده. این آزمون شامل 6 مسئله خواهد بود.
📆 جلسه اول: آشنایی
توضیحات مقدماتی راجع به مزایای یادگیری ساختار داده و الگوریتم در صنعت و حوزههای آکادمیک.
📚 تکلیف این جسله: دو یا سه مسئله که در جلسه بعدی توضیح داده خواهند شد.
📆 جلسه دوم: آشنایی با جاج (judge)-های آنلاین و ساختار دادههای STL
این جلسه شامل صحبتی کوتاه راجع به جاجهای آنلاین و ساختار دادههای STL خواهد بود. پس از آن چند مسئله ساده ساختار داده به شرکتکنندگان ارائه خواهد شد که در کلاس حل میشوند. علاوه بر آن از شرکتکنندگان درخواست خواهد شد تا در گروههای مورد نیاز عضو شوند.
📚 تکلیف این جلسه: چند مسئله ساده از ساختار داده در کوئرا
📆 جلسه سوم: پیچیدگی زمانی
یک توضیح کلی از پیچیدگی زمانی ارائه خواهد شد. به دلیل سخت بودن این مبحث، از توضیح برخی از مسائل آن اجتناب خواهد شد.
📚 تکلیف این جلسه: پنج مسئله بروت فورس در کوئرا به همراه چند مسئله آنالیز پیچیدگی زمانی
📆 جلسه چهارم: الگوریتمهای سورت
چند الگوریتم معروف سورت کردن معرفی خواهند شد. در نهایت از شرکتکنندگان درخواست میشود تا یکی از این الگوریتمها (به جز bubble sort) را پیادهسازی کنند. علاوه بر آن، با استفاده از اطلاعات جلسات قبلی، پیچیدگی زمانی برخی از این الگوریتمها را محاسبه میکنیم.
📚 تکلیف این جلسه: دو مسئله سورت کردن با پیچیدگی زمانی مختلف پیادهسازی خواهند شد. چند ویدیو آموزشی و منابع از set-ها و map-ها برای مطالعه معرفی خواهند شد.
📆 جلسه پنجم: الگوریتمهای بازگشتی
شروع جلسه با ایجاد تمام زیرمجموعههای یک مسئله با استفاده از bitmask خواهد بود. علاوه بر آن نحوه محاسبه تمام جایگشتها را نیز بحث خواهیم کرد.
📚 تکلیف این جلسه: چند ویدیو راجع به backtracking و DFS ارائه خواهد شد که با استفاده از آن، شرکتکنندگان قادر به حل مسائل موجود در کوئرا خواهند بود.
📆 جلسه ششم: اولین مسابقه
یک مسابقه یک و نیم ساعته؛ ممکن است در قالب تیمهای دو نفره مسابقه انجام شود. علاوه بر آن در انتهای مسابقه جوایز ارائه خواهد شد.
📆 جلسه هفتم: آشنایی با الگوریتمهای حریصانه
در این جلسه تعدادی مسئله به شرکتکنندگان ارائه خواهد شد تا شهود خود را تقویت کنند. در نهایت جوایزی ارائه خواهد شد.
📚 تکلیف این جلسه: تکلیفی در این جلسه نخواهد بود تا شرکتکنندگان به موضوعات قبلی برسند.
📆 جلسه هشتم: آشنایی با جستجوی دودویی
به شرکتکنندگان تعدادی مسئله برای آشنایی با این مفهوم ارائه خواهد بود. در نهایت مفهوم set-ها را مرور کرده و توابع upper_bound و lower_bound را معرفی میکنیم.
📆 جلسه نهم: آشنایی با Prefix Sum و Recap
توضیحاتی حول Prefix Sum داده خواهد شد و مسئله معروف “maximum subarray sum” حل خواهد شد. علاوه بر آن Prefix Sum را برای حالت آرایه دو بعدی نیز حل خواهیم کرد.
📚 تکلیف این جلسه: چند مسئله ساده در رابطه با بهینه کردن partial sum-ها ارائه خواهد شد.
📆 جلسه دهم: آشنایی با گرافها
کمی راجع به نحوه ذخیره کردن گرافها، الگوریتم DFS روی گراف و داده ساختار استک صحبت میکنیم.
📚 تکلیف این جلسه: چند مسئله مرتبط روی کوئرا آپلود خواهد شد.
📆 جلسه یازدهم: الگوریتم BFS،
داده ساختار صف و کوتاهترین مسیر در گرافهای ساده توضیحاتی راجع به نحوه پیادهسازی BFS با استفاده از صفها داده خواهد شد.
📚 تکلیف این جلسه: چند مسئله مرتبط رو کوئرا قرار خواهد گرفت.
📆 جلسه دوازدهم: آشنایی با DP
مسائل جلسه نهم رو با ایده DP حل خواهیم کرد.
📚 تکلیف این جلسه: چند مسئله از Atcoder DP contest ارائه خواهد شد.
📆 جلسه سیزدهم: ادامه DP و Memoization
توضیحات بیشتری حول DP داده خواهد شد. علاوه بر آن مسائل بازگشتی و recursive را با استفاده از حافظه و Memoization حل خواهیم کرد.
📚 تکلیف این جلسه: چند مسئله معروف در این مورد ارائه خواهد شد.
📆 جلسه چهاردهم: آخرین مسابقه
یک مسابقه دو ساعته؛ احتمالا در تیمهای دو نفره. در انتهای مسابقه جوایزی ارائه خواهد شد.
این مسابقه در کوئرا برگزار خواهد شد و شامل مسائلی برای مرور و یادگیری عمیقتر جلسات پیشین خواهد بود.
مدرس: سروش صحرایی
- دارای مدال نقره المپیاد کامپیوتر ایران
- دارای مدال نقره ICPC غرب آسیا
- یک سال تدریس المپیاد کامپیوتر در مرکز آموزشی علامه حلی یک
مهلت ثبت نام تمام شده است.