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

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

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