وبلاگ سمیه!

درس های موازی و تقریبی را دارد!

mycourse.blog.ir

هسته سریع برای مدل جویبار داده (تیموتی چان)

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/eugene_faster_core-set_winter.pdf

جلسه پنجم

مدل جویبار داده (Streaming Model)

تعریف: یک الگوریتم stream الگوریتمی است که ورودی را در یک عبور (pass) می بیند و حافظه محدود دارد. {بهتر است بگوییم جویبار داده نامحدود است!}

*حل مساله قطر با جویبار داده

الگوریتم دقیق:

برای یک بعد: با محاسبه مینیمم و ماکسیمم با O(1) حافظه به دست می آید و با یک pass انجام پذیر است.

برای دو بعد: حداقل به اندازه ی تعداد نقاط حافظه نیاز داریم چون ممکن است نقطه ای که آن را حذف می کنیم (هر نقطه ای!) در آینده یکی از دو نقظه ی مرزی در محاسبه قطر نقاط باشد.

پس برای بیشتر از یک بعد نمی توانیم الگوریتم جویبار داده ی دقیق بدهیم.

الگوریتم تقریبی:

روش 0 (پیدا کردن دورترین نقطه از یک نقطه): O(1) حافظه می خواهد و در یک عبور امکان پذیر است.

روش 1 (پیدا کردن دورترین نقطه از یک نقطه و دورترین نقطه از آن): به دو عبور نیاز دارد. (نمی شود)

روش 2 (توری): نمی شود چون برای به دست آوردن تقریب اندازه خانه های توری (که گفتیم با یکی از الگوریتم های قبلی انجام می شود) به 2 عبور نیاز خواهد داشت.

روش 3 (رند کردن نقاط در جهت های مختلف): می شود چون بیشتر از یک عبور نیاز نداریم. حافظه ی O(1/epsilon^((d-1)/2)) می خواهد.

* مزیت الگوریتم 0 این است که در ابعاد بالا هم کار می کند، اما الگوریتم 3 نمایی است.

---------------------------------

*آیا می توان مساله نزدیک ترین دو نقطه را در مدل جویبار داده حل کرد؟ خیر، حتی نمی توان تقریب زد.

*آیا می توان مساله عرض نقاط را با این حل کرد؟ بله، با همان coreset گستره نقاط (extent)

*محاسبه عرض نقاط

الگوریتم 1: یک epsilon-هسته از نوع گستره نقاط پیدا کن

ایده: ادغام و کاهش (به آن روش لگاریتمی هم می گویند.)

اضافه کردن نقطه:

1) یک هسته شامل مجموعه تک عضوی {p} بساز. (سطح 0)

2) تا وقتی 2 هسته ی S1 و S2 به ترتیب برای مجموعه نقاط P1 و P2 وجود دارند و در یک سطح هستند:

2-1) اپسیلون هسته ی S که اجتماع S1 و S2 است محاسبه کن.

2-2) S را به عنوان هسته ی P1 U P2 در سطح i برچسب بزن. {حس می کنم اینجا باید i+1 باشه!}

2-3) S1 و S2 را حذف کن.

{جواب هم باید هسته ای باشه که در مرحله ی آخر =بالاترین سطح درخت باقی می ماند.}

دلیل نام گذاری این است که مجموعه نقاط هم سطح را ادغام می کند و وقتی برای سطح بالاتر هسته ساخت هسته های سطح پایین تر را حذف می کند.

{البته فکر کنم کاهش منظور همان ساختن هسته و کاهش نقاط است.}

تحلیل

تعداد سطح ها: O(log n)

فضای لازم: O(1/epsilon^d lg n) (اصطلاحاً polylog( n))

زمان: O(1/epsilon^d n)

( ضریب 1/epsilon^d از اندازه ی هسته می آید. lg n از عمق درخت. n از تعداد ادغام ها= کل گره های درخت)

دلیل حفظ ضریب تقریب هسته (هنگامی که دو هسته ادغام می شود) این است که هسته های قبلی نقاط مجزا داشته اند:

*اگر S1 یک اپسیلون-هسته برای P1 و S2 یک اپسیلون-هسته برای P2 باشد، S1 U S2 یک اپسیلون-هسته برای P1 U P2 است.

*اگر S یک اپسیلون-هسته برای Q باشد و Q یک اپسیلون پریم-هسته برای P باشد، آنگاه S یک (اپسیلون+اپسیلون پریم) - هسته برای P است.

