ترجمه تخصصی رشته ریاضی - گراف های تصادفی

گراف های دنیای واقعی

در بحثی مثل بحث بخش 4.2.3 دیدید که تمایز PDEها منجر به مسائل محاسباتی می شود  که جنبه ای از گراف برای آنها دارد. ویژگی های اینگونه گراف ها موجب می شود در معرض مسائل خاصی قرار گیرند. بر ای مثال، استفاده از FDMها یا FEMها برای مدل سازی اشیای دو یا سه بُعدی منجر به گراف هایی می شود که هر گره فقط به چند همسایه متصل است. این امر موجب می شود جدا کننده به راحتی پیدا شود و در نتیجه بکارگیری متدهایی مثل تشریح تو در تور را ممکن می سازد؛ رجوع کنید به بخش 6.9.1.

 

ثبت سفارش ترجمه تخصصی

 

با  این حال اپلیکیشن­هایی وجود دارد که مسائل گرافیکی آنها از نظر محاسباتی دشوار است و شبیه به گراف های FEM نیستند. به طور خلاصه مثالی از وب و الگوریتم هایی مثل PageRank گوگل را بررسی می­کنیم که سعی می کنند گره های معتبر را پیدا کنند.

چنین گراف هایی را گراف تصادفی می­نامیم، اگرجه این عبارت معنای فنی نیز دارد [52].

9.2.1. ویژگی های گراف های تصادفی

ویژگی­های گراف هایی که در بیشتر این دوره دیدیم از این واقعیت ریشه می گیرند که اشیای در دنیای به بعدی را مدل سای می کنند. بنابراین فاصله معمول بین دو گره معمولا O (N^1/3) است که N تعداد گره است. گراف­های تصادفی چنین رفتاری ندارد: آنها غالبا ویژگی دنیای کوچک را  دارند که فاصله معمول در آن O(log N) است. مثالی معروف گراف بازیگران فیلم و ارتباط آنها با حضور در یک فیلم است: طبق "شش  درجه فاصله"، در این گراف فاصله هیچ بازیگری با دیگری بیش از شش نیست.

گراف های  دنیای کوچک ویژگی های دیگری دارند، مثل وجود دسته ها (اگرچه این ویژگی نیز منجر به مسائل FEM مرتبه بالا می شود) و هاب ها: گره های درجه بالا. این امر دلالت­هایی دارد، مثلا: پاک کردن گره تصادفی در چنین گرافی تاثیر زیادی بر کوتاهترین مسیرها ندارد.

تمرین 9.8. با در نظر گرفتن گراف فرودگاه­ها و مسیرهای بین آنها، اگر فقط هاب و غیرهاب ها وجود داشته باشد، نشان دهید که پاک کردن غیرهاب تاثیری بر کوتاهترین مسیر بین فرودگاههای دیگر ندارد. از سوی دیگر، گره هایی را در نظر بگیرید که در شبکه دو بعدی قرار دارند، و گرهی دلخواه را پاک کنید. چند مسیر از کوتاهترین مسیرها تحت تاثیر قرار می گیرد؟

9.2.2. مفاهیم

دو معیار مرکزیت: مرکزیت بردار آیگن و بینابینی بودن. EC پایین و بینابین بودن کار "دروازه بان" را نشان می­دهد.

درجه، قطر، فاصله طبق معمول تعریف می شود.

بینابین بودن عبارت است از

Cv= _s≠t≠v≠s,t بین مسیر کوتاهترین_s≠t≠v≠s,tبین مسیر کوتاهترینv میگذرد از که

 

مرکزیت بردار آیگن اندازه مولفه گره در بردار پرون (Perron) است؛ رجوع کنید به بخش 9.3.

نزدیکی میانگین فاصله گره تا بقیه را تعیین می کند:

ضریب دسته­ بندی میزان سازماندهی گراف در دسته را اندازه می گیرد. ضریب عمومی عبارت است از

≠بسته چندتایی≠باز چندتایی

که در آن چند تایی باز چندتایی i, j, k است به طوریکه

در حالیکه برای چندتایی بسته، رابطه آخر شامل می شود. تعریف محلی براساس این واقعیت است که دسته k گره k(k – 1) / 2 لبه است (در گراف بدون جهت). با تعریف محله گره i به صورت

می توان ضریب دسته بندی محلی را اینگونه تعریف کرد

9.3. الگوریتم­های فرامتنی

چندین الگوریتم براساس جبر خطی برای اندازه گیری اهمیت سایت های وب وجود دارد [111]. به طور خلاصه چند الگوریتم را بررسی می کنیم و دلالت های محاسباتی آنها را بحث می کنیم.

9.3.1. HITS

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

L_ij=1 دارد اشاره j سند به i سند0 غیراینصورت در

نمرات اعتبار x_i به صورت مجموع نمرات هاب y_i هر چیزی که به i اشاره دارد، تعریف می شود، و بالعکس. بنابراین

یا x = LL^tx و y = L^tLy، که نشان می دهد این مسئله مقدار آیگن است. بردار آیگن که نیاز داریم فقط مدخل­های منفی دارد؛ چنین برداری برای ماتریش غیرمنفی بردار پرون نامیده می شود، رجوع کنید به ضمیمه 16.4. بردار پرون با متد توان محاسبه می شود؛ رجوع کنید به 16.3.

استراتژی جستجوی عملی عبارت است از:

