الگوریتم تصادفی -بقیه فصلها
چهارشنبه, ۶ آذر ۱۳۹۲، ۰۷:۱۲ ب.ظ
حوصله ی اینکه بقیه اش رو بخونم ندارم. در نتیجه خلاصه ی ایده های فصل های بعد رو می نویسم:
مسیریابی: برای حذف بدترین حالت روی ورودی جایگشت رندم اعمال کنیم. + تقارن
روش احتمالاتی: برای حل مسائل ترکیبیاتی از احتمال استفاده کنیم (اثبات). برای این کار دو راه هست:
1-حداقل یک x هست که از E(X) کمتر مساوی باشه و یک x هست که حداقل E(x) باشه.
2-اگر احتمال وجود یک خاصیت در یک چیز که تصادفی از یک مجموعه انتخاب شده، بزرگتر از صفر باشه چیزی وجود داره که اون خاصیت رو داشته باشه!
*اگر بتوانیم با احتمال بالایی بگوییم که این چیز مستقل از مجموعه است، به یک الگوریتم لاس وگاس برای پیدا کردن اون چیز با این خاصیت می رسیم.
