جواب سوال سمیه!

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

می خواهم N عدد k بیتی را مرتب کنیم. یک آرایه از پردازنده ها داریم که k سطر (معادل هر بیت عدد) و N ستون (معادل هر عدد) دارد. حالت خاص زیر را در نظر بگیرید (بیتهای پر ارزش در سطرهای بالا و کم ارزش در سطرهای پایین اند)

x 0 0 ... 0

0 1 1 ... 1

0 0 0 ... 0

...

1 0 0 ... 0

همه ی اعداد به جز عدد اولی با هم مساویند. حالا گفته است که بیت آخر جواب آرایه مرتب شده اگر x=0 باشد 1 است و اگر x=1 باشد 0 است. یعنی باید مقدار پردازنده 1و1 به پردازنده ی k,N برسد. که این یعنی قطر شبکه را طی کند.

http://mycourse.blog.ir/1392/12/05/%D8%AD%D8%AF-%D9%BE%D8%A7%DB%8C%DB%8C%D9%86-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%D9%85%D9%88%D8%A7%D8%B2%DB%8C