آموزش:الگوریتم های تکمیلی:سیلابس
فهرست مندرجات
طراحی الگوریتم‌ها
تحلیل الگوریتم‌ها
اثبات الگوریتم‌ها با استقرا و ناوردایی
مفهوم مرتبه (Order)
- پیچیدگی زمان اجرا و حافظه
- محاسبه‌ی مرتبه‌ی روابط بازگشتی
الگوریتم‌های پایه‌ای
جست‌وجوی دودویی
مرتب‌سازی و مطالب مرتبط
مرتب‌سازی خطی
- count-sort
- bucket-sort
- radix-sort
مرتب‌سازی مبتنی بر مقایسه
- bubble-sort
- selection-sort
- insertion-sort
- merge-sort
- heap-sort
- quick-sort
- حد پایین مرتب‌سازی
Order Statistics
- الگوریتم تصادفی شناسایی عنصر $k$ام
- الگوریتم شناسایی میانه در $O(n)$
داده‌ساختارها
داده‌ساختارهای نگه‌دارنده (Container)
- Array و Sorted-Array
- Linked-List
- Heap
- BST
- RBT
- Order-Statistic Tree
- Hash Table
- مقایسه‌ی داده‌ساختارهای نگه‌دارنده (خاصیت‌ها: sequential, ordered، عملیات‌ها: search, random-access, iterate, add, batch-add, delete, findMin)
داده‌ساختارهای دیگر
- صف و پشته
- درخت عبارت
- درخت Trie
- Distjoint Sets
- اعداد بزرگ
- Segment Tree
- Fenwick Tree
- ساختارهای Range Minimum Query
- Binary Indexed Tree
- Interval Tree
- Range Tree
- Heavy-Light Tree Decomposition
الگوهای طراحی الگوریتم
طراحی الگوریتم با روش‌های استقرایی
- مسئله‌ی زیرگراف القایی بیشینه با حداقل درجه $k$
- مسئله‌ی محاسبه‌ی مقدار چندجمله‌ای در $O(n)$
- مسئله‌ی زیررشته‌ی با بیشترین مجموع
- مسئله‌ی شناسایی celebrity
- مسئله‌ی شناسایی majority
- مسئله‌ی نمایش در مبنای فاکتوریل
بررسی تمام حالات (Brute-Force)
- مسائل مرتبط در USACO به‌خصوص قسمت 1.2
- back-tracking
- مسئله‌ی قراردادن وزیر‌ها در صفحه‌ی شطرنج
- تناظر حالت‌ها با اعداد
- مسئله‌ی تبدیل جایگشت به عدد و برعکس
الگوریتم‌های حریصانه
- فرم کلی اثبات الگوریتم‌های حریصانه
- مسائل USACO قسمت 1.3
- مسئله‌ی زمان‌بندی واحد‌های کاری با ضرب‌العجل و جریمه
- مسئله‌ی تطابق و مجموعه‌مستقل بیشینه در درخت
- مسئله‌ی کد هافمن
- مسئله‌ی ازدواج پایدار
الگوریتم‌های بازگشتی
- مسئله‌ی دنباله‌ی Gray
- الگوریتم محاسبه‌ی $x^n$ در $O(\log n)$
- مسئله‌ی حل رابطه‌های بازگشتی خطی در $O(\log n)$
تقسیم و حل
- مسئله‌ی Sky Line
- الگوریتم Karatsuba برای ضرب چندجمله‌ای
- الگوریتم Strassen برای ضرب ماتریس
- الگوریتم مبتنی‌بر FFT برای ضرب چندجمله‌ای
الگوریتم‌های پویا
- الگوریتم‌های بازگشتی با روش یادداشت‌برداری‌شده (memoized)
- مسئله‌های سایت http://codeforces.com/blog/entry/325
- مسئله‌های USACO قسمت 2.2 و 2.3
- مسئله‌ی خرد کردن پول
- مسئله‌ی OBST
- مسئله‌ی زمان‌بندی پردازنده‌های وزن‌دار
الگوریتم‌های پویای نمایی
- مسئله‌ی پوشاندن جدول ۱۰×n با دومینو
طراحی الگوریتم با تحلیل سرشکن
مفاهیم پیشرفته
- دوگان و minimax
- ماتروید
- شناسایی رده‌ی مسئله از روی LP و دوگان آن
الگوریتم‌های گراف
داده‌ساختارهای گراف
- ماتریس مجاورت
- لیست مجاورت
پیمایش گراف‌ها
- BFS
- DFS
- شناسایی مؤلفه‌های همبندی
- مسئله‌ی شناسایی کمر گراف
- مسئله‌ی شناسایی مرکز گراف
- مسئله‌ی شناسایی قطر گراف
الگوریتم‌های ویژه‌ی درخت‌ها
- الگوریتم شناسایی مرکز درخت
- الگوریتم شناسایی قطر درخت
- افراز درخت به دو درخت تقریبا هم‌اندازه با حذف یال یا رأس
- مسئله‌ی هم‌ریختی درخت‌ها
الگوریتم‌های ویژه‌ی درخت‌های ریشه‌دار
- پیمایش‌های درخت
- پیش‌ترتیب
- میان‌ترتیب
- پس‌ترتیب
- ترتیب سطح اول
- الگوریتم شناسایی پایین‌ترین جد مشترک
الگوریتم‌های ویژه‌ی گراف‌های بی‌جهت
- رأس‌های برشی
- یال‌های برشی
- مؤلفه‌های دوهمبند
الگوریتم‌های ویژه‌ی گراف‌های جهت‌دار
- تست DAG بودن گراف
- Topological Sorting
- مؤلفه‌های قویاً همبند
- بستار تعدی
تور اویلری
- ساخت تور اویلری با استقرا
- الگوریتم فلوری برای گراف‌های بی‌جهت
- الگوریتم فلوری برای گراف‌های جهت‌دار
- ساخت تور اویلری به‌کمک DFS
- مسئله‌ی De Bruijn
مسائل کوتاه‌ترین مسیر
- معرفی مفاهیم کوتاه‌ترین گشت و دور منفی
کوتاه‌ترین مسیر با یک مبدأ مشخص
- Dijkstra
- Bellman-Ford
- الگوریتم $A^*$
- الگوریتم Leviticus (؟؟؟)
کوتاه‌ترین مسیر بین هر جفت رأس
- روش ضرب ماتریسی $O(n3logn)$
- روش تقسیم و حل (؟؟؟)
- Floyd-Warshall
- Johnson (برای گراف‌های خلوت)
مسائل مرتبط با کوتاه‌ترین مسیر
- مسئله‌ی شناسایی دور منفی
- مسئله‌ی شناسایی دور با کم‌ترین میانگین وزن
- مسئله‌ی حالت خاص LP با نامساوی‌های دوتایی
Minimum Spanning Tree
- Kruskal
- Prim
- مسئله‌ی کوتاه‌ترین مسیر با هزینه‌ی گلوگاهی
تطابق بیشینه
تطابق دوبخشی
- مسائل متناظر با تطابق دوبخشی (پوشش رأسی، پوشش یالی، مجموعه مستقل)
- الگوریتم Kuhn (تطابق دوبخشی با DFS)
- الگوریتم Hopcroft-Karp (تطابق دوبخشی با BFS)
تطابق دوبخشی کامل با وزن بیشینه
تطابق بیشینه در گراف‌های کلی
- الگوریتم شکوفه ادموند
- الگوریتم تصادفی با ماتریس Tutte
جریان بیشینه و برش کمینه
- الگوریتم Ford-Fulkerson
- الگوریتم Edmonds-Karp
- الگوریتم Dinics
- الگوریتم Push-relabel
- الگوریتم Relabel-to-front
- مسئله‌ی مسیرهای یال‌مجزا
- مسئله‌ی مسیرهای رأس‌مجزا
- مسئله‌ی Lower-bound Flow
- مسئله‌ی Min-Cost Flow
الگوریتم‌ها وساختارهای رشته‌ای
- روش‌های مبتنی‌بر Hash در کار با رشته‌ها
String Matching
- الگوریتم String Matching بدیهی
- الگوریتم Rabin-Karp
- الگوریتم KMP
- الگوریتم DFA-String-Matching
Suffix Tree و Suffix Array
عبارت‌های ریاضی
- شیوه‌ی نمایش عبارت‌های ریاضی
- prefix
- infix
- postfix
- مسئله‌ی parse کردن عبارت‌های ریاضی در $O(n)$
- الگوریتم Shunting-yard
متفرقه
- مسئله‌های فصل ۷ از کتاب «مسئله‌های الگوریتمی»
الگوریتم‌های مرتبط با منطق و ساختارهای گسسته
- Horn-SAT
- 2SAT
مجموعه‌ی مرتب جزئی
- مسئله‌ی شناسایی بزرگ‌ترین زنجیر
- مسئله‌ی شناسایی بزرگ‌ترین پادزنجیر
- مسئله‌ی شناسایی کوچک‌ترین افراز به زنجیر
- مسئله‌ی شناسایی کوچک‌ترین افراز به پادزنجیر
بازی‌ها
- بازی‌های منصفانه (Nimِ معادل و MEX و …)
- alpha-beta-pruning
- مسئله‌های فصل ۴ از کتاب «مسئله‌های الگوریتمی»
نظریه اعداد
- الگوریتم محاسبه‌ی ب.م.م
- الگوریتم‌های وارون در $Z_p$
- پیدا کردن وارون با extended-gcd
- پیدا کردن وارون با رساندن به‌توان $p-2$
- باقی‌مانده‌ی چینی
الگوریتم‌های هندسی
- مفاهیم اولیه در الگوریتم‌های هندسی
- اعداد مختلط
- ضرب داخلی
- ضرب خارجی
محاسبات پایه‌ای هندسه‌ی دوبعدی
- مساحت چندضلعی ساده
- جهت چندضلعی محدب
- جهت چندضلعی ساده
- فاصله‌ی دو نقطه
- یکه‌کردن بردار
- فاصله‌ی علامت‌دار نقطه از خط (پاره‌خط)
- وضعیت نقطه نسبت به خط (پاره‌خط)
- محاسبه‌ی زاویه‌ی بی‌علامت
- محاسبه‌ی زاویه‌ی علامت‌دار
- تعیین نقطه
- تصویر نقطه روی خط (پاره‌خط)
- نقطه‌ی متقارن یک نقطه نسبت به یک خط
- تقاطع دو خط (پاره‌خط)
- تقاطع‌های دایره و خط (پاره‌خط)
- تقاطع‌های دو دایره
- تعیین خط (پاره‌خط)
- خط عبوری از دو نقطه
- عمودمنصف دو نقطه
- نیم‌ساز زاویه
- خط عبوری از یک نقطه، با یک زاویه‌ی مشخص
- خط عبوری از یک نقطه، موازی یک خط دیگر
- خط عبوری از یک نقطه، عمود بر یک خط دیگر
- مماس مشترک‌های نقطه و دایره
- مماس مشترک‌های دو دایره
- تعیین دایره
- دایره‌ی عبوری از سه نقطه (دایره‌ی محیطی مثلث)
- دایره‌های مماس با سه خط (دایره‌ی محاطی مثلث)
- دایره‌های عبوری از دو نقطه و مماس با یک خط
- دایره‌های عبوری از یک نقطه و مماس با دو خط
- دایره‌های عبوری از دو نقطه با شعاع مشخص
- دایره‌های مماس با دو خط با شعاع مشخص
- دایره‌های عبوری از یک نقطه و مماس با یک خط و با شعاع مشخص
- محاسبه‌ی کمان‌درخور دو نقطه با داشتن زاویه
الگوریتم‌های Point-in-Polygon
- Ray Casting (تقاطع با نیم‌خط و قانون زوج‌وفرد)
- Winding Number (محاسبه‌ی عدد چرخش با تجمیع زوایا)
الگوریتم‌های پوش محدب
- Gift-Wrapping
- Graham’s Scan
- حد پایین زمان اجرا برای پوش محدب
- مسئله‌ی دورترین دو نقطه
استفاده از تقسیم و حل
- مسئله‌ی نزدیک‌ترین دو نقطه
استفاده از خط جاروب
- مسئله‌ی برخورد پاره‌خط‌ها
- مسئله‌ی برخورد دایره‌ها
- حل مسئله‌ی Sky-Line با خط جاروب
- مسئله‌ی اجتماع مستطیل‌ها
مباحث دیگر
- مسئله‌های کوتاه‌ترین مسیر در فضای هندسی
- جمع مینکوفسکی
- داده‌ساختار DCEL
- دیاگرام Voronoi
- Priority Search Tree و k-d Tree
- Fractional Cascading
- داده‌ساختار Point-Location
- مسئله‌های فصل ۳ از کتاب «مسئله‌های الگوریتمی»
تبدیل‌های هندسی دوبعدی
- انتقال، تقارن و دوران
- تبدیل دوگان
- تبدیل Hough
- انعکاس
هندسه‌ی سه‌بُعدی
- محاسبه‌ی زاویه در فضای سه‌بعدی
- بردار نرمال (عمود بر) صفحه
- صفحه‌ی عبوری از سه نقطه
- وضعیت نقطه نسبت به صفحه
- وضعیت نقطه نسبت به خط
- وضعیت خط نسبت به صفحه
- وضعیت دو خط نسبت به‌هم
- وضعیت دو صفحه نسبت به‌هم
- تصویر نقطه روی صفحه
- تصویر نقطه روی خط
- تصویر خط روی صفحه
- خط مشترک دو صفحه
- نقطه‌ی تقاطع سه صفحه
- طول کوتاه‌ترین خم بین دو نقطه روی کره
جبر خطی
- شناسایی بزرگ‌ترین زیرمجموعه‌ی مستقل خطی
- محاسبه‌ی دترمینان
- حل دستگاه خطی با روش حذف گاوسی
- دستگاه خطی در فضای $Z_p$
- محاسبه‌ی معکوس ماتریس
- LP و دوگان
- Simplex
پیچیدگی محاسبات
- مسئله‌های تصمیم‌گیری
- تعریف دقیق مرتبه‌ی زمان اجرا و حافظه
- الگوریتم‌های Pseudo-Polynomial
- مفهوم عدم قطعیت
- کلاس‌های P و NP
- مفهوم کاهش (Mapping-Reduction)
- کلاس‌های C-Hard و C-Complete
- مسئله‌ی Circuite-Evaluation
- مسئله‌ی SAT
- مسئله‌ی CNF-SAT
- مسئله‌ی 3SAT
- مسئله‌ی Integer Programming
- مسئله‌های معروف NP-Complete (http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)
مسائل بهینه‌سازی
- Branch & Bound
- DFS with Iterative Deepening
- Hill Climbing
- Simulated Annealing
- مسائل USACO قسمت 4.1
- مسئله‌ی TSP
الگوریتم‌های تقریبی
- مسئله‌ی TSP – الگوریتم‌های تقریبی
- مسئله‌ی پوشش رأسی – الگوریتم‌های تقریبی
- تقریب ناپذیری
الگوریتم‌های تصادفی
- الگوریتم‌های لاس‌وگاس و مونت‌کارلو
- مسئله استخدام (Hiring Problem)
- مسئله پیچ و مهره (؟؟؟)
- درخت بازی (؟؟؟)
- مسئله کوچک‌ترین دایره محیطی
- برنامه‌ریزی خطی
- Power of Two Choices
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