(چون ضریب تقریب های آنها جمع می شود.)

در کل یک O(epsilon* log n)-هسته به دست می آید. اپسیلون را طوری تعیین می کنیم که log n حذف شود:

epsilon' = epsilon/lg n

و با این اپسیلون جدید هسته ها را به دست می آوریم.

فضای کل لازم O( 1/epsilon^(d-1) log^d n) است.

این مدل برای جویبار داده قابل استفاده هست اما می خواهیم مستقل از n کنیم.

تمرین های فصل 1.2 لیتون

23- نشان دهید چطور الگوریتم جمع carry-lookahead را تغییر دهیم تا یک عدد N بیتی را از یک عدد دیگر در زمان 2logN+2 قدم بیتی کم کند. می توانید از مکمل 2 استفاده کنید اما خروجی باید با فرمت ورودی باشد.

خود carry look ahead :

برای اینکه فرمت ورودی به هم نخورد، عملگر را از اول تعریف می کنیم:

1-1 = 0 , 0-0 = 0 ==> propagate (p)

0-1=1, carry(-1) ==> generate (g)

1-0 = 1 ==> stop (s)

بقیه مراحل الگوریتم مثل قبل است.

24- یک درخت دودویی کامل N-برگی داده شده است که هر برگ حافظه O(log N) بیتی دارد. نشان دهید چطور دو عدد N log N بیتی را روی این درخت با O( log N) قدم بیتی جمع کنیم. کارایی این الگوریتم چقدر است؟

تعداد برگها N/2 است پس در هر برگ log N/(N/2) = 2 log N بیت از جواب قرار می گیرد. carry ایجاد شده در هر برگ مثل سوال قبل محاسبه می شود.

E = T_best_serial/W_parallel = N log N / (log N * N) = 1

25- نشان دهید چطور یک الگوریتم موازی پیشوندی (parallel prefix) را روی یک درخت سه تایی انجام دهیم. تعمیم الگوریتم برای درخت d-تایی چطور خواهد بود؟ (d>3)

در هر گره باید به صورت سریال عملیات را روی فرزندان انجام بدهیم. عمق درخت لگاریتم در مبنای d خواهد شد ولی زمان محاسبه سریال d عنصر هم در زمان ضرب می شود که در کل همان مرتبه لگاریتمی است.

26- چقدر طول می کشد که دو عدد N بیتی را روی یک آرایه sqrt(N)*sqrt(N) ضرب کنیم؟

با روش مارپیچی (که سطرهای زوج را صعودی و سطرهای فرد را نزولی مرتب می کردیم و بعد ستونها را صعودی مرتب می کردیم و تکرار) بار اول نصف کمتر و بیشتر اعداد مشخص می شد و همین کار تکرار می شد. کلا log (sqrt(N)) = O(log N) بار تکرار لازم است هر بار یک مرتب کردن هم داریم که O(sqrt(N)) طول می کشد پس کلاً O(sqrt(N) log(N)) زمان می خواهد.

27- الگوریتم پیشوندی موازی (parallel prefix) قسمت 1.2.2 را تغییر دهید تا پسوند حساب کند.

فاز اول تغییری نمی کند، فاز دوم را به جای اینکه سمت چپ ترین مسیر را به همه ی زیر درخت های سمت راست بفرستیم، سمت راست ترین مسیر را به همه ی زیردرخت های چپ می فرستیم.

شکل پیشوندی: (آخرین شکل: هر گره از بالا پسوند سمت راستی را می گیرد و مقدار خودش را به اول آن اضافه می کند.)

28- مساله توزیع داده شامل توزیع مقدار مشخصی داده بین مجموعه ای از پردازنده ها است. به ما مقدار عمق درخت دودویی (D) و m مقدار v1,...,vm داده شده است. هر برگ درخت یا شامل یک درخواست ri برای مقدار i-ام است یا خود مقدار v_i. به علاوه ما فرض می کنیم همه درخواستهای مقدار i بلافاصله بعد از خود مقدار i آمده اند. مثلا در شکل 1-119. مساله توزیع vi به هر برگ متقاضی آن است. نشان دهید چطور این کار در O(D) گام ممکن است، اگر در ابتدای کار ندانیم کدام برگ ها درخواست اند و کدام برگ ها مقادیر هستند.

