الگوریتم تقریبی (قسمت دوم)

http://www.cse.buffalo.edu/~hungngo/classes/2006/594/

Fast Computation of Output-Sensitive Maxima in a Word RAM

http://www.madalgo.au.dk/~peyman/pubdata/maxima.soda14.pdf

algebraic decision tree

اگر با یک تابع چندجمله‌ای جدا کنیم به آن algebraic decision tree می‌گویند. حالت خاص آن درخت تصمیم معمولی است که بر مبنای مقایسه تقسیم می‌کند. حالت خطی linear decision tree با تابع خطی جدا می‌کند.

مرجع: http://en.wikipedia.org/wiki/Algebraic_decision_tree

word ram model of computation

http://courses.csail.mit.edu/6.851/spring07/scribe/lec12.pdf

ارائه‌ی هندسه محاسباتی پیشرفته

http://sarielhp.org/p/12/net_prune/stoc_slides.pdf

O با یک علامت ~

http://en.wikipedia.org/wiki/%C3%95#Mathematical_use

حل سوالهای باقیمانده از نمونه سوالهای پردازش موازی

سوالی که ماکسیمم را در مدل CRCW می‌خواست: n^2 پردازنده داریم که هر کدام مقدار i ام و j ام را مقایسه می‌کند و اگر اولی کمتر بود درایه‌ی متناظر آن را صفر می‌کند. عنصری که درایه‌ی متناظر آن ۱ است جواب است. می‌توانیم فرض کنیم مرحله بعد n پردازنده بیت متناظر را می‌خوانند و اگر ۱ بود جواب را در محل جواب می‌نویسند. که کل این کار O(1) زمان می‌برد.

سوال بعدی در مورد این بود که الگوریتمی داده شده بود و قرار بود ثابت کنیم 2n/p عنصر حداکثر عناصر هر پردازنده خواهد بود. دلیل آن این است که هر کدام از جداکننده‌های اولیه n/p2 عنصر را جدا می‌کردند و می‌دانیم در بدترین حالت می‌تواند جداکننده نهایی طوری با بقیه اختلاف داشته باشد که قبل از میانه بعدی باشد اما همه‌ی عددهای بین را شامل شود. در این حالت p*n/p2 عنصر بیشتر از کران پایین (که n/p است) داریم پس حداکثر تعداد عناصر 2n/p می‌شود.

حل دوم سوال ۱ میان ترم هندسه پیشرفته

کران مثلث متساوی الاضلاع محاط در دایره برای مساحت مثلث ضریب تقریب از مرتبه‌ی نسبت قطر به عرض نقاط است. حالتی را در نظر بگیرید که r فاصله‌ی کمی با pq داشته باشد. در این صورت مساحت مثلث به دلیل کم بودن عرض کم خواهد شد ولی مساحت مثلث متساوی الاضلاع فقط تابعی از شعاع دایره (تقریبی از قطر نقاط) است.

هندسه ترکیبیاتی

*مسأله‌ی سیلوستر: تعدادی نقطه در صفحه داریم می‌شود همیشه خطی پیدا کرد که دقیقاً از ۲ تا نقطه بگذرد؟ (فرض کنید همه روی یک خط نیستند)

بله، اثبات: برهان خلف:

به ازای هر سه نقطه غیر هم خط فاصله‌ی یکی را از دو نقطه‌ی دیگر در نظر می‌گیریم و مینیمم این مجموعه را نقطه r و پاره‌خط pq می‌نامیم. نقطه‌ی دیگری که روی خط گذرنده از p و q است را s می‌نامیم. (چون می‌دانیم هر خطی طبق فرض خلف از دقیقاً دو نقطه نمی‌گذرد و اینجا p و q روی خط هستند پس از حداقل ۳ نقطه می‌گذرد.)

اگر پای عمود رسم شده از r روی pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از rs کمتر از فاصله‌ی مینیمم است که این تناقض است.

اگر پای عمود رسم شده از r بیرون pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از خط گذرنده از r و نقطه‌ی دورتر به s کمتر از فاصله‌ی مینیمم است که تناقض است.

*مسأله‌ی هاپکرافت: n نقطه و n خط داریم، حداکثر تعداد incidence ها چندتا است؟ (یعنی نقطه روی خط بیفتد و اگر یک نقطه روی تقاطع چند خط باشد چند بار شمرده می‌شود.)

