در این مسئله، با یک سیستم چند پردازنده سر و کار داریم. چنین سیستمی از تعدادی پردازنده‌ی $k$ بیتی تشکیل شده است که به شکل خاصی به هم اتصال دارند. یک پردازنده‌ی $k$ بیتی، پردازنده‌ای است که دارای $k$ بیت حافظه و تعدادی ورودی و خروجی است و در هر لحظه‌ی $t$، بر اساس مقدار ورودی‌ها و حافظه‌اش، مقدار خروجی‌هایش که می‌توانند ورودی‌های پردازنده‌های دیگری در لحظه‌ی $t+1$ باشند را تعیین می‌کند. (تعیین این خروجی‌ها با استفاده از یک الگوریتم مشخص که از پیش به پردازنده‌ها داده شده است صورت می‌گیرد.)

فرض کنید که $2n$ پردازنده‌ی یک بیتی در اختیار داریم که مانند شکل زیر به هم متصل شده‌اند. ورودی سمت چپ پردازنده‌ی اول و ورودی سمت راست پردازنده‌ی $2n$ ام از بیرون از سیستم داده می‌شوند.

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

دو عدد $n$ بیتی (در مبنای دو) به این صورت به این سیستم وارد می‌شوند: در لحظه‌ی $t=1$، رقم سمت راستی عدد اول در ورودی سمت چپ پردازنده‌ی اول قرار داده می‌شود؛ در لحظه‌ی $t=2$، رقم سمت چپی عدد دوم در ورودی سمت راست پردازنده‌ی $2n$ ام قرار داده می‌شود؛ در لحظه‌ی $t=3$، رقم دوم (از سمت راست) عدد اول در ورودی سمت چپ پردازنده‌ی اول قرار داده می‌شود؛ در لحظه‌ی $t=4$، رقم دوم (از سمت چپ) عدد دوم در ورودی سمت راست پردازنده‌ی $2n$ ام قرار داده می‌شود و … .

هدف مسئله این است که شما الگوریتمی که پردازنده‌ها بر اساس آن عمل می‌کنند را به نحوی طراحی کنید که پس از وارد شدن دو عدد $n$ بیتی به این سیستم و پس از گذشت چند مرحله، اگر مقدار حافظه‌های پردازنده‌های اول تا $2n$ ام (که هر یک، یک رقم صفر با یک است) را از چپ به راست پشت سر هم بنویسیم (یعنی حافظه‌ی پردازنده‌ی اول سمت چپ و حافظه‌ی پردازنده‌ی $2n$ ام سمت راست قرار گیرد)، عددی که دیده می‌شود (در مبنای دو) برابر با حصل ضرب دو عدد $n$ بیتی داده شده باشد. به عبارت دیگر، سیستم چند پردازنده باید بتواند دو عدد $n$ بیتی را در هم ضرب کند.

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

• سوال بعد
• سوال قبل