جواب سوال 3

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

جواب سوال 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 کیلوبایت