الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

توپ و ظرف و گراف تصادفی

جمعه, ۸ آذر ۱۳۹۲، ۰۹:۱۹ ق.ظ

http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture13.pdf

توپ و ظرف:

m توپ را در n ظرف به صورت یکنواخت و مستقل می اندازیم. می خواهیم به سه سوال زیر جواب بدهیم:

1- توزیع توپ ها چیست؟

2- چند تا ظرف خالی داریم؟

3- بیشترین تعداد توپ در یک ظرف چندتا است؟ (maximum load)

جواب:

3- ماکسیمم لود:

Pr( L > 3 ln(n)/ln(ln(n)) ) < 1/n

2- احتمال خالی بودن هر ظرف: آزمایش برنولی: اگر توپ درون این ظرف افتاد موفقیت و در غیر این صورت شکست

p( success ) = 1/n

p( fail ) = 1-1/n

p(emty bin) = p( fail in all m repeats ) = (1-1/n)^m = e^-(m/n)

1- احتمال اینکه در هر ظرف دقیقا r توپ داشته باشد:

( e^-(m/n) ) * (m/n)^r / r!

که توزیع پواسون است!

توجه: توزیع پواسون با آزمایش پواسون متفاوت است. توزیع پواسون:

Pr(X=r) = e^-(avg) * avg^r / r!

نکته: مجموع متغیرهای پواسون متغیر پواسون با میانگین مجموع آنهاست.

**ارتباط متغیر تصادفی پواسون و نامساوی چرنف:

* می دانیم توزیع توپ ها در هر ظرف یک توزیع دوجمله ای است، که تعداد متغیرهای آن به تعداد ظرفها و احتمال آن 1 تقسیم بر تعداد توپها است.

اگر تعداد تکرار بینهایت باشد، توزیع دوجمله ای به توزیع پواسون تبدیل می شود.

------------------------------------------

گراف رندم

http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture16.pdf

دو نوع گراف رندم داریم:

 G(n,p) که در آن احتمال انتخاب هر یال p است و تعداد راسها n است.

G(n,N) که در آن N یال به صورت یکنواخت از یالهای باقیمانده انتخاب و به گراف قبلی اضافه می کنیم. (شروع از گراف تهی)

فرق این دو تا مثل فرق دوجمله ای و پواسونه، یعنی برای N بزرگ مثل هم هستند تقریبا.

گراف رندم، احتمال انتخاب هر یال p است، چون انتخاب یالها مستقل است می توانیم از نامساوی چرنف استفاده کنیم.

(اگر راسها را انتخاب می کردیم انتخاب یالها مستقل نبود و نمی توانستیم از چرنف استفاده کنیم.)

توپ = یالها

ظرف = راسها

 هر بار دو توپ پرت می کنیم!

**چه زمانی از گراف رندم استفاده می کنیم؟
وقتی که فقط به ازای ورودی های خاصی حالت خیلی بدی رخ می دهد و در اکثر موراد زمان اجرا خوب است.
*مثال: دور همیلتونی
اول الگوریتمی که ارائه می دهد این است که یکی یکی راسها را برود و هر جا به خودش برخورد کرد، این قسمت از مسیر را برعکس کند.
بعد یک الگوریتم دیگر ارائه می دهد که در آن احتمال دیده شدن یک یال بیش از یک بار وجود دارد. که در آن عملیات الگوریتم اول با احتمال رخ دادنشان انتخاب می شوند. الگوریتم دوم برای گراف جهت دار درست کار می کند.
گرافی به این صورت می سازد که هر راس به احتمال q با راسهای دیگر همسایه است. (زیرگراف رندم گراف کامل) -- مزیت: تقارن
در این گراف الگوریتم دوم همان نتیجه ی الگوریتم اول را می دهد.
----
به این نتیجه رسیدم که این طوری به جایی نمی رسم، در نتیجه جواب ها رو می خونم این دفعه! :)
موافقین ۰ مخالفین ۰ ۹۲/۰۹/۰۸
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی