ابزار کاربر

ابزار سایت


درس:۴۰۶۸۵

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

Randomized Algorithms

شماره درس: ۴۰۶۸۵ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

هدف از اين درس، آشنایی دانش‌جویان با الگوریتم‌های تصادفی و تحلیل آن‌هاست.

ریز مواد

  • احتمال و اثبات با روش احتمالاتی (۵ جلسه)
    • تعاریف و قضایای پایه‌ای
    • امید ریاضی و نامساوی مارکوف
    • انحراف معیار و نامساوی چبیشف
    • نامساوی چرنف
    • مسئله توپ و ظرف‌ها و مسئله جمع‌آوری کوپن‌ها
  • الگوریتم‌های تصادفی پایه‌ای (۲ جلسه)
    • الگوریتم‌های لاس‌وگاس و مونتوکارلو: مسئله میانه تقریبی
    • الگوریتم‌های مقایسه‌ای: انتخاب، مرتب‌سازی، پیچ و مهره
  • جایگشت تصادفی و کاربردهای‌ آن (۳ جلسه)
    • مسئله‌ی استخدام
    • مسئله‌ی مسیریابی در ابرمکعب
    • الگوریتم‌های افزایشی: کوچک‌ترین دایره محیطی و Binary space partition
  • کران پایین الگوریتم‌های تصادفی (۲ جلسه)
    • قضیه Yao's minmax: بررسی مسئله پوشش نقاط با بازه‌های واحد در مدل آنلاین
    • game tree evaluation
  • ساختمان‌داده (۲ جلسه)
    • Skip lists
    • Treaps
  • قدم‌زدن تصادفی (۲ جلسه)
    • قدم‌زدن تصادفی در گراف‌های بدون جهت و کاربرد آن در مسئله‌های 2SAT و 3SAT
    • فرایند مارکوف (قدم زدن تصادفی در گراف‌های جهت‌دار با توزیع داده‌شده) و محاسبه احتمال بودن در یک گره در بی‌نهایت
  • روش مونتوکارلو (۳ جلسه)
    • معرفی روش مونتوکارلو: تخمین عدد π
    • معرفی الگوریتم‌های تقریبی تصادفی کاملا چندجمله‌ای: DNF counting problem
    • نمونه‌برداری تقریبی و شمارش تقریبی: مسئله شمارش مجموعه‌های مستقل در گراف بصورت تقریبی
    • روش نمونه‌برداری مونتوکارلو با استفاده از فرایند مارکوف
  • روش‌های جبری (۱ جلسه)
    • روش اثرانگشت: تساوی چند‌جمله‌ای‌ها و تطابق رشته‌ها
  • الگوریتم‌های گراف (۲ جلسه)
    • برش کمینه
    • درخت پوشای کمینه
  • آنتروپی (۲ جلسه)
    • تابع آنتروپی و خواص آن
    • آنتروپی و ضرایب دوجمله‌ای
    • آنتروپی: یک معیار تصادفی بودن

ارزیابی

  • آزمون: آزمون‌های میان ترم و پایان ترم (۱۴ نمره)
  • ارائه و گزارش پژوهشی (۳ نمره)
  • تمرین تئوری (۳ نمره)

مراجع

  1. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  2. J. Matoušek and J. Vondrák. The Probabilistic Method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague, 2001.
  3. M. Mitzenmacher and E. Upfa. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
درس/۴۰۶۸۵.txt · آخرین ویرایش: 2020/03/22 14:01 توسط حمید ضرابی زاده