(راهنمایی: از پیشوند موازی استفاده کنید.)

(الآن به ذهنم رسید یک سری از حل های قبلی باید غلط باشند چون من بیشتر از یک داده از یک لینک رد می کردم!!)

اول کران پایین را برای این مساله حساب می کنیم:

bisection width = 2 ==> lower_bound1 = 2m/2 = O(2*2^d/2) = O(2^d)

diameter = 2d ==> lower_bound2 = 2d

==> lower bound = max(m,2d)

به ازای d>5 مقدار کران پایین مساله برای درخت دودویی کامل از O(d) که سوال خواسته است بیشتر می شود. پس با عملیات کلمه ای این مساله حل نمی شود.

باید از ایده ای مشابه مرتب سازی استفاده کنیم، در آنجا کاری که می کردیم به این کار خیلی شبیه بود، فقط از اول جای نهایی اعداد را می دانستیم که اینجا می توانیم آن را با عملیات پیشوندی موازی به صورت بیتی به دست بیاوریم. یک عدد m بیتی بگیریم که هر بیت آن بودن یک درخواست را نشان می دهد و برای محاسبه ی مقدار ریشه آن را or کنیم. در هر زیردرختی فقط مقداری را می فرستیم که درخواست شده باشد و این کار را هم به صورت بیتی انجام می دهیم. ؟؟ یادم نیست در مرتب سازی چطور اعداد را جا به جا می کردیم؟!

29- دو مساله پیشوندی با N ورودی داده شده اند، نشان دهید چطور آنها می توانند به صورت یک مساله پیشوندی موازی (اما پیچیده تر) حل شوند.

هر بار در هر پردازنده دو تا مقدار نگه داریم که هر کدام مربوط به یکی از مسائل است.

30- نشان دهید چطور مقایسه دو عدد N بیتی می تواند توسط محاسبه پیشوندی موازی انجام شود.

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

31- نشان دهید که الگوریتم دو مرحله ای زیر پیشوندها را روی درخت دودویی حساب می کند. در ورودی i-امین برگ xi را ذخیره می کند. در فاز حرکت به سمت بالا هر گره میانه مقدار فرزند چپ خود را ذخیره می کند و concat مقادیر فرزندانش را به پدرش می فرستد. در فاز حرکت به سمت پایین هر گره میانی مقداری که از پدرش دریافت کرده به فرزند چپش می فرستد و concat مقدار پدرش را با مقدار خودش را به فرزند راستش می فرستد. (شکل 1-120)

ارائه خودم (به زودی!)

قرار بود در مورد LSH ارائه بدهم، سری قبل انقدر نمره کم گرفته بودم که اصلا دلم نمی خواد برم ارائه بدم حتی! ترجیح می دهم همینجا بگذارمش.

دریافت
حجم: 1.22 مگابایت

تمرین های لایتون - 1.1

1- اگر کار یک الگوریتم T-مرحله ای را به صورت N1+...+NT که Ni تعداد پردازنده های به کار رفته در مرحله i هستند تعریف کنیم، چقدر کار توسط فاز 1 الگوریتم مرتب سازی آرایه خطی با N پردازنده (قسمت 1.1.1 کتاب) مصرف شده است؟ نتیجه چقدر فرق می کند اگر از تعریف استاندارد W=PT برای کار استفاده کنیم؟

حل:

1+2+2+3+...+N+N=2*(1+...+N)-1 = N(N+1)-1 = N^2+N-1

W=PT=N*(2N-1) = 2N^2-N

difference: 2N^2-N-N^2-N+1=N^2-2N+1=(N-1)^2

2- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. کدام الگوریتم کاراتر است؟ فرض کنید که هزینه استفاده از ماشین P-پردازنده ای برای T گام، T^aP^b است که a و b ثابت هستند و P=M یا P=M^2 است. برای کدام مقادیر a و b الگوریتم اول برای استفاده ارزان تر است؟ برای کدام مقادیر a و b الگوریتم دوم ارزان تر است؟

efficiency = time_best_sequential/work_parallel = time_best_sequential/(T*P) = S/P

S = time_best_sequential/time_parallel

---------

T_best=time best sequential

E1 = T_best/(M*M)

E2 = T_best/(sqrt(M)*M^2)

E2 < E1

پس الگوریتم اول کاراتر است.

cost1 = M^a*M^b = M^(a+b)

cost2 = sqrt(M)^a*M^2b = M^(a/2+2b)

