سوالهای جزوه الگوریتم تصادفی
شنبه, ۹ آذر ۱۳۹۲، ۰۴:۳۴ ب.ظ
1-
مجموعه ی X را داریم و n عضوی است. مجموعه ی زیر مجموعه های k عضوی X را که اشتراک دو به دوی آنها تهی نباشد، F می نامیم. ثابت کنید تعداد اعضای F از انتخاب k-1 از n-1 کمتر مساوی است.
حل: تعداد کل زیر مجموعه های k عضوی X می شود انتخاب k از n. اگر یک عضو را در همه مشترک بگیریم می شود انتخاب k-1 از n-1. پس این را می شود ساخت باید ثابت کنیم که بهتر از این نمی شود.
یک عضو از F مثلا a را در نظر بگیرید. یک زیرمجموعه از X که با a اشتراک داره رو b بگیرید. می دونیم میشه یه جایگشتی روی a داد که اعضای a اشتراک b همه شون بیفتن ته a و میشه یه جایگشتی روی b داد که این اعضا بیفتن اولش. حالا می خوایم بگیم که تعداد b ها به ازای یک a چندتاست؟
یکی اینکه همه ی جایگشت های a رو حساب کنیم، چون b هم می دونیم k عضویه و فرض هم کردیم که دیگه a و b اشتراکی ندارند، تعداد حالت های b میشه این:
k!*(n-k)!*|F|
کلا (n-1)! جایگشت دوری داریم، حداکثر k تا از اعضای F می تونه توی هر جایگشت دوری اومده باشه، پس در کل میشه:
k* (n-1)!
یعنی عبارت اولیه از عبارت دومیه کمتره. حالا اینو که ساده کنیم به همون چیزی که اول می خواستیم می رسیم.
اثبات های دیگه ی این: http://www.math.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf
2-
تعداد مسیرهای همیلتونی توی گراف کامل که رندم جهت دهی شده چند تاست؟ (امید ریاضی)
طول هر مسیر = n
احتمال اینکه یک جایگشت از رئوس یک مسیر تشکیل بدن:
(1/2)^n-1
تعداد کل جایگشت ها هم n! تا است. پس کلا میشه:
n!*(1/2)^n-1
3-
گراف n راس و m یال داریم، بزرگترین زیرگراف تهی این گراف بیشتر از n/2d راس دارد. که d = میانگین درجه ی هر راس = 2m/n
زیرگراف تهی یعنی همه ی راسها درجه ی صفر باشند. احتمال اینکه درجه ی یک راس توی زیرگرافی که انتخاب می کنیم صفر بشه
1/(deg(v)+1)
چون باید هیچ کدوم از همسایه های اون راس توی گراف نباشن و خودش باشه.
می خوایم ثابت کنیم که یه چیزی وجود داره که یه چیزی رو بیشتر از یه مقداری داره، یعنی باید امید ریاضی اش رو حساب کنیم بعد بگیم حتما یکی هست که از امید ریاضی بیشتر باشه.
E(X) = E(sigma(Xi)) = sigma(E(Xi)) = sigma(1/(di+1)) >= (n^2) / sigma(di+1) = n^2/(n+2m) = n/(1+d) >= n/(2d)
راه دیگر: با گراف رندمی که احتمال وجود هر راسی p است، (پس احتمال وجود هر یال p2 است) یک سر هر یال را حذف کنیم. X = تعداد راسها و Y = تعداد یالها
E(X-Y) = np-np2 = np(1-p) ==> minimize ==> p = 1/d
4-
ماکسیمم درجه ی گراف رندم با احتمال انتخاب هر یال 1/2
حلش مثل نسبت باینری سرچ به باینری سرچ روی مقادیره. یعنی ماکسیمم درجه رو ازش امید ریاضی گرفته: احتمال اینکه ماکسیمم درجه انقدر باشه ضربدر ماکسیمم درجه. بقیه اش دیگه کار خاصی نبوده اومده اون قسمتی که می خواسته رو احتمالش رو گفته کمتر از یکه و مقدارش هم کمتر از کران بالایی بوده که قبلا با چرنف درآورده بوده. اون یکی تیکه رو هم یه کاری کرده :)
5-
یک مجموعه رو با دو رنگ آبی و قرمز رنگ کردیم، اختلاف تعداد آبی و قرمزها حداکثر چندتاست؟
رندم رنگ می کنیم و آبی = 1 و قرمز = -1. بعد t=2|red|*ln(|blue|) :D
6-
ثابت کنید زمان اجرای quick sort به احتمال یک منهای یک nام O(nlogn) است.
احتمال اینکه طول مسیر از این بیشتر بشه رو حساب می کنیم. باید ببینیم کدوم انتخاب های تصادفی هستند که زمان رو زیاد می کنند (ارتفاع رو زیاد می کنند.) و ثابت کنیم تعدادشون کمه.