کران ساده: خطوط را به m دسته‌ی n/m تایی تقسیم کنیم و در هر کدام می‌دانیم تعداد تقاطع‌ها حداکثر تعداد خط‌ها به توان ۲ است. از اینجا m طوری به دست می‌آید که O(n^3/2) وقوع (incidence) داریم. از روی جمع درجات=تعداد یالها*۲ می‌فهمیم چون هر وقوع معادل عبور یک خط از یک نقطه است که درجه آن نقطه را ۲ تا زیاد می‌کند.

کران بهتر:

O(n+x) که x تعداد تقاطع‌ها است. طبق crossing lemma (لم تقاطع)‌ تعداد یالهای O(n+n^2/3 x^1/3) است. با جایگذاری O(n^4/3) به دست می‌آید.

*مسأله‌ی اردوش: n نقطه داریم چند تا فاصله‌شان از هم دقیقاً ۱ است؟

دور هر نقطه دایره به شعاع ۱ می‌زنیم. همان اثبات مسأله‌ی هاپکرافت را می‌توانیم برای این مسأله به کار ببریم چون از خط بودن هیچ استفاده‌ای نکرده‌ایم.

استراتژی‌های حل مسأله

دیدم کتابش را برداشتم گفتم حالا چند مورد را از روی کتاب بگویم اتفاقی نمی‌افتد... :) این‌ها بیشتر قسمت‌هایی است که خودم دوست داشتم! :)

نزول نامتناهی: ایده مربوط به زمان فیثاغورث است که میگه اگر فرض کنیم یک مسأله در اعداد طبیعی جواب داشته باشه و از روی این جواب بشه نتیجه گرفت برای اعداد کوچکتری هم مسأله در اعداد طبیعی جواب دارد یعنی کلاً جواب ندارد چون اعداد طبیعی از پائین کران‌دار اند! :) یک جوری مثل شهود استقرا توی یه حالت خاصه ولی فکر کنم اون موقع هنوز استقرا نیومده بوده! :)

ناوردایی: مسأله مشخصاتی داره که با یک عمل ثابت می‌مونه. برای حل مسأله دو جور میشه از این استفاده کرد یکی اینکه بگیم ویژگی توی حالت‌های مجاز مسأله هست که توی حالت جواب نیست پس هیچ وقت به جواب نمی‌رسه. حالت دیگه اینه که بگیم مثلاً رشد تابع هدف مسأله ثابته. اگر مسأله هدفش یک تابع صعودی /نزولی باشه یعنی هر بار مقدارش زیاد/کم بشه. مثلاً تابع هدف میتونه تعداد حالت‌های مسأله باشه که محدوده یا هزینه‌ی مسأله باشه که کرانداره چون همه‌اش داره کم/زیاد میشه حداکثر به اندازه‌ی تعداد حالت‌ها (کران) تقسیم بر تغییری که هر بار میکنه تکرار برای رسیدن به جواب لازمه.

http://en.wikipedia.org/wiki/Invariant_(mathematics)

نظریه بازی‌ها: حالت‌های مسأله به دو دسته‌ی برد و باخت تقسیم می‌شوند که با یک گراف میشه نشون داد که با هر حرکت مثلاً از مجموعه برد به باخت میریم یا توی برد می‌مونیم. شبیه اتوماتاست بیشتر به نظرم (از این نظر که روی گرافش داریم می‌نویسیم که چه کاری باید انجام بشه).

رنگ‌آمیزی: من قبلاً با این مسأله حل کردم توی همین وبلاگ ولی اشاره به اسمش نکردم. یک سری ویژگی توی مسأله هستند که هر کدام را با یک رنگ مشخص می‌کنیم و بعد وقتی مسأله را حل می‌کنیم می‌توانیم با نگه داشتن هزینه‌ی هر کدام از رنگ‌ها (ویژگی‌ها) بدانیم اوضاع چطوریه! :) این را با اسم پارامتر ثابت می‌شناسند که هر کدام از رنگ‌ها یک پارامتر اند و تعداد اشیای هر رنگ مقدار آن پارامتر است.

*حالا اینها شاید خیلی هم درست نباشن و ادامه هم می‌دونم دارن ولی حالا دیگه این چیزی بود که من بلد بودم.