cost1 <= cost2 ==> a+b <= a/2+2b ==> a/2 <= b

پس اگر a<=2b باشد ماشین اول ارزانتر است و در غیر این صورت ماشین دوم. (حالت a=2b مساویند.)

3- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. کدام الگوریتم روی یک ماشین N-پردازنده ای سریعتر اجرا می شود؟ (راهنمایی: جواب شما به اندازه نسبی N و M بستگی دارد و باید از این حقیقت استفاده کنید که یک ماشین N-پردازنده ای می تواند کار یک ماشین P-پردازنده ای را شبیه سازی کند و سرعت P/N برابر می شود).

اگر N<M باشد می توانیم برنامه اول را روی ماشین N-پردازنده ای اجرای کنیم و سرعت به این صورت خواهد شد:

S = T_best_seq/M ==> S' = N/M*S = N/M*t_best_seq/M = N*t_best_seq/M^2

اگر N < M^2 باشد می توانیم برنامه دوم را روی ماشین N-پردازنده ای اجرا کنیم و سرعت به این صورت خواهد شد:

S = T_best_seq/sqrt(M) ==> S'=N/M^2*t_best_seq/sqrt(M) = N*t_best_seq/(M^2*sqrt(M))

پس جواب:

اگر N<M: الگوریتم اول بهتر است چون speed up بیشتری دارد.

اگر M<N<M*sqrt(M): الگوریتم اول بهتر است چون 

S1=M*t_best_seq/M^2 = t_best_seq/M

S2 <= M*sqrt(M)*t_best_seq/(M^2*sqrt(M)) = t_best_seq/M = S1

اگر M*sqrt(M) <N<M^2: الگوریتم دوم بهتر است چون

S2 >= M*sqrt(M)*t_best_seq/(M^2*sqrt(M)) = t_best_seq/M = S1

اگر M^2 < N: الگوریتم دوم بهتر است چون

S2 = M^2*t_best_seq/(M^2*sqrt(M)) = t_best_seq/sqrt(M)

4- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. اگر نیاز داشته باشیم الگوریتم X بار اجرا شود و یک ماشین N-پردازنده ای داشته باشیم. روی مقادیر X و M و N شرط بگذارید و مشخص کنید کدام بهتر است؟

Time = S*T*X

T1 = M

T2 = sqrt(M)

پس جواب:

اگر N < M باشد، الگوریتم دوم زمان کمتری دارد.

Time1 = N*t_best_seq/M^2 * M = N*t_best_seq/M

Time2 = N*t_best_seq/(M^2*sqrt(M)) * sqrt(M) = N*t_best_seq/M^2

اگر M<N<M^2): الگوریتم دوم چون زمان کمتری دارد.

Time1 = t_best_seq/M * M = t_best_seq

Time2 = N*t_best_seq/(M^2*sqrt(M)) * sqrt(M) = N*t_best_seq/M^2 < t_best_seq

اگر M^2 < N باشد، هر دو مثل هم کار می کنند.

Time1 = t_best_seq/M * M = t_best_seq

Time2 = t_best_seq/sqrt(M) * sqrt(M) = t_best_seq

کلا مقدار X تاثیری ندارد.

5- چه چیزهای دیگری ممکن است باعث شوند در طراحی الگوریتم موازی سرعت مهمتر از کارایی باشد؟ (راهنمایی: فرض کنید اندازه باتری یک موشک را دارید با الگوریتم موازی کنترل می کنید.)

کاربردهای real time

6- الگوریتمی برای مرتب کردن N عدد روی مدل آرایه خطی با P پردازنده با کارایی teta( log N / N) بدهید (برای P < N) با استفاده از روشی که در قسمت 1.1.1 گفته شد.

E = T_best_serial / work_parallel = T_best_serial / T_parallel * P = log N / N

T_best_serial = N log N

==> T_parallel = N^2 / P = N * N/P

یعنی همان الگوریتم 1.1.1 را با همان روشی که گفته شد (که N/P پردازنده کار هر پردازنده را انجام بدهند) جواب می دهد. برای این کار هر پردازنده حافظه ای به اندازه N/P عدد دارد و هر کدام عملیات N/P پردازنده متوالی از مدل اولیه را انجام می دهند، که اینجا می شود مرتب کردن N/P عدد متوالی.