• همه اسنادی را که عبارت جستجو دارند، پیدا کنید؛
• زیرگرافی از این اسناد، و یک یا دو سطح در رابطه با آنها ایجاد کنید؛
• نمره اعتبار و هاب در این اسناد را محاسبه کنید آنها را به ترتیبی که در فهرست آمده است به کاربر ارائه دهید.

9.3.2. Page Rank

نظریه اساسی PageRank شبیه به HITS است. بازهم ماتریس اتصال را به اینصورت تعریف می کنیم:

M_ij=1 شود متصل i به j صفحه اگر0                 غیراینصورت در

که در آن e = (1, . . ., 1)، بردار d^t = e^tM تعداد لینک­ها در صفحه را نشان می د هد: d_i تعداد لینک در صفحه i است. ماتریس قطری D = diag(d₁, . . .) را می سازیم، M را به T = MD^-1 به هنجار می کنیم.

حالا مجموع همه ستون­ها (یعنی مجموع المان ها در هر ستون) T برابر 1 است، که می توان به صورت e^tT=e^t بیان کرد که در آن e^t = (1, . . ., 1) است. چنین ماتریسی ماتریس تصادفی نامیده می شود و دلالت های زیر را دارد:

اگر p بردار احتمال باشد، یعنی p_i احتمال نگاه کردن کاربر به صفحه i باشد، در اینصورت T_p بردار احتمال بعد از کلیک کاربر روی لینک تصادفی است.

 

ثبت سفارش ترجمه تخصصی

تمرین 9.9. از نظر ریاضی، مجموع المان های بردار احتمال 1 است. نشان دهید که حاصل ضرب ماتریس تصادفی و بردار احتمال بازهم بردار احتمال است.

حالا الگوریتم PageRank این پرسش را از دیدگاه ریاضی بررسی می کند که "اگر کاربر به کلیک روی لینک­هایی ادامه دهد که از لحاظی مطلوب ترین لینک­ها در صفحه هستند، مجموعه کلی مطلوب ترین لینک ها چه خواهد بود". در اصل این معادل است با در نظر گرفتن بردار تصادفی اختیاری p، محاسبه متد توان T_p, T²_p, T³_p, . . . و بررسی اینکه آیا این توالی با چیزی همگراست یا نه.

با این حال، مسنله کوچکی در این الگوریتم وجود دارد. اگر صفحه لینک بیرون رونده نداشته باشد، کاربر آنجا پایان می­دهد و هرگز (صفحه را) ترک نمی کند. از نظر ریاضی نیز این مسئله پیش می­آید. برای مثال، وب با 2 صفحه و ماتریس مجاورت زیر را در نظر بگیرید:

بررسی کنید که آیا این معادل است با صفحه دوم بدون لینک به بیرون. حالا p را بردار شروع p^t = (1,1) بگیرید، و چند تکرار متد توان را انجام دهید. آیا احتمال بودن کاربر در صفحه دوم تا 1 افزایش می یابد؟ در اینجا مسئله این است که ما با ماتریس کاهشی سر و کار داریم.

برای پیشگیری از این مسئله، PageRank المان دیگری اضافه می کند: گاهی کاربر از کلیک کردن خسته می شود، و به صفحه ای دلخواه می رود (شرایطی نیز برای صفحات بدون لینک به بیرون وجود دارد). اگر s را احتمال کلیک کاربر روی یک لینک بگیریم، در اینصورت احتمال رفتن به صفحه­ای دلخواه 1 – s است. در مجموع فرآیند زیر را داریم،

یعنی اگر p بردار احتمالات باشد، p’ بردار احتمالاتی است که توصیف می کند کاربر بعد از گذر از یک صفحه در کجاست، یا با کلیک روی یک لینک یا با "تلپورت".

 

ترجمه تخصصی رشته ریاضی

 

بردار PageRank نقطه ثابت این فرآیند است؛ می توانید آن را توزیع احتمال بعد از بی­نهایت گذار کاربر در نظر بگیرید. بردار PageRank با رابطه زیر مطابقت دارد،

بنابراین حالا باید بفهمیم که آیا I – sT معکوس دارد یا نه. اگر معکوس وجود داشته باشد، با رابطه زیر مطابقت دارد،

به راحتی می توان دید که معکوس وجود دارد: با قضیه گاوسی (ضمیمه 16.5) می­توان دید که مقادیر آیگن T با |λ| ≤ 1 مطابقت دارد. حالا s < 1 را بکار برید، بنابراین مجموع نسبی همگراست.

فرمول معکوس بالا راهی برای مقایسه بردار PageRank، p با استفاده از یک سری ضرب ماتریس-بردار را نیز نشان می دهد.

تمرین 9.10. با ماتریس T شبه کدی برای محاسبه بردار PageRank بنویسید. نشان د هید که نیازی به محاسبه صریح توان ها نیست. (این نمونه ای از قانون هورنر است).

وقتی s = 1 است، به این معنی است که جابجایی ( تله پورت) را غیرمحتمل می دانیم، بردار PageRank با p= TP مطابقت دارد، که بازهم مسئله یافتن بردار پرون است؛ رجوع کنید به ضمیمه 16.4.

بردار پرون را با تکرار توان پیدا می کنیم (بخش 16.3).

ثبت سفارش ترجمه تخصصی

P⁽ⁱ⁺¹⁾ = Tp⁽ⁱ⁾

این ضرب بردار- ماتیس اسپارس است، اما برخلاف مورد BVP، احتمال نمی رود ساختار اسپارس نواری داشته باشد. از نظر محاسبه، شاید لازم باشد از همان آرگومان های موازی سازی ماتریس متراکم استفاده کنیم: ماتریس باید به صورت دوبُعدی توزیع شود [130].

