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

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

طراحی الگوریتم‌ها (تکمیلی)
این صفحه حاوی الگوریتم‌های تکمیلی است که بیشتر برای دانش‌پژوهان دوره‌ی طلا و کسانی که قصد شرکت در مسابقات ‌ای‌سی‌ام را دارند مفید می‌باشد.
داده‌ساختارها
• درخت پاره‌خطی دوبعدی
• درخت فنویک
• درخت دکارتی
• درخت بازه‌ای
• درخت کی‌دی
• درخت محدوده‌ای
• روش انتشار آبشاری
• اعداد بزرگ


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


جست‌وجوی فضای حالات
• هرس آلفا-بتا
• تناظر حالت‌ها با اعداد ( تبدیل جایگشت به عدد و برعکس)


الگوریتم‌های گراف
پیمایش گراف‌ها
• پیدا کردن راس برشی
• پیدا کردن یال برشی
• پیدا کردن یال‌های برشی در مدل برخط
• مولفه‌های دوهمبند


کوتاه‌ترین مسیر و مسائل مرتبط
• الگوریتم A∗
• برنامه‌ریزی خطی با نامساوی‌های دو متغیره


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


دورها
• مفاهیم کوتاهترین گشت و دور منفی
• پیدا کردن دور با کم‌ترین میانگین وزن


شار و مسائل مرتبط
• شار بیشینه و برش کمینه
• الگوریتم Ford-Fulkerson
• الگوریتم Edmonds-Karp
• الگوریتم Dinics
• الگوریتم Push-relabe
• الگوریتم Relabel-to-front
• شار با حد پایین
• مسیرهای مجزای یالی
• مسیرهای مجزای راسی
• ماکزیمم تطابق در گراف‌های دو بخشی
• صحیح کردن درایه‌های ماتریس با حفظ جمع سطر و ستون‌ها


تطابق و مسائل مرتبط
• تطابق و مسائل متناظر آن
• الگوریتم Kuhn
• الگوریتم Hopcroft-Karp
• الگوریتم Edmonds
• الگوریتم تصادفی با ماتریس Tutte
• پوشش راس‌ها در گراف جهت‌دار بی‌دور با مسیرهای مجزا


الگوریتم‌های درخت
• تجزیه‌ی سبک-سنگین درخت‌ها
• تجزیه‌ی درخت به دو درخت‌ تقریبا هم‌اندازه با حذف یک یال یا یک راس
• یک‌ریختی درخت‌ها
پردازش رشته‌ها
• آرایه‌ی پسوندی
• الگوریتم مبتنی بر DFA
• روش‌های مبتی بر درهم سازی در کار با رشته‌ها


ترکیبیات
• ضرایب دوجمله‌ای
• عدد کاتالان
• تولید ترکیب و جایگشت
• اصل طرد و شمول
• لم Burnside
• تولید پرانتز گذاری‌های معتبر


مجموعه‌ی مرتب جزئی
• شناسایی بزرگ‌ترین زنجیر
• شناسایی بزرگ‌ترین پادزنجیر
• شناسایی کوچک‌ترین افراز به زنجیر
• شناسایی کوچک‌ترین افراز به پادزنجیر


نظریه‌ی اعداد
• محاسبه‌ی تابع اویلر
• محاسبه‌ی بزرگ‌ترین مقسوم‌علیه مشترک
• غربال اراتستن
• محاسبه‌ی عضو معکوس در همنشتی
• قضیه‌ی باقی‌مانده‌ی چینی
• ریشه اولیه و محاسبه‌ی آن
• محاسبه‌ی فاکتوریل در همنهشتی
• محاسبه‌ی توان یک عدد در فاکتوریل
• محاسبه‌ی لگاریتم در همنهشتی
• محاسبه‌ی ریشه kام در همنهشتی
• حل معادله‌ی خطی دو متغیره در همنهشتی
• اعداد فیبوناچی و محاسبه‌ی سریع آن
• تست اول بودن عدد
• تجزیه‌ی اعداد


الگوریتم‌های تصادفی
• الگوریتم‌های لاس‌وگاس و مونتوکارلو
• مسئله استخدام
• مسئله پیچ و مهره
• درخت بازی
• مسئله کوچک‌ترین دایره محیطی
• برنامه‌ریزی خطی


جبر خطی
• محاسبه‌ی دترمینان ماتریس
• محاسبه‌ی معکوس ماتریس
• محاسبه‌ی مرتبه‌ی ماتریس
• حل دستگاه خطی با روش حذف گوسی
• حل دستگاه خطی در همنهشتی


مسائل بهینه‌سازی
• DFS with Iterative Deepening
• Hill Climbing
• Simulated Annealing
 

برنامه‌ریزی خطی
• برنامه‌ریز خطی
• دوگان برنامه‌ریزی خطی و رابطه‌ی بیشنیه و کمینه
• شناسایی رده‌ی مسائل با استفاده از برنامه‌ریزی خطی و دوگان آن
• الگوریتم Simplex
 

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


محاسبات پایه‌ای هندسه‌ی سه‌بُعدی
• محاسبه‌ی زاویه در فضای سه‌بعدی
• بردار نرمال (عمود بر) صفحه
• صفحه‌ی عبوری از سه نقطه
• وضعیت نقطه نسبت به صفحه
• وضعیت نقطه نسبت به خط
• وضعیت خط نسبت به صفحه
• وضعیت دو خط نسبت به‌هم
• وضعیت دو صفحه نسبت به‌هم
• تصویر نقطه روی صفحه
• تصویر نقطه روی خط
• تصویر خط روی صفحه
• خط مشترک دو صفحه
• نقطه‌ی تقاطع سه صفحه
• طول کوتاه‌ترین خم بین دو نقطه روی کره


تبدیل‌های هندسی دوبعدی
• انتقال، تقارن و دوران
• دوگان
• تبدیل Hough
• انعکاس


الگوریتم‌های هندسی پایه
• پوسته‌ی محدب
o الگوریتم Gift-Wrapping
o الگوریتم گراهام
• پیدا کردن دورترین دو نقطه
• پیدا کردن نزدیک‌ترین دو نقطه
• الگوریتم‌های جاروب
o محاسبه‌ی تقاطع مجموعه‌ای از پاره‌خط‌ها
o محاسبه‌ی تقاطع مجموعه‌ای از دایره‌ها
o محاسبه‌ی مساحت اجتماع مستطیل‌ها
o مجموع طول پاره‌خط‌ها
• کوتاه‌ترین مسیر در فضای هندسی
• جمع مینکوفسکی
• نقشه‌ی ورونوی
• داده‌ساختار DCEL
• داده‌ساختار مکان‌یابی


پیچیدگی محاسبات
• مسائل تصمیم‌گیری
• صدق‌پذیری
• برنامه‌ریزی صحیح
• کاهش مسئله
• نمونه‌هایی از کاهش به مسئله برنامه‌ریزی صحیح
• کلاس پی‌، ان‌پی و ان‌پی‌سی
• مسائل نمونه ان‌پی‌سی
• الگوریتم‌های شبه‌چندجمله‌ای
• الگوریتم‌های تقریبی (معرفی)