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

Randomized Algorithms

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

هدف از این درس، آشنایی دانشجویان با الگوریتم‌های تصادفی و روش‌های تحلیل آن‌هاست. در این درس دانشجویان با مفاهیم مهم مرتبط با الگوریتم‌های تصادفی از جمله آنتروپی، روش مونت کارلو، قدم‌زنی تصادفی، روش‌های جبری و همچنین اثبات با روش احتمالاتی آشنا می‌شوند.

سرفصل‌ها

  1. احتمالات و متغیرهای تصادفی
  2. الگوریتم‌های تصادفی پایه‌ای
  3. جایگشت تصادفی و کاربردهای آن
  4. کران پایین الگوریتم‌های تصادفی
  5. اثبات با روش احتمالاتی
  6. داده‌ساختارهای تصادفی
  7. قدم‌زدن تصادفی
  8. روش مونت‌کارلو
  9. روش‌های جبری
  10. الگوریتم‌های گراف
  11. آنتروپی

ارزیابی پیشنهادی

  • آزمون: آزمون‌های میان‌ترم و پایان‌ترم (۷۰ درصد نمره)
  • پروژه: ارائه و گزارش پژوهشی (۱۵ درصد نمره)
  • تمرین: سه تمرین نظری (۱۵ درصد نمره)

منابع پیشنهادی

  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. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.