9.4. تئوری گراف محاسباتی مقیاس بزرگ

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

همانند بخش 6.5، در بسیاری موارد می­توان توزیع تک بعدی ماتریس را انجام داد که ناشی از توزیع گره های گراف است: اگر پردازشگری یک گره i داشته باشد،  همه لبه های i, j را داراست.

با این حال، محاسبه غالبا نامتوازن است. برای مثال، در الگوریتم کوتاهترین مسیر، فقط بردارهای در امتداد جلو فعال هستند. به همین دلیل، گاهی توزیع لبه ها به جای توزیع بردارها بهتر جواب می دهد. برای توزان یکنواخت بار می توان از توزیع تصادفی یکنواخت استفاده کرد.

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

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

یکی از راه­حل­ها این است که ماتریس اسپارس را متراکم در نظر بگیریم، و آرگومان ها از بخش 6.2.2. را برای تصمیم گیری در مورد توزیع دو بُعدی ماتریس بکار گیریم. (برای بکارگیری در مسئله BFS، رجوع کنید به [169]؛ آنها الگوریتم را برحسب گراف تنظیم می کنند، اما ساختار ضرب بردار – ماتریس دو بعدی به روشنی قابل درک است.) الگوریتم ضرب دو بعدی فقط به مشترک­ها در ردیف­ها و ستون­ها نیاز دارد، بنابراین تعداد پردازشگر عبارت است از  O P.

 

 

 

فصل 10

مسائل جسم – N

در فصل 4 پدیده­های پیوسته را بررسی کردیم، مثل رفتار میله گرم در کل بازه [0, 1] در دوره زمانی معین. هم­چنین در برخی کاربردها­ها ممکن است تعداد محدودی نقطه درج شود. یکی از این کاربردها مطالعه مجموعه ذرات است، احتمالا ذرات بسیار بزرگی مثل سیاره ها یا ستارگان تحت تاثیر نیرویی مثل نیروی جاذبه یا نیروی الکتریکی. (ممکن است نیروهای خارجی نیز وجود داشته باشد، که از آنها صرفنظر می کنیم، هم چنین فرض می کنیم که تصادمی وجود ندارد، در غیراینصورت باید فعل و انفعالات نزدیک­ترین همسایه را ادغام کنیم.) این نوع مسائل مسئله جسم – N نامیده می شود؛ برای معرفی رجوع کنید به http://www.scholarpedia.org/article/N-body_simulations_(gravitational)

الگوریتم اساسی چنین مسئله­ای راحت است:

• بازه زمانی کوچکی را انتخاب کنید،
• با داشتن جای همه ذرات، نیروهای وارد بر هر ذره را محاسبه کنید،
• جای هر ذره را طوری جابجا کنید که نیروی وارد بر آن در کل بازه ثابت بماند.

برای بازه زمانی که به اندازه کافی کوچک است این الگوریتم برآوردی با درستی قابل قبول می دهد.

مرحله آخر، یعنی به روزسازی جاهای ذره، آسان و کاملا موازی است: مسئله در ارزیابی نیروهاست. این محاسبه به اندازه کافی ساده است و حتی کاملا موازی است:

برای هر ذره i

برای هر ذره j

r̃_ij را بردار بین i و j بگیرید؛

بنابراین نیروی وارد بر i ناشی از j عبارت است از

(که در آن m_i, m_j جرم یا شارژ است) و

هدف اصلی برای این الگوریتم این است که پیچیدگی محاسباتی کوادراتیک داشته باشد: برای N ذره، تعداد عمل O(N²) است.

شکل 10.1 جمع زدن همه نیروهای وارد بر ذره.

تمرین 10.1. اگر n پردازشگر داشته باشیم، محاسبات برای یک مرحله به روزسازی به زمان O(N) نیاز خواهد داشت. پیچیدگی ارتباط چیست؟ راهنمایی: آیا عملیات مشترک (جمعی) می توانید بکار برید؟

چندین الگوریتم برای بدست آوردن پیچیدگی ترتیبی تا O(N log N) یا حتی O (N) ایجاد شده است. همانطور که انتظار می رود، پیاده سازی این الگوریتم­ها دشوارتر از الگوریتم ساده است. متدی متداول را بررسی می کنیم: الگوریتم بارنز – هانت [5]، که با پیچیدگی O (N log N) است.

10.1 الگوریتم بارنز – هانت

مشاهده اساسی که موجب کاهش پیچیدگی می شود به این ترتیب است. اگر نیروهای وارد بر ذره i₁, i₂ را محاسبه می کنید که نزدیک به هم هستند، و نیروها از دو دره j_i, j₂ می­آید که آنها هم نزدیک به هم هستند، می توانید j₁, j₂  را باهم در یک ذره ادغام کنید و از آن برای هر دوی i₁ , i₂ استفاده کنید.

ثبت سفارش ترجمه تخصصی

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

شکل 10.2. تقسیم مجدد بازگشتی دامنه به کوادرانت­هایی که سطح­شان نشان داده شده است (چپ)؛  تقسیم مجدد یک ذره برای هر باکس (راست).

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

برای هر سطح l، از ریز به درشت:

برای هر سلول c در سطح l:

مجموع جرم و مرکز جرم را محاسبه کنید

برای سلول c با در نظر گرفتن فرزندانش

اگر ذره ای در این سلول نباشد،

جرم آن را صفر بگیرید

سپس سطوح برای محاسبه فعل و انفعال با ذره بکار می رود:

برای هر ذره p:

برای هر سلول c در سطح بالا

اگر c به اندازه کافی از p دور باشد:

از مجموع جرم و مرکز جرم c استفاده کنید؛

در غیراینصورت فرزند c را در نظر بگیرید

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

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

محاسبه مرکز جرم باید هربار بعد از جابجایی ذره انجام گیرد. به روزسازی ممکن است کم هزینه تر از محاسبه از روی رسم باشد. هم چنین ممکن است ذره از مرز سلول عبور کند که در اینصورت ساختار داده ها باید به روز شود. در بدترین حالت، ذره به سلولی می­رودی که معمولا خالی بود.

شکل 10.3. باکس هایی با نسبت فاصله و قطر ثابت.

10.2 متد ضرب سریع

متد ضرب سریع (FFM) عبارتی را برای پتانسیل در هر نقطه محاسبه می کند، و همانندمتد بارنز-هانت نیرو را محاسبه نمی کند. FMM از اطلاعات بیشتری از جرم و مرکز ذرات در باکس استفاده می کند. این گستره پیچیده­تر دقیق­تر هست، هم چنین پرهزینه­تر نیز هست. در مقایسه، FMM از مجموعه ثابتی از باکس­ها برای محاسبه پتانسیل استفاده می کند، به جای اینکه با پارامتر دقت تتا و محل مرکز جرم تغییر کند.

با این حال، FMM از نظر محاسباتی بیشتر شبیه به متد بارنز-هانت است، بنابراین می توان پیاده­سازی آنها را باهم بحث کرد.

10.2. محاسبه کامل

علیرغم متدهای بالا برای برآورد مدبرانه­تر، کارهایی نیز در محاسبه کامل با N² تکرار وجود دارد؛ برای مثال کد NBODY6، Sverre Aresth؛ رجوع کنید به http://www.ast.cam.acu.uk/˜sverre/web/pages/home. چنین کدهایی از انتگرال­گیرهای مرتبه بالا و مراحل زمانی سازگار استفاده می­کنند. اولین پیاده سازی در کامپیوتر Grape وجوددارد؛ موازی­سازی کلی معمولا به خاطر نیازه با توازن بار منظم سخت است.

10.4. پیاده­سازی

متدهای Octree چالش­هایی در ساختارهای با عملکرد بالا بوجود می­آورند. اولا مسئله بی­قاعده است، و دوماً، بی­قاعدگی به صورت پویا تغییر می کند. جنبه دوم بیشتر در حافظه توزیع شده پیش می­آید، و به توازن مجدد بار نیاز دارد؛ رجوع کنید به بخش 2.10.1. در این بخش بر محاسبه نیرو در یک مرحله تمرکز می­کنیم.

10.4.1 برداری سازی

ساختار مسئله­ای مانند شکل 10.2 کاملا بی­قاعده است. این مسئله برداری­سازی در مقیاس کوچک دستورات SSE/AVX و در مقیاس بزرگ مسئله پردازشگر های خط لوله بردار است (رجوع کنید به بخش 2.3.1 برای توضیح درباره هر دو). مراحل برنامه "برای همه فرزندان باکس معین کاری بکن" با طول بی­قاعده خواهد بود، ممکن است داده ها به صورت باقاعده (منظم) ذخیره نشود.

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

ثبت سفارش ترجمه تخصصی

10.4.2. پیاده سازی حافظه مشترک

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

10.4.3. پیاده سازی حافظه توزیع شده

نسخه بالا از الگوریتم بارنز – هانت با حافظه مشترک را نمی توان در زمینه حافظه توزیع شده بکار برد زیرا هر ذره می تواند به اطلاعات هر قسمتی از کل داده ها دسترسی داشته باشد. می­توان با استفاده از درخت هشت تایی درهم یا هش (hashed octree) پیاده سازی الگوریتم را در این راستا انجام داد، اما ما اینکار را نمی­کنیم.

مشاهده می کنیم که دسترسی به داده ها بیش از آنچه که در ابتدا به نظر می رسد، ساختاری است. ذره p و سلول های در سطح l را در نظر بگیرید که با آن فعل و انفعال دارند. ذرات نزدیک به p با سلول های یکسانی فعل و انعفال خواهند داشت، بنابراین می توان با نگاهی به سلول های در سطح l و سلول های دیگر در همان سطح که با آن فعل و انفعال دارند، فعل و انفعال را بازآرایی کرد.

با اینکار الگوریتم زیر بدست می­آید [97]: محاسبه مرکز جرم به محاسبه نیرو g_p^(l) اعمال شده توسط p بر سطح l تبدیل می شود:

برای سطح l از یکی بالاتر از ریزترین تا درشت ترین:

برای هر c در سطح l

g_c ^(l) را ترکیب g_j^{(l +1}) برای همه فرزندان i از c بگیرید

 با این الگوریتم نیروی وارد بر سلول را محاسبه می کنیم:

برای سطح l از یکی بالاتر از درشت ترین تا ریزترین

برای هر سلول c از سطح l:

f_c^(l) را مجموع بگیرید:

 

1. نیروی f_p^(l-1) بر والد p از c، و
2. مجموع g_i^(l) برای همه i در سطح l که

با معیار باز شدن سلول مطابقت دارد

می توان دید که در هر سطح، هر سلول فقط با تعداد اندکی همسایه در آن سطح فعل و انفعال دارد. در نیمه اول الگوریتم با استفاده از روابط فرزند – والد بین سلول­ها از درخت بالا می رویم. احتمالا این کار خیلی آسان است.

