تمرین الگوریتم تقریبی (نسخه اصلاح شده!)

از سوال ۷ قسمت پیدا کردن کران L مانده. در سوال ۵ هم اشکال هست. (خودم حل کرده بودم انگار!)

حل‌های فعلی را آپلود کردم اگر این‌ها اشکال دیگری دارند یا در مورد سوالهای ۷ و ۵ جواب بهتری دارید بگید.

دریافت
حجم: 90.9 کیلوبایت

اصلاحیه حل سوال ۷ تقریبی

گونه‌هایی از بشر واقعاً خنگ آفریده شده‌اند (خودم) من ایمیل زدم که چرا سوال 7-Acyclic graph شرط بدون دور بودن را ندارد؟ :)

حل قبلی که در وبلاگ زدم درست است!

وضعیت من بدون شرح است. دوستان در صورتی که چنین چیزهایی می‌بینید سریعاً اطلاع بدید!

جواب سوال ۷ تمرین الگوریتم تقریبی

گراف جهت‌داری داده شده است که یالهای آن علاوه بر طول، وزن هم دارند. می‌خواهیم به ازای دو رأس مشخص s و t مسیر با کمترین هزینه از s به t را پیدا کنیم که طول آن از L بیشتر نباشد.

ما حل مسأله را در حالتی که طول همه‌ی یالها برابر باشند بلدیم: کوتاهترین مسیر را روی وزن یالها اجرا می‌کنیم. پس اگر اختلاف کوتاهترین مسیر و طولانی‌ترین مسیر کم باشد می‌توانیم آن را تقریبی حل کنیم. اگر بتوانیم با عملی مانند جستجوی دودویی کرانهای بالا و پایین را به هم نزدیک کنیم به نتیجه مورد نظر می‌رسیم. برای این کار طول مسیر را بر (n-1) تقسیم می‌کنیم و برای یالها کران به دست می‌آوریم بعد با تقسیم وزن یالها به این مقدار تعداد وزن‌های متمایز را محدود می‌کنیم و می‌توانیم با dynamic programming مسأله را حل کنیم. هر بار طول مسیر را یکی زیاد می‌کنیم و در صورتی که جواب بهتر شد آن را جایگزین جواب قبلی می‌کنیم.

؟؟ در مقاله اصلی گفته شده که رأسها را طوری شماره‌گذاری می‌کنیم که اگر بین دو رأس یال باشد رأس اول شماره کمتری از رأس دوم دارد. این topological sort است که نیاز به شرط نبودن دور در گراف دارد.

دو الگوریتم بر حسب طول مسیر و وزن مسیر داده است که اولی از مرتبه‌ی تعداد یالهای * حداکثر طول یال و دومی از مرتبه‌ی تعداد یالها * هزینه مسیر بهینه است. (هر دو dp). الگوریتم‌های دقیق هستند برای حالتی از مسأله که ماکسیمم طول مسیر مشخص باشد.

صورت سوالهای تمرین ۲ پردازش موازی

تمرین ۳ پردازش موازی

HW3 from Parhami's:

6.3

6.4

6.6

6.11

5.15

5.10

2.4

2.8

Due: 7/2/92

سوال و جواب امتحان هندسه محاسباتی پیشرفته (میان ترم)

۱- یک الگوریتم ساده بدهید که در زمان خطی تقریبی از بزرگترین مثلث ساخته شده با رئوس نقاط P بدهد.

راهنمایی: نقطه p و دورترین نقطه از آن q را در نظر بگیرید.

جواب: نقطه r را که دورترین نقطه نسبت به pq است در نظر می‌گیریم. می‌دانیم pq یک ۲-تقریب از قطر نقاط است و r یک ۴-تقریب از عرض نقاط است. مساحت مثلث pqr بر حسب قطر و عرض نقاط به دست می‌آید. حالا باید مساحت مثلث بهینه را بر حسب قطر و عرض نقاط به دست بیاوریم. بدیهی است که مساحت هر مثلث (از جمله مثلث بهینه) در رابطه زیر صدق می‌کند:

1/2*width^2 < S < 1/2*diamter^2

