محاسبه وارون ماتریس

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

روش حذفی گاوس

می توان با استفاده از نیمه ی بالایی یک مش مساله را حل کرد. دلیل درستی آن این است که ما برای محاسبه ی xi می خواهیم یک سطر مقدار i-امین عنصر آن ناصفر باشد و مقدار بقیه عناصر آن صفر باشد. به دلیل اینکه به محض اینکه سطر مورد نظر را پیدا کردیم xi را حساب می کنیم، ترتیب عناصر به هم نمی خورد. همچنین برای سطرهای قبلی هم مشکلی پیش نمی آید، چون درایه ی iام آنها خود به خود صفر بوده است و نیازی به اینکه ما آن را صفر کنیم نیست.

فصل 2 WS

* زمانبندی کارهای دارای ددلاین روی یک ماشین

هدف این کار می تواند تمام شدن همه ی کارها در کمترین زمان، کم شدن میانگین زمان انجام کار باشد. ما ساده ترین نسخه را حل می کنیم.

مساله: فرض کنید n کار را می خواهیم روی یک ماشین زمانبندی کنیم که هر ماشین در هر زمان می تواند یک کار را پردازش کند و کار را بعد از شروع آن باید تا اتمام آن ادامه دهد. فرض کنید پردازش کار jام از زمان مشخصی زودتر قابل انجام نباشد (r_j). فرض می کنیم زمانبندی در زمان 0 شروع می شود و هر زمان انجامی مثبت است. به علاوه کار jام یک زمان پایان d_j دارد. اگر کار را در زمان Cj تمام کنیم، دیرکرد آن Lj = Cj-dj است، ما می خواهیم کارها را طوری زمانبندی کنیم که L_max را مینیمم کنیم که L_max ماکسیمم دیرکردها (Lj) ها است.

این مساله NP-hard است. حتی نسخه ی تصمیم گیری اینکه L_max < 0 است (= تصمیم گیری اینکه همه کارها می توانند قبل از زمان مهلتشان تمام شوند) هم strongly np-hard است.

ما در زندگی روزمره مان با یک الگوریتم تقریبی ساده این کار را انجام می دهیم: روی کاری با نزدیک ترین مهلت تمرکز کنید. نشان می دهیم که در شرایط خاصی قابل اثبات است که این کار خوبی است. هرچند همان طور که گفته شد جواب نزدیک بهینه (تقریبی) ندارد. اگر یک الگوریتم تقریبی برای آن بود، برای هر مساله با جواب L_max = 0 راه حل تقریبی مساله در حالت کلی برای آن ضریب تقریب * 0 = 0 پس باید برای مساله تمام شدن همه ی کارها قبل از ددلاین یک راه حل بهینه باشد که ممکن نیست مگر اینکه P=NP. برای حالت هایی که L_max مینیمم در آنها منفی شود، کار سخت تر است. یک حالت ساده ی رخ دادن این مشکل این است که فرض کنیم همه ی زمان های پایانی منفی هستند که باعث می شود جواب همیشه مثبت باشد. برای این حالت یک الگوریتم 2-تقریبی می دهیم.

ابتدا یک کران پایین خوب برای جواب بهینه برای مساله زمانبندی می دهیم. فرض کنید S زیرمجموعه ای از کارها باشد و r(S) را مینیمم r_j ها قرار دهید (زمان شروع ها) و p(S) را جمع pjها (زمان پردازش ها) و d(S) را ماکسیمم dj ها (زمان پایان ها). L* جواب بهینه است.

لم: برای هر زیر مجموعه از کارها داریم:

L*_max >= r(S)+p(S)-d(S)

اثبات:

هر کاری در زودترین زمانی که می تواند برسد r(S) است که اگر همه ی کارها پشت سر هم انجام شوند p(S) طول می کشد پس زمان بیشتر از r(S)+p(S) است که از طرفین d(S) را کم می کنیم. (پایان اثبات)

یک کار j در زمان t مجاز است اگر زمان رسیدن r_j از t کمتر مساوی باشد. الگوریتم زیر را در نظر می گیریم: در هر لحظه که ماشین بیکار است، کار در دسترس بعدی که زودترین ددلاین را دارد شروع کن. به این کار earliest due date (EDD) (زودترین مهلت انجام) می گویند.

قضیه: قانون EDD یک الگوریتم 2-تقریبی برای مساله کمینه کردن ماکسیمم تاخیر (L_max) روی یک ماشین با توجه به زمانهای رسیدن و با فرض مهلت پایان های منفی است. {با فرض اینکه مهلت کارها گذشته باشد.}

