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

1. مفاهیم پایه احتمال
   • تعاریف و قضایای پایه‌ای
   • امید ریاضی و نامساوی مارکوف
   • انحراف معیار و نامساوی چبیشف
   • نامساوی چرنف و نامساوی هوفدینگ و کاربردها: درجه گراف تصادفی
   • توزیع‌های احتمال: پواسون، هندسی، گاوسی، نمایی، …
2. الگوریتم‌های تصادفی پایه‌ای 
   • الگوریتم‌های لاس‌وگاس و مونتوکارلو: مسئله میانه تقریبی
   • جایگشت تصادفی و کاربردهای آن: انتخاب، مرتب‌سازی، مسئله استخدام
   • مسئله برش کمینه
   • روش اثرانگشت: تساوی چند‌جمله‌ای‌ها و تطابق رشته‌ها
3. قدم‌زدن تصادفی  و فرایند مارکوف
   • قدم‌زدن تصادفی در گراف‌های بدون جهت و کاربرد آن در مسئله‌های 2-SAT و 3-SAT
   • فرایند مارکوف (قدم زدن تصادفی در گراف‌های جهت‌دار با توزیع داده‌شده) و محاسبه احتمال بودن در یک گره در بی‌نهایت
4. روش مونتوکارلو 
   • معرفی روش مونتوکارلو: تخمین عدد پی
   • معرفی الگوریتم‌های تقریبی تصادفی: مسئله شمارش جواب‌های DNF
   • نمونه‌برداری تقریبی و شمارش تقریبی: مسئله شمارش مجموعه‌های مستقل در گراف
   • روش نمونه‌برداری مونتوکارلو با استفاده از فرایند مارکوف
5. مدل جویباری و روش‌های احتمالی
   • معرفی مدل و انواع آن: مسئله پیدا کردن اعداد با تکرار زیاد
   • توابع درهم‌ساز universal و 2-universal
   • پیدا کردن تعداد اعداد متمایز
   • تخمین Frequency Moments و کاربردهای آن: محاسبه تعداد مثلث‌ها در گراف
6. بردارهای تصادفی در ابعاد بالا
   • تمرکز نرم‌ها
   • ماتریس کوواریانس بردارهای تصادفی
   • مثال‌هایی از توابع توزیع‌ احتمالی در ابعاد بالا: برش بیشینه در گراف‌ها
   • لم Johnson-Lindenstrauss
7. ماتریس‌های تصادفی
   • نت‌ها، عدد پوششی و عدد بسته‌بندی
   • کران بالا برای ماتریس‌های گاوسی: تشخیص احتماع‌ها در شبکه‌ها
   • کران دو طرفه برای ماتریس‌های گاوسی: تخمین کوواریانس و خوشه‌بندی
   • نامساوی برناشتاین برای ماتریس‌ها: تشخیص احتماع‌ها در شبکه‌های خلوت

• آزمون: ۶۰ % کل نمره
• تمرین تئوری: ۲۰ % کل نمره
• تمرین عملی: ۲۰% کل نمره