هسته سازی(kernelization): الگوریتم‌های پارامتر ثابت

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

هسته‌سازی یک تبدیل چندجمله‌ای است که یک نسخه از مسأله را به یک نسخه‌ی با پارامتر کوچکتر تبدیل می‌کند که اندازه‌ی این نمونه‌ی جدید از تابعی از پارامتر کمتر باشد و جواب آن تغییر نکند. (نسخه‌ی تصمیم گیری مسأله)

*اگر یک الگوریتم قابل کرنل‌سازی باشد، FPT است.

اثبات: نسخه‌ی کوچکتر بر حسب k نمایی است (چون در کرنل خود اندازه مسأله برحسب k نمایی است) پس آن را با brute force (امتحان کردن همه‌ی حالت‌ها) حل می‌کنیم.

*عکس قضیه: هر مسأله‌ی FPT دارای یک الگوریتم کرنل‌سازی است.

اثبات: حالت بندی می‌کنیم. اگر f(k)<n باشد، که مسأله چندجمله‌ای حل می‌شود و آن را حل می‌کنیم و یک نسخه‌ی بدیهی از مسأله با همان جواب را به عنوان کرنل برمی‌گردانیم.

اگر n<f(k) باشد هم خودش یک کرنل است و خودش را برمی‌گردانیم.

سوالهای پایان ترم داده‌های حجیم

۱- قطر یک درخت که یالهای آن داده شده است را حساب کنید. پیچیدگی I/O الگوریتم شما چقدر است؟
۲- همان سوال محاسبه‌ی عنصر اکثریت وقتی دو تا جویبار داده را به هم بچسبانیم.
۳-در پیمایش Van Emde Boas زمان جستجو را به صورت دقیق حساب کنید و ثابت کنید که 4 log_B N/B در بدترین حالت می‌شود و در حالت متوسط 2 log_B N/B می‌شود.
۴- همان سوال نمونه سوالها که گفته بود رنگ یک مولفه همبندی را تغییر بدهید.

نمونه سوال گراف در مدل I/O (داده‌های حجیم)

http://www.cs.au.dk/~gerth/io10graph/assignment.pdf

سوالات از: Norbert Zeh

نمونه سوالهای ناآگاه از کش (الگوریتم‌های داده‌های حجیم)

این بیشتر از نظر سوال اولش برایم جالب بود. چرا زمان گفته اصلاً؟

http://jeffe.cs.illinois.edu/teaching/473/hw3final.pdf

بقیه:

https://algo2.iti.kit.edu/download/homework1.pdf

http://www3.cs.stonybrook.edu/~rezaul/Spring-2013/CSE638/CSE638-hw3.pdf

نمونه سوال پایان ترم داده‌های حجیم

http://www.win.tue.nl/~hermanh/teaching/2IL35/homework.pdf

حلش هم می‌کنم به زودی. فقط اگر در حل‌ها اشکال بود کامنت بگذارید!

سوالات مدل ناآگاه از کش (داده‌های حجیم)

۱- برعکس کردن یک آرایه بدون حافظه‌ی اضافی (حافظه O(1))

جواب: از دو طرف scan می‌کنیم و به جای هم می‌نویسیم. (با توجه به اینکه LRU استفاده می‌شود این هم زمانش به اندازه‌ی scan می‌شود.)

۲-درخت بی در مدل ناآگاه از کش: از ترکیب چینش van Emde Boas و استفاده از اشاره‌گر در هر گره ساخته می‌شود. (مشابه فایل مرتب)

زمان حذف و درج در فایل مرتب lg^2 N /B می‌شود که برای درخت بی هم هست فقط زمان جستجوی این log_B N می‌شود. (سرشکن)

۳-هرم در مدل ناآگاه از کش

جواب: مثل روش لگاریتمی و مرتب‌سازی در مدل ناآگاه از کش عمل می‌کنیم. یک سری قیف و یک سری بافر نگه می‌داریم که از نظر سایز هر بار ۲ برابر می‌شوند (نزدیک خروجی کوچکترند) و برای حذف آن مشابه هرم در مدل I/O عمل می‌کنیم.

هزینه‌ی درج و حذف کوچکترین عنصر در آن O(1/B log_{M/B} N/B) است (سرشکن).