7- الگوریتمی برای مرتب کردن N عدد روی یک درخت دودویی کامل با O(log N) پردازنده بدهید که کارایی آن teta(1) باشد. (می توانید فرض کنید که هر پردازنده می تواند O(N/ log N) عدد را نگه دارد و می توانید از این حقیقت استفاده کنید که یک مرتب کننده ترتیبی (معمولی، غیر موازی) می تواند M عدد را در O(M log M) مرحله مرتب کند. می توانید در هر گره ای هم ورودی/خروجی داشته باشید.)

E = N log N / (T_parallel * log N) = 1 ==> T_parallel = O(N)

مشابه روشی که برای مرتب کردن بیت ها انجام دادیم عمل می کنیم. یک درخت دودویی روی اعداد می سازیم و اول پر ارزش ترین بیت را مرتب می کنیم و بعد از بین آنهایی که بیت پر ارزش مساوی دارند، بیت های بعدی را مقایسه می کنیم. برای این کار مشابه کاری که در prefix sum انجام دادیم و یک | اضافه کردیم عمل می کنیم و حاصل عملیات اعداد قبل از فاصله را در نظر نمی گیریم (اینجا یعنی جا به جا نمی کنیم).

کاری که گفته شد به O(N) پردازنده نیاز دارد. ما O(log N) پردازنده داریم. پس می توانیم همین کار را انجام بدهیم، فقط N/log N کاهش سرعت داریم.

N processor version: S = N log N / N = log N

log N processor version: S = N / log N * log N = N

8- (سوال ستاره دار): الگوریتمی برای مرتب کردن N عدد روی یک آرایه خطی O(log N)-پردازنده ای بدهید که کارایی teta(1) داشته باشد.

E = N log N / (T_parallel * log N) ==> T_parallel = N

اگر از درخت استفاده نکنیم و بخواهیم مرتب سازی را به روش سوال قبل انجام بدهیم، می توانیم در مرحله اول بیت های پر ارزشتر را مقایسه کنیم و مرتب سازی انجام بدهیم و در مرحله i-ام بیت های i ام را. این کار O(N) طول می کشد. (چون سمت چپ ترین عدد باید بتواند به سمت راست ترین مکان برسد و در هر مرحله هم حداکثر یک خانه جا به جا می شود).

9- یک مدل ترکیبی موازی/ترتیبی را برای محاسبه در نظر بگیرید که در آن یک آرایه خطی P-پردازنده ای داریم (که هر پردازنده O(1) حافظه محلی دارد) که به یک پردازنده با حافظه ی O(N) وصل است. نشان دهید که برای مرتب کردن N عدد به O( N log N / log P) مرحله نیاز است (با این مدل برای N >= P).

اگر پردازنده های میانی O(N/P) حافظه داشتند می توانستیم همان الگوریتم 1.1.1 را اجرا کنیم و زمان آن همین می شد. از آنجایی که این کار امکان پذیر نیست، چون حافظه های پردازنده های میانی O(1) هستند، باید از حافظه ی پردازنده ی آخر استفاده کنیم. اگر هر پردازنده هر بار ماکسیمم عدد خودش و عدد ورودی را به راست بفرستند (الگوریتم 1.1.1) و در پردازنده ی آخر این اعداد را قرار بدهیم، P عدد بزرگتر در آخرین مکانهای پردازنده آخر و P عدد بعد از آنها در P مکان حافظه ی بعدی هستند و ... . حالا هر دسته از این P عدد را در پردازنده های آرایه خطی می ریزیم و مرتب می کنیم. کل اعداد مرتب می شوند و زمان لازم به صورت زیر خواهد بود:

N+N/P * P = 2N ==> O(N)

10- (ستاره دار): نشان دهید که N عدد k-بیتی را چطور در O(N+k) مرحله روی یک آرایه N*N مرتب کنیم که k می تواند بزرگتر از N باشد.

الگوریتم 1.1.1 جواب می دهد و اگر مقایسه را در نظر نگیریم O(N) است و برای مقایسه ی K بیت هم O(K) در نظر بگیریم، کلا O(Nk) می شود. به جای این کار یک bit mask درست می کنیم که در سطر i-ام k/N بیت i-ام را مقایسه کند و به ردیف پایین اعلام می کند که عدد را به پردازنده سمت راستش بفرستند. زمان این کار O(k) می شود. با انجام این کار برای N مرحله کل اعداد مرتب می شوند و زمان الگوریتم O(N+k) خواهد شد. 

