self-reducibility

http://en.wikipedia.org/wiki/Random_self-reducibility

مکانیزم نمره‌دهی

داشتم به این فکر می‌کردم که برای نمره دادن استادها یک مکانیزم طراحی کنیم که یکی پیدا کردم:

http://web.mit.edu/primes/materials/2013/conf/7-1-Kaashoek-Wu.pdf

جدا کردن نقاط با تعداد مساوی به وسیله‌ی خط

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

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

(در تمرین O(n^2) خواسته بود این O(n) است.)

فاصله‌ی نقاط متحرک

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

سوال Convex Hull نقاط متحرک را به خاطر بیاورید. حالا دور هر نقطه یک ناحیه با فاصله‌ی ۱ (نرم بینهایت) از آن رسم کنید. هدف ما تشخیص تقاطع داشتن این ناحیه‌ها با هم است. چون این ناحیه نقاطش نسبت به نقاط ورودی ثابت هستند، می‌توانیم معادله‌ی آنها را بر حسب معادله‌ی این نقطه به دست بیاوریم و به چند تا نمودار متقاطع برسیم. حالا با همان روش قبلی (tournament tree) و جاروب روی محور زمان می‌توانیم جواب مسأله را به دست بیاوریم.

خوشه‌بندی ۲-مرکز

حالت خاص مسأله‌ی خوشه‌بندی k-مرکز است که در آن k=2 است. یعنی می‌خواهیم نقاط را به دو دسته تقسیم کنیم که فاصله‌ی بین مرکز خوشه و نقاط خوشه مینیمم شود.

نتایج:

۱- اگر خوشه‌ها متقاطع باشند، نقاط درون اشتراک خوشه‌ها مهم نیستند، چون توسط دو خوشه پوشیده شده‌اند، باید حتماً به دلیل نقاط دیگر خوشه‌ها متقاطع شده باشند.

۲- همیشه یک خط وجود دارد که به خط المرکزین خوشه‌ها عمود است و آنها را از هم جدا می‌کند. این خط از نقاط تقاطع دو خوشه (در صورت وجود) عبور می‌کند. اگر خوشه‌ها مجزا باشند، خط‌های عمود و غیرعمود زیادی جداکننده هستند.

۳- نقاط مرزی خوشه‌ها ممکن است در هیچ جهتی اکسترمم (ماکسیمم/مینیمم) نقاط نباشند. این اتفاق وقتی می‌افتد که دو خوشه متقاطع باشند و مماسی که از مرکز یکی رسم می‌شود دورتر از نقطه‌ی تقاطع دو دایره محیط دایره دیگر را قطع کند. در این صورت نقاط بین محل تماس مماس بر دایره و محل تقاطع دایره‌ها در هیچ راستایی اکسترمم نقاط نیستند. در واقع هیچ کدام از نقاط بین مماس مشترک‌های داخلی نقاط اکسترمم نیستند (چون نقطه‌ای روی محیط دایره‌ی دیگر هست که اکسترمم است) اما چون طبق ۱ نقاط اشتراک مهم نیستند، فقط این قسمت باقی می‌ماند.

۴- برای حل مشکل ۳ می‌شود توری جهتی ساخت و در هر سطر/ستون/... (بستگی به تعداد بعدها دارد) اکسترمم گرفت. تنها نکته‌ای که باقی می‌ماند این است که نقاط یک دایره ممکن است نقاط دایره‌ی دیگر را حذف کنند. برای حل این مشکل می‌شود در خانه‌های توری که بیشتر از یک نقطه دارند و به عنوان اکسترمم شناخته شده‌اند، نقاط اکسترمم درون آن (پوسته محدب) را برداریم.

۵- این کار برای شکل‌های دایره‌ای (خوشه دایره‌ای) بهترین راه حل نیست، اما می‌توانیم از آن برای شکل‌های دیگر استفاده کنیم. فقط باید بتوانیم مشابه اینها را برای آن ثابت کنیم.

۶- این کار برای بیشتر از ۲ دایره ممکن نیست. چون مثلاً حالتی که سه دایره متقاطع داشته باشیم که اشتراک سه تای آنها با هم تهی باشد، نقاط وسط سه دایره (خارج از دایره ها و بین نقاط تقاطع) نقاط مهمی در شکل خوشه (شعاع خوشه) هستند، در حالی که حذف می‌شوند.

مرجع: موضوع اولی بود که قرار بود برای پروژه‌ام انتخاب کنم!

تعمیم parity

صورت سوال این بود که می‌خواهیم یک سری داده را به تعدادی بلوک تقسیم کنیم، طوری که تعداد بلوک‌های لازم برای بازسازی آن مینیمم شود.

مثال: عبارت parity بر حسب بلوک‌های زیر باشد: (در این صورت از بین ۱۰ تا بلوک موجود، با ساختن ۵ تا عبارت می‌شود بازسازی هر کدام را انجام داد.)

1 1 - - 1