۴-لیست پیوندی: فکر کنم این است که لیست‌ها را به زیرلیست‌های r عنصری تقسیم می‌کند و مشابه فایل مرتب (پویا) با آن رفتار می‌کند.

الگوریتم تصادفی شمارش مثلث‌ها (جلسه آخر داده‌های حجیم)

الگوریتم این بود که هر بار یک یال را با احتمال یکنواخت انتخاب می‌کرد و در بقیه‌ی جویبار داده چک می‌کرد که یک مثلث تشکیل می‌دهد یا نه و اگر می‌داد (n-2)|E| برمی‌گرداند.

خب کلاً |E| تا یال داریم و به جز دو سر یال n-2 رأس هستند که می‌توانند با آن تشکیل یک مثلث بدهند. پس به احتمال وجود یک مثلث، مقداری که برمی‌گردد (n-2)|E| است و به احتمال نبودنش صفر است. وقتی که امید ریاضی آن را حساب می‌کنیم، با تعداد مثلث‌ها مساوی می‌شود.

سوالهای مبحث جویباری (داده‌های حجیم)

فصل۲، صفحه ۹:

موضوع: الگوریتم پیدا کردن عنصر با بیشترین تکرار جویباری با یک عبور و حافظه‌ی k

سوال ۱: ثابت کنید که تقریب الگوریتم به جای m/k می‌تواند به (m-m^)/k برسد که m^ مجموع به دست آمده در الگوریتم است.

جواب:

چون m^ بار در شرط حذف نمی‌افتیم، حداکثر تعداد بارهایی که در شرط حذف می‌افتیم m-m^ بار است. چون کل جویبار m تا عنصر داشت و m^ بار هیچ عنصری حذف نشده است. مشابه قبل می‌توانیم بگوییم که حداکثر تعداد بارهایی که از یک عنصر در حافظه مقداری کم شده است (m-m^)/k است.

سوال ۲: فرض کنید الگوریتم را روی دو جویبار s1 و s2 اجرا کنیم و خلاصه‌ی آنها را در شمارنده‌های kتایی نگه داریم. الگوریتم زیر برای ادغام آنها به صورت یک جویبار را در نظر بگیرید:

۱) شمارنده‌ها را ادغام کنید و اگر اعداد متناظر آنها مساوی بودند با هم جمع کنید.

۲)‌اگر بیشتر از k شمارنده هست،

۲-۱) مقدار k+1 امین شمارنده در ترتیب صعودی را c بگیرید.

۲-۲) مقدار c را از همه‌ی شمارنده‌ها کم کنید و مقادیر نامثبت را حذف کنید.

ثابت کنید که خلاصه‌ی به دست آمده برای اتصال جویبارهای s1 و s2 تقریب مشابه قبل می‌دهد.

جواب:

یک شرط لازم دارد که از ابتدا فرکانس عنصر با بیشترین تکرار از (m1+m2)/k بیشتر باشد.

برای ترکیب شمارنده‌ها، چون به ازای هر عنصر، خطای آن جمع می‌شود، خطا برابر است با:

(m1-m1^)/k+(m2-m2^)/k

که چون m=m1+m2 و m1^+m2^>m^ است پس حکم اثبات می‌شود.

---------

فصل ۲ بیشتر سوالهایش از 2-universal hash بود که نمی‌نویسم چون بیشتر تصادفی است. از این الگوریتم هم می‌شود برای همه‌ی توانهای فرکانس‌های اعداد استفاده کرد و حافظه‌اش هم log n است.

در مورد شمارش مثلث‌ها با این روش هم حافظه باز هم log n می‌ماند.

Exact SAT

http://www.cs.umd.edu/~gasarch/TOPICS/sat/SATtalk.pdf

کسی هست که تعداد عبارت‌ها را هم به عنوان پارامتر این مسأله در نظر گرفته باشد؟

http://www.cs.bme.hu/~dmarx/papers/marx-bergen-2013-csp.pdf

شمردن 3-satها

سوالی که برای من پیش آمد این است که چند تا عبارت 3-sat متمایز می‌شود نوشت که با تغییر متغیر به هم تبدیل نشوند؟

و جوابش به صورت خنده‌داری ۲ است که یکی true می‌شود و دیگری false.