مسابقات برنامهسازی پیشرفته
Advanced Programming Contests
| شماره درس: ۹۰۲۱ | تعداد واحد: ۳ |
| نوع درس: نظری | پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها |
اهداف درس
هدف از اين درس، آشنایی دانش‌جویان با مهارت‌های برنامهسازی پیشرفته است که در مسابقات برنامهسازی مانند مسابقات icpc مورد استفاده قرار می‌گیرد. پیش‌نیاز این درس، درس داده‌ساختارها و الگوریتم‌ها می‌باشد.
ریزمواد
- الگوریتم های هندسی (۲ جلسه)
- مفاهیم اولیه
- عملیات پایه هندسی
- پوسته محدب
- نمونه مسائل هندسی
- الگوریتم‌های گراف (۲ جلسه)
- بزرگترین جد مشترک و کاربردهای آن
- شار بیشینه
- برنامهسازی پویا (۲ جلسه)
- بلندترین زیردنباله صعودی
- برنامهسازی پویا دوبعدی (edit distance)
- برنامهسازی پویا روی بازه (مسئله ضرب بهینه ماتریس‌ها)
- برنامهسازی پویا روی درخت (محاسبه بزرگترین مجموعه مستقل وزن‌دار روی درخت)
- برنامهسازی پویای نمایی (پیدا کردن مسیر هامیلتونی در گراف)
- جبرخطی (۱جلسه)
- $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.