2 2 - 2 -

3 3 3 - -

4 - 4 4 -

5 - 5 - 5

6 - - 6 6

- 7 7 7 -

- 8 8 - 8

- 9 - 9 9

- - 10 10 10

فرض کنید تعداد بلوکهای ورودی n تا و تعداد بلوکهای عبارت کدشده k تا باشد.

چون هر ترتیب، جایگشت نام بلوک‌های مختلف است که نسبت به هم تقارن دارند چون هیچ بلوکی به دیگری برتری ندارد، پس فقط مهم این است که همه‌ی رشته‌هایی که دارای ۳ تا یک هستند (پس حداکثر ۳ بلوک از بین برود باز هم کار می‌کنند) را پیدا کنیم که کلاً C(k,3) می‌شود و باید تعداد بلوک‌ها کمتر مساوی این مقدار باشد تا جواب بدهد. چون parity باید ۳ جا مقدار را داشته باشد تا بتواند بازسازی را انجام بدهد.

تعمیم آن با جایگزین کردن ۳ با d انجام می‌شود که در این صورت باید n=C(k,d) بلوک بسازیم سپس همه‌ی رشته‌های به طول k و با دقیقاً d تا یک را بسازیم سپس آنها را زیر هم بنویسیم و هر ستون را به عنوان یک رابطه خطی از بلوک‌ها بنویسیم که ۱ بودن معادل حضور بلوک متناظر آن سطر در رابطه‌ی کدشده است.

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

* جالب بود که اکثر بچه‌ها (از جمله خود من!) بار اولی که سوال را شنیدیم به hypergraph فکر کردیم. چون از این نظر که بلوکها چه ارتباطی با هم دارند چنین مدلی به ذهن می‌رسد. در حالی که این مدل کردن بیتی به سادگی مسأله را حل کرد.

* مرجع سوال: Majid Khabbazian دانشگاه آلبرتا

تقسیم کیک بین ۳ نفر

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

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

حل من:

اگر هر فردی که به مقدار ۱/۳ و ۲/۳ می‌رسد اعلام کند و نفر اولی که اعلام می‌کند با A و نفر دومی که اعلام می‌کند با B و فرد دیگر را با C نشان بدهیم، ترتیب‌های مختلف به صورت زیر است:

۱) یک حرف تکرار شود: در این صورت یک نفر ۲/۳ کیک را طی کرده است در حالی که بقیه به ۱/۳شان هم نرسیده‌اند. در این صورت قسمت مورد نظر این فرد را به او می‌دهیم. (شکل اول)

۲) یک حرف با یک فاصله تکرار شود. (شکل دوم). در این صورت یک دور به وجود می‌آید (چون حرف تکراری نداریم). مثلاً ABACBC. در این حالت باید مبدأ را عوض کنیم وگرنه هیچ برشی وجود ندارد و این عوض کردن مبدأ هم به تابع آن بستگی دارد.

۳) ABCABC: کیک را از روی اعلامهای B می‌بریم. فرد A قسمت اول، فرد C قسمت آخر و فرد B قسمت وسط را می‌گیرند.

این قسمت را غلط حل کردم! چون از نظر A قسمت اول از ۱/۳ بیشتر و قسمت آخر از ۱/۳ کمتر است، در نتیجه قسمت دوم می‌تواند از قسمت اول کمتر یا بیشتر باشد. از نظر نفر سوم برعکس است، یعنی قسمت آخر از ۱/۳ بیشتر، قسمت اول از ۱/۳ کمتر است و ممکن است قسمت دوم از همه بزرگتر باشد. در نتیجه در حالتی که A و C هر دو بگویند که قسمت وسط بیشتر از همه است به مشکل برمی‌خورد.

مرجع سوال: ارائه‌ی الگوریتم در مورد cake cutting

string matching

http://www.cadmo.ethz.ch/education/lectures/HS07/acmlab/11_string_matching.pdf

قضیه کوک

مسأله‌ی تصدیق دودویی ان‌پی-کامل است.

http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

کاربردهای شارش شبکه

*matching

(یک یال مجاور هر رأس انتخاب شود)

در حالت دوبخشی می‌توانیم آن را با وصل کردن یک بخش به مبدا و دیگری به مقصد حل کنیم.

الگوریتم‌های تطابق (به جز این موردی که گفتم)

http://www.dis.uniroma1.it/~sankowski/lecture2.pdf

*assignment

(اختصاص دادن کار به ماشین‌ها)

http://www.comp.nus.edu.sg/~rahul/CS3230-12_files/lectures/pearson/07assignment.pdf

http://www.me.utexas.edu/~jensen/models/network/net9.html

*transportation

(رساندن کالا به مشتری)

http://www.me.utexas.edu/~jensen/models/network/net8.html

*جایابی؟ (من مطمئن نبودم این چه مسأله‌ای است!)

http://people.orie.cornell.edu/dpw/techreports/cornell-flow.pdf