You are not allowed to perform this action
روش‌های تصادفی و احتمالاتی
Randomized and Probabilistic Methods
| شماره درس: ۴۰۸۰۱.۸ | تعداد واحد: ۳ |
| مقطع: کارشناسی ارشد | نوع درس: نظری |
| پیش‌نیاز: – | هم‌نیاز: – |
اهداف درس
هدف این درس، آشنا کردن دانشجویان کارشناسی ارشد و دکترا با روش‌های احتمالی و تصادفی در حوزه علوم داده می‌باشد.
ریز مواد
- مفاهیم پایه احتمال
- تعاریف و قضایای پایه‌ای
- امید ریاضی و نامساوی مارکوف
- انحراف معیار و نامساوی چبیشف
- نامساوی چرنف و نامساوی هوفدینگ و کاربردها: درجه گراف تصادفی
- توزیع‌های احتمال: پواسون، هندسی، گاوسی، نمایی، …
- الگوریتم‌های تصادفی پایه‌ای
- الگوریتم‌های لاس‌وگاس و مونتوکارلو: مسئله میانه تقریبی
- جایگشت تصادفی و کاربردهای آن: انتخاب، مرتب‌سازی، مسئله استخدام
- مسئله برش کمینه
- روش اثرانگشت: تساوی چند‌جمله‌ای‌ها و تطابق رشته‌ها
- قدم‌زدن تصادفی و فرایند مارکوف
- قدم‌زدن تصادفی در گراف‌های بدون جهت و کاربرد آن در مسئله‌های 2-SAT و 3-SAT
- فرایند مارکوف (قدم زدن تصادفی در گراف‌های جهت‌دار با توزیع داده‌شده) و محاسبه احتمال بودن در یک گره در بی‌نهایت
- روش مونتوکارلو
- معرفی روش مونتوکارلو: تخمین عدد پی
- معرفی الگوریتم‌های تقریبی تصادفی: مسئله شمارش جواب‌های DNF
- نمونه‌برداری تقریبی و شمارش تقریبی: مسئله شمارش مجموعه‌های مستقل در گراف
- روش نمونه‌برداری مونتوکارلو با استفاده از فرایند مارکوف
- مدل جویباری و روش‌های احتمالی
- معرفی مدل و انواع آن: مسئله پیدا کردن اعداد با تکرار زیاد
- توابع درهم‌ساز universal و 2-universal
- پیدا کردن تعداد اعداد متمایز
- تخمین Frequency Moments و کاربردهای آن: محاسبه تعداد مثلث‌ها در گراف
- بردارهای تصادفی در ابعاد بالا
- تمرکز نرم‌ها
- ماتریس کوواریانس بردارهای تصادفی
- مثال‌هایی از توابع توزیع احتمالی در ابعاد بالا: برش بیشینه در گراف‌ها
- لم Johnson-Lindenstrauss
- ماتریس‌های تصادفی
- نت‌ها، عدد پوششی و عدد بسته‌بندی
- کران بالا برای ماتریس‌های گاوسی: تشخیص احتماع‌ها در شبکه‌ها
- کران دو طرفه برای ماتریس‌های گاوسی: تخمین کوواریانس و خوشه‌بندی
- نامساوی برناشتاین برای ماتریس‌ها: تشخیص احتماع‌ها در شبکه‌های خلوت
ارزیابی
- آزمون: ۶۰ % کل نمره
- تمرین تئوری: ۲۰ % کل نمره
- تمرین عملی: ۲۰% کل نمره
مراجع
- M. Mitzenmacher and E. Upfa. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
- R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, to appear.