اثبات: جواب الگوریتم را در نظر بگیرید. فرض کنید j کاری باشد که L_max به ازای آن رخ می دهد. Lmax = Cj-dj. روی زمان Cj بحث می کنیم: اولین زمانی را پیدا کنید t<= Cj که ماشین به ازای آن در کل بازه ی بسته ی t تا باز Cj در حال کار بوده است. چندین کار می توانسته اند در این زمان پردازش شوند. ما فقط کارهایی را که ماشین به ازای آنها مدتی بیکار نباشد لازم داریم. فرض کنید S مجموعه کارهایی باشد که در بازه ی t بسته تا Cj باز پردازش می شوند. با توجه به نحوه انتخاب t، می دانیم که قبل از t هیچ کدام از این کارها در دسترس نبوده اند ( و حتما یک کار در S در زمان t در دسترس بوده است)؛ پس r(S) = t. به علاوه چون تنها کارهای موجود در S در طول این زمان پردازش می شوند: p(S) = Cj-t=Cj-r(S). پس Cj <= r(S)+p(S).

چون d(S) منفی است پس طبق لم قبل:

L*_max >= r(S)+p(S)-d(S) >= r(S)+p(S) >= Cj

با استفاده از همین لم و در نظر گرفتن مجموعه تک عضوی کار j-ام داریم:

L*_max >= rj+pj-dj >= -dj

از جمع دو نامساوی قبل به دست می آید:

2*L*_max >= Cj-dj

Cj-dj = L_max

==> L_max <= 2*L*_max

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

* زمانبندی کارها روی ماشین های موازی یکسان

نسخه ای از مساله که در آن چند ماشین داریم و هیچ زمان شروعی نداریم، اما هدف ما مینیمم کردن زمانی است که همه ی کارها تمام شوند. فرض کنید n کار باید پردازش شوند، و m ماشین یکسان هستند که به طور موازی کار می کنند و به هر کدام هر کار ممکن است اختصاص داده شود. هر کار باید روی یکی از این ماشینها به مدت pj بدون وقفه اجرا شود و همه ی کارها در زمان 0 در دسترس هستند. هر ماسین می تواند یک کار را در هر زمان انجام دهد. هدف تمام کردن همه ی کارها در زودترین زمان است، یعنی اگر کار j در زمان Cj (با فرض اینکه زمانبندی از 0 شروع شود) تمام شود، می خواهیم C_max را مینیمم کنیم که C_max ماکسیمم C_j ها است. که معمولا makespan یا طول برنامه نامیده می شود. یک دید معادل به مساله، مساله load-balancing است: n چیز داریم که وزن pj دارند و بین m ماشین توزیع شده اند، هدف تخصیص دادن هر چیز به یک ماشین است که ماکسیمم جمع وزن داده شده به یک ماشین را مینیمم کنیم.

این مساله انقدر ساده است که هم جستحو محلی هم حریصانه برای طول برنامه تقریب 2 می دهند.

الگوریتم جستجوی محلی به صورت تغییرات محلی یا حرکت های محلی است که یک جواب ممکن را به یک جواب ممکن دیگر تبدیل می کنند. ساده ترین جستجوی محلی برای این مساله زمانبندی به صورت زیر است: با یک زمانبندی شروع کنید؛ کار j را در نظر بگیرید که آخرین کاری است که تمام می شود، چک کنید که ماشینی وجود دارد که بتوان این کار را به آن داد و زودتر تمام شود. اگر هست، کار j را به آن ماشین بدهید. می توانیم تشخیص دهیم که کار j را به ماشین دیگر منتقل کنیم یا نه، با چک کردن اینکه آیا ماشینی وجود دارد که این کارهایش را زودتر از Cj-pj تمام می کند. {یعنی قبل از شروع کار j توسط ماشین فعلی بیکار شده باشد.} الگوریتم جستجوی محلی این کار را تا زمانی که آخرین کار تمام شده نتواند منتقل شود ادامه می دهد.

برای تحلیل عملکرد این الگوریتم جستجوی محلی، ما ابتدا یک کران پایین روی طول زمانبندی بهینه C*_max می دهیم. چون هر کار باید پردازش شود، داریم:

2.3: C*_max >= max(pi)

از طرف دیگر می دانیم که در کل باید P = sum(pi) واحد پردازش انجام شود و کلا m ماشین داریم. پس میانگین P/m کار به هر ماشین داده می شود، پس ماشینی هست که حداقل به اندازه میانگین کار داشته باشد:

2.4: C*_max >= ( sum(pi) )/m