11- ثابت کنید قطر هر گراف N-راسی که حداکثر درجه ی هر راس آن d است، حداقل (log N) / (log d) است.

قطر = حداکثر عمق bfs

در هر عمق dfs حداکثر d شاخه تولید می شود، پس حداکثر تعداد گره ها N = d^diameter

==> log (N,d) < diameter ==> log N / log d <= diameter

12- از مساله 11 استفاده کنید تا نشان دهید که هر شبکه با اتصالهای ثابت در هر پردازنده، حداقل omega(log N) مرحله برای محاسبه x1#x2#...#xN نیاز دارد که xi ها 0 و 1 اند. (علامت # را xor در نظر بگیرید.)

چون عمل xor بین دو عدد حداکثر محاسبه ای است که انجام می دهیم، d=2 است پس طبق قضیه قبل قطر از log N بیشتر مساوی است و چون قطر کران پایین برای زمان است پس حل مساله Omega(log N) است.

13- یک الگوریتم ساده و یک مدل شبکه برای حل مساله 12 با همان کران بدهید.

مدل درختی و الگوریتم هم xor هر دو عدد را به پدر آنها بدهد.

14- ثابت کنید که عرض دو نیم کننده (bisection width) برای یک توری M * N حداقل min( M,N) است برای هر MوN.

با رسم یک خط عمودی یا افقی، اگر عرض بیشتر بود افقی و اگر طول بیشتر بود عمودی، روی M/2 یا N/2 می توانیم این کار را انجام بدهیم.

15- نشان دهید چطور می توان N عدد k-بیتی را روی یک درخت دودویی کامل بخش 1.1.4 با زمان O(2^k log N) قدم بیتی مرتب کرد؟

نگاه کنید به جواب سوال 7.

16- (ستاره دار): توضیح دهید چرا کران داده شده در مساله 1.15 را نمی توان بهبود داد وقتی k <= 1/2 log n؟

#nodes = O(log N)

max # swaps in a depth = max # numbers in a node = O(2^k)

k <= 1.2 log n ==> 2^k <= sqrt(n) ==> #swaps = O(n)

17- نشان دهید هر الگوریتمی برای مرتب کردن N عدد log N بیتی روی یک درخت دودویی کامل با N برگ حداقل omega(N) قدم بیتی زمان می برد.

اگر اعداد ما به ترتیب عکس مرتب شده باشند و هر دو عدد حداکثر 2 بیت مساوی داشته باشند، به حداقل N قدم نیاز داریم. (مقایسه یا جابه جایی)

18- (ستاره دار): نشان دهید هر الگوریتمی برای مرتب کردن N عدد k بیتی روی درخت دودویی کامل به حداقل omega(kN) قدم بیتی نیاز دارد، اگر k >= (1+epsilon) log N باشد. (برای ثابت مثبت اپسیلون)

مثال سوال 17 را در نظر بگیرید و از اصل لانه کبوتری استفاده کنید. برای تمایز دادن بین اعداد حداقل به k/(log N) عمل نیاز داریم پس کلا زمان kN را حداقل نیاز داریم.

19- (سوال دوستاره دار!): نشان دهید که محاسبه میانه N عدد روی یک درخت دودویی کامل O(log^3 N) مرحله نیاز دارد.

به جای این کار رتبه عنصر را به دست می آوریم. درخت ماکسیمم اعداد را می سازیم. مقدار هر گره میانی را به فرزندان آن می فرستیم و آن فرزندی که مقدارش با مقدار گره پدرش مساوی است، به اعداد زیردرختش می فرستد که رتبه خودشان را به اندازه ی زیر درخت کناری اضافه کنند. (توانی از 2).

در هر گره میانی مقدار مینیمم و ماکسیمم فرزندان آن را نگه می داریم و  مقدار فرزندانی که به گره بالاتر فرستاده شده اند را پاک می کنیم. با این کار دیگر مقدار تکراری نخواهیم داشت. اگر اعداد فرد باشند، عدد مرحله آخر که در ریشه است و اگر زوج باشند میانگین دو عدد مرحله آخر که در ریشه هستند را به عنوان جواب بر می گردانیم. چون در هر گام 2 عدد حذف می شوند، کلا O(log N) گام لازم است.

20- نشان دهید چگونه هر مجموعه ای از N عدد را در  O(N) گام کلمه ای روی یک درخت دودویی کامل با N برگ مرتب کنیم.

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

