3SUM

http://en.wikipedia.org/wiki/3SUM

Competitive facility location

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

سوال کانتست بیان هم بود که خواسته بود تعداد حالت‌ها را بشماریم. توی اسلایدها نوشته بود PSPACE است و حالتی از independent set است.

گرافهای هندسی و روش‌های احتمالاتی

مرجع:

گرافهای هندسی

http://web.mit.edu/~holden1/www/coursework/math/18.318/main.pdf

روش‌های احتمالاتی

http://web.mit.edu/~holden1/www/coursework/math/18997/notes.pdf

اثبات قدم زدن تصادفی با spanner تتا گراف

کلا ربات ۸ تا سنسور دارد که هر کدام یک بازه‌ی مساوی را می‌بینند. (یک دایره است که به ۸ قسمت تقسیم شده است.)

این ۸ همان مقدار لازم برای همبند بودن تتا گراف است.

به این صورت گراف متناظر آن ساخته می‌شود و بقیه اثبات مثل random walk معمولی است.

الگوریتم قدم زدن تصادفی زاویه‌ای

بالاخره چیزی که می‌خواستم پیدا کردم:

که وقتی ربات آن را اجرا می‌کند نتیجه این می‌شود:

جواب سوال تمرین/امتحان

http://www.bioinfo.org.cn/~wangchao/maa/HW3_201018013229070_Chao_Wang.pdf

واقعا چیزی که درس داده شده تا تمرین و امتحان فاصله ی زیادی داره. اشتباه کردم که نرفتم مثل بقیه حفظ کنم جواب تمرین ها رو بنویسم سر امتحان.

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

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

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

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

حل:

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

تعداد ظرفها: تعداد شماره های 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