الگوریتم تصادفی -فصل1

وقتی یه الگوریتم معمولی رو از یه حالت رندم شروع می کنیم تا زمانش به طور میانگین (expected value) بهتر بشه.

چیزهایی که باید حساب کنیم کل حالت های ممکن (S)، یه زیر مجموعه از حالت های ممکن(A)، احتمال اونها (p) و نسبت دادن یه عدد به A یعنی X(متغیر تصادفی) است.

متغیرهای مستقل: متغیرهایی که امید ریاضی حاصل ضرب و احتمال اشتراکشون بشه حاصلضرب امیدریاضی و حاصل ضرب احتمالشون.

نامساوی مارکوف: برای هر X>=0 و t>0 که میانگین X بشه m داریم: pr(x>mt)<=1/t.

آزمایش برنولی: اگر موفقیت و شکست نتیجه ی آزمایش باشد و احتمال موفقیت p باشد، تعداد تکرارهای آزمایش برای رسیدن به اولین موفقیت به طور میانگین عکس احتمال موفقیت است.

آزمایش پواسون: اگر در آزمایش برنولی، احتمال موفقیت تغییر کند، یک آزمایش پواسون داریم. تخمین احتمال کرانهای یک آزمایش پواسون رو با نامساوی چرنف به دست میارن.

--------------------

الگوریتم تصادفی تقریبی برای به دست آوردن میانه: (با به طور کلی kامین عدد)

زمان حل کردن دقیق مساله: = k بار مینیمم رو در بیاریم = O(n)

فرض کنید ما دقیقا عدد وسطی رو نمی خوایم فقط می خوایم تقریبا وسط باشه.

راه حل 0: یک عدد رندم انتخاب می کنیم، اگر تقریبا وسط بود به عنوان جواب بر می گردونیم و پایان؛ در غیر این صورت خطا.

زمان : O(n)

الزاما به جواب درست نمی رسه. یعنی هیچ مزیتی نسبت به راه حل معمولی اش نداره.

ایده: سعی و خطا! :) -- پایه الگوریتم تصادفی

پس باید احتمال موفقیت رو افزایش بدیم. احتمال موفقیت در این حالت تعداد اعداد نزدیک به میانه به تعداد کل اعداده، یعنی با فرض ضریب delta برابر میانه احتمال اینکه درست جواب بده میشه 2*delta.

(  (n/2+delta*n/2)+(n/2-delta*n/2)  )/n = 2*delta

راه حل 1:(مانتی کارلو) تعداد ثابتی (c) بار این کار رو انجام بدیم.

زمان: O(c*n)

احتمال خطا:

(1-2*delta)^c

ایده: می دانیم delta*2 عدد بین صفر و یک است. پس توانهای بزرگترش کوچکتر می شوند.

راه حل 2: (لاس وگاس) تکرار تا رسیدن به جواب.

زمان: آزمایش برنولی است که احتمال موفقیت در آن 2*delta است، پس تعداد تکرار برای رسیدن به موفقیت به طور متوسط: 

p_success = 1/(2*delta)

E(T(n)) = O(n)*1/p_success = O(n)*1/(2*delta) = O(n/delta)

ایده: حذف احتمال خطا با احتمال افزایش زمان اجرا

هدف الگوریتم تصادفی: حذف بدترین حالت (زمان اجرا) و رسیدن به متوسط زمان بهتر

مثال: استخدام بهترین منشی: (هر اخراج به اندازه ی f ضرر می زند)

راه حل معمولی: همه را به ترتیب چک کند و هر وقت آدم بهتری پیدا کرد قبلی را اخراج کند. O(nf)

ایده: روی ورودی یک جایگشت رندم اعمال کنیم.

از آنجایی که بهترین را می خواهیم الگوریتم لاس وگاس را باید به کار ببریم.

هزینه الگوریتم: به تعداد افرادی وابسته است که اشتباهی استخدام شده اند = متغیر تصادفی X

X = sum(Xi) ; Xi = 1 if i-th person is hired, 0 otherwise

E(cost(n)) = E(f*X) = f*sum(E(xi)) = f*sum(Pi) = f*(1/1+1/2+...+1/n) = f*ln(n)

نکته: تصادفی بودن نباید روی ورودی باشد، یعنی به آن بستگی داشته باشد.

مثال: اگر هر بار جای عنصر آخر و i ام آرایه را عوض کنیم، رندم نیست.

مثال: اگر هر بار جای یک عنصر رندم و i ام آرایه را عوض کنیم، رندم است.