نیمه دوم الگوریتم از دسترسی پیچیده تری به داده استفاده می کند. سلول های i در عبارت دوم همگی از سلول c که نیرو را در آن محاسبه می کنیم، فاصله دارند. در عبارات گراف این سلول ها را می توان عموزاده، خاله­زاده توصیف کرد: فرزندان خواهر و برادر والدین c، و غیره.

تمرین 10.2. توضیح دهید که این عمل محاسبه نیرو از نظر ساختاری اشتراک زیادی با ضرب بردار – ماتریس اسپارس دارد.

در مورد حافظه مشترک قبلا تاکید کردیم که زیردرخت های مختلف زمان متفاوتی برای پردازش نیاز دارند، اما از انجا که ممکن است تعداد کارها بیشتر از هسته­های پردازشگر باشد، باید بار را به دقت تخصیص دهیم. منحنی­های پر کردن فضا (SFC) می توانند در اینجا موثر باشند (رجوع کنید به بخش 2.10.1.5).

 

 

 

 

 

 

 

 

فصل 11

متدهای مونت کارلو

شبیه سازی مونت کارلو عبارت گسترده ای برای متدهایی است که از اعداد تصادفی و نمونه­گیری آماری برای حل مسائل به جای مدل سازی دقیق استفاده می­کنند. به خاطر ماهیت این نمونه گیری، نتیجه با حدودی نااطمینانی خواهد بود، اما "قانون اعداد بزرگ" آماری تضمین می کند که نااطمینانی با افزایش تعداد نمونه کاهش می یابد. این قانون آماری می گوید: اگر N مشاهده مستقل از کمیت با انحراف معیار σ داشته باشیم، در اینصورت انحراف معیار میانگین  σ/Nاست. این یعنی با مشاهدات بیشتر دقت بیشتری حاصل می شود؛ چیزی که موجب می­شود متدهای مونت کارلو جالب باشد این است که دقت حاصل رابطه­ای با ابعادی بودن مسئله اصلی ندارد.

تکنیک های مونت کارلو کاندید طبیعی برای شبیه سازی پدیده هایی محسوب می شود که ماهیت آماری دارند مثل تجزیه رادیواکتیو، یا حرکت براونی. مسائل دیگری که شبیه سازی مونت کارلو در آنها جذاب است خارج از حوزه محاسبه علمی است. برای مثال، مدل بلک شولز برای قیمت گذاری امتیاز خرید یا فروش سهام به بهاى از پیش تعیین شده [11] از شبیه سازی مونت کارلو استفاده می کند.

ثبت سفارش ترجمه تخصصی

برخی مسائلی که قبلا دیدی، مثل حل معادلات سیستم خطی، را می توان با تکنیک های مونت کارلو دنبال کرد. با این حال، این کاربرد معمول نیست. در ادامه دو کاربرد را بررسی می کنیم که در آنها محاسبه متدهای د قیق زمان خیلی زیادی طول می­کشد و نمونه گیری آماری پاسخ سریع و قابل قبولی می دهد.

ابزاری مهم برای نمونه گیری آماری تولید کننده عدد تصادفی است. با بحث کوتاهی درباره مسائل ایجاد اعداد تصادفی، بویژه به صورت موازی، شروع می کنیم.

11.1. ایجاد عدد تصادفی موازی

غالبا اعداد تصادفی در شبیه سازی­ها بکار می رود که در چند مثال زیر نیز آمده است. بدست آوردن اعداد تصادفی واقعی دشوار است: آنها را می توان با اندازه گیری فرآیندهای کوانتومی مثل ذرات رادیواکتیو بدست آورد، اما اینکار خیلی خسته کننده است. به جای آن ما از اعداد شبه تصادفی استفاده می کنیم. این عین از فرآیند ریاضی قطعی استفاده می کنیم، یعنی به اندازه کافی بیقاعده است و برای اهداف عملی نمی توان ترتیبی در آن یافت.

یکی از راههای آسان برای ایجاد اعداد تصادفی (مشخصه شبه تصادفی بودن را کنار می گذاریم) استفاده از تولید کننده های هم ارز خطی است (برای اطلاعات بیشتر در مورد اعداد تصادفی رجوع کنید به نوت [99])، که به این شکل است،

x_k+1 = (ax_k + b)   mod m.

این توالی دوره ای است، زیرا شامل اعداد صحیح غیرمنفی در بیشتر m-1 است، و با دوره m تحت شرایط معین است. دوره معمول 2³¹ است. نقطه شروع x₀ سری "بذر" نامیده می شود. نرم افزار اعداد تصادفی غالبا امکان مشخص کردن بذر را فراهم می کند. برای بدست آوردن نتایجی با قابلیت بازتولید، برنامه را با یک بذر چندین بار تکرار می کنید؛ برای بدست آوردن رفتار تصادفی در چند دور اجرای برنامه می­توانید بذر دوم را از روی توابع ساعت و تقویم بدست آورید.

تولید عدد تصادفی به صورت موازی مشکل ساز است. برای دیدن این مسئله، فرآیند موازی را در نظر بگیرید که از تولید کننده عدد تصادفی در هر زیرفرآیند استفاده می کند و یک پردازشگر را در نظر بگیرید که از فرآیند موازی تقلید می کند. حالا این یک فرآیند تولید کننده عدد تصادفی دارد که شامل نتایج تولید کننده موازی جاگذاری است. یعنی اگر از یک تولید کننده در همه فرآیندهای موازی استفاده کنیم، تولید کننده موثر در کل فرآیند گستره­هایی با مقادیر همانند ایجاد خواهد کرد.

