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

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

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

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

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

بایگانی

۶۲ مطلب در بهمن ۱۳۹۲ ثبت شده است

1- یک الگوریتم تقریبی با ضریب 1/2 بدهید که سوال زیر را حل کند:

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

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

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

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

1/2OPT<=ALG

1/2*OPT <= max(deg_>, deg_<)

OPT <= 2*max(deg_>,deg_<)

OPT <= |E|=deg_>+deg_< <= 2*max(deg_>,deg_<)

2- یک الگوریتم با ضریب تقریب 2 بدهید که این مساله را حل کند: یک تطابق ماکسیمال با کمترین تعداد اعضا روی یک گراف بدون جهت به دست بیاورد.

راهنمایی: از این حقیقت استفاده کنید که هر تطابق ماکسیمالی حداقل به اندازه ی نصف تطابق بیشینه یال دارد.

حل:

یک تطابق از گراف می دهیم: یالها را به تطابق اضافه می کنیم تا وقتی که دیگر نتوانیم یال اضافه کنیم. (وقتی که یالی نماند که یک سر آن قبلا در یالهای دیگر انتخاب نشده باشد).

تعداد یالهای این تطابق کمتر از تعداد یالهای تطابق بیشینه و بیشتر از نصف تعداد یالهای تطابق بیشینه است.

تعداد یالهای تطابق ماکسیمال با کمترین اعضا (جواب بهینه) حداقل به اندازه ی نصف تطابق بیشینه است. (طبق راهنمایی)
این دو نامساوی را بنویسیم خود به خود به جواب می رسیم:
1/2*|MM| <= OPT ==> |MM| <= 2*opt
ALG = |M| <= |MM|
==> ALG=|M| <= 2*OPT
3- الگوریتم تقریبی با ضریب 2 زیر را در نظر بگیرید که تعداد اعضای پوشش راسی را حساب می کند. یک درخت پیمایش عمقی (dfs) روی گراف G پیدا کنید و مجموعه ی S از همه ی راسهای غیر برگ این درخت را برگردانید. نشان دهید S یک پوشش راسی از G است و 
|S| <= 2.OPT
راهنمایی: نشان دهید که G یک تطابق با اندازه ی |S| دارد.
حل:
اول راهنمایی را ثابت می کنیم: عمقهای زوج و فرد را به صورت دو بخش گراف دوبخشی در نظر می گیریم. (تطابق). باید ثابت کنیم بین این دو بخش حداقل |S| یال هست. به ازای هر راس میانی حداقل یک راس میانی دیگر یا یک برگ در بخش دیگر وجود دارد.
از راهنمایی نتیجه می گیریم هر کدام از بخشهای گراف حداقل |S| راس دارند که چون بین آنها یال نیست یک پوشش راسی هستند. اگر دو سر این یالها را به عنوان جواب برگردانیم حداکثر دوبرابر جواب بهینه خواهد بود.

۰ نظر موافقین ۰ مخالفین ۱ ۱۳ بهمن ۹۲ ، ۱۳:۰۸
سپیده آقاملائی
۱ نظر موافقین ۰ مخالفین ۰ ۱۳ بهمن ۹۲ ، ۱۱:۵۳
سپیده آقاملائی
۰ نظر موافقین ۰ مخالفین ۰ ۱۳ بهمن ۹۲ ، ۱۱:۲۴
سپیده آقاملائی
یک سمینار در مورد این توی دانشگاه بود یه سری شکلات تابلرون هم جایزه می دادن! الآن دیدم توی اسلایدهای الگوریتم تقریبی هست.
http://algo2.iti.kit.edu/appol/les8.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۱۲ بهمن ۹۲ ، ۱۸:۰۶
سپیده آقاملائی

چیزی که من در پست TSP دور ترجمه کردم "گشت" بوده.

http://algo2.iti.kit.edu/appol/tsp.pdf

بدتر از اون چیزیه که توی گزارش ام نوشتم :)) wlog می شده without loss of generality بعد من مطمئنم یه چیز دیگه ترجمه کردم.

این اسلایدها یکم آلمانی داره ولی شکل های خوبی داره و درست توضیح داده:

http://algo2.iti.kit.edu/appol

۰ نظر موافقین ۰ مخالفین ۰ ۱۲ بهمن ۹۲ ، ۰۸:۳۴
سپیده آقاملائی

http://algo2.iti.kit.edu/appol/les7.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۱۲ بهمن ۹۲ ، ۰۸:۰۵
سپیده آقاملائی

http://www.cs.ucr.edu/~neal/2006/cs260/piyush.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۱۲ بهمن ۹۲ ، ۰۷:۵۴
سپیده آقاملائی

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

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

۰ نظر موافقین ۰ مخالفین ۰ ۱۱ بهمن ۹۲ ، ۰۹:۱۸
سپیده آقاملائی

http://electures.informatik.uni-freiburg.de/portal/download/3/9211/thm17%20-%20list%20ranking.pdf

۰ نظر موافقین ۰ مخالفین ۰ ۱۰ بهمن ۹۲ ، ۲۰:۴۴
سپیده آقاملائی

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/twodim/shear/shearsorten.htm

من چون خودم که الگوریتم رو خوندم اصلا نفهمیدم چرا درست کار می کنه، گفتم اثباتش رو پیدا کنم.

هنوز هم ایده ای ندارم چطوری این به ذهنشون رسیده.

۰ نظر موافقین ۰ مخالفین ۰ ۱۰ بهمن ۹۲ ، ۲۰:۴۱
سپیده آقاملائی