ابزار کاربر

ابزار سایت


هندسه_محاسباتی:ریز_مواد

هندسه‌ی محاسباتی (۴۰۷۳۵)

اهداف درس

هدف از این درس، آشنایی دانش‌جویان با داده‌ساختارها و الگوریتم‌های کارا برای حل مسائل هندسی است. موضوعات ارائه‌شده در این درس در سایر حوزه‌های علوم کامپیوتر از جمله گرافیک کامپیوتری، روباتیک، سیستم‌های اطلاعات جغرافیایی و پایگاه‌های داده مورد استفاده قرار می‌گیرند.

ریز مواد

  • مقدمه
    • معرفی درس، نمونه مسائل هندسی
  • پوسته‌ی محدب
    • محاسبه‌ی پوسته‌ی محدب در صفحه، عملیات پایه‌ی هندسی
    • چند روش برای محاسبه‌ی پوسته‌ی محدب در صفحه
    • اثبات کران پایین، قضیه‌ی بن-اُر
    • الگوریتم‌های حساس به خروجی، دو الگوریتم بهینه از چن
  • دوگان هندسی
    • دوگان نقاط، پوش‌های بالایی و پایینی، کاربردها، دوگان در فضای سه‌بعدی
  • پوسته‌ی محدب در فضای سه‌بعدی
    • پیچیدگی ترکیبیاتی، نحوه‌ی نمایش، الگوریتم کادوپیچی
    • الگوریتم تصادفی کلارکسون-شور، پوسته‌ی محدب در فضاهای بالاتر
  • تقاطع و چینش خطوط
    • ساخت چینش خطوط، الگوریتم افزایشی، قضیه‌ی قلمرو یک خط
    • تقاطع پاره‌خط‌ها، الگوریتم جاروب صفحه، الگوریتم تقسیم و حل
  • نمودار ورونوی و مثلث‌بندی دلونی
    • تعریف نمودار ورونوی، ویژگی‌ها و قضایا
    • مثلث‌بندی دلونی و خواص آن، الگوریتم فورچیون
    • ارتباط با پوسته‌ی محدب، الگوریتم تصادفی ساخت
    • کاربردهای نمودار ورونوی و مثلث‌بندی دلونی، نمودار ورونوی مرتبه‌ی بالاتر
  • برنامه‌ریزی خطی
    • تعریف برنامه‌ریزی خطی، کاربردهای هندسی در فضای پایین
    • الگوریتم هرس و جست‌وجوی مگیدو، الگوریتم تصادفی-افزایشی سایدل
    • الگوریتم نمونه‌برداری تصادفی کلارکسون
    • مسائل شبیه به برنامه‌ریزی خطی، کوچک‌ترین دایره‌ی محیطی
  • مکان‌یابی نقاط
    • روش تقسیم و حل، نقشه‌ی ذوزنقه‌ای، الگوریتم افزایشی تصادفی
    • الگوریتم هرس و جست‌وجوی کرکپاتریک
  • مثلث‌بندی چندضلعی
    • روش ذوزنقه‌بندی، الگوریتم تصادفی سایدل
    • کاربردهای مثلث‌بندی، مسئله‌ی گالری هنر
  • جست‌وجوی بازه‌ای
    • بازه‌های متعامد: درخت کی‌دی، درخت بازه، آبشار کسری
    • بازه‌های کلی، درخت افراز، درخت برش
    • پنجره‌بندی، درخت جست‌وجوی اولویت، درخت پاره‌خط

ارزیابی

  • آزمون‌های میان‌ترم و پایان‌ترم (۱۰ نمره)
  • سه تمرین‌ نظری (۶ نمره)

مراجع

  • M‎. ‎de Berg‎, ‎O‎. ‎Cheong‎, ‎M‎. ‎van Kreveld‎, ‎and M‎. ‎Overmars‎. ‎Computational Geometry‎: Algorithms and Applications. ‎Third edition‎, ‎Springer-Verlag‎, ‎2008.‎
  • J. O'Rourke. Computational Geometry in C. Second edition, Cambridge University Press, 1998.
هندسه_محاسباتی/ریز_مواد.txt · آخرین ویرایش: 2020/05/15 14:58 توسط حمید ضرابی زاده