سوالهای پایان ترم الگوریتم تصادفی

پوشش راسی

دریافت
عنوان: vertex cover
حجم: 113 کیلوبایت

قدم زدن تصادفی روی زنجیره مارکوف فضای مساله

جواب تمرین الگوریتم تصادفی خودمون

تمرین های کتاب (مبحث توپ و ظرف)

حل:

الف) طوری که احتمال وجود دو تا پسورد مساوی کمتر از احتمال متمایز بودن پسوردها باشد.

تعداد ظرفها: تعداد شماره های 4 رقمی = 10 به توان 4

p=(1-1/10000)(1-2/10000)...(1-(n-1)/10000)

p>1-p ==> p>1/2

1-a/b < e^-a/b ==> p < product( e^-i/10000) {1<= i < n} ==> p < e^-sum(i)/10000

p < e^-n*(n-1)/20000

ln: -1 < -n(n-1)/20000

20000 > n(n-1)

==> n =...

20000 > n^2 ==> 100=n مثلا

ب) طوری که دو شماره مساوی نداشته باشیم..

تعداد ظرفها: تعداد شماره های 9 رقمی = 10 به توان 9

بقیه حل مثل الف

ج) اگر 13 رقمی باشد..

الف که همان جواب قبلی است، چون فقط 4 رقم آخر مهم است.

ب تعداد ظرفها به تعداد شماره های 13 رقمی است.

__________________________________________________

راه ساده تر حل سوال این است که از مساله توپ و ظرف استفاده کنیم: اگر n*ln(n) توپ داشته باشیم هیچ ظرفی خالی نیست. (با احتمال خوب)

الف)

10^4*log(10^4) > 12*10^4

ب)

10^9*log(10^9) > 27*10^9

ج)

10^13*log(10^13) > 39*10^13

قدم زدن تصادفی روی دایره و گراف آبنبات چوبی

(مرجع http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/ )

سوالهای کتاب (مبحث زنجیره مارکوف)

حل:

تقارن ندارد و احتمالها یکنواخت هم نیستند، پس حالت خاص نیست. با matlab حساب کردم این شد: 

>> P^33

ans =

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

جوابش همون طور که می بینید همه ی سطرهاش مساویند.

حل:

راه حل دوم: با رسم گراف آن می بینیم که احتمال تغییر وضعیت 1-p و احتمال ماندن در هر وضعیت p است.

حل:

با یک random walk گراف را رنگ می کنیم. راس اولی که در آن هستیم، قرمز می کنیم و راس بعدی را آبی و ادامه می دهیم. (بقیه اش سخت بود راه حل رو بخونید:)

جواب
حجم: 282 کیلوبایت

مرجع: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/sol7.ps

سوال تمرین تصادفی (مبحث آنتروپی)

جواب سوال 4: نمونه سوال آنتروپی

1- یک تاس n وجهی داریم که احتمال آمدن هر وجه آن pi است. ثابت کنید آنتروپی آن وقتی ماکسیمم است که pi=1/n باشد.

H(X) = sum(H(Xi))

طبق نامساوی حسابی هندسی (مثلا) مجموع وقتی ماکسیمم می شود که همه با هم برابر باشند.

i,j: H(Xi) = H(Xj) ==> pi = pj = 1/n

2- 

فرض می کنیم یک سکه با احتمال q داریم و می خواهیم اعداد n بیتی بسازیم.

دو به توان آنتروپی n بار پرتاب سکه:

2^(n*H(q)) = q^nq * (1-q)^n(1-q)

چیزی که باید ثابت کنیم این است:

C(n,nq) >= q^nq * (1-q)^(n-nq) / ( 2*sqrt(n) )

از باز کردن سمت چپ استفاده می کنیم:

C(n,nq) = n!/ ( (nq)! (n-nq)! )

طبق فرمول استرلینگ داریم:

n! > sqrt(2*pi*n)*(n/e)^n

1/n! > 1/ ( sqrt(2*pi*n) * (n/e)^n * e^1/(12n) )

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

جمله ی (n/e)^n را هم به دو جمله با توانهای nq و n-nq می شکنیم:

C(n,nq) >= (e^1/12n) / ( q^-nq * (1-q)^-n(1-q) * e^(1/12nq+1/12(n-nq) )

C(n,nq) >= 2^nH(q)

پس کافی است ثابت کنیم:

e^ (1/12n-1/12nq-1/12(n-nq) ) >= 1/ (2*sqrt(n) )

ساده می کنیم:

1/12n-1/12nq-1/12(n-nq) = 1/(12n) * ( 1-1/q-1/(1-q) )

1/ ( 2*sqrt(n) ) = 1/2* n^-1/2

نامساوی حسابی هندسی:

1/q+1/(1-q) = 1/( q*(1-q) ) >= 4

1-1/q-1/(1-q) <= -3

e^ (1/12n-1/12nq-1/12(n-nq) ) >= e^-3*(1/12n) = e^-1/(4n)

یعنی باید ثابت کنیم

e^ -1/(4n) >= 1/ (2*sqrt(n) )

e^-1/(4n) = (1/e)^1/(4n) >= (1/2)^1/(4n) >= 

جواب سوال 3

من فکر کردم همین نامساوی اجتماع چندتا پیشامد کمتر از جمع احتمال تک تکشونه خوبه براش!