جوابی که توسط الگوریتم جستجوی محلی تولید شده است را در نظر بگیرید. فرض کنید j کاری باشد که در برنامه نهایی آخرین کاری باشد که انجام می شود؛ پس زمان اتمام کار j یعنی Cj جواب مساله است. چون الگوریتم با کار j-ام پایان یافته است، پس همه ی پردازنده های دیگر باید از شروع زمان (0) تا زمان شروع کار j-ام مشغول باشند. Sj = Cj-pj (زمان شروع کار j). می توانیم زمانبندی را به دو بازه ی زمانی مجزا تقسیم کنیم، یکی از 0 تا شروع j یعنی Sj و دیگری از آن زمان تا پایان کل برنامه. طبق نامساوی 2.3 بازه ی دوم اندازه ی حداکثر C*_max دارد. حالا بازه ی اول را در نظر بگیرید، چون همه ی ماشین ها در این زمان مشغول هستند پس m*Sj زمان کار در این بازه انجام شده است که بدیهی است از کل کاری که باید انجام شود یعنی sum(pi) ها کمتر است. پس:

2.5: Sj <= (sum(pi) / m)

با ترکیب این نامساوی و نامساوی 2.4 به دست می آید:

Sj <= C*_max

پس، طول برنامه قبل از شروع کار j حداکثر C*_max بوده است و طول آن بعد از انجام کار هم همین قدر است، پس طول برنامه ی الگوریتم حداکثر دو برابر جواب بهینه (2C*_max) است.

حالا زمان اجرای این الگوریتم را در نظر بگیرید. این جستجوی محلی این خاصیت را دارد که دنباله ی C_max های تولید شده در آن هیچ گاه نزولی نیست ( می تواند ثابت باشد اما در این صورت تعداد ماشین هایی که به مقدار زمان بیشینه می رسند کاهش می یابد). یک فرض طبیعی این است که وقتی کاری را به یک ماشین دیگر می دهیم، آن را به ماشینی بدهیم که در حال حاضر زودتر از همه کارش را تمام می کند. ما زمان اجرای این نسخه را به جای قبلی به دست می آوریم. فرض کنید C_min زمان اتمام ماشینی باشد که زودتر از همه کارهایش را تمام می کند. یک نتیجه ی تمرکز روی این نسخه این است که C_min هیچ گاه کم نمی شود (و اگر همان قدر بماند، تعداد ماشینهایی که این کمترین مقدار را به دست می آورند کاهش می یابد). در ادامه نشان می دهیم که این نتیجه می دهد که ما هیچ وقت یک کار را دو بار جا به جا نمی کنیم. فرض کنید این ادعا درست نباشد، اولین کار j را که دو بار جا به جا شده است در نظر بگیرید، فرض کنید از ماشین i به ماشین i' و بعد از آن به i*. وقتی کار j از ماشین i به i' منتقل می شود، در زمان Cmin برنامه فعلی شروع می شود. به طور مشابه وقتی کار j از i' به i* منتقل می شود، در زمان C'_min شروع می شود. به علاوه هیچ تغییری روی ماشین i' در بین این دو انتقل رخ نداده اشت. پس C'_min باید اکیدا کمتر از C_min باشد (تا انتقال یک عمل بهبود دهنده باشد) اما این با ادعای C_min در طول اجرای الگوریتم جستجوی محلی غیر نزولی است متناقض است. پس هیچ کاری دو بار منتقل نشده است و بعد از حداکثر n گام، الگوریتم متوقف می شود. پس ما قضیه زیر را ثابت کردیم:

قضیه 2.5: الگوریتم جستجوی محلی برای زمانبندی کارها روی ماشین های موازی یکسان یک الگوریتم 2-تقریبی است.

تحلیل ضریب تقریب می تواند کمی بهبد یابد. در به دست آوردن نامساوی 2.5، کار j را بین کارهایی که قبل از شروع کار j تمام می شوند حساب کرده ایم. پس می توانیم به دست بیاوریم:

Sj <= (sum( pi) -pj) / m

==> total length <= pj+(sum(pi)-pj)/m = (1-1/m)pj+sum(pi) /m

با اعمال دو کران پاینن 2.3 و 2.4 روی دو جمله بالا می توانیم نشان دهیم که طول برنامه حداکثر 

(2-1/m)C*_max

است. البته تفاوت بین این کران و 2 تنها وقتی مهم است که تعداد ماشینها خیلی کم باشد.

-----

