نمونه سوال گراف در مدل 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.

رتبه‌بندی لیست (الگوریتم‌های داده‌های حجیم-قسمت ۱)

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

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

حالا برای به دست آوردن مجموعه‌ی مستقل، چون یک لیست است اگر همین طوری حریصانه حساب کنیم، به یک مجموعه‌ی مستقل با n/3 رأس می‌رسیم. برای ساختنش هم کافی است یک فایل بسازیم و هر بار عنصر بعدی (و احتمالاً قبلی؟) هر عنصر را اضافه کنیم. حالا رأس بعدی را که انتخاب می‌کنیم اول چک می‌کنیم در فایل آنهایی که همسایه‌شان قبلاً انتخاب شده نباشد.

T(N) = T(2/3N)+O(Sort(N)) (N>M)

T(N) = N/B (N<= M)

==> T(N) = O(Sort(N))

اسلایدهای ارائه داده‌های حجیم

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