طراحی الگوریتم ها در آموزش المپیاد کامپیوتر-اول مشاور
17 اسفند 1395

طراحی الگوریتم ها در آموزش المپیاد کامپیوتر-اول مشاور

طراحی الگوریتم‌ها
مقدمات
• مقدمه‌ای بر طراحی الگوریتم
• پیچیدگی الگوریتم‌ها و مرتبه‌ی توابع
• مرتبه‌ی روابط بازگشتی
مرتب‌سازی و مرتبه آماری
• مرتبه‌ی آماری
o الگوریتم تصادفی شناسایی عنصر k
o الگوریتم شناسایی میانه
• مرتب‌سازی مقایسه‌ای
o درجی
o حبابی
o انتخابی
o ادغامی
o سریع
o هرمی
o حد پایین تعداد مقایسه‌ها
• مرتب‌سازی در زمان خطی
o شمارشی
o رقمی
o سطلی
داده‌ ساختارها
• آرایه و لیست
• صف و پشته
• درخت
• درخت عبارت
• درخت‌ جست‌وجوی دودویی
• درخت ترای
• هرم
• درهم‌سازی
• مجموعه‌های مجزا
• داده‌ساختار برای پرسمان‌های محدوده‌ای (روش RMQ)
• درخت پاره‌خطی یک بعدی
طراحی الگوریتم‌ها
الگوریتم‌ بازگشتی
• طراحی بازگشتی
• دنباله‌ی گری
• محاسبه‌ی توان
• برج هانوی
طراحی الگوریتم با استقراء
• طراحی الگوریتم با استقراء
• زیر آرایه با بیشینه‌ی جمع
• عنصر غالب
• مشهورترین شخص
• محاسبه‌ی مقدار چندجمله‌ای
• زیر گراف القایی با بیشینه درجه
روش تقسیم و حل
• روش تقسیم و حل
• به توان رساندن ماتریس‌ها و کاربردهایش
• زیرآرایه با بیشینه‌ی جمع
• آسمان‌خراش‌ها
• ضرب ماتریس‌ها
برنامه‌ریزی پویا
• برنامه‌های بازگشتی و روش به‌خاطرسپاری
• برنامه‌ریزی پویا
• طولانی‌ترین زیردنباله مشترک
• طولانی‌ترین زیردنباله صعودی
• خرد کردن‌ پول
• کوله پشتی
• ضرب ماتریس‌ها
• فاصله‌ی ویرایشی
• درخت جست‌وجوی بهینه
• زمانبندی پردازه‌های وزن‌دار
• برنامه‌ریزی پویای نامرتب در گراف حالات
الگوریتم‌های حریصانه
• الگوریتم‌های حریصانه
• زمانبندی پردازه‌ها
• خرد کردن پول
• کوله‌پشتی
• تطابق و مجموعه‌‌ی مستقل بیشینه در درخت
جست‌وجوی فضای حالات
• پس‌گرد
o وزیرها
• انشعاب و حد
o رنگ‌آمیزی گراف‌ها
o فروشنده دوره‌گرد
الگوریتم‌های گراف
الگوریتم‌های پایه
• نمایش گراف‌ها
• پیمایش گراف‌ها
o جست‌وجوی عمق‌اول
o جست‌وجوی سطح‌اول
• کاربردهای پیمایش گراف‌ها
o تست دو بخشی بودن گراف
o شناسایی مرکز گراف
o شناسایی کمر گراف
o شناسایی قطر گراف
o پیدا کردن مؤلفه‌‌های همبند
گراف‌های جهت‌دار
• مرتب‌سازی توپولوژیک
• تست غیردوری بودن گراف جهت‌دار
• گراف حالات و جست‌وجو در گراف‌های جهت‌دار
• پیدا کردن مولفه‌های قویا همبند
• بستار تعدی
کوتاه‌ترین مسیر با مبدا مشخص
• درخت کوتاه‌ترین مسیر و ویژگی‌های آن
• الگوریتم دایکسترا
• الگوریتم بلمن-فورد
همه‌ی زوج کوتاه‌ترین مسیرها
• الگوریتم تقسیم و حل
• الگوریتم ضرب ماتریسی
• الگوریتم فلوید-وارشال
درخت پوشای کمینه
• تعریف و ویژگی‌های درخت پوشای کمینه
• الگوریتم پریم
• الگوریتم کروسکال
دور اویلری
• ساخت تور اویلری با استقراء
• الگوریتم فلوری برای گراف‌های بی‌جهت
• الگوریتم فلوری برای گراف‌های جهت‌دار
• ساخت تور اویلری به‌کمک DFS
• مسئله‌ی De Bruijn
الگوریتم‌های درخت
• پیمایش درخت‌ها (پیش‌ترتیب٬ میان‌ترتیب و پس‌ترتیب)
• زمان شروع و پایان گره‌ها در پیمایش میان‌ترتیب
• ترتیب سطح‌اول گره‌ها
• محاسبه‌ی پایین‌ترین جد مشترک
• محاسبه‌ی قطر و مرکز درخت
دو صدق‌پذیری
• تشخیص دو صدق‌پذیر بودن
• کاهش به مسئله دو صدق‌پذیری
پردازش رشته‌ها
• الگوریتم رابین-کارپ
• الگوریتم KMP
الگوریتم‌های هندسی
• اعداد مختلط و کار با آن‌‌ها
• تقاطع‌ خط و پاره‌خط‌ها
• ضرب داخلی و خارجی
• مساحت چندضلعی و جمع زوایا
• تشخیص داخل بودن نقطه در چندضلعی