برنامه تابستان دانشجوهای ارشد

Mesh of Trees

ما بهترین مدلی که داریم شبیه PRAM یک گراف دوبخشی کامل است که هر رأس از هر بخش را به هر رأس از بخش دیگر وصل می‌کند. دلیل ادغام پردازنده‌های ریشه در MOT هم همین است که گراف K_(N,N) معادل N پردازنده باشد که هر کدام به N پردازنده‌ی دیگر وصل هستند. دلیل اینکه از درخت به جای گره‌ها استفاده می‌کنیم این است که در غیر این صورت درجه‌ی رأسها به شدت زیاد می‌شود.

پس از اینجا می‌فهمیم که برای طراحی الگوریتم برای MOT باید ابتدا PRAM آن را طراحی کنیم بعد آن را به MOT تبدیل کنیم.

بدون نظر

از این به بعد همه‌ی مطالب وبلاگ بدون امکان نظر دادن خواهد بود!

حل سوال ۲ امتحان تقریبی

من سوال ۲ را از خود استاد پرسیدم حل آن با این روش است:

می‌توانیم همیشه یک جواب صحیح بسازیم که جواب بهینه باشد. برای این کار وزن هر یال را صفر می‌کنیم و به یکی از یالهای غیرصفر همسایه‌اش می‌دهیم. در این صورت چون دور فرد (و در نتیجه مثلث) نداریم جمع همچنان ثابت می‌ماند و جواب مسأله تغییر نمی‌کند و قیدی هم به هم نمی‌خورد. با این کار به یک جواب صحیح می‌رسیم، چون جمع یالهای مجاور هر رأس ۱ است. چون قید صفر بودن متغیر یک رأس اگر اتفاق بیفتد، سر دیگر یالهای متصل به آن باید ۱ شوند تا قیدهای مسأله به هم نخورد و در این صورت جمعشان ۱ می‌شود. در این صورت یک گراف دوبخشی ساخته می‌شود که جواب بهینه‌ی آن باید ۰و۱ باشد. پس جواب بهینه‌ی صحیح برای مسأله وجود دارد. اگر یک رأس در هر دو دسته باشد هم مشکلی پیش نمی‌آید، چون در این صورت همه‌ی قیدهای مکمل برقرار می‌شوند.

broadcasting on hypercube

روشهای ارسال یک پیام به همه‌ی پردازنده‌ها در مدل ابرمکعب (هر پردازنده یک عدد q بیتی دارد و هر بیت آن را عوض کنیم به یک پردازنده‌ی همسایه‌ی آن می‌رسیم.)

۱- روش درخت دوجمله‌ای: در این روش یک پردازنده (مثلاً صفر) اطلاعات را به ترتیب به همسایه بعد آخر تا اول خود می‌فرستد. این پردازنده ها هم به همین ترتیب برای پردازنده‌های زیرمجموعه خود می‌فرستند.

زمان این کار به اندازه‌ی طول پیام * تعداد بیت‌های پردازنده‌ها (لگاریتم تعداد پردازنده‌ها) می‌شود.

۲- الگوریتم خط لوله درخت دوجمله‌ای (pipelined binomial tree)

در این روش به جای اینکه کل پیام را هر بار بفرستیم یک بیت پیام را می‌فرستیم و در مرحله‌ی بعد بیت بعدی و ادامه می‌دهیم تا کل پیام ارسال شود. زمان این کار به اندازه‌ی طول پیام به اضافه‌ی تعداد بیت‌های پردازنده‌ها (لگاریتم تعداد پردازنده‌ها) می‌شود.

۳- الگوریتم جانسون و هو (Johnsson & Ho)

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

سوال ۱۴.۹ پرهامی (موازی)

زمانش از لگاریتمی بهتر نمی‌شود و در نتیجه efficiency آن هم ۱ نمی‌شود ولی باز هم انگار به عنوان الگوریتم خوب مورد قبول است!! (اشکال کتاب پرهامی)

http://www.mcs.anl.gov/~itf/dbpp/text/node126.html

مغز انیشتن!

http://thespiritscience.net/2014/04/29/how-was-einsteins-brain-different/

خلاصه‌اش این است که دانشمندها فهمیدند که مغز انیشتین از هر دو نیمه‌اش استفاده می‌کرده و به صورت مداوم از یکی به اون یکی. :))

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

تقدیم به همه‌ی اساتید عزیز

http://tapastic.com/episode/41894

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

راستی سوالها رو هم تی‌ای عزیزمون داده بود.

جواب سوال ۲ و ۵ پایان ترم تقریبی

همون طوری که پیش بینی می‌شد سوالها نکاتش همان نکات تمرین‌ها بود. به طرز جالبی بد دادم! :| یکی رو خودم غلط حل کرده بودم، یکی رو سوال راهنمایی اشتباه کرده بود، یکی رو فکر می‌کردم نیست جزو مباحث امتحان، یکی رو هم یادم رفته بود. وقت هم تمدید نشد (نیم ساعت حساب نیست).

نمی‌دونم الآن چطوری باید برای خودم متأسف باشم! :| این سری هم نفر آخر کلاس میشم. (تازه اگه شانس بیارم!)

http://personal.vu.nl/l.stougie/Courses/ALP/col10.pdf

http://www.cse.cuhk.edu.hk/~chi/csc5160-2008/notes/L10-stable.pdf