آموزش الگوریتم‌های حریصانه، درخت‌های پوشای کمینه و برنامه‌نویسی پویا - آخرین آپدیت

هفته اول Week 1

• کاربرد: مسیریابی اینترنت Application: Internet Routing

• کاربرد: هم‌ترازی توالی Application: Sequence Alignment

• مقدمه‌ای بر الگوریتم‌های حریصانه Introduction to Greedy Algorithms

• کاربرد: حافظه پنهان (Caching) بهینه Application: Optimal Caching

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

• یک الگوریتم حریصانه A Greedy Algorithm

• اثبات درستی بخش اول Correctness Proof - Part I

• اثبات درستی بخش دوم Correctness Proof - Part II

• مدیریت موارد برابر [پیشرفته - اختیاری] Handling Ties [Advanced - Optional]

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

• الگوریتم MST پرایم Prim's MST Algorithm

• اثبات درستی ۱ Correctness Proof I

• اثبات درستی ۲ Correctness Proof II

• اثبات ویژگی برش [پیشرفته - اختیاری] Proof of Cut Property [Advanced - Optional]

• پیاده‌سازی سریع ۱ Fast Implementation I

• پیاده‌سازی سریع ۲ Fast Implementation II

هفته دوم Week 2

• الگوریتم MST کروسکال Kruskal's MST Algorithm

• درستی الگوریتم کروسکال Correctness of Kruskal's Algorithm

• پیاده‌سازی الگوریتم کروسکال با استفاده از Union Find ۱ Implementing Kruskal's Algorithm via Union-Find I

• پیاده‌سازی الگوریتم کروسکال با استفاده از Union Find ۲ Implementing Kruskal's Algorithm via Union-Find II

• درخت‌های پوشای کمینه: وضعیت فعلی و سوالات باز [پیشرفته - اختیاری] MSTs: State-of-the-Art and Open Questions [Advanced - Optional]

• کاربرد در خوشه‌بندی Application to Clustering

• درستی الگوریتم خوشه‌بندی Correctness of Clustering Algorithm

• اتحادهای تنبل (Lazy Unions) [پیشرفته - اختیاری] Lazy Unions [Advanced - Optional]

• اتحاد بر اساس رتبه [پیشرفته - اختیاری] Union-by-Rank [Advanced - Optional]

• تحلیل اتحاد بر اساس رتبه [پیشرفته - اختیاری] Analysis of Union-by-Rank [Advanced - Optional]

• فشردگی مسیر [پیشرفته - اختیاری] Path Compression [Advanced - Optional]

• فشردگی مسیر: تحلیل هاپکرافت اولمن ۱ [پیشرفته - اختیاری] Path Compression: The Hopcroft-Ullman Analysis I [Advanced - Optional]

• فشردگی مسیر: تحلیل هاپکرافت اولمن ۲ [پیشرفته - اختیاری] Path Compression: The Hopcroft-Ullman Analysis II [Advanced - Optional]

• تابع آکرمن [پیشرفته - اختیاری] The Ackermann Function [Advanced - Optional]

• فشردگی مسیر: تحلیل تارجان ۱ [پیشرفته - اختیاری] Path Compression: Tarjan's Analysis I [Advanced - Optional]

• فشردگی مسیر: تحلیل تارجان ۲ [پیشرفته - اختیاری] Path Compression: Tarjan's Analysis II [Advanced - Optional]

هفته سوم Week 3

• مقدمه و انگیزه Introduction and Motivation

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

• یک الگوریتم حریصانه A Greedy Algorithm

• یک مثال پیچیده‌تر A More Complex Example

• اثبات درستی ۱ Correctness Proof I

• اثبات درستی ۲ Correctness Proof II

• مقدمه: مجموعه‌های مستقل وزن‌دار در گراف‌های مسیر Introduction: Weighted Independent Sets in Path Graphs

• مجموعه‌های مستقل وزن‌دار در گراف‌های مسیر: زیرساختار بهینه WIS in Path Graphs: Optimal Substructure

• مجموعه‌های مستقل وزن‌دار در گراف‌های مسیر: یک الگوریتم با زمان خطی WIS in Path Graphs: A Linear-Time Algorithm

• مجموعه‌های مستقل وزن‌دار در گراف‌های مسیر: الگوریتم بازسازی WIS in Path Graphs: A Reconstruction Algorithm

• اصول برنامه‌نویسی پویا Principles of Dynamic Programming

هفته چهارم Week 4

• مسئله کوله‌پشتی The Knapsack Problem

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

• مثال [مرور - اختیاری] Example [Review - Optional]

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

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

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

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

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

• یک الگوریتم برنامه‌نویسی پویا ۱ A Dynamic Programming Algorithm I

• یک الگوریتم برنامه‌نویسی پویا ۲ A Dynamic Programming Algorithm II