با این کار رتبه ی اعداد به دست می آید و زمانی که می برد  O(N log N) است.

الگوریتم سوال 19 را اجرا می کنیم ولی در ریشه حافظه ی بیشتری می گیریم و اعداد مراحل قبل را نگه می داریم. اگر نخواهیم حافظه ی بیشتر استفاده کنیم، به هر گره یک حافظه اضافه می کنیم و مقادیر را به جایگاه درست آنها می فرستیم (می توانیم در ریشه یک شمارنده بگذاریم تا رتبه ی هر عنصر و در نتیجه مکان جدید آن را مشخص کند).

21- نشان دهید چطور مجموعه ای از N عدد را در O(N) گام کلمه ای روی هر شبکه درختی با درجه محدود (bounded) مرتب کنیم و فقط از کنترل محلی استفاده کنیم.

الگوریتم سوال قبل را اجرا کنیم. در هر گام حداقل 1 عدد مرتب می شود پس به بیشتر از N گام نیاز نداریم.

22- توضیح دهید که کران سوال 1.21 نمی تواند بهبود داده شود، مهم نیست چه شبکه درختی استفاده شود. (مرتب کردن بسته ها در شبکه)

به دلیل اینکه عرض درخت ثابت است، N/width از مرتبه O(N) خواهد بود.

محاسبه معکوس ماتریس - موازی

*محاسبه معکوس ماتریس پایین مثلثی

تمرین های فصل 5 وزیرانی

1- نشان دهید اگر وزن یالی در نامساوی مثلث صدق نکند، آنگاه مساله k-مرکز نمی تواند تقریبی بهتر از a(n) برای هر تابع a(n) قابل محاسبه داشته باشد.

راهنمایی: از ایده قضیه 3.6 و 5.7 استفاده کنید.

5.7 = dominating set، یالهای گراف 1، یالهای دیگر 2

3.6 = وجود جواب برای مساله: هزینه ی n، عدم وجود جواب: هزینه a(n).n

حل: 

حل دستگاه معادلات - موازی

*حل دستگاه ماتریس پایین مثلثی

مشابه ضرب ماتریس و بردار عمل می کنیم (ماتریس A و بردار x) و حاصل جمع را حساب می کنیم. حالا باید ti را حساب کنیم، چون بین مقادیر دیگر فاصله گذاشتیم بین ti ها هم باید فاصله بگذاریم تا جواب درست به دست بیاید. ؟؟

مراحل این کار را در شکل زیر بهتری می بینید. به ترتیب مقادیر xi محاسبه می شوند و به سمت راست می روند و در درایه های ماتریس سطر بعد ضرب می شوند (و همزمان باز هم به راست می روند تا درایه های بعدی را بسازند) و از مقدار قبلی ti کم می شوند و ti جدید به سمت چپ می رود تا مقدار xi بعدی محاسبه شود.

ضرب ماتریسی موازی

*ضرب ماتریس در بردار

برای ضرب ماتریس در بردار، باید هر سطر آن را در بردار ضرب کنیم. جواب ما یک بردار n بیتی است پس می توانیم با n پردازنده آن را به دست بیاوریم (در هر پردازنده یک درایه ی آن را نگهداری کنیم). مثل قبل عمل جمع ساده است؛ اعمال ضرب لازم برای هر درایه، ضرب هر عدد از بردار در هر عدد از سطر j-ام ماتریس است، (به همان ترتیب خودشان). پس به پردازنده j-ام بردار و سطر j-ام ماتریس وارد می شوند. (مستقل از بقیه پردازنده ها). شکل زیر این کار را نشان می دهد:

* ضرب دو ماتریس

برای ضرب دو ماتریس هر سطر اولی باید در هر ستون دومی ضرب شود و می توانیم ماتریس دوم را به صورت n تا بردار در نظر بگیریم و همان روش ضرب ماتریس در بردار را روی آنها انجام دهیم.

* ضرب ماتریس و بردار با مدل حلقه

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

* ضرب دو ماتریس در مدل حلقه

از ضرب ماتریس و بردار در حلقه استفاده می کنیم و هر ستون ماتریس دوم را مثل یک بردار می گیریم.

*کلا ایده ی اصلی این است که مقدار هر پردازنده (جواب) را بنویسیم و با توجه به آن سیستم را طراحی کنیم.