فهرست مندرجات
طراحی الگوریتم‌ها (تکمیلی)
این صفحه حاوی الگوریتم‌های تکمیلی است که بیشتر برای دانش‌پژوهان دوره‌ی طلا و کسانی که قصد شرکت در مسابقات ای‌سی‌ام را دارند مفید می‌باشد.
داده‌ساختارها
طراحی الگوریتم
روش تقسیم و حل
برنامه‌ریزی پویا
الگوریتم‌های حریصانه
جست‌وجوی فضای حالات
الگوریتم‌های گراف
پیمایش گراف‌ها
کوتاهترین مسیر و مسائل مرتبط
همه‌ی زوج کوتاهترین مسیرها
درخت پوشای کمینه و مسائل مرتبط
دورها
شار و مسائل مرتبط
تطابق و مسائل مرتبط
الگوریتم‌های درخت
پردازش رشته‌ها
ترکیبیات
چارچوب‌های ترکیبیاتی و الگوریتمی
مجموعه‌های مرتب جزئی
- مجموعه‌های مرتب جزئی: تعاریف، مثال‌ها و کاربردها، خاصیت‌ها، قضیه‌ها و دوگان‌ها
- مشبکه‌ها (lattices): تعاریف، مثال‌ها و کاربردها، خاصیت‌ها و قضیه‌ها
ماترویدها
- ماترویدها: تعاریف، مثال‌ها و کاربردها، خاصیت‌ها و قضیه‌ها
برنامه‌ریزی خطی
- برنامه‌ریز خطی: تعاریف، مثال‌ها و کاربردها، و برنامه‌ریزی صحیح
نظریه‌ی اعداد
الگوریتم‌های تصادفی
جبر خطی
مسائل بهینه‌سازی
الگوریتم‌های هندسی
محاسبات پایه‌ای هندسه‌ی دوبعدی
- تعیین نقطه
- تعیین خط (پاره‌خط)
- تعیین دایره
محاسبات پایه‌ای هندسه‌ی $n$-بُعدی
-
- محاسبه‌ی $\alpha$ برای یک نقطه‌ی روی خط در مدل پارامتریِ $X = A + \alpha \cdot AB$
محاسبات پایه‌ای هندسه‌ی سه‌بُعدی
-
- راستای $(\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$
-
- این طرف صفحه، آن طرف صفحه، یا هم‌صفحه شامل داخل مثلث، خارج مثلث، یا روی مرز آن
-
- درون، بیرون، روی رأس، روی لبه، یا روی وجه
-
- تقارن نقطه نسبت به‌یک نقطه
- تقارن نقطه نسبت به‌یک خط
- تقارن نقطه نسبت به‌یک صفحه
- تقارن اجسام دیگر
-
- دوران نقطه حول یک محور اصلی
- دوران نقطه حول یک خط دل‌خواه
- دوران نقطه حول نقطه‌ی مبدأ
- دوران نقطه حول یک نقطه‌ی دل‌خواه
- دوران اجسام دیگر
- مکان‌هندسی نقاط هم‌فاصله
- تعیین خط
- خط متقاطع با چهار خط دیگر (خیلی سخت)
- تعیین صفحه
- کُره و دایره
- تعریف دایره (دو بعدی) و کُره در فضای سه بعدی
- وضعیت یک نقطه نسبت به‌یک کره
- تصویر نقطه روی سطح کره
- مساحت و حجم کره
- طول کوتاهترین خم بین دو نقطه روی سطح یک کره
- تقاطع خط (پاره‌خط) با کره
- تقاطع صفحه با کره
- تقاطع دو کره
- دایره‌ی عبوری از سه نقطه در فضا
- کره‌ی محیطی (عبوری از) چهار نقطه در فضا
- تعریف صفحه و خط مماس بر کره
- صفحه‌ی مماس بر یک کره در یک نقطه‌ی خاص از سطح کره
- خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و متقاطع با یک خط دیگر
- خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و موازی با یک صفحه
- صفحه‌ی عبوری از یک خط (یا دو نقطه) و مماس بر یک کره
- صفحه‌ی عمود بر یک خط (یا موازی با یک صفحه‌ی دیگر، یا موازی با دو خط، یا عمود بر دو صفحه‌ی دیگر) و مماس بر یک کره
- صفحه‌ی موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر دو کره
- صفحه‌ی عبوری از یک نقطه، موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر یک کره
- صفحه‌ی عبوری از یک نقطه و مماس بر دو کره (سخت)
- خط عبوری از یک نقطه و مماس بر دو کره (سخت)
- خط عبوری از یک نقطه، موازی با یک صفحه و مماس بر یک کره
- خط عبوری از یک نقطه، متقاطع با یک خط دیگر و مماس بر یک کره
- خط درون یک صفحه و مماس بر دو کره
- خط درون یک صفحه، متقاطع با یک خط دیگر و مماس بر یک کره
- خط درون یک صفحه، موازی با یک صفحه‌ی دیگر (با فرض تقاطع دو صفحه) و مماس بر یک کره
- خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر) و مماس بر دو کره
- خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر)، متقاطع با یک خط دیگر و مماس بر یک کره
- خط متقاطع و عمود بر یک خط دیگر، موازی با یک صفحه و مماس بر یک کره
- موارد خیلی سخت
- صفحه‌ی مماس بر سه کره
- خط متقاطع و عمود بر یک خط دیگر، متقاطع با یک خط دیگر و مماس بر یک کره
- خط متقاطع و عمود بر یک خط دیگر و مماس بر دو کره
- خط موازی با یک صفحه و مماس بر سه کره
- خط موازی با یک صفحه، متقاطع با دو خط دیگر و مماس بر یک کره
- خط موازی با یک صفحه، متقاطع با یک خط دیگر و مماس بر دو کره
- خط متقاطع با سه خط دیگر و مماس بر یک کره
- خط متقاطع با دو خط دیگر و مماس بر دو کره
- خط متقاطع با یک خط دیگر و مماس بر سه کره
- خط مماس بر چهار کره
تبدیل‌های هندسی دوبعدی
الگوریتم‌های هندسی
-
-
- توپ پوشاننده کمینه (Minimum Enclosing Ball)