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

می‌خواستم وقتی کامل شد بذارم ولی حالا می‌گذارم. حل بقیه سوالها روی وبلاگ هست. اگر اشکالی بود خبر بدهید اگر چیزی را عوض کردم اصلاحیه می‌زنم.

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

حرکت بهینه ربات دیسکی با سنسور gap

http://msl.cs.uiuc.edu/~lavalle/papers/LopMurLav12.pdf

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

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

الگوریتم‌های جلسه قبل از مرتبه O(dn) بودند یعنی برای ابعاد بالا قابل استفاده نیستند. پس یک بار دیگر عملکرد الگوریتم‌های جلسه قبل را بررسی می‌کنیم.

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

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

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

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

من الآن دارم مقاله را می‌خوانم و حس می‌کنم این‌ها هیچ ربطی به مطالب مقاله ندارند.

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

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

روش اول که پیدا کردن دورترین نقطه است از اینجا به ذهن می‌رسد که ماکسیمم فاصله هر دو نقطه قطر را می‌دهد. برای اثبات تقریب باید به ازای هر نقطه p از نقاط اولیه ثابت کنیم که دو نقطه‌ی جواب (مثلا a و b) تقریبی از قطر می‌دهند.

ALG < OPT < c*ALG

max(pa,pb) < ab < pa+pb < 2*max(pa,pb)

یعنی اگر ماکسیمم فاصله‌ از هر نقطه دلخواهی را به عنوان جواب برگردانیم ۲-تقریب جواب بهینه است.

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

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

حالا الگوریتم brute force را روی این نقاط جدید که تعداد کمی دارند (همان طور که گفته شد وابسته به اپسیلون است.) اجرا می‌کنیم که مرتبه‌ی n^2 است و زمان ما همچنان خطی بر حسب n و یک بر اپسیلون خواهد بود. (PTAS) زمان خطی مربوط به رند کردن نقاط به توری است که با یک کف گرفتن (جزء صحیح) انجام می‌شود.

ضریب تقریب آن رادیکال d برابر عرض هر خانه (=قطر هر خانه) خواهد بود که چون تعداد ابعاد را از قبل می‌دانیم می‌توانیم به هر اپسیلون دلخواهی برسیم.

در این توری می‌دانیم که نقاطی که درون مکعب می‌افتند تاثیری در محاسبه‌ی قطر ندارند پس با در نظر گرفتن نقاط روی سطح آن می‌توانیم توان یک بر اپسیلون را در محاسبه‌ی تعداد نقاط یکی کم کنیم.

مدل‌های برنامه‌نویسی موازی

قسمت اول ارائه‌ی خودم است. تا سر برنامه‌نویسی موازی توضیح دادم و منبع هم همان کتاب برنامه‌نویسی موازی است و قسمت‌های جدید از ویکیپدیا است.

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

تعمیم توری شش وجهی و EJ Networks (موازی)

دریافت
حجم: 3.94 مگابایت

موتور جستجوی گراف موازی

http://graphlab.org/files/osdi2012-gonzalez-low-gu-bickson-guestrin.pdf

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

این مقاله فکر کنم یک روش خاص GAS (Gather Add Scatter) را به کار می‌برد که با توجه به مثالی که زده است تقریباً نیاز به توضیح بیشتری ندارد:

اما چیزی که فکر کنم من شنیده بودم قبلاً GraphLab بود. چون یادم است که اسم ساده‌ای داشت، موازی بود و یک framework برای جستجو بود که بر اساس abstraction بود.

http://en.wikipedia.org/wiki/GraphLab

تابع به روز رسانی page rank به زبان ML

منبع: http://select.cs.cmu.edu/code/graphlab/abstractiononly.pdf

نیمکره راست یا چپ

همین الآن تست نیمکره راست و چپ مغز را دادم و نیمکره راستم فعال‌تر بود که تمایل به بی‌نظمی و خلاقیت و ... دارد. (در مقابل نیمکره چپ که تمایل به منطق و ... دارد.)

