المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم های تکمیلی:فهرست

طراحی الگوریتم‌ها (تکمیلی)

این صفحه حاوی الگوریتم‌های تکمیلی است که بیشتر برای دانش‌پژوهان دوره‌ی طلا و کسانی که قصد شرکت در مسابقات ‌ای‌سی‌ام را دارند مفید می‌باشد.

داده‌ساختارها

طراحی الگوریتم

روش تقسیم و حل

برنامه‌ریزی پویا

الگوریتم‌های حریصانه

جست‌وجوی فضای حالات

الگوریتم‌های گراف

پیمایش گراف‌ها

کوتاه‌ترین مسیر و مسائل مرتبط

همه‌ی زوج کوتاه‌ترین مسیرها

درخت پوشای کمینه و مسائل مرتبط

دورها

شار و مسائل مرتبط

تطابق و مسائل مرتبط

الگوریتم‌های درخت

دو صدق‌پذیری

پردازش رشته‌ها

ترکیبیات

چارچوب‌های ترکیبیاتی و الگوریتمی

مجموعه‌های مرتب جزئی

ماترویدها

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

نظریه‌ی اعداد

الگوریتم‌های تصادفی

جبر خطی

مسائل بهینه‌سازی

الگوریتم‌های هندسی

محاسبات پایه‌ای هندسه‌ی دوبعدی

محاسبات پایه‌ای هندسه‌ی $n$-بُعدی

محاسبات پایه‌ای هندسه‌ی سه‌بُعدی

    • راستای $(\theta, \phi)$ برای $ -\pi \leq \theta < \pi $ و $ -\pi/2 \leq \phi \leq \pi/2$
    • یعنی اول نقطه‌ی دکارتیِ $(1, 0, 0)$ را در نظر بگیر. بعد آن را به‌اندازه‌ی $\theta$ (رادیان) حول محورِ $z$ (پادساعت‌گرد) بچرخان. بعد (برای تغییرِ $z$)، آن را به‌اندازه‌ی $\phi$ (رادیان) به سمت بالا بچرخان (بدون تغییرِ اندازه و $\theta$).
    • رایج در مباحث جغرافیا و نجوم
  • فرم‌های نگه‌داری داده‌ها و تبدیل آن‌ها به هم‌دیگر
      1. مختصات دکارتی $(x, y, z)$
      2. مختصات قطبی $(r, \theta, \phi)$
      1. سه نقطه روی صفحه
      2. بردار نرمال و یک نقطه روی صفحه
      3. فرمول خطی $a x + b y + c z = d$
      4. مدل پارامتری $X = A + \alpha \cdot AB + \beta \cdot AC$
        • محاسبه‌ی $\alpha$ و $\beta$ برای یک نقطه‌ی روی صفحه در مدل پارامتریِ $X = A + \alpha \cdot AB + \beta \cdot AC$
      5. بردار نرمال و فاصله از مبدأ
      6. فرم قطبی (فاصله‌ی صفحه از مبدأ و $\theta$ و $\phi$ از بردار نرمال)
      1. دو نقطه روی خط
      2. جفت فرمول خطی (تقاطع دو صفحه)
      3. پارامتری $X = A + \alpha \cdot AB$
      4. یک نقطه از خط و بردار راستا (بردار $AB$ در مورد قبلی)
      5. یک نقطه از خط و $\theta$ و $\phi$ از بردار راستا
  • کُره و دایره
    • تعریف دایره (دو بعدی) و کُره در فضای سه بعدی
    • وضعیت یک نقطه نسبت به یک کره
    • تصویر نقطه روی سطح کره
    • مساحت و حجم کره
    • طول کوتاه‌ترین خم بین دو نقطه روی سطح یک کره
    • تقاطع خط (پاره‌خط) با کره
    • تقاطع صفحه با کره
    • تقاطع دو کره
    • دایره‌ی عبوری از سه نقطه در فضا
    • کره‌ی محیطی (عبوری از) چهار نقطه در فضا
    • تعریف صفحه و خط مماس بر کره
    • صفحه‌ی مماس بر یک کره در یک نقطه‌ی خاص از سطح کره
    • خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و متقاطع با یک خط دیگر
    • خط مماس بر یک کره در یک نقطه‌ی خاص از سطح کره و موازی با یک صفحه
    • صفحه‌ی عبوری از یک خط (یا دو نقطه) و مماس بر یک کره
    • صفحه‌ی عمود بر یک خط (یا موازی با یک صفحه‌ی دیگر، یا موازی با دو خط، یا عمود بر دو صفحه‌ی دیگر) و مماس بر یک کره
    • صفحه‌ی موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر دو کره
    • صفحه‌ی عبوری از یک نقطه، موازی با یک خط (یا عمود بر یک صفحه‌ی دیگر) و مماس بر یک کره
    • صفحه‌ی عبوری از یک نقطه و مماس بر دو کره (سخت)
    • خط عبوری از یک نقطه و مماس بر دو کره (سخت)
    • خط عبوری از یک نقطه، موازی با یک صفحه و مماس بر یک کره
    • خط عبوری از یک نقطه، متقاطع با یک خط دیگر و مماس بر یک کره
    • خط درون یک صفحه و مماس بر دو کره
    • خط درون یک صفحه، متقاطع با یک خط دیگر و مماس بر یک کره
    • خط درون یک صفحه، موازی با یک صفحه‌ی دیگر (با فرض تقاطع دو صفحه) و مماس بر یک کره
    • خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر) و مماس بر دو کره
    • خط عمود بر یک صفحه (یا موازی با دو صفحه، یا موازی با یک خط دیگر)، متقاطع با یک خط دیگر و مماس بر یک کره
    • خط متقاطع و عمود بر یک خط دیگر، موازی با یک صفحه و مماس بر یک کره
    • موارد خیلی سخت
      • صفحه‌ی مماس بر سه کره
      • خط متقاطع و عمود بر یک خط دیگر، متقاطع با یک خط دیگر و مماس بر یک کره
      • خط متقاطع و عمود بر یک خط دیگر و مماس بر دو کره
      • خط موازی با یک صفحه و مماس بر سه کره
      • خط موازی با یک صفحه، متقاطع با دو خط دیگر و مماس بر یک کره
      • خط موازی با یک صفحه، متقاطع با یک خط دیگر و مماس بر دو کره
      • خط متقاطع با سه خط دیگر و مماس بر یک کره
      • خط متقاطع با دو خط دیگر و مماس بر دو کره
      • خط متقاطع با یک خط دیگر و مماس بر سه کره
      • خط مماس بر چهار کره

تبدیل‌های هندسی دوبعدی

الگوریتم‌های هندسی

پیچیدگی محاسبات


ابزار صفحه