می توان این مسئله را با داشتن کاری مرکزی حل کرد که مقادیر تصادفی برای همه پردازشگرها تامین می کند، اما اینکار عمل محدود کننده ایجاد می کند. راه حل بهتر این است که تولید کننده­های مستقل با پارامترهایی تنظیم کنیم که تصادفی آماری را تضمین کنند. اینکار ساده نیست. برای مثال، اگر دو توالی x_i⁽¹⁾, x_i⁽²⁾ مقادیر یکسان a, b, m را داشته باشند، و نقطه شروع آنها نزدیک به هم باشد، توالی ها همبستگی قوی خواهند داشت. مثال­های مهم تری از همبستگی نیز وجود دارد.

تکنیک های مختلفی برای ایجاد اعداد تصادفی وجود دارد، مثل بکارگیری دو توالی که یکی نقاط شروع برای توالی دیگر را تولید می کند، که همان تکنیکی است که در واقع در شبیه سازی بکار می رود. نرم افزار تولید کننده اعداد تصادفی موازی را می توان در http://sprng.cs.fsu.edu/ یافت [120].

11.2. مثال­ها

11.2.1. ادغام با آمار

بهتر از با چیزی ساده­تر از ادغام شروع کنیم: اندازه گیری  مساحت. فرض کنید استخری به شکل غیرعادی در حیاط دارید، و خود حیاط مربع و با ابعاد مشخص است. اگر سنگریزه هایی را به حیاط پرتاب کنید به طوریکه به صورت برابر در هر نقطه ای فرود آیند، در اینصورت نسبت سنگریزه هایی که به استخر می افتند به سنگریزه­هایی که به بیرون از آن می افتند برابر با نسبت مساحت است.

برحسب ریاضی، Ω ϵ [0, 1]² بگیرید، و تابع f(x̃) را در توصیف مرز Ω در نظر بگیرید، یعنی

حالا جاهای تصادفی x̃₀, x̃₁, x̃₂, ϵ [0, 1]² در نظر بگیرید، در اینصورت می توان مساحت Ω را با در نظر گرفتن اینکه f(x̃_i) چند وقت یکبار منفی یا مثبت است، برآورد کرد.

می توان این نظریه را به ادغام بسط داد. میانگین تابع در بازه (a, b) عبارت است از

از سوی دیگر، اگر نقاط x_i به صورت تصادفی توزیع شود و تابع f خیلی ریسکی نباشد، می توان میانگین را به اینصورت نیز برآورد کرد،

ثبت سفارش ترجمه تخصصی

با اینکار داریم،

تئوری آماری، که حالا به آن می­پردازیم، می­گوید نااطمینانی σ_I در عدد صحیح با انحراف معیار σ_f برای توزیع­های نرمال با رابطه زیر مرتبط است،

تا اینجا ادغام مونت کارلو چندان متفاوت از ادغام کلاسیک به نظر نمی رسد. تفاوت زمانی است که به ابعاد بالاتر می رویم. در اینصورت برای ادغام کلاسیک به N نقطه در هر بعد نیاز خواهیم داشت، که منجر به N^d نقطه در d بعد می شود. اما در متد مونت کارلو نقاط به صورت تصادفی از فضای d بعدی در نظر گرفته می شود و تعداد بسیار کمتری نقطه کافی است.

از نظر محاسباتی، متدهای مونت کارلو جذاب هستند زیرا همه ارزیابی های تابع را می توان به صورت موازی انجام داد.

11.2.2. شبیه سازی مدل آیزینگ (Ising) به روش مونت کارلو

مدل آیزینگ (برای مقدمه رجوع کنید به [28]) در اصل برای مدل سازی فرومغناطیس پیشنهاد شد. مغناطیس نتیجه تراز اتم ها در جهت چرخش است: چرخش را فقط روبه بالا و پایین در نظر بگیرید، در اینصورت ماده در صورتی دارای مغناطیس است که اتم های بیشتر به بالا و پایین بچرخند، یا بالعکس. اتم­های در ساختاری قرار می گیرند که شبکه ( بلوری) نامیده می شود.

حالا گرم شدن ماده را تصور کنید که اتم ها را سست می کند. اگر میدان خارجی بر ماده اعمال شود، اتم ها حول میدان تراز می شوند، و اگر میدان برداشته شود مغناطیس دوباره از بین می رود . با این حال، در زیر دمای بحرانی معینی ماده مغناطیس خود را حفظ می کند. از شبیه سازی مونت کارلو برای یافتن پیکربندی های باثباتی که باقی می مانند، استفاده می کنیم.

شبکه Λ را با N اتم در نظر بگیرید، و پیکربندی اتم ها را با σ = (σ₁, . . ., σ_N) نشان می دهیم که در آن هر σ_i = ± 1 است. انرژی شبکه عبارت است از

جمله اول فعل و انفعال بین چرخش­های انفرادی σ_i را میدان خارجی J مدل سازی می کند. جمله دوم نزدیک­ترین جفت همسایه را جمع می زند، تراز جفت اتم ها را مدل سازی می کند: حاصل σ_iσ_j در صورتی مثبت است که اتم ها چرخش همانند داشته باشند و در غیراینصورت منفی است.

در مکانیسم آماری، احتمال پیکربندی عبارت است از

که در آن تعریف "تابع تقسیم بندی" Z عبارت است از

که در آن جمع 2^N پیکربندی را دربرمی گیرد.

