آموزش مرور کوتاه‌ترین مسیرها، مسائل NP-Complete و راهکارهای حل آن‌ها - آخرین آپدیت

هفته اول Week 1

• مرور کوتاه‌ترین مسیرهای تک منبع Single-Source Shortest Paths, Revisted

• زیرساخت بهینه Optimal Substructure

• الگوریتم پایه ۱ The Basic Algorithm I

• الگوریتم پایه ۲ The Basic Algorithm II

• تشخیص چرخ‌های منفی Detecting Negative Cycles

• بهینه‌سازی فضا A Space Optimization

• مسیریابی اینترنتی ۱ [اختیاری] Internet Routing I [Optional]

• مسیریابی اینترنتی ۲ [اختیاری] Internet Routing II [Optional]

• تعریف مسئله Problem Definition

• زیرساخت بهینه Optimal Substructure

• الگوریتم فلوید-وارشال The Floyd-Warshall Algorithm

• تکنیک بازوزن‌دهی A Reweighting Technique

• الگوریتم جانسون ۱ Johnson's Algorithm I

• الگوریتم جانسون ۲ Johnson's Algorithm II

هفته دوم Week 2

• مسائل قابل حل در زمان چندجمله‌ای Polynomial-Time Solvable Problems

• کاهش‌ها و کامل بودن Reductions and Completeness

• تعریف و تفسیر NP-Completeness ۱ Definition and Interpretation of NP-Completeness I

• تعریف و تفسیر NP-Completeness ۲ Definition and Interpretation of NP-Completeness II

• پرسش P در مقابل NP The P vs. NP Question

• رویکردهای الگوریتمی برای مسائل NP-Complete Algorithmic Approaches to NP-Complete Problems

• مسئله پوشش رأس (Vertex Cover) The Vertex Cover Problem

• جستجوی هوشمندتر برای پوشش رأس ۱ Smarter Search for Vertex Cover I

• جستجوی هوشمندتر برای پوشش رأس ۲ Smarter Search for Vertex Cover II

• مسئله فروشنده دوره‌گرد (TSP) The Traveling Salesman Problem

• الگوریتم برنامه‌نویسی پویا برای TSP A Dynamic Programming Algorithm for TSP

هفته سوم Week 3

• هیوریستیک حریصانه کوله‌پشتی A Greedy Knapsack Heuristic

• تحلیل هیوریستیک حریصانه کوله‌پشتی ۱ Analysis of a Greedy Knapsack Heuristic I

• تحلیل هیوریستیک حریصانه کوله‌پشتی ۲ Analysis of a Greedy Knapsack Heuristic II

• هیوریستیک برنامه‌نویسی پویا برای کوله‌پشتی A Dynamic Programming Heuristic for Knapsack

• مرور مسئله کوله‌پشتی از طریق برنامه‌نویسی پویا Knapsack via Dynamic Programming, Revisited

• تحلیل هیوریستیک برنامه‌نویسی پویا Ananysis of Dynamic Programming Heuristic

هفته چهارم Week 4

• مسئله برش بیشینه ۱ The Maximum Cut Problem I

• مسئله برش بیشینه ۲ The Maximum Cut Problem II

• اصول جستجوی محلی ۱ Principles of Local Search I

• اصول جستجوی محلی ۲ Principles of Local Search II

• مسئله 2-SAT The 2-SAT Problem

• گشت‌های تصادفی روی خط Random Walks on a Line

• تحلیل الگوریتم پاپادیمیریو Analysis of Papadimitriou's Algorithm

• تطبیق پایدار [اختیاری] Stable Matching [Optional]

• تطبیق‌ها، جریان‌ها و پارادوکس برائس [اختیاری] Matchings, Flows, and Braess's Paradox [Optional]

• برنامه‌نویسی خطی و فراتر از آن [اختیاری] Linear Programming and Beyond [Optional]

• موخره Epilogue