الآن تازه می‌فهمم چرا من سوالهای کتاب creative را راحت حل می‌کردم و اینکه چرا سر کلاس دکتر آبام هیچی از درس نمی‌فهمم! چون مثل این است که آدم نسبت به یک رنگ کوررنگی داشته باشد و استاد با آن رنگ روی تخته درس بدهد.

حداقل می‌دانم اگر به مقطع بالاتر راه پیدا کنم اکثر ایده‌هام جدید خواهند بود و به موفقیت کافی می‌رسم که جبران این مدت را هم می‌کند.

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

*جستجوی نزدیک‌ترین همسایه

ساختمان داده‌ای بسازید روی مجموعه نقاط d-بعدی P که به ازای نقطه کوئری داده شده نزدیک‌ترین نقطه را به آن برگرداند.

روش دقیق:

دیاگرام ورونوی و point location: پیش پردازش O(nlogn) و کوئری O(log n) و حافظه O(n) (دو بعدی)

برای ابعاد بالاتر حافظه O(n^ceil(d/2)) می‌شود یا می‌توان زمان کوئری را بیشتر کرد و O(n) کوئری (توان کمتر از ۱ بود) و O(n) حافظه داشت.

روش تقریبی:

تعریف مسأله: به ازای نقطه کوئری و شعاع همسایگی داده شده نقطه‌ای برگردانید که فاصله‌ی آن حداکثر ۱+اپسیلون برابر جواب بهینه باشد.

نسخه تصمیم گیری: اگر نقطه‌ای با مشخصات مورد نظر وجود داشت آن را برگردان و در غیر این صورت جواب بده وجود ندارد.

؟؟؟ فکر کنم نسخه‌ی تصمیم گیری فقط این باشه که این نقطه برای این مسأله جواب هست یا نه. (بله/خیر)

*روش ساده برای حالتی که شعاع همسایگی ثابت باشد:

یک توری با اندازه خانه‌های epsilon*r/sqrt(d) می‌سازیم و چک می‌کنیم که آیا هیچ خانه‌ی توری با توپ حول نقطه کوئری تقاطع دارد یا نه. روش: هشینگ

وقتی هش می‌کنیم یک مجموعه از خانه‌های توری برگردانده می‌شوند و باید کل آنها را بگردیم و نقاط آنها را چک کنیم که درون دایره می‌افتند یا نه و در بدترین حالت می‌شود که همه‌ی نقاط درون مکعب و خارج توپ بیفتند. اما چون از هر خانه فقط یک نقطه را نگه داریم مشکل قبلی حل می‌شود و زمان الگوریتم هم epsilon^-d می‌شود که تعداد خانه‌های توری است. دانستن شعاع هم برای ساختن توری لازم است.

*روش ساده ۲ برای حالتی که شعاع همسایگی ثابت باشد:

به جای پیدا کردن همسایه‌های نقطه کوئری، خانه‌های همسایه‌ی نقاط اصلی را پیدا کنیم و به ازای نقطه کوئری فقط باید چک کنیم که خانه‌ی شامل آن نقطه در همسایگی کدام مجموعه از نقاط آمده است. کوئری آن زمان O(1) می‌برد و فضای لازم آن O(epsilon^-d * n) است. چون به ازای هر خانه‌ی توری حداکثر n نقطه همسایه باید برای آن نگه داریم.

Parallel LSH

مرجع: http://padas.ices.utexas.edu/static/papers/sc11-knn.pdf

این پوستر(!) مربوط به LSH موازی است. با دیدن اینکه فقط به عنوان پوستر پذیرفته شده حس می‌کنم هدف الگوریتم‌های sublinear موازی حل کردن مسأله است و تازه می‌فهمم ایده‌ی Hashing چرا برای حل این مسأله استفاده شده است.