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

جریان‌ها در شبکه‌ها Flows in Networks

• مقدمه Introduction

• جریان‌های شبکه Network Flows

• شبکه‌های باقی‌مانده Residual Networks

• حداکثر جریان - حداقل برش Maxflow-Mincut

• الگوریتم فورد-فالکرسون The Ford–Fulkerson Algorithm

• مثال کند Slow Example

• الگوریتم ادموندز-کارپ The Edmonds–Karp Algorithm

• تطبیق دو parte Bipartite Matching

• بخش‌بندی تصویر Image Segmentation

برنامه‌ریزی خطی Linear Programming

• مقدمه Introduction

• برنامه‌ریزی خطی Linear Programming

• جبر خطی: روش جایگذاری Linear Algebra: Method of Substitution

• جبر خطی: حذف گاوسی Linear Algebra: Gaussian Elimination

• محدب بودن Convexity

• دوگانگی Duality

• (اختیاری) اثبات‌های دوگانگی (Optional) Duality Proofs

• فرمول‌بندی‌های برنامه‌ریزی خطی Linear Programming Formulations

• الگوریتم سیمپلکس The Simplex Algorithm

• (اختیاری) الگوریتم بیضی (Optional) The Ellipsoid Algorithm

مسائل NP کامل NP-complete Problems

• جستجوی نیروی محض Brute Force Search

• مسائل جستجو Search Problems

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

• مسئله چرخه همیلتونی Hamiltonian Cycle Problem

• مسئله طولانی‌ترین مسیر Longest Path Problem

• مسئله برنامه‌ریزی خطی عدد صحیح Integer Linear Programming Problem

• مسئله مجموعه مستقل Independent Set Problem

• کلاس‌های P و NP P and NP

• کاهش‌ها (Reductions) Reductions

• نشان دادن NP کامل بودن Showing NP-completeness

• کاهش مجموعه مستقل به پوشش رأس Independent Set to Vertex Cover

• کاهش 3-SAT به مجموعه مستقل 3-SAT to Independent Set

• کاهش SAT به 3-SAT SAT to 3-SAT

• کاهش مدار SAT به SAT Circuit SAT to SAT

• کاهش تمام مسائل NP به مدار SAT All of NP to Circuit SAT

• استفاده از حل‌کننده‌های SAT Using SAT-solvers

مقابله با کامل بودن NP Coping with NP-completeness

• مقدمه Introduction

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

• الگوریتم 2-SAT 2-SAT: Algorithm

• مجموعه‌های مستقل در درخت‌ها Independent Sets in Trees

• 3-SAT: عقب‌گرد (Backtracking) 3-SAT: Backtracking

• 3-SAT: جستجوی محلی 3-SAT: Local Search

• TSP: برنامه‌ریزی پویا TSP: Dynamic Programming

• TSP: شاخه و کران TSP: Branch and Bound

• پوشش رأس Vertex Cover

• TSP متری Metric TSP

• TSP: جستجوی محلی TSP: Local Search

الگوریتم‌های جریانی (اختیاری) Streaming Algorithms (Optional)

• مقدمه Introduction

• مسئله عناصر پر تکرار (Heavy Hitters) Heavy Hitters Problem

• کاهش اول Reduction 1

• کاهش دوم Reduction 2

• تخمین پایه اول Basic Estimate 1

• تخمین پایه دوم Basic Estimate 2

• الگوریتم نهایی اول Final Algorithm 1

• الگوریتم نهایی دوم Final Algorithm 2

• اثبات‌ها اول Proofs 1

• اثبات‌ها دوم Proofs 2