مسابقات برنامهسازی پیشرفته
| مدرس: کمیته علمی مسابقات برنامهسازی | گواهی: رسمی دوزبانه |
| ترم: آبان و آذر ۱۴۰۳ | پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها |
| زمان ارائه: یک‌شنبه و سه‌شنبه ۱۶:۳۰ تا ۱۸:۰۰ | محل برگزاری: کلاس مجازی |
هدف کلی
هدف از این درس، آشنایی دانش‌جویان با مهارت‌های برنامهسازی پیشرفته است که در مسابقات برنامهسازی مانند مسابقات بین‌المللی رایان و ICPC مورد استفاده قرار می‌گیرد. پیش‌نیاز این درس، درس داده‌ساختارها و الگوریتم‌ها می‌باشد.
ریزمواد
- الگوریتم های هندسی (۲ جلسه)
- مفاهیم اولیه
- عملیات پایه هندسی
- پوسته محدب
- نمونه مسائل هندسی
- الگوریتم‌های گراف (۲ جلسه)
- بزرگ‌ترین جد مشترک و کاربردهای آن
- شار بیشینه
- برنامهسازی پویا (۲ جلسه)
- بلندترین زیردنباله صعودی
- برنامهسازی پویا دوبعدی
- برنامهسازی پویا روی بازه
- برنامهسازی پویا روی درخت
- برنامهسازی پویای نمایی
- جبر خطی (۱جلسه)
- n معادله و m مجهول
- حل مسائل به کمک ضرب ماتریس‌ها
- نظریه اعداد (۱ جلسه)
- ب.م.م. و معادله ax+by=c
- باقی مانده چینی
- الگوریتم های رشته (۲ جلسه)
- درخت پیش‌وندی
- آرایهٔ پس‌وندی
- الگوریتم KMP
- چکیده‌سازی
- کتابخانه STL (۱ جلسه)
- دربرگیرنده‌ها
- شمارنده‌ها
- الگوریتم‌ها
- استراتژی مسابقه دادن (۱ جلسه)
- استراتژی‌های کلی مسابقات برنامهسازی رقابتی
- مدیریت استرس
- مدیریت زمان
- کار تیمی
- قواعد پیاده‌سازی مسائل با کد پیچیده
ارزیابی
- تمرین‌های عملی
منابع
- S. Halim, F. Halim, and S. Effendy. Competitive Programming 4. The new lower bound of programming contests in the 2020s. Lulu, 2020.
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd edition, Springer-Verlag, 2008.