.
藥 = دانشگاه پیام نور کارشناسی مرکز آزمون و سنجش حضرت علی(ع): دانش راهبر نیکویی برای ایمان است تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱ عنوان درس : نظریه محاسبه
رشته تحصیلی / کد درس : علوم کامپیوتر ۱۱۱۱۴۱۶
استفاده از ماشین حساب ساده مجاز است
۱- اگر ساختار 110d101 ساختار 11q2011 را نتیجه دهد تابع انتقال آن به چه صورت خواهد بود؟ δ:(q1,0) = (q2,0, L) δ:(q1,0) = (q2,1, R) .)
δ:(q1,0) = (q2,0, R) δ:(q1,0) = (q2,1, L)
"- برای تصمیم گیری زبان }A = b. | n > o یک ماشین تورینگ تعریف می کنیم. ماشین تورینگ M روی رشته ورودی از
چپ به راست حرکت می کند و صفرها را بصورت یک در میان علامت می گذارد. کدامیک از گزینه های زیر صحیح نیست؟
۱. اگر در هر مرحله فقط یک عدد صفر وجود داشته باشد به مرحله پذیرش می رود.
۲. اگر در هر مرحله بیش از یک عدد صفر وجود داشته باشد و تعداد صفرها فرد باشد به مرحله عدم پذیرش می رود.
r
- اگر تعداد صفرها زوج باشد به مرحله پذیرش می رود. ۴ . هیچکدام
۳- کدام مورد در تمامی انواع ماشینهای تورینگ یکسان است.
۱. قدرت ۲. تعداد هدها ۳. تعداد حالتها ۴. تعداد نوارها
۴- در ماشین تورینگ ۲ نواره نامعین تابع انتقال به چه صورتی است؟
6:0xT“–ox{L.R.' " 6:0° xF= P(o">T“x{L,R}*) " ð:охг* —э P(охг*х(LR)*) " доxг“ -oxг“x(Lк, ------------------- ۵- یک ماشین تورینگ نامعین را تصمیم گیرنده گویند اگر
۱. تمام مسیرهای آن روی هر رشته ورودی متوقف شوند. ۲. حداقل یک مسیر روی هر رشته ورودی متوقف شود. ۳. تمام مسیرهای آن روی هر رشته ورودی به پذیرش منتهی شوند.
۴. حداقل یک مسیر روی هر رشته ورودی به پذیرش منتهی شود.
۶- یک برشمارنده یک ......................... با یک ...................... است. ۱. ماشین تورینگ - الهام گیرنده ۲. ماشین تورینگ - چاپگر ۳. اتوماتای متناهی - چاپگر ۰۴ اتوماتای متناهی - الهام گیرنده
نیمسال دوم ۹۳-۱۳۹۲ صفحه ۱ از ۵
M.).|).). YYY).***
= دانشگاه پیام نور کارشناسی مرکز آزمون و سنجش
.
حضرت علی(ع): دانش راهبر نیکویی برای ایمان است
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک عنوان درس : نظریه محاسبه رشته تحصیلی /کد درس : علوم کامپیوتر ۱۱۱۱۴۱۶
----------- ۷- یک زبان را تشخیصی پذیر تورینگ گویند اگر و تنها اگر ۱. روی همه ورودی ها در حالت پذیرش خاتمه یابد. ۲. روی برخی از ورودی ها متوقف نشود. ۳. روی همه ورودی ها متوقف شود. ۲. یک برشمارنده برای برشمردن آن موجود باشد.
۸- تفاوت اتوماتای متناهی و ماشین تورینگ در کدامیک از موارد زیر است؟ ۱. حجم حافظه ۲. نحوه ورود و خروج داده ها در حافظه
۳. تعداد هدها ۴. تعداد نوارها
۹- ریشه های چندجمله ای 1 + 32 - 5۲ در چه بازه ای تغییر می کنند. [-15,15] * [-10,10] -° [—5,5] -* |-3,3] .)
۱۰- فرض کنید یک K- PDA یک آتوماتای پشته ای با K پشته باشد کدامیک از جملات ز نیست. (منظور از قویتر بودن این است فرضی کنی دوما دای پ ی با N پ - یہ تب ار زیر صحیح دی را از شوی تر بودن این
که زبانهای بیشتری را تشخیص می دهد).
۱. PDA-1 از CPDA قویتر است. ۲. PDA_2 از PDA-1 قویتر است.
e- gess 2-PDA ; 3-PDA : * c. 2.; 0–PDA ; 2–PDA v. ۱۱- کدامیک از مجموعه های زیر نسبت به همه عملگرهای اجتماع، اتصال، بستار، مکمل و اشتراک بسته است؟
۱. مجموعه زبانهای تصمیم پذیر ۲. مجموعه زبانهای تشخیص پذیر
۳. کلاس زبانهای مستقل از متن ۴. تصمیم پذیر و مستقل از متن
۱۲- مجموعه زبان های تشخیصی پذیر تورینگ تحت کدام یک از عملگرهای زیر بسته نیست؟
۱. مکمل ۲. اجتماع ۳. اشتراک ۴. ستاره یا بستار ۱۳- کدامیک از زبانهای زیر تصمیم پذیر نیست؟
۱. { A یک DFA بوده و EDFA = { | L(A) = b
EODEA = { | L(A) = L(B) 3 sez: DFA ss,» B s A } . Y
Ecos = { | L(G) = p , ss, CFG & G \ . Y.
ETM = {M.).|).). YYY).
صفحه ۲ از ۵
نیمسال دوم ۹۳-۱۳۹۲***
. = دانشگاه پیام نور کارشناسی 纂 مرکز آزمون و سنجش حضرت علی(ع): دانش راهبر نیکویی برای ایمان است تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک عنوان درس : نظریه محاسبه
رشته تحصیلی /کد درس : علوم کامپیوتر ۱۱۱۱۴۱۶
۱۴- اگر گرامر مستقل از متن G به فرم نرمال چامسکی باشد، هر اشتقال W به طول ۵ دارای چند گام می باشد؟ Yt t Yめ .Y A Y \ . . ) ۱۵- کدامیک از جملات زیر صحیح نیست؟ ۱. هر زبان منظم، مستقل از متن هم هست. ۲. هر زبان منظم، تصمیم پذیر هست. "هر زبان تصمیم پذیر، مستقل از متن هم هست. ۲. هر زبان مستقل از متن تشخیص پذیر هست.
۱۶- کدامیک از زبانهای زیر تصمیم پذیر است؟
ALLCFG = {< G > | c. L(G)=X ss, CFG & G \ . )
۲. {P یک نمونه برای مسأله تطابق پست بوده و دارای تطبیق است. || ۳. {M یک LBA بوده که رشته W را می پذیرد || < W و ALBA = {< M
ELBA = { < M > | L(M) = ø , ss: LBA · K, M } , * ۱۷- کدامیک از مجموعه های زیر ناشمار است؟
۱. مجموعه اعداد گویا ۲. مجموعه تمام ماشین های تورینگ
.Y . مجموعه اعداد صحیح .Y . مجموعه تمام زبانها ۱۸- اگر A به B کاهش پذیر باشد کدام گزینه صحیح نیست؟
۱. اگر B قابل حل باشد آنگاه A نیز قابل حل است. ۲. اگر B تصمیم پذیر باشد آنگاه A نیز تصمیم پذیر است. .*
اگر A تصمیم پذیر نباشد آنگاه B نیز تصمیم پذیر نیست. ۴. اگر B تصمیم پذیر نباشد آنگاه A نیز تصمیم پذیر نیست. ۱۹- کدامیک از مجموعه دومینوهای زیر می تواند حاوی تطبیق باشد.
{[abc/ab], [ca/al,[acc/ba]} Y {[b/ca], [a/ab),[ca/al,[abc/c]} .)
{[bab/abab),[b/aa], [abaa/babl) Y {[ab / abab], [b /aa], [aba/ bab], [aa/ba]} .Y
M.).|).). YYY).
نیمسال دوم ۹۳-۱۳۹۲ صفحه ۳ از ۵***
.
藥 کارشناسی مرکز آزمون و سنجش حضرت علی(ع): دانش راهبر نیکویی برای ایمان است
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰
عنوان درس : نظریه محاسبه رشته تحصیلی /کد درس : علوم کامپیوتر ۱۱۱۱۴۱۶
۲۰- در مورد ( M یک ماشین تورینگ حداقل است || < MINTM = { < M کدامیک از گزینه های زیر صحیح است ؟
۱. MINTM تصمیم پذیر است. ۲. MINTM تصمیم پذیر نیست ولی تشخیص پذیر است.
۳. MINTM هم تشخیص پذیر است و هم تصمیم پذیر ۴. MINTM نه تشخیصی پذیر است و نه تصمیم پذیر
۲۱- کدامیک از فرمولهای زیر خوش تعریف است؟ VY۱ E۴۲ / R۱( ۴۱, ۲۲ ) ۸ R۲ ( ۴۱, ۲, ۳۳ )/۰۲ ΚΙ (χ1, χ2)ν R1 (χ2,x1, χ3)
VχΙ Ξx2 R (χΙ) Λ R2 (χ1, χ2). * -IR (χΙ, χ2, χ3)ν - R2 (χ3, χ2, χ1) "
------برابر است با R(xo , x2 , Xs( در فرمول اتمی R ۲۲- رتبه نماد رابطه ای
۲۳- کدامیک از فرمولهای زیر یک عبارت نمی باشد. VxHy [R1(x,z,y) a—R2(y,x)] - Y Vx, y [R(x, y) v R(y,x)] .)
Vx, y [R(x,y) → - R(y,x)] . . VxHy Hz [R1(x,z,y)] V ۲۴- در مورد توصیف حداقل اتصال دو رشته x و y یعنی (RK(Xy کدامیک از گزینه های زیر صحیح نیست؟
[K(xy) < 2 log(K(x)) + K(x) + K(y)+c] 'Y [K(xy) < 2K(x) + K(y)+c] .)
[K(xy) > K(x) + K(y)+c] . . [K(xy) < K(x) + K(y)+c) Y
----- ۲۵- حداکثر تعداد رشته های به طول ۸ که قابل فشرده شدن به طول ۴ باشد برابر است با
ΥΔ . * ץ. ו"ז "ו. "ז"ו *१ . M.).|).). YYY).
= نیمسال دوم ۹۳-۱۳۹۲ = صفحه ۴ از ۵
***