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

فصل۲، صفحه ۹:

موضوع: الگوریتم پیدا کردن عنصر با بیشترین تکرار جویباری با یک عبور و حافظه‌ی 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 می‌ماند.