جواب سوال 2

باید تقریب رو از روی نمونه گیری به روی تعداد نمونه ها ببریم. (با به دست آوردن رابطه ی بین دقت نمونه گیری و تعداد تکرارهای اون)

جواب سوال 1

از این استفاده می کنیم که زمان متوسطی که فرض کردیم در واقع cover time گراف است یعنی همه ی راسها دیده می شوند.

سوالهای باقی مانده

1- چطور ثابت کنیم قدم زدن تصادفی را می شود در زمان کمتری انجام داد؟

2- تقریب اپسیلون و دلتا برای یک نمونه گیری تصادفی را چطور ثابت کنیم؟ (تعداد نمونه گیری ها را به دست بیاوریم)

3- چطور می توانیم از نامساوی چرنف استفاده کنیم، برای متغیرهای نامستقل (وابسته)؟

4- نمونه سوال آنتروپی؟

تقریب اپسیلون و دلتا

مثال: (ادامه سوال independent set های گراف)

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

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

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

سوال 4 این سوال 1 تمرینه: (موش و گربه)

http://www.eecs.berkeley.edu/~vkanade/cs174/HW/HW9_sol.pdf

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

این اومده گفته این یه زنجیره مارکوفه و برای هر وضعیت مساله یک راس گرفته گفته و حل کرده.

من گفتم که این معادل یک random walk روی یک گراف دیگه است که هر راسش جای موش و گربه است.

ظاهر این دو تا حل مثل همه (یعنی این قسمتی که من گفتم) ولی بقیه اش خیلی فرق داره.

جزوه الگوریتم تصادفی

دریافت
حجم: 2.12 مگابایت

مال دانشگاه خودمون نیست ولی خیلی خوب و کامل توضیح داده.

سوالهای امتحان

نمی دونم چرا قبلا ندیده بودم. روی فلشم هم بود! :) دقیقا سوالها از این مجموعه بود!

سوالها
حجم: 615 کیلوبایت

استفاده از مشخصات مساله

به جای اینکه مساله را مستقیما حل کنیم می توانیم مشخصاتی از آن را در نظر بگیریم و این مشخصات را با هم مقایسه کنیم. (چون چک کردن تساوی آنها به طور مستقیم زمانبر است.)

در این صورت می توانیم با چک کردن تصادفی این مشخصات مسائلی که یکسان بودن دو چیز را بررسی می کنند حل کنیم.

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

تحلیل: دو حالت وجود دارد: واقعا مساوی بودن (A) و واقعا نامساوی بودن (A'). پیشامد B را هم تشخیص درست در نظر می گیریم. طبق احتمال شرطی داریم:

pr(B) = Pr(B|A)Pr(A)+Pr(B|A')Pr(A')

با استفاده از pr<=1 و محاسبه ی احتمالهایی مثل محاسبه ی احتمالهای دیگر برای آن کران پیدا کرد.