پیکربندی در صورتی باثبات است که انرژی آن تحت اغتشاشات اندک تغییر نکند. برای بررسی این امر، الگوریتم را روش شبکه تکرار می کنیم و بررسی می کنیم که آیا چرخش اتم­ها انرژی را کاهش می دهد یا نه. المان احتمال را برای پیشگیری از جواب های مصنوعی اضافه می کنیم. (این الگوریتم متروپولیس است [123].)

برای تعداد معین تکرار do

برای اتم i do

تغییر ∆E را از روی تغییر علامت σ_i محاسبه کنید

اگر ∆E < یا exp(-∆E) بزرگتر از عدد تصادفی باشد then

تغییر را قبول کنید

ثبت سفارش ترجمه تخصصی

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

تکرار هر پردازشگر روی نقاط محلی در شبکه معادل است با مرتب سازی عمومی ویژه شبکه؛ برای موازی کردن محاسبه معادل با محاسبه متوالی، به تولید کننده تصادفی موازی نیز نیاز داریم (بخش 11.1).

 

 

فصل 12

بیولوژی محاسباتی

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

در پروژه­های ژنوم، توالی ژنوم کامل موجود زنده تعیین می شود. این کار غالبا با شکستن کروموزوم­ها به تعداد زیادی تکه های کوتاه انجام می گیرد که با ماشین های توالی بندی اتوماتیک قابل خواندن هستند. الگوریتم های توالی بندی کل کروموزوم را با یافتن مناطق منطبق بر هم بازسازی می کنند.

12.1. روش های برنامه نویسی پویا

یکی از استراتژی های الگوریتمی متداول همترازی ژن برنامه نویسی پویاست، که در الگوریتم نیدلمن – وانش (Needleman-Wunsch) [127] و گونه هایی مثل الگوریتم اسمیت – واترمن بکار می رود.

ما این الگوریتم را به طور خلاصه طرح می کنیم. فرض کنید ∑ یک الفباست، و A = a₀, . . ., a_m-1، B=b₀, . . ., b_n-1 کلماتی در این الفبا است (اگر این واژگان برای شما عجیب است، رجوع کنید به ضمیمه 22)، سپس ماتریس H_ij را با نمرات شباعت i ≤ m, j ≤ m می سازیم. ابتدا وزن w_match, w_mismatch را تعریف می کنیم، که معمولا مثبت و صفر یا منفی هستند و تابع وزن نمره خلاء روی  ∪ { - } عبارت است از

حالا وارد می کنیم،

و به صورت القایی H_ij را برای اندیس­ها می سازیم که در آن I > 0 یا j > 0 است.

فرض کنید A, B با i, j مطابقت داده شده است، یعنی نمره h_i’,j’ را برای ارتباط دادن همه توالی های a₀ . . .a_i’ به b₀ . . . b_j’ داریم با i' ≤ i, j’ ≤ j به جز i’ = i, j’ = j، بنابراین:

• اگر a_i = b_j باشد، نمره h را در i, j به اینصورت می گیریم،

• اگر b_j a_i ≠ باشد، یعنی توالی ژن جهش یافته باشد، تمره h را در i, j به اینصورت می گیریم،

شکل 12.1. وابستگی­ها در الگوریتم اسمیت – واترمن؛ قطرها غیروابسته به هم هستند

• اگر a_i کاراکتر حذف شده در توالی B باشد، w_deletion را به نمره در i – 1,j اضافه می کنیم:

• اگر bj کاراکتر حذف شده در توالی A باشد، w_deletion را به نمره در i, j – 1 ا ضافه می کنیم:

به طور خلاصه داریم:

به این ترتیب نمره­ای در h_mm بدست می­آید و با بازگشت به عقب درمی­یابیم که توالی چگونه منطبق شده است.

ملاحظات محاسباتی

• در هر ردیف یا ستون، مقدار ماتریس H به صورت بازگشتی تعیین می شود.بنابراین روش­هایی بر اساس در نظر گرفتن هر قطر به عنوان جبهه موج امتحان شده است [117]. این کار در شکل 12.1 نشان داده شده است؛ برای اطلاعات بیشتر در مورد جبهه های موج رجوع کنید به بخش 6.11.1. هر قطر فقط به دو قطر قبل برای محاسبه نیاز دارد، بنابراین میزان فضای موقتی لازم در اندازه ورودی خطی است.
• معمولا بسیاری از قسمت ها باید همتراز شود، و همه این عملیات غیروابسته به هم است. یعنی روش­های SIMD، از جمله GPUها امکان پذیر است. اگر توالی ها طول برابر نداشته باشند، می توان آنها را با اندکی هزینه سربار بیشتر لایی­دار کرد.
• این الگوریتم کار متناسب با mn، با m + n ورودی و خروجی اسکالر دارد. این برای پیاده سازی در GPUها مطلوب است.

12.2. درخت پسوند

http://homepage.usask.ca/˜ctl271/857/suffix_tree.shtml

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

ثبت سفارش ترجمه تخصصی

مثال: کلمه “Mississippi” حاوی حروف i,m,p,s است، بنابراین در سطح اول درخت باید این حروف را منطبق کنیم.

می­توان بعد از “i"، “p” یا “s” قرار  داد، بنابراین در سطح بعدی درخت باید آن را قرار  دهیم.

با این حال، بعد از “ip” فقط یک احتمال وجود دارد، “ippi”، و همین طور بعد از “is” رشته “issi” به صورت منحصر می­آید و ما نمی توانیم بین “p” یا “s” انتخاب کنیم.

بعد از ساخت کل درخت پسوند، ساختار داده بدست می­آید که در آن زمان یافتن رشته­ای به طور m عبارت است از O(m). ساخت درخت پسوند برای رشته­ای به طور n را می توان در زمان O(n) انجام داد.

هم همترازی ژنوم و هم انتخاب امضا را می توان با درخت پسوند انجام داد.

 

 

 

 

 

 

 

 

فصل 13

داده­های بزرگ

13.1. سیستم­های توصیه­گر

مقاله http://www2.research.att.com/˜volinsky/papers/ieeecomputer.pdf سیستم­ هایی را مثلا از Netflix توضیح می دهد که سعی دارند پیش بینی کنند یک شخص تا چه اندازه­ای آیتم معینی را دوست خواهد داشت.

روشی که در اینجا بکار گرفته می شود شناسایی فضای R^f (نسبتا با بُعد کم) ویژگی­هاست. مثلا برای فیلم­ها می توان دو ویژگی را اتخاذ کرد: سطح پایین (عامیانه) در برابر سطح بالا (عالمانه)، و  تاریخی در برابر معاصر. (سطح بالای تاریخی: هملت؛ تاریخی سطح پایین: رابین هود، men in tights؛ معاصر سطح بالا: همه چیز درباره جرارد؛ معاصر سطح پایین، اه، حتما باید مثال پیدا کنم؟) برای هر آیتم (فیلم) i بردار q_i ϵ R^f وجود دارد که آن آیتم را مشخص می کند، و برای هر شخص بردار p_j ϵ R^f وجود دارد که مشخص می کند آن شخص فیلم­ها را تا چه حدی دوست دارد. ریتینگ پیش بینی شده برای کاربر فیلم عبارت است از r_ij = q^t_ip_j.

بردارهای q_i, p_j به تدریج براساس ریتینگ واقعی r_ij، مثلا با حداقل سازی تدریجی مشخص می شود

13.1.1. نزول گرادیان تصادفی

e_ij = r_ij – q^t_ip_j را اختلاف بین ریتینگ واقعی و پیش بینی شده بگیرید.

13.1.2. ابتدا همه p_j را مشخص کنید q_i را به حداقل برسانید (به صورت موازی)، سپس q_i را مشخص کرده و p_j را به حداقل برسانید. اینکار از عهده داده های گم شده بهتر برمی­آید.

 

فصل 14

گرافیک کامپیوتر

مسائل زیادی در گرافیک کامپیوتر را می توان موردی از برنامه نویسی SIMD در نظر گرفت: تصویر آرایه مربع یا مستطیل است که در آن هر پیکسل را می توان جداگانه، و اغلب با یک عمل، دستکاری کرد.

برای مثال، تصویری با 1024 × 1024 پیکسل، هر کدام 8 بیت، 2²0 بایت یا 1 مگابایت خواهد شد. در زمینه  فیلمی با فرمت 60 فریم، و پردازشگری با میانگین نسبت دستور 1 GHz، این یعنی هر عمل حدود 16 نانوثانیه طول می کشد. (با اینکه این نسبت عمل قابل قبول به نظر می رسد، باید به پهنای باند نیز توجه داشته باشیم.)

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

کارهای دیگر چند پیکسل را باهم دربرمی گیرند: عملیات پرداخت مثل حذف نویز با  استفاده  از استنسیل اختلاف. استنسیل میانگین معمول عبارت است از

استنسیل­هایی که در فصل 4 دیدید تمایز را نشان می دهند؛ در گرافیک­هایی که می توان برای عملیاتی مثل شناسایی لبه بکار برد. گزینه­ای متداول برای استنسیل تمایز عبارت است از

کد توالی برای بکارگیری استنسیل 3 × 3 در تصویر N ×  N به این شکل خواهد بود

به طوریکه در بخش 2.6.9 بحث شد، این ساختار کد برای انواع خاصی از موازی­سازی مفید است. برای مثال، در CUDA! (CUDA!) کرنلی حاوی دو حلقه داخلی نوشته می شود و به صورت موازی در هر مختصات [i,j] آرایه میانگین­ها بکار می رود.

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

 

 

 

 

 

 

 

ثبت سفارش ترجمه تخصصی

 

 

فصل 16

اپلیکیشن­های فیزیکی دیگر

15.1. متدهای شبکه بولتزمن

متدهای شبکه بولتزمن (LBM) راهی متفاوت برای محاسبه جوابی متمایز برای PDE، براساس تقسیم دامنه به سلول­ها فراهم می کنند. نظریه اصلی این است که آیا در این سلول ذره­ای وجود دارد، و با توجه به نیرو در این سلول، ذره به کجا حرکت می کند؟" به جای توجیه درباره ذرات واقعی، LBM این احتمال را در نظر می گیرد که در سلول ذره وجود دارد، و این احتمال چگونه به روز می شود.

تابع توزیع f (یا توزیع سرعت ذره، همانند معادله؟). برای هر سلول i

که در آن Ω_i عملگر تصادم با داشتن نسبت تغییر، تابع توزیع f_i است.

چگالی: p = ∑_i f_i، چگالی گشتاور: pu = ∑_I f_ie_i.

حفظ جرم  ∑_i Ω_i = 0، حفظ گشتاور ∑_i Ω_ie_i = 0

معادله اصلی، مرتبه دوم در ϵ:

15.2. تئوری کاربردی هارتری-فوک / چگالی

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

میدان ماتریس ارزیابی شده است

تبدیل ماتریس مربع به قطری را در ماتریس Kohn-sham تکرار کنید.