===== طراحی الگوریتم‌ها (تکمیلی) ===== این صفحه حاوی الگوریتم‌های تکمیلی است که بیشتر برای دانش‌پژوهان دوره‌ی طلا و کسانی که قصد شرکت در مسابقات ‌ای‌سی‌ام را دارند مفید می‌باشد. ===== داده‌ساختارها ===== * [[درخت پاره‌خطی دوبعدی]] * [[درخت فنویک]] * [[درخت دکارتی]] * [[درخت بازه‌ای]] * [[درخت کی‌دی]] * [[درخت محدوده‌ای]] * [[روش انتشار آبشاری]] * [[اعداد بزرگ]] ===== طراحی الگوریتم ===== ==== روش تقسیم و حل ==== * [[تبدیل فوریه]] * [[ضرب اعداد صحیح]] ==== برنامه‌ریزی پویا ==== * [[پوشاندن جدول با دومینو]] * [[مجموعه‌ی مستقل در درخت]] ==== الگوریتم‌های حریصانه ==== * [[ازدواج پایدار]] * [[کد هافمن]] ==== جست‌وجوی فضای حالات ==== * [[هرس آلفا-بتا]] * [[تناظر حالت‌ها با اعداد ( تبدیل جایگشت به عدد و برعکس)]] ===== الگوریتم‌های گراف ===== ==== پیمایش گراف‌ها ==== * [[پیدا کردن راس برشی]] * [[پیدا کردن یال برشی]] * [[پیدا کردن یال‌های برشی در مدل برخط]] * [[مولفه‌های دوهمبند]] ==== کوتاه‌ترین مسیر و مسائل مرتبط ==== * [[الگوریتم $A^*$]] * [[برنامه‌ریزی خطی با نامساوی‌های دو متغیره]] ==== همه‌ی زوج کوتاه‌ترین مسیرها ==== * [[الگوریتم جانسون]] * [[شمارش تعداد مسیرها با طول ثابت بین هر دو راس]] ==== درخت پوشای کمینه و مسائل مرتبط ==== * [[محاسبه‌ی تعداد درخت‌‌های پوشا]] * [[تعداد راه‌های همبند کردن یک گراف]] * [[پیدا کردن یال گلوگاهی]] ==== دورها ==== * [[مفاهیم کوتاهترین گشت و دور منفی]] * [[پیدا کردن دور با کم‌ترین میانگین وزن]] ==== شار و مسائل مرتبط ==== * [[شار بیشینه و برش کمینه]] * [[الگوریتم Ford-Fulkerson]] * [[الگوریتم Edmonds-Karp]] * [[الگوریتم Dinics]] * [[الگوریتم Push-relabe]] * [[الگوریتم Relabel-to-front]] * [[شار با حد پایین]] * [[مسیرهای مجزای یالی]] * [[مسیرهای مجزای راسی]] * [[ماکزیمم تطابق در گراف‌های دو بخشی]] * [[صحیح کردن درایه‌های ماتریس با حفظ جمع سطر و ستون‌ها]] ==== تطابق و مسائل مرتبط ==== * [[تطابق و مسائل متناظر آن]] * [[الگوریتم Kuhn]] * [[الگوریتم Hopcroft-Karp]] * [[الگوریتم Edmonds]] * [[الگوریتم تصادفی با ماتریس Tutte]] * [[پوشش راس‌ها در گراف جهت‌دار بی‌دور با مسیرهای مجزا]] ==== الگوریتم‌های درخت ==== * [[تجزیه‌ی سبک-سنگین درخت‌ها]] * [[تجزیه مرکزی درخت‌ها]] * [[یک‌ریختی درخت‌ها]] ===== پردازش رشته‌ها ===== * [[آرایه‌ی پسوندی]] * [[الگوریتم مبتنی بر DFA]] * [[روش‌های مبتی بر درهم سازی در کار با رشته‌ها]] ===== ترکیبیات ===== * [[ضرایب دوجمله‌ای]] * [[عدد کاتالان]] * [[تولید ترکیب و جایگشت]] * [[اصل طرد و شمول]] * [[لم Burnside]] * [[تولید پرانتزگذاری‌های معتبر]] ===== چارچوب‌های ترکیبیاتی و الگوریتمی ===== ==== مجموعه‌های مرتب جزئی ==== * [[مجموعه‌های مرتب جزئی]]: تعاریف، مثال‌ها و کاربردها، خاصیت‌ها، قضیه‌ها و دوگان‌ها * [[الگوریتم شناسایی بزرگ‌ترین زنجیر و کوچک‌ترین افراز به پادزنجیر]] * [[الگوریتم شناسایی بزرگ‌ترین پادزنجیر و کوچک‌ترین افراز به زنجیر]] * [[مشبکه‌ها]] (lattices): تعاریف، مثال‌ها و کاربردها، خاصیت‌ها و قضیه‌ها ==== ماترویدها ==== * [[ماترویدها]]: تعاریف، مثال‌ها و کاربردها، خاصیت‌ها و قضیه‌ها * [[الگوریتم‌های حریصانه مبتنی بر ماترویدها]] * [[اشتراک دو ماتروید و الگوریتم‌های مربوطه]] ==== برنامه‌ریزی خطی ==== * [[برنامه‌ریز خطی]]: تعاریف، مثال‌ها و کاربردها، و برنامه‌ریزی صحیح * [[دوگان برنامه‌ریزی خطی و رابطه‌ی بیشنیه و کمینه]] * [[شناسایی رده‌ی مسائل با استفاده از برنامه‌ریزی خطی و دوگان آن]] * [[الگوریتم اولیه-دوگان (primal-dual)]] * [[الگوریتم Simplex]] * [[یافتن جواب تقریبی به کمک برنامه‌ریزی خطی]] ===== نظریه‌ی اعداد ===== * [[آموزش:محاسبه‌ی تابع اویلر]] * [[محاسبه‌ی بزرگ‌ترین مقسوم‌علیه مشترک]] * [[غربال اراتستن]] * [[محاسبه‌ی عضو معکوس در همنشتی]] * [[قضیه‌ی باقی‌مانده‌ی چینی]] * [[ریشه اولیه و محاسبه‌ی آن]] * [[محاسبه‌ی فاکتوریل در همنهشتی]] * [[محاسبه‌ی توان یک عدد در فاکتوریل]] * [[محاسبه‌ی لگاریتم در همنهشتی]] * [[محاسبه‌ی ریشه kام در همنهشتی]] * [[حل معادله‌ی خطی دو متغیره در همنهشتی]] * [[اعداد فیبوناچی و محاسبه‌ی سریع آن]] * [[تست اول بودن عدد]] * [[تجزیه‌ی اعداد]] ===== الگوریتم‌های تصادفی ===== * [[الگوریتم‌های لاس‌وگاس و مونتوکارلو]] * [[مسئله استخدام]] * [[مسئله پیچ و مهره]] * [[درخت بازی]] * [[مسئله کوچک‌ترین دایره محیطی]] * [[برنامه‌ریزی خطی در ابعاد ثابت]] ===== جبر خطی ===== * [[محاسبه‌ی دترمینان ماتریس]] * [[محاسبه‌ی معکوس ماتریس]] * [[محاسبه‌ی مرتبه‌ی ماتریس]] * [[حل دستگاه خطی با روش حذف گوسی]] * [[حل دستگاه خطی در همنهشتی]] ===== مسائل بهینه‌سازی ===== * [[DFS with Iterative Deepening]] * [[Hill Climbing]] * [[Simulated Annealing]] ===== الگوریتم‌های هندسی ===== ==== محاسبات پایه‌ای هندسه‌ی دوبعدی ==== * [[جهت چندضلعی محدب]] * [[جهت چندضلعی ساده]] * [[فاصله‌ی دو نقطه]] * [[یکه‌کردن بردار]] * [[فاصله‌ی علامت‌دار نقطه از خط (پاره‌خط)]] * [[وضعیت نقطه نسبت به خط (پاره‌خط)]] * [[محاسبه‌ی زاویه‌ی بی‌علامت]] * [[محاسبه‌ی زاویه‌ی علامت‌دار]] * تعیین نقطه * [[تصویر نقطه روی خط (پاره‌خط)]] * [[نقطه‌ی متقارن یک نقطه نسبت به یک خط]] * [[تقاطع دو خط (پاره‌خط)]] * [[تقاطع‌های دایره و خط (پاره‌خط)]] * [[تقاطع‌های دو دایره]] * تعیین خط (پاره‌خط) * [[خط عبوری از دو نقطه]] * [[عمودمنصف دو نقطه]] * [[نیم‌ساز زاویه]] * [[خط عبوری از یک نقطه، با یک زاویه‌ی مشخص]] * [[خط عبوری از یک نقطه، موازی یک خط دیگر]] * [[خط عبوری از یک نقطه، عمود بر یک خط دیگر]] * [[مماس مشترک‌های نقطه و دایره]] * [[مماس مشترک‌های دو دایره]] * تعیین دایره * [[دایره‌ی عبوری از سه نقطه (دایره‌ی محیطی مثلث)]] * [[دایره‌های مماس با سه خط (دایره‌های محاطی مثلث)]] * [[دایره‌های مماس با دو خط با شعاع مشخص]] * [[دایره‌های عبوری از دو نقطه با شعاع مشخص]] * [[دایره‌های عبوری از یک نقطه و مماس با یک خط و با شعاع مشخص]] * [[دایره‌های عبوری از دو نقطه و مماس با یک خط]] * [[دایره‌های عبوری از یک نقطه و مماس با دو خط]] ==== محاسبات پایه‌ای هندسه‌ی $n$-بُعدی ==== * [[اندازه‌ی بردار n-بعدی]] * [[یکه کردن بردار n-بعدی]] * [[فاصله‌ی دو نقطه‌ در فضای n-بعدی]] * [[زاویه‌ی بی‌علامت بین سه نقطه در فضای n-بعدی]] * [[تصویر یک نقطه روی (خط راستای) یک بردار در فضای n-بعدی]] * [[تصویر یک نقطه روی یک خط (پاره‌خط) دل‌خواه در فضای n-بعدی]] * [[وضعیت یک نقطه نسبت به یک خط (پاره‌خط) در فضای n-بعدی]] * محاسبه‌ی $\alpha$ برای یک نقطه‌ی روی خط در مدل پارامتریِ $X = A + \alpha \cdot AB$ *‌ [[فاصله‌ی (بی‌علامت) یک نقطه از یک خط در فضای n-بعدی]] ==== محاسبات پایه‌ای هندسه‌ی سه‌بُعدی ==== * [[بردار نرمال (عمود بر) صفحه]] * [[مفهوم راستای قطبی در فضای سه‌بُعدی]] * راستای $(\theta, \phi)$ برای $ -\pi \leq \theta < \pi $ و $ -\pi/2 \leq \phi \leq \pi/2$ * یعنی اول نقطه‌ی دکارتیِ $(1, 0, 0)$ را در نظر بگیر. بعد آن را به‌اندازه‌ی $\theta$ (رادیان) حول محورِ $z$ (پادساعت‌گرد) بچرخان. بعد (برای تغییرِ $z$)، آن را به‌اندازه‌ی $\phi$ (رادیان) به سمت بالا بچرخان (بدون تغییرِ اندازه و $\theta$). * رایج در مباحث جغرافیا و نجوم * فرم‌های نگه‌داری داده‌ها و تبدیل آن‌ها به هم‌دیگر * [[فرم‌های نگه‌داری نقطه و تبدیل آن‌ها]] - مختصات دکارتی $(x, y, z)$ - مختصات قطبی $(r, \theta, \phi)$ * [[فرم‌های نگه‌داری صفحه و تبدیل آن‌ها]] - سه نقطه روی صفحه - بردار نرمال و یک نقطه روی صفحه - فرمول خطی $a x + b y + c z = d$ - مدل پارامتری $X = A + \alpha \cdot AB + \beta \cdot AC$ * محاسبه‌ی $\alpha$ و $\beta$ برای یک نقطه‌ی روی صفحه در مدل پارامتریِ $X = A + \alpha \cdot AB + \beta \cdot AC$ - بردار نرمال و فاصله از مبدأ - فرم قطبی (فاصله‌ی صفحه از مبدأ و $\theta$ و $\phi$ از بردار نرمال) * [[فرم‌های نگه‌داری خط و تبدیل آن‌ها]] - دو نقطه روی خط - جفت فرمول خطی (تقاطع دو صفحه) - پارامتری $X = A + \alpha \cdot AB$ - یک نقطه از خط و بردار راستا (بردار $AB$ در مورد قبلی) - یک نقطه از خط و $\theta$ و $\phi$ از بردار راستا * محاسبه‌ی مساحت و حجم * [[مساحت و جهت مثلث حاصل از سه نقطه در فضای سه‌بعدی]] * [[حجم علامت‌دار اجسام بسته در فضای سه‌بعدی]] * چهاروجهی حاصل از چهار نقطه * چندوجهی دل‌خواهِ بسته که هر وجه آن یک مثلث است * محاسبه‌ی وضعیت، تصویر، فاصله، زاویه، و اشتراک (تقاطع) * [[وضعیت سه نقطه نسبت به هم]] (هم‌خط بودن/نبودن) * [[وضعیت چهار نقطه نسبت به هم]] (هم‌صفحه بودن/نبودن) * [[تصویر یک نقطه روی یک خط (پاره‌خط)]] * [[وضعیت یک نقطه نسبت به یک خط (پاره‌خط)]] *‌ [[فاصله‌ی (بی‌علامت) یک نقطه از یک خط]] *‌ [[وضعیت دو خط نسبت به‌هم]] * موازی، متقاطع، متنافر (غیر هم‌صفحه) *‌ [[فاصله (بی‌علامت) بین دو خط موازی]] * [[نقطه‌ی اشتراک دو خط (پاره‌خط) متقاطع و وضعیت آن نسبت به پاره‌خط‌ها]] *‌ [[زاویه (بی‌علامت) بین دو خط متقاطع]] * بین $0$ و $\pi$ *‌ [[کم‌ترین فاصله بین دو خط متنافر و نزدیک‌ترین دو نقطه]] *‌ [[وضعیت تصویر دو خط متنافر روی هم]] *‌ [[فاصله‌ی علامت‌دار یک نقطه از یک صفحه]] *‌ [[وضعیت یک نقطه نسبت به یک صفحه]] * [[تصویر یک نقطه روی یک صفحه]] * [[وضعیت یک خط نسبت به یک صفحه]] *‌ [[فاصله‌ی علامت‌دارِ یک خط از صفحه‌ی موازی با آن]] * [[نقطه‌ی اشتراک یک خط و یک صفحه‌ی متقاطع با آن]] *‌ [[زاویه‌ی علامت‌دار بین یک خط و یک صفحه‌ی متقاطع با آن]] * بین $-\pi/2$ و $\pi/2$ * [[تصویر یک خط روی یک صفحه]] *‌ [[وضعیت دو صفحه نسبت به‌هم]] *‌ [[فاصله‌ی علامت‌دار بین دو صفحه‌ی موازی]] * [[فصل (خط) مشترک دو صفحه‌ی متقاطع]] *‌ [[زاویه (بی‌علامت) بین دو صفحه‌ی متقاطع]] * بین $0$ و $\pi$ * [[وضعیت سه صفحه نسبت به هم]] * [[نقطه‌ی اشتراک سه صفحه‌ی متقاطع]] * [[وضعیت یک نقطه نسبت به یک مثلث]] * این طرف صفحه، آن طرف صفحه، یا هم‌صفحه شامل داخل مثلث، خارج مثلث، یا روی مرز آن *‌ [[وضعیت نقطه نسبت به یک چهاروجهی]] * درون، بیرون، روی رأس، روی لبه، یا روی وجه * [[تقارن در سه بعد]] * تقارن نقطه نسبت به یک نقطه * تقارن نقطه نسبت به یک خط * تقارن نقطه نسبت به یک صفحه * تقارن اجسام دیگر * [[دوَران در سه بعد]] * دوران نقطه حول یک محور اصلی * دوران نقطه حول یک خط دل‌خواه * دوران نقطه حول نقطه‌ی مبدأ * دوران نقطه حول یک نقطه‌ی دل‌خواه * دوران اجسام دیگر * مکان‌هندسی نقاط هم‌فاصله * [[صفحه‌ی عمودمنصف دو نقطه]] * [[مکان‌هندسی نقاط هم‌فاصله از سه نقطه]] * [[نقطه‌ی هم‌فاصله از چهار نقطه]] * [[نیم‌ساز زاویه‌ی سه نقطه]] * [[مکان‌هندسی نقاط هم‌فاصله از دو صفحه]] * تعیین خط * [[خط عبوری از یک نقطه و موازی با یک خط دیگر]] * [[خط عبوری از یک نقطه و عمود بر یک صفحه]] * [[خط عبوری از یک نقطه و موازی با دو صفحه]] * [[خط عبوری از یک نقطه و متقاطع و عمود بر یک خط دیگر]] * [[خط عبوری از یک نقطه و متقاطع با دو خط دیگر]] * [[خط عبوری از یک نقطه، متقاطع با یک خط دیگر و موازی با یک صفحه]] * [[خط عبوری از یک نقطه، درون یک صفحه و موازی با یک صفحه‌ی دیگر]] * [[خط درون یک صفحه و متقاطع با دو خط دیگر]] * [[خط درون یک صفحه و متقاطع و عمود بر یک خط دیگر]] * [[خط موازی با یک خط دیگر و متقاطع با دو خط دیگر]] * [[خط عمود بر یک صفحه و متقاطع با دو خط دیگر]] * [[خط موازی با دو صفحه و متقاطع با دو خط دیگر]] * [[خط موازی با یک صفحه، متقاطع و عمود بر یک خط دیگر و متقاطع با یک خط دیگر]] * [[خط موازی با یک صفحه و متقاطع با سه خط دیگر]] * [[خط متقاطع و عمود بر یک خط دیگر و متقاطع با دو خط دیگر]] * [[خط متقاطع و عمود بر دو خط دیگر]] * خط متقاطع با چهار خط دیگر (خیلی سخت) * تعیین صفحه * [[صفحه‌ی عبوری از یک نقطه و موازی با یک صفحه‌ی دیگر]] * [[صفحه‌ی عبوری از یک نقطه و عمود بر یک خط]] * [[صفحه‌ی عبوری از یک نقطه و یک خط]] * [[صفحه‌ی عبوری از یک نقطه و موازی با دو خط]] * [[صفحه‌ی عبوری از یک نقطه و عمود بر دو صفحه‌ی دیگر]] * [[صفحه‌ی عبوری از یک نقطه، موازی با یک و عمود بر یک صفحه‌ی دیگر]] * [[صفحه‌ی عبوری از یک نقطه و با بیشترین فاصله از یک نقطه‌ی دیگر]] * [[صفحه‌ی عبوری از یک نقطه و موازی و با بیشترین فاصله از یک خط]] * [[صفحه‌ی عبوری از دو خط (در صورت وجود)]] * [[صفحه‌ی عبوری از یک خط و عمود بر یک صفحه‌ی دیگر]] * [[صفحه‌ی عبوری از یک خط و موازی با یک خط دیگر]] * [[صفحه‌ی عبوری از یک خط و با بیشترین فاصله از یک نقطه]] * [[صفحه‌ی عبوری از یک خط و با بیشترین فاصله از یک خط دیگر]] * کُره و دایره * تعریف دایره (دو بعدی) و کُره در فضای سه بعدی * وضعیت یک نقطه نسبت به یک کره * تصویر نقطه روی سطح کره * مساحت و حجم کره * طول کوتاه‌ترین خم بین دو نقطه روی سطح یک کره * تقاطع خط (پاره‌خط) با کره * تقاطع صفحه با کره * تقاطع دو کره * دایره‌ی عبوری از سه نقطه در فضا * کره‌ی محیطی (عبوری از) چهار نقطه در فضا * تعریف صفحه و خط مماس بر کره * صفحه‌ی مماس بر یک کره در یک نقطه‌ی خاص از سطح کره * خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و متقاطع با یک خط دیگر * خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و موازی با یک صفحه * صفحه‌ی عبوری از یک خط (یا دو نقطه) و مماس بر یک کره * صفحه‌ی عمود بر یک خط (یا موازی با یک صفحه‌ی دیگر، یا موازی با دو خط، یا عمود بر دو صفحه‌ی دیگر) و مماس بر یک کره * صفحه‌ی موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر دو کره * صفحه‌ی عبوری از یک نقطه، موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر یک کره * صفحه‌ی عبوری از یک نقطه و مماس بر دو کره (سخت) * خط عبوری از یک نقطه و مماس بر دو کره (سخت) * خط عبوری از یک نقطه، موازی با یک صفحه و مماس بر یک کره * خط عبوری از یک نقطه، متقاطع با یک خط دیگر و مماس بر یک کره * خط درون یک صفحه و مماس بر دو کره * خط درون یک صفحه، متقاطع با یک خط دیگر و مماس بر یک کره * خط درون یک صفحه، موازی با یک صفحه‌ی دیگر (با فرض تقاطع دو صفحه) و مماس بر یک کره * خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر) و مماس بر دو کره * خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر)، متقاطع با یک خط دیگر و مماس بر یک کره * خط متقاطع و عمود بر یک خط دیگر، موازی با یک صفحه و مماس بر یک کره * موارد خیلی سخت * صفحه‌ی مماس بر سه کره * خط متقاطع و عمود بر یک خط دیگر، متقاطع با یک خط دیگر و مماس بر یک کره * خط متقاطع و عمود بر یک خط دیگر و مماس بر دو کره * خط موازی با یک صفحه و مماس بر سه کره * خط موازی با یک صفحه، متقاطع با دو خط دیگر و مماس بر یک کره * خط موازی با یک صفحه، متقاطع با یک خط دیگر و مماس بر دو کره * خط متقاطع با سه خط دیگر و مماس بر یک کره * خط متقاطع با دو خط دیگر و مماس بر دو کره * خط متقاطع با یک خط دیگر و مماس بر سه کره * خط مماس بر چهار کره ==== تبدیل‌های هندسی دوبعدی ==== * [[انتقال، تقارن و دوران]] * [[دوگان هندسی]] * [[تبدیل Hough]] * [[انعکاس]] ==== الگوریتم‌های هندسی ==== * [[پوسته‌ی محدب]] * [[الگوریتم Gift-Wrapping]] * [[الگوریتم گراهام]] * [[پیدا کردن دورترین دو نقطه]] * [[پیدا کردن نزدیک‌ترین دو نقطه]] * [[الگوریتم‌های جاروب]] * [[محاسبه‌ی تقاطع مجموعه‌ای از پاره‌خط‌ها]] * [[محاسبه‌ی تقاطع مجموعه‌ای از دایره‌ها]] * [[محاسبه‌ی مساحت اجتماع مستطیل‌ها]] * [[مجموع طول پاره‌خط‌ها]] * [[کوتاه‌ترین مسیر در فضای هندسی]] * [[جمع مینکوفسکی]] * [[نقشه‌ی ورونوی]] * [[داده‌ساختار DCEL]] * [[داده‌ساختار مکان‌یابی]] * [[برنامه‌ریزی خطی]] * [[توپ پوشاننده کمینه]] (Minimum Enclosing Ball) ===== پیچیدگی محاسبات ===== * [[مسائل تصمیم‌گیری]] * [[صدق‌پذیری]] * [[برنامه‌ریزی صحیح]] * [[کاهش مسئله]] * [[نمونه‌هایی از کاهش به مسئله برنامه‌ریزی صحیح]] * [[کلاس پی‌٬ ان‌پی و ان‌پی‌سی]] * [[مسائل نمونه ان‌پی‌سی]] * [[الگوریتم‌های شبه‌چندجمله‌ای]] * [[الگوریتم‌های تقریبی (معرفی)]]