الگوریتم تقریبی MIT

http://courses.csail.mit.edu/6.891-s00/

پایان نامه کارشناسی در مورد الگوریتم تقریبی

http://www.seas.upenn.edu/~sassadi/stuff/papers/thesis.pdf

صندلی‌های نوی آزمایشگاه

صندلی‌های نو آوردن برامون! :) (۱۰ تا!)

الآن من حاضرم برای بهبود وضع آزمایشگاه میزها رو خودم دستمال بکشم! :)

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

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

سوال ۲ برای اینکه تقریب ۱-اپسیلون به دست بیاورید به جای اینکه در نامساوی c.OPT بگذارید ۱-اپسیلون بگذارید. در این صورت جواب بر حسب اپسیلون به دست خواهد آمد. همان طور که از صورت سوال هم مشخص است اپسیلون باید از c بیشتر باشد.

Terrain Visibility with Multiple Viewpoint

http://arxiv.org/pdf/1309.4323v1.pdf

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

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

دریافت
حجم: 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 کیلوبایت