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

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 هارپلد

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

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

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

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

کتاب هارپلد (فصل ۲)

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

زمان ساخت درخت از اینجا n log phi به دست می‌آید. (phi = نسبت قطر به عرض)

درخت فشرده

برای رسیدن به زمان لگاریتمی بر حسب n باید از مسأله فصل قبل استفاده کنیم و توری مناسب را بسازیم. با این کار اندازه خانه‌ای که باید نقاط را بر حسب آن به دو قسمت تقسیم کنیم به دست می‌آید. ثابت می‌شود که این تقسیم نقاط را تقریبا نصف می‌کند.

*درخت چهارتایی فشرده برای مکان یابی نقطه

جستجوی دودویی روی عمق درخت

*

کتاب هارپلد (فصل ۱)

*نزدیک‌ترین زوج نقاط

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

بهبود: جایگشت تصادفی از نقاط را حساب می‌کنیم. به صورت افزایشی نقاط را اضافه می‌کنیم و جواب را به دست می‌آوریم. اگر از قبل بهتر شده بود توری را مجدداً می‌سازیم. (با توجه به مقدار جدید). این کار زمان O(i) در مرحله i-ام می‌گیرد. چون این احتمال 1/i است پس متوسط زمان اجرا

sum i*1/i = sum 1 = n

یعنی خطی است.

*الگوریتم ۲-تقریبی برای دیسک شامل k نقطه

یک توری تطبیق پذیر را به این صورت می‌سازیم که هر قسمت شامل k نقطه باشد و هر کدام از این قسمت‌ها را به قسمت‌های k/4 نقطه دار تقسیم می‌کنیم.

برای این کار از الگوریتم پیدا کردن عنصر با رتبه مشخص استفاده می‌کنیم که زمان O(n log n/k) می‌گیرد که O(n) برای قسمت اول است و در قسمت دوم چون بازگشتی تا جایی پیش می‌رویم که k/4 نقطه بماند زمان آن O(log n/k) می‌شود.

سپس برای هر خانه از رئوس توری کوچکترین دایره شامل k نقطه را پیدا می‌کنیم.

تعداد رأسهای توری (n/k)^2 تا است و برای پیدا کردن کوچکترین دایره شامل نقاط به چک کردن بیش از n نقطه نیاز نخواهیم داشت. پس کلاً زمان O(n (n/k)^2) می‌گیرد.

هر دایره برای اینکه k نقطه داشته باشد باید حداقل ۴ ناحیه را قطع کند. پس حتما شامل یکی از رأسهای توری می‌شود.

بهبود:

با استفاده از توری سلسله مراتبی و ساختاری مشابه skiplist می‌توانیم به زمان خطی برای این مسأله برسیم. این کار را تا جایی ادامه می‌دهیم که k نقطه در آن سطح باقی بمانند.

هیچ خانه توری بیش از 5k نقطه ندارد. (اثبات با رسم ۴ دایره در گوشه‌های خانه توری و دایره محاطی خانه توری+ماکسیمم تعداد نقاطی که در دایره به شعاع خانه توری جا می‌شوند)

جواب را برای توری در هر عمق حساب می‌کنیم (زمان خطی). توری هر مرحله از جواب عمق بالاتر خود به دست آمده است.

ساخت skip-list زمان خطی می‌برد. زمان محاسبه جواب برای هر توری O(k) است. با تلاش فراوان (!) زمان متوسط خطی به دست می‌آید.

*حل تمرین‌های فصل ۱

http://softday.blog.ir/1392/11/21/%D8%AA%D9%85%D8%B1%DB%8C%D9%86-%D9%87%D8%A7%DB%8C-%D9%81%D8%B5%D9%84-1-%DA%A9%D8%AA%D8%A7%D8%A8-%D9%87%D9%86%D8%AF%D8%B3%D9%87-har-peled

اصلاحیه تمرین تقریبی

در مورد سوال max k-cut تمرین‌ها بود.

اشکال ایده‌ای که گفتند این بود که تعداد یالهای بین دو مجموعه توزیع یکنواخت ندارند که احتمال آنها به سادگی حساب شود. (در صورتی که یالها را تصادفی بین مجموعه‌ها تقسیم می‌کردیم این جواب درست بود.)

در مورد ایده‌ی خودم هم احتمال حضور هر یال:

(k^2-k)/(k^2) = (k-1)/k = 1-1/k

می‌شود که در نتیجه جواب قبلی غلط است.

اما از آنجا که k>=2 است نتیجه می‌گیریم که مقدار بالا از ۱/۲ بیشتر است و حکم ثابت می‌شود.

جواب سوال سمیه (موازی)

http://en.wikipedia.org/wiki/Prime-counting_function

تعداد اعداد اول از x/ln(x) بیشتر است پس اگر تعداد پردازنده‌های ما از n/ln(n) کمتر باشد به مشکل بر نمی‌خوریم چون همیشه عددی که می‌خواهیم از قبل پیدا شده است.

سوال این بود که اگر مضارب ۲ را کنار می‌گذاشتیم، با چندتا پردازنده بقیه را می‌شد پیدا کرد. (سوال کتاب هم هست.)

البته فکر کنم باز هم هیچ وقت به اون کران نیاز پیدا نمی‌کنیم و باز هم مثلاً تعداد مضارب ۳ کران را می‌دهند.