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

جوابهای خودم اند.

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

ب) قسمت اول: نسبت مساحت قسمتی که مرکز دایره می‌تواند در آن قرار بگیرد به کل خانه را حساب می‌کنیم و این احتمال مورد نظر است.

قسمت دوم: با قسمت قبل و به دست آوردن i با کمک شرط خاتمه به احتمال مورد نظر می‌رسیم.

ج) احتمال مورد نظر کمتر از مکعب شامل دایره به مرکز نقطه کوئری و شعاع بهینه است. نسبت حجم توپ و مکعب شامل توپ ثابت است پس احتمال مورد نظر از مرتبه نسبت مکعب محیطی توپ و مکعب خانه داده شده است.

د) جستجوی دودویی+اجرای الگوریتم

ه) جمع مقادیر قسمت قبل است. رابطه‌ی آن قبلاً آورده شده است.

۲- الف) حداکثر ۴ نوار اطراف (راست چپ بالا و پایین) خطا ایجاد می‌کنند پس با قرار دادن ۴*اپسیلون به جای اپسیلون به جواب می‌رسیم. (حکم را در تعداد نقاط هر خانه ضرب کنید.)

ب) روش merge & reduce را به کار ببرید. لگاریتمی بودن را با فرض داشتن n حل کنید.

ج) اپسیلون خلاصه را بسازید و طبق قسمت ب تقریب به دست می‌آید.

*مهلت تحویل تمرین: سه‌شنبه

ادامه حل سوالهای موازی

سوال ۱.۱۶۱: در تحلیل سوال ۱.۱۶۰ مقدار r=sqrt(n log n) و p=n است. فقط باید مستطیل را روی مربع اجرا کنیم.

به مناسبت پایان تعطیلات نوروزی و ددلاین تمرینات

ضرب ماتریس روی شش وجهی (موازی)

ارائه‌ی الگوریتم تقریبی

پیچیدگی پارامتری

دریافت

حجم: 134 کیلوبایت

اسپارس کردن (خلاصه سازی گراف)

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

تعدادی از درس‌های الگوریتمی

الگوریتم تقریبی پیشرفته

http://www.cs.cmu.edu/~anupamg/adv-approx/

الگوریتم‌های دنیای واقعی (شامل LSH و چند تا از مدل‌های جویبار داده و الگوریتم موازی و ...)

http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS14.html

کاربرد متریک در مسائل الگوریتمی

http://www.cs.cmu.edu/~anupamg/metrics/index.html

همه‌ی این درس‌ها را یک نفر ارائه می‌دهد:

http://www.cs.cmu.edu/~anupamg/

ellipsoid method

با این روش می‌توان یک مسأله‌ی LP را که تعداد قیدهای آن بر حسب اندازه مسأله نمایی است، با فرض داشتن یک جداکننده با زمان چندجمله‌ای در زمان چندجمله‌ای حل کرد. منظور از جداکننده این است که یک جواب احتمالی را بگیرد و بگوید واقعا جواب مسأله هست یا نه و اگر نبود قیدی را که نقض می‌کند برگرداند. (فصل ۴.۳ کتاب WS)

الگوریتم تقریبی رنگ آمیزی گراف

منبع:‌ صفحه ۱۸۵ کتاب Approximation Algorithms and Semidefinite Programming نوشته‌ی Bernd Gärtner, Jiří Matoušek

(کلاً کتاب خوبی نبود ولی اتفاقی این سوال رو توش دیدم که سوال اول تمرینهاست! البته من حل خودم رو تحویل میدم.)

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

نسبت مجموع زیرمجموعه‌ها

http://www.lamsade.dauphine.fr/~bazgan/Papers/icalp98.pdf

می‌خواهیم دو زیرمجموعه مجزا از اشیا انتخاب کنیم که نسبت مجموع آنها مینیمم شود.

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

مسیر فروشنده دوره‌گرد

به جای دور فروشنده دوره‌گرد مسیر فروشنده دوره‌گرد را به دست بیاورید.

من مقاله‌ای که جواب این سوال در آن هست را آپلود کردم اما اثباتش هم طولانی بود هم عجیب.

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