دانلود رایگان سوالات نظریه محاسبه با جواب (استخدامی)
قسمتی از سوالات نظریه محاسبه :
– اگر مجموعه اعداد طبیعی و E مجموعه اعداد طبیعی زوج باشد از نظر اندازه ……
الف. N بزرگتر از E است.
ب. N بزرگتر از E است.
ج. N و E هم اندازه هستند. ☑
N و E ناشما را هستند.
د. N و E ناشمارا هستند
– برتری که یک ماشین تورینگ نسبت به آتوماتای متناهی خطی دارد در چیست؟
الف. قدرت تصمیم گیری بیشتر
ب. دسترسی نامحدود به حافظه ☑
ج. تنوع در رشته ورودی
د. ماشین تورینگ هیچ برتری ای نسبت به آتومانای متناهی خطی ندارد.
– اگر در یک LBA با طول نوار n=5 تعداد حالتها 2 برابر شود تعداد ساختارها چند برابر می شود؟
الف. 2 برابر ☑
ب. 10 برابر
ج. 32 برابر
د. 25 برابر
– اگر در یک LBA تعداد حالتها در الفبای نوار 2 برابر شود و طول نوار 5 باشد. تعداد ساختارهای متفاوت از این LBA چه تغییری خواهد کرد؟
الف. 2 برابر می شود. ☑
ب. 10 برابر می شود.
ج. 25 برابر می شود.
د. 32 برابر می شود.
– یک ماشین تورینگ است که ورودی خود را نادیده گرفته و یک کپی از توصیف خودش را چاپ می کند؟
الف. برشمارنده
ب. سلف (SELF) ☑
ج. الهام گیرنده
د. تصمیم گیرنده
– به مجموعه ای از دستورالعملهای ساده که کار مشخصی را انجام میدهند چه گفته می شود؟
الف. الگوریتم ☑
ب. سیستم
ج. مدل
د. محاسبه
– مجموعه زبانهای تشخیص پذیر تورینگ نسبت به کدامیک از عملگرهای زیر بسته نیست؟
الف. بستار
ب. مکمل ☑
ج. اشتراک
د. اجتماع
– مشخصه ماشین تورینگ چیست؟
الف. حافظه محدود – قدرت کم
ب. حافظه نامحدود- قدرت کم
ج. حافظه محدود – قدرت زیاد
د. حافظه نامحدود – قدرت زیاد ☑
– اگر G یک گرامر به فرم نرمال چامسکی باشد هر اشتقاق به طول 9 دارای چند گام می باشد؟
الف. 9
ب. 18
ج. 10
د. 17 ☑
– اگر A به کاهش پذیر بوده و B تشخیص پذیر تورینگ باشد آنگاه ………..
الف. تشخیص پذیر تورینگ است. ☑
ب. تصمیم پذیر است.
ج. تشخیص پذیر تورینگ مکمل است.
د. نمی توان اظهار نظر کرد.
– حداکثر چند رشته به طول 5 وجود دارد که قابل فشرده شدن به مقدار 3 هستند؟
الف. 29
ب. 25
ج. 23
د. 7 ☑
– کدامیک از جملات زیر در مورد پرشمارنده ها صحیح نیست؟
الف. یک برشمارنده یک ماشین تورینگ با یک جایگر است.
ب. یک بر شمارنده با یک نوار خالی شروع به کار می کند.
ج. زبان برشمرده شده توسط یک برشمارنده مانند E مجموعه تمام رشته هایی است که در نهایت چاپ می شوند.
د. یک پرشمارنده رشته های زبان را به ترتیب و هر کدام را دقیقا یکبار تولید می کند. ☑
– یک ماشین تورینگ که ورودی خود را نادیده گرفته و یک کپی از توصیف خودش را چاپ می کند چه نام دارد؟
الف. پرشمارنده
ب. سلف (SELF) ☑
ج. الهام گیرنده
د. تصمیم گیرنده
– مجموعه جهانی به همراه نمادهای رابطه ای تخصیص داده شده را …………….. گویند.
الف. عبارت
ب. متغیر آزاد
ج. مدل ☑
د. سور
– یک زبان را تصمیم پذیر تورینگ گویند اگر و تنها اگر…………
الف. تشخیص پذیر باشد.
ب. همه ورودی ها را بپذیرد.
ج. یک برشمارنده برای برشمردن آن موجود باشد.
د. خودش و مکملش تشخیص پذیر تورینگ باشد. ☑
– این نوع ماشینها مدل خوبی برای وسایلی است که حافظه خیلی کمی دارند.
الف. اتومانای مشاهی ☑
ب. اتوماتای خطی
ج. اتوماتای پشته ای
د. اتوماتای تورینگ
– در هنگام کار با ماشین تورینگ نحوه تنظیم کدام اجرا را ساختار یا Configuration ماشین تورینگ می گویند؟
الف. تابع انتقال وضعیت فعلی نوار و محل هد
ب. حالت، تابع انتقال و محل هد
ج. وضعیت فعلی نوار نماد فعلی نوار و محل هد ☑
د. الفبای ورودی حالت وضعیت فعلی نوار
– اگر ماشین در سمت چپ ترین نماد باشد و بخواهد به سمت چپ حرکت کند ماشین ……….
الف. متوقف می شود.
ب. در حلقه می افتد.
ج. به حالت عدم پذیرش می رود.
د. در همان خانه باقی می ماند. ☑
– این نوع زبانها را بازگشتی یا recursive نیز می نامند.
الف. تصمیم پذیر ☑
ب. تشخیص پذیر
ج. تصمیم ناپذیر
د. تشخیص ناپذیر
– انواع ماشین تورینگ معمولی نامعین و چند نواره از لحاظ قدرت نسبت به هم چه وضعی دارند؟
الف. با هم برابرند. ☑
ب. تورینگ معمولی قدرت بیشتری دارد.
ج. تورینگ چند نواره قدرت بیشتری دارد.
د. تورینگ نامعین قدرت بیشتری دارد.
– مجموعه زبانهای تشخیص پذیر تورینگ نسبت به کدامیک از عملگرهای زیر بسته نیست؟
الف. بستار
ب. مکمل ☑
ج. اشتراک
د. اجتماع
– کدامیک از جملات زیر نادرست می باشد.
الف. هر زبان مستقل از من منظم هم هست. ☑
ب. هر زبان مستقل از متن تصمیم پذیر هم هست.
ج. هر زبان مستقل از متن تشخیص پذیر هم هست.
د. هر زبان تصمیم پذیر، تشخیص پذیر هم هست.
– اگر A به B کاهش پذیر باشد کدام گزینه صحیح است؟
الف. اگر B تصمیم پذیر باشد آنگاه A نیز تصمیم پذیر است. ☑
ب. اگر A تصمیم پذیر باشد آنگاه B نیز تصمیم پذیر است.
ج. اگر A قابل حل باشد انگاه B نیز قابل حل است.
د. اگر B تصمیم پذیر نباشد آنگاه A نیز تصمیم پذیر نیست.
– کدام گزینه قضیه رایس را به شکل صحیحی بیان میکند؟
الف. هر کاهش یافته ATM یک زبان تصمیم ناپذیر است.
ب. آزمایش هر ویژگی برای زبان یک ماشین تورینگ تصمیم ناپذیر است. ☑
ج. هر زبان مستقل از متن یک زبان تصمیم دیر است.
د. معادل بودن دو ماشین تورینگ تصمیم ناپذیر است.
– برتری که یک ماشین تورینگ نسبت به آتومانای متناهی خطی دارد در چیست؟
الف. قدرت تصمیم گیری بیشتر
ب. دسترسی نامحدود به حافظه ☑
ج. تنوع در رشته ورودی
د. ماشین تورینگ هیچ برتری ای نسبت به اتوماتای متناهی خطی ندارد.
