- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
ماشین محاسباتی «هاتی» دارای n خانه ی حافظه ی M1، M2، ...، و Mn است. هر یک از این خانه های حافظه می توانند یکی از مقادیر 0 یا 1 را در خود ذخیره کنند. برای راحتی کار اعداد ذخیره شده در خانه های حافظه را با یک رشته به طول هاتی می تواند دو نوع دستورالعمل ساده را اجرا کند:
* دستور ci در این دستور i یک عدد صحیح بین 1 تا n است. با اجرای این دستور، عدد ذخیره شده در خانه ی حافظه ی Mi عوض می شود ( از 0 به 1 به 0 تغییر می کند.)
* دستور Di در اینجا نیز i یک عدد صحیح بین 1 تا n است. هاتی برای اجرای این دستور عدد ذخیره شده در تمامی خانه های حافظه به جز Mi را بررسی می کند: در صورتی که تمامی این مقادیر 1 بودند، فقط عدد ذخیره شده در Mi را عوض می کند، و در غیر این صورت (اگر حداقل یکی از آن ها صفر بود) تغییری در مقادیر خانه ها ایجاد نمی کند.
مثلا فرض کنید هاتی 3 خانه ی حافظه دارد که مقادیر (0,0,1) در آن ذخیره شده اند. حال اگر دستور c2 را به ماشین بدهیم، این مقادیر تبدیل به (0,1,1) خواهند شد. در ادامه اگر دستور D1 را وارد کنیم، حاصل برابر (1,1,1) خواهد شد. اما اگر دستور D1 را قبل از دادن دستور C2 به ماشین بدهیم، این مقادیر تبدیل به (0,1,1) خواهند شد. در ادامه اگر دستور D1 را وارد کنیم، حاصل برابر (1,1,1) می شود. اما اگر دستور D1 را قبل از دادن دستور C2 به ماشین می دادیم، حاصل همان (0,0,1) باقی می ماند.
یک « جدول صورت مسأله » جدولی شامل 2n سطر و 2 ستون است که در هر ستون آن تمامی رشته های به طول n از 0 و 1، هر رشته دقیقا یک بار، آمده است. به رشته های ستون اول « رشته ها ی ورودی » و به رشته های ستون دوم «رشته های خروجی» می گوییم. ما باید برای هاتی یک «برنامه» بنویسیم، به نحوی که اگر هر یک از رشته های ورودی در خانه های حافظه ی هاتی باشد، پس از اجرای این برنامه، رشته ی خروجی هم سطر با آن رشته ی ورودی در حافظه ی هاتی قرار گرفته باشد.
یک برنامه شامل چند دستورالعمل است که پشت سر هم نوشته شده اند. هنگامی که یک برنامه را به هاتی بدهیم، دستورالعمل های این برنامه به ترتیب اجرا می شوند. مثلا فرض کنید هاتی 2 خانه ی حافظه دارد (n=2) و جدول صورت مسأله ی زیر داده شده است:
رشته ی ورودی رشته ی خروجی
00 01
01 10
10 11
11 00
یک برنامه ی نمونه که این کار را انجام می دهد به صورت زیر است:
D1
C2
الف) یک جدول صورت مسأله را «ساده» می نامیم اگر در آن هر رشته ی ورودی مساوی رشته ی خروجی هم سطرش باشد، بجز دو رشته ی A و B که این دو رشته فقط در یکی از n، عنصر خود با هم تفاوت داشته باشند. توجه کنید که در آن جدول، A رشته ی خروجی هم سطر با رشته ی ورودی B و هم چنین B، رشته ی خروجی هم سطر با رشته ی ورودی A است. ثابت کنید که می توان برای هر جدول صورت مسأله ی ساده، یک برنامه نوشت.
ب) ثابت کنید که می توان برای هر جدول صورت مسأله، یک برنامه نوشت.
* دستور ci در این دستور i یک عدد صحیح بین 1 تا n است. با اجرای این دستور، عدد ذخیره شده در خانه ی حافظه ی Mi عوض می شود ( از 0 به 1 به 0 تغییر می کند.)
* دستور Di در اینجا نیز i یک عدد صحیح بین 1 تا n است. هاتی برای اجرای این دستور عدد ذخیره شده در تمامی خانه های حافظه به جز Mi را بررسی می کند: در صورتی که تمامی این مقادیر 1 بودند، فقط عدد ذخیره شده در Mi را عوض می کند، و در غیر این صورت (اگر حداقل یکی از آن ها صفر بود) تغییری در مقادیر خانه ها ایجاد نمی کند.
مثلا فرض کنید هاتی 3 خانه ی حافظه دارد که مقادیر (0,0,1) در آن ذخیره شده اند. حال اگر دستور c2 را به ماشین بدهیم، این مقادیر تبدیل به (0,1,1) خواهند شد. در ادامه اگر دستور D1 را وارد کنیم، حاصل برابر (1,1,1) خواهد شد. اما اگر دستور D1 را قبل از دادن دستور C2 به ماشین بدهیم، این مقادیر تبدیل به (0,1,1) خواهند شد. در ادامه اگر دستور D1 را وارد کنیم، حاصل برابر (1,1,1) می شود. اما اگر دستور D1 را قبل از دادن دستور C2 به ماشین می دادیم، حاصل همان (0,0,1) باقی می ماند.
یک « جدول صورت مسأله » جدولی شامل 2n سطر و 2 ستون است که در هر ستون آن تمامی رشته های به طول n از 0 و 1، هر رشته دقیقا یک بار، آمده است. به رشته های ستون اول « رشته ها ی ورودی » و به رشته های ستون دوم «رشته های خروجی» می گوییم. ما باید برای هاتی یک «برنامه» بنویسیم، به نحوی که اگر هر یک از رشته های ورودی در خانه های حافظه ی هاتی باشد، پس از اجرای این برنامه، رشته ی خروجی هم سطر با آن رشته ی ورودی در حافظه ی هاتی قرار گرفته باشد.
یک برنامه شامل چند دستورالعمل است که پشت سر هم نوشته شده اند. هنگامی که یک برنامه را به هاتی بدهیم، دستورالعمل های این برنامه به ترتیب اجرا می شوند. مثلا فرض کنید هاتی 2 خانه ی حافظه دارد (n=2) و جدول صورت مسأله ی زیر داده شده است:
رشته ی ورودی رشته ی خروجی
00 01
01 10
10 11
11 00
یک برنامه ی نمونه که این کار را انجام می دهد به صورت زیر است:
D1
C2
الف) یک جدول صورت مسأله را «ساده» می نامیم اگر در آن هر رشته ی ورودی مساوی رشته ی خروجی هم سطرش باشد، بجز دو رشته ی A و B که این دو رشته فقط در یکی از n، عنصر خود با هم تفاوت داشته باشند. توجه کنید که در آن جدول، A رشته ی خروجی هم سطر با رشته ی ورودی B و هم چنین B، رشته ی خروجی هم سطر با رشته ی ورودی A است. ثابت کنید که می توان برای هر جدول صورت مسأله ی ساده، یک برنامه نوشت.
ب) ثابت کنید که می توان برای هر جدول صورت مسأله، یک برنامه نوشت.