الگوریتم طبیعی دیگری که برای محاسبه برنامه است الگوریتم حریصانه ای است که هر کار را به محض اینکه یک ماشین بیکار شد به آن اختصاص می دهد. این الگوریتم معمولا list scheduling algorithm نامیده می شود، چون می توان الگوریتم را به صورت مرتب کردن کارها در یک لیست به ترتیب دلخواه دید که کار بعدی که انجام می شود کار سر لیست است. یک دید دیگر، از دیدگاه load-balancing است که کار بعدی لیست به ماشینی که الآن کمترین بار را دارد اختصاص داده شود. در این حالت است که الگوریتم می تواند به صورت حریصانه دیده شود. تحلیل این الگوریتم اکنون بدیهی است؛ اگر کسی از این برنامه به عنوان نقطه شروع جستجوی محلی استفاده کند، الگوریتم همان موقع اعلام می کند که زمانبندی نمی تواند بهبود داده شود. برای فهمیدن این موضوع، کار j را که یکی از کارهاست که آخرین کاری است که اجرایش تمام می شود، در نظر بگیرید. هر ماشینی تا زمان Cj-pj مشغول است، چون در غیر این صورت به آن کار j را اختصاص می دادیم. پس هیچ انتقالی امکان پذیر نیست.

قضیه 2.6: الگوریتم list scheduling برای مساله کمینه کردن طول برنامه با داشتن m ماشین یکسان موازی 2-تقریبی است.

به دست آوردن نتیجه بهتر با بهبود این الگوریتم سخت نیست. همه ی لیست ها یک برنامه را نمی دهند و طبیعی است که از قانون حریصانه ی اضافی استفاده کنیم که ابتدا کارها را به صورت غیر صعودی مرتب می کند. {نزولی غیر اکید}. یک راه برای دیدن نتیجه قضیه 2.5 و 2.6 این است که خطای نسبی طول برنامه کاملا مربوط به آخرین کار انجام شده است. پس اگر کار کوتاهی انجام شود، خطا خیلی بزرگ نمی شود. این الگوریتم حریصانه longest processing time یا به اختصار LPT نامیده می شود.

قضیه 2.7: LPT یک الگوریتم 4/3-تقریبی برای زمانبندی کارها برای مینمم کردن طول برنامه روی ماشین های موازی یکسان است.

اثبات: برهان خلف: فرض کنید یک ورودی مثال نقضی برای قضیه باشد. برای سادگی نگارش فرض کنید p1>= ...>= pn باشد. ابتدا می توانیم فرض کنیم که آخرین کاری که انجام می شود آخرین (کوتاهترین) کار در لیست است. این نتیجه می دهد (بدون از دست رفتن عمومیت مساله) که هر مثال نقضی که آخرین کار آن کوتاهترین کار نباشد و کار j-ام باشد، می توانیم ثابت کنیم که غلط است، چون کارهای j+1,...,n راحذف می کنیم، طول برنامه همان می ماند و جواب بهینه ورودی کاهش یافته نمی تواند بزرگتر باشد. پس این ورودی کاهش یافته هم یک مثال نقض است.

پس می دانیم که آخرین کاری که کامل می شود کار nام است. اگر این یک مثال نقض باشد، ما در مورد pn=pj چه می دانیم؟ اگر pj <= C*_max باشد، تحلیل قضیه 2.6 نتیجه می دهد که طول برنامه حداکثر (4/3)C*_max است و درنتیجه این یک مثال نقض نیست. پس می دانیم که در این مثال نقض فرضی، کار n ام (و در نتیجه همه کارها) زمان پردازش اکیداً بیشتر از 1/3C*_max دارند. این نتیجه ی ساده ی زیر را دارد:

در زمانبندی بهینه، هر ماشین می تواند حداکثر دو کار را پردازش کند (چون در غیر این صورت زمان پردازش آن از C*_max بیشتر می شود).

اینجا مثال نقض فرض مان به جایی رسیده است که وجود آن امکان پذیر نیست. برای ورودی های دارای این ساختار، لم بعد را به کار می بریم.

لم 2.8: برای هر ورودی مساله مینیمم کردن زمان روی ماشین های موازی یکسان که در آن نیازمندی های هر کار از 1/3 طول زمان مورد نیاز بیشتر است، longest processing time (LPT) جواب بهینه را به دست می آورد.

این لم می تواند با استفاده از چک کردن حالت ها انجام شود (تمرین 2.2). هر چند نتیجه این لم مشخص است: هیچ مثال نقضی برای این قضیه وجود ندارد پس برقرار است.

در قسمت 3.2 نشان می دهیم که می توان برای این مساله الگوریتم تقریبی با زمان چندجمله ای ارائه داد.

وبلاگ سمیه!

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

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) خواهد بود.

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

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