(یکی از بچه‌ها اینجا نتیجه گرفته بود که width=diameter بدترین حالت است و مثلث متساوی الاضلاع گرفته بود اما من باز هم نتوانستم طرف کمتر قضیه را اثبات کنم در نتیجه فعلاً جواب درست را نمی‌دانم. دیروز به نظرم این جواب درست بود.)

۲- الگوریتمی داریم که در زمان O(n log n) برای یک چندضلعی (نه لزوما محدب) بزرگترین مربع محاطی که اضلاع آن موازی محورهای مختصات است را به دست می‌آورد. یک ۱+اپسیلون تقریب برای بزرگترین مربع محاطی در جهت دلخواه بدهید.

جواب: تعدادی بردار جهتی را در نظر می‌گیریم و جواب را در جهت آنها حساب می‌کنیم (رند کردن جهتی) می‌دانیم با تغییر زاویه به اندازه دلتا اندازه ضلع حداکثر به اندازه‌ی ۱-کسینوس دلتا تغییر می‌کند که از مرتبه‌ی دلتا به توان دو است که اگر اپسیلون را این مقدار قرار دهیم جواب به دست می‌آید.

۳- روش merge and reduce را بنویسید و ثابت کنید.

جواب: به جزوه مراجعه کنید. فقط قسمتی که من در جزوه‌ی خودم ننوشته بودم:

دلیل اینکه اپسیلون از مرتبه لگاریتمی تغییر می‌کند این است که هر بار یک اپسیلون با آن جمع می‌شود؛ چون تقریب قبلی مثلاً 2epsilon است (مرحله merge) و وقتی از آن اپسیلون تقریب می‌گیریم epsilon+2epsilon می‌شود (مرحله reduce).

۴- مسأله‌ی k-center را با فرض داشتن یک الگوریتم ۲-تقریبی برای آن با تقریب ۱+اپسیلون حل کنید. یک هسته با اندازه‌ی O(k/epsilon^d) بدهید که این مسأله را حل کند.

راهنمایی: ابتدا الگوریتم ۲-تقریب را اجرا کنید سپس آن را با توری به ا+اپسیلون تقریب تبدیل کنید.

جواب: برای هر کدام از توپ‌ها یک توری می‌سازیم که اندازه آن 2r و هر خانه‌ی آن r*epsilon/sqrt(d) است که چون قطر هر خانه sqrt(d) برابر ضلع آن است فاصله هر نقطه حداکثر انقدر است. یعنی اگر نقاط را به نزدیک‌ترین رأس توری رند کنیم حداکثر خطای ما این مقدار خواهد بود.

۵- مسأله‌ای که در وبلاگ هم آمده است و سوال ۱۴.۱۰ کتاب de-berge است.

لینک

شخصاً سر این اشتباهی انجام دادم که تا سالها مایه‌ی خنده و شادی بشریت خواهد شد، چون در کل کلاس هم اعلام کردم. دلیل اشتباهم هم خیلی خنده‌دار همین حقیقت بود که همیشه آدم حس می‌کند که عمق درخت باید از مرتبه‌ی لگاریتم تعداد برگ‌ها باشد و در درخت چهارتایی اشتباهی بزرگتر از این نیست چون برگ‌ها از مرتبه‌ی تعداد نقاط اند در حالی که عمق درخت از مرتبه‌ی قطر تقسیم بر عرض است و فقط در درخت متوازن که عمق درخت از مرتبه لگاریتم تعداد برگ‌ها است این موضوع درست است.

*در مورد سوال ۱ به شدت پذیرای حل‌های شما دوستان عزیز هستیم!

خیلی خوش گذشت

بعد از این همه خوندن نمره نمی‌گیرم.

کار دیگه‌ای به ذهنم نمی‌رسه که بخوام انجام بدم یا چیزی که بخونم.

فکر کنم همون ایده‌ی سمیه که پول بدم برم دکتری منطقی‌ترین گزینه است!

فصل 22 هارپلد

مرکزهای متحرک

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

تقریب بدیهی دایره محیطی با عرض

این جوابی بود که سر کلاس تی‌ای هم داده شد: