æ tbd | ×wih . WWW29FILE.ORG کاو شنا را به خانههای
2/S = انشتاه پیام نور
W.:*. مر=ح--ز آزمون و سنجش দ্বাক্ষ تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱ عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی )۱۱۱۱۱۰۷
استفاده از ماشین حساب ساده مجاز است ۱- یک وسلیه خارجی است برای زبان B که این قابلیت را دارد که مشخص کند که رشته W عضو B می باشد یا خیر؟ ۱. الهام گیرنده ۲. تصمیم گیرنده
.Y . تشخیصی دهنده f ماشین تورینگ کاهش پذیر
۱. هر زبان تصمیم پذیر، تشخیصی پذیر هم هست. ۲. یک زبان تشخیص پذیر تورینگ است اگر و تنها اگر شمارنده ای برای بر شمردن آن موجود باشد. ۳. قدرت ماشین های تورینگ معین و نامعین باهم یکسان است. ۴. قدرت ماشین های تورینگ چندنواره از ماشین های تورینگ معین و نامعین بیشتر است.
۳- اگر ماشین تورینگ M برای رشته های W عضو زبان دنباله محاسباتی پذیرش شونده داشته باشد ولی برای برخی رشته ----- های غیر عضو زبان دنباله محاسباتی رد شونده نداشته باشد آنگاه
۱. (L(M تشخیصی پذیر است. ۲. (L(M تصمیم پذیر است.
۳. (L(M هم تصمیم ناپذیر و هم تشخیصی ناپذیر است. ۴. (L(M تشخیصی ناپذیر است. ۴- اگر تابع انتقال برای ساختار ttaq ibw بصورت (O(qi ,b) = (qj ,b, L باشد ساختار بعدی چیست؟
aav . )
q,uabv , * иаq;уb .* uq jabv V иq j
۵- در ماشین تورینگ معین تابع انتقال به چه صورتی است؟ 6:охг" —эox{ LR)" ” ð: OX T—> O X TX ( L, R } )
6:Qx T-> P(QXTX {L, R}) : * 6:Qxr" —»QxT" x{ L.R)" '
۶- کدامیک از زبانهای زیر تصمیم پذیر نیست؟ ۱. ( G گراف همبند بدون جهت است || ۴. ( W دارای تعداد مساوی ۰ و ۱ است |D= { W
1010/10.1031258
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۱ از ۴
***
æ tbd | ×wih . WWW29FILE.ORG کاو شنا را به خانههای
2/S = انشتاه پیام نور
W.:*. مر=ح--ز آزمون و سنجش দ্বাক্ষ تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱ عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی )۱۱۱۱۱۰۷
استفاده از ماشین حساب ساده مجاز است ۱- یک وسلیه خارجی است برای زبان B که این قابلیت را دارد که مشخص کند که رشته W عضو B می باشد یا خیر؟ ۱. الهام گیرنده ۲. تصمیم گیرنده
.Y . تشخیصی دهنده f ماشین تورینگ کاهش پذیر
۱. هر زبان تصمیم پذیر، تشخیصی پذیر هم هست. ۲. یک زبان تشخیص پذیر تورینگ است اگر و تنها اگر شمارنده ای برای بر شمردن آن موجود باشد. ۳. قدرت ماشین های تورینگ معین و نامعین باهم یکسان است. ۴. قدرت ماشین های تورینگ چندنواره از ماشین های تورینگ معین و نامعین بیشتر است.
۳- اگر ماشین تورینگ M برای رشته های W عضو زبان دنباله محاسباتی پذیرش شونده داشته باشد ولی برای برخی رشته ----- های غیر عضو زبان دنباله محاسباتی رد شونده نداشته باشد آنگاه
۱. (L(M تشخیصی پذیر است. ۲. (L(M تصمیم پذیر است.
۳. (L(M هم تصمیم ناپذیر و هم تشخیصی ناپذیر است. ۴. (L(M تشخیصی ناپذیر است. ۴- اگر تابع انتقال برای ساختار ttaq ibw بصورت (O(qi ,b) = (qj ,b, L باشد ساختار بعدی چیست؟
aav . )
q,uabv , * иаq;уb .* uq jabv V иq j
۵- در ماشین تورینگ معین تابع انتقال به چه صورتی است؟ 6:охг" —эox{ LR)" ” ð: OX T—> O X TX ( L, R } )
6:Qx T-> P(QXTX {L, R}) : * 6:Qxr" —»QxT" x{ L.R)" '
۶- کدامیک از زبانهای زیر تصمیم پذیر نیست؟ ۱. ( G گراف همبند بدون جهت است || ۴. ( W دارای تعداد مساوی ۰ و ۱ است |D= { W
1010/10.1031258
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۱ از ۴
***
æ tbd | ×wih . WWW29FILE.ORG کاو شنا را به خانههای
業 = انش متاه پیام نور
W.:*. 25 محسن آنتون و سنجش تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱
عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی ) ۱۱۱۱۱۰۷
۷- اگر P چندجمله ای 7 + 6۲ + 4x2 - 23 + 3۲ - 65 باشد ریشه های P در چه بازه ای تغییر می کنند؟ [–8. 8] . * I_7.7|| ." |–6 . 6] . Y [–5.5] . )
۸- مجموعه زبانهای تشخیص پذیر نسبت به کدام دسته از عملگرهای زیر بسته هستند؟ ۱. اجتماع و اشتراک ۲. اشتراک و مکمل ۳. اجتماع و مکمل آ، اجتماع و اشتراک و مکمل
۹- اگر گرامر مستقل از متن G به فرم نرمال چامسکی باشد، هر اشتقال W به طول n دارای چند گام می باشد؟
n_1 . Y. m-|. 1 . Yo Yn_1 Y Yn4.1 . ۱۰- در مورد گرامرهای مستقل از متن کدامیک از موارد زیر تصمیم ناپذیر است. ۱. هر زبان مستقل از متن ۲. ( G یک گرامر مستقل از متن بوده و ECEG = { | L(G)= O ۳. ( G یک گرامر مستقل از متن بوده که رشته ورودی W را می پذیرد || < AcrG ={۴. (G یک گرامر مستقل از متن بوده و All CFG = ( < G> |L(G)=XE
۱۱- برای اثبات ناشمارا بودن R پیمایش روی عناصر ماتریس را به چه صورتی انجام می دهیم؟
۱. سطری ". ستونی ۳. قطری ۴. تصادفی
۱۲- به این دلیل بعضی از زبانها تشخیصی پذیر تورینگ نیستند که؟
۱. تعداد زبانها و تعداد ماشین های تورینگ هردو ناشمارا می باشد. ۲. تعداد زبان ها از تعداد ماشین ها تورینگ شمارا بیشتر است. ۳. تعدا زبان ها از تعداد ماشین ها تورینگ شمارا کمتر است. ۲. مکمل آنها تشخیص پذیر تورینگ است. ۱۳- اگر A به B کاهش پذیر باشد کدام گزینه صحیح نیست؟ ۱. اگر A تصمیم پذیر نباشد آنگاه B نیز تصمیم پذیر نیست. ۲. اگر B تشخیص پذیر نباشد آنگاه A نیز تشخیص پذیر نیست. ۳. اگر B تصمیم پذیر باشد آنگاه A نیز تصمیم پذیر است.
۴. اگر B قابل حل باشد آنگاه A نیز قابل حل است.
γ«Υ /Υ γ«Υ"ΥΥΔΛ نیمسال دوم qY"—AY"\\ = صفحه ۲ از ۴
***
æ tbd | ×wih . WWW29FILE.ORG کاو شنا را به خانههای
業 = انش متاه پیام نور
W.:*. 25 محسن آنتون و سنجش تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : یک ۱
عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی ) ۱۱۱۱۱۰۷
۷- اگر P چندجمله ای 7 + 6۲ + 4x2 - 23 + 3۲ - 65 باشد ریشه های P در چه بازه ای تغییر می کنند؟ [–8. 8] . * I_7.7|| ." |–6 . 6] . Y [–5.5] . )
۸- مجموعه زبانهای تشخیص پذیر نسبت به کدام دسته از عملگرهای زیر بسته هستند؟ ۱. اجتماع و اشتراک ۲. اشتراک و مکمل ۳. اجتماع و مکمل آ، اجتماع و اشتراک و مکمل
۹- اگر گرامر مستقل از متن G به فرم نرمال چامسکی باشد، هر اشتقال W به طول n دارای چند گام می باشد؟
n_1 . Y. m-|. 1 . Yo Yn_1 Y Yn4.1 . ۱۰- در مورد گرامرهای مستقل از متن کدامیک از موارد زیر تصمیم ناپذیر است. ۱. هر زبان مستقل از متن ۲. ( G یک گرامر مستقل از متن بوده و ECEG = { | L(G)= O ۳. ( G یک گرامر مستقل از متن بوده که رشته ورودی W را می پذیرد || < AcrG ={۴. (G یک گرامر مستقل از متن بوده و All CFG = ( < G> |L(G)=XE
۱۱- برای اثبات ناشمارا بودن R پیمایش روی عناصر ماتریس را به چه صورتی انجام می دهیم؟
۱. سطری ". ستونی ۳. قطری ۴. تصادفی
۱۲- به این دلیل بعضی از زبانها تشخیصی پذیر تورینگ نیستند که؟
۱. تعداد زبانها و تعداد ماشین های تورینگ هردو ناشمارا می باشد. ۲. تعداد زبان ها از تعداد ماشین ها تورینگ شمارا بیشتر است. ۳. تعدا زبان ها از تعداد ماشین ها تورینگ شمارا کمتر است. ۲. مکمل آنها تشخیص پذیر تورینگ است. ۱۳- اگر A به B کاهش پذیر باشد کدام گزینه صحیح نیست؟ ۱. اگر A تصمیم پذیر نباشد آنگاه B نیز تصمیم پذیر نیست. ۲. اگر B تشخیص پذیر نباشد آنگاه A نیز تشخیص پذیر نیست. ۳. اگر B تصمیم پذیر باشد آنگاه A نیز تصمیم پذیر است.
۴. اگر B قابل حل باشد آنگاه A نیز قابل حل است.
γ«Υ /Υ γ«Υ"ΥΥΔΛ نیمسال دوم qY"—AY"\\ = صفحه ۲ از ۴
***
WWWy 2pFIL E. ORG . = انشتاه پیام نور کارشناسی - :7ץ:/"זריזו
W.:*. مر=ح--ز آزمون و سنجش
S!! 2
-> -->
-
|
Z NS
تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک
عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی ) ۱۱۱۱۱۰۷
۱۴- اگر M یک LBA با ۲ حالت و ۴ نماد در الفبای نوار باشد چند ساختار متفاوت از m برای یک نوار به طول ۳ وجود دارد؟ ャ人や f ○%Y .Y %や人 。Y Y \ 2 . )
۱۵- اگر در یک LBA تعداد حالتها ۵ برابر شود، تعداد ساختارهای متفاوت از این LBA چه تغییری خواهد کرد. ۱. 5m برابر می شود ۲. به اندازه "5 تا بیشتر می شود
. Y.
۵۰۲ برابر می شود "3 برابر می شود
۱۶- در مورد مسأله تطابق پست کدامیک از گزینه های زیر صحیح است؟
۱. تصمیم پذیر است. ۲. منظم است. ۳. تشخیصی ناپذیر است. ۴. تصمیم ناپذیر است. - —W ----- باشد انگاه A گm A تشخیص پذیر تورینگ بوده و A اگر ۱. A تصمیم ناپذیر است. ۲. A تشخیص ناپذیر است. ۳. A تصمیم پذیر است. ۴. چنین چیزی امکان ندارد. ۱۸- کدامیک از عبارات ریاضی زیر بیان می کند که تعداد اعداد اول نامتناهی هستند؟ VqE p Hx,y[p > q^(x, y> \ → xyz p )] .\ Vg=p Vx,ylp > q^(x, y > → xy + p^ wチp+Yル 。ャ V4Ep Vx,ylp > q^(x, y > → xy + p \| " V45p Vx,ylp < q v(x, y > ) → xy + p.)| : ۱۹- کدامیک از فرمولهای زیر خوش تعریف نیست؟ —IRI (x1, x2, x3)v R2 (x3, x2, x1) - V -R1 (χ1, χ2)Λ R2 (χ2, χ3) . ) VxI =x2 [R1(x1, x2) A R2 (x1, x3) v R(x3)] . . R (x1,x, x3) Y ۲۰- کدامیک از فرمولهای زیر یک عبارت است؟ Exp Wx» [Rj (x1, x»)v R» (x1, x3)] - Y VχΙ R] (χ1)ν R] (χ2) . ! Vxl Ex2 [R1(x1, x2) v R2 (x2, x1, x3)] * VχΙ Ηx2 [R1(χ1, χ2)ν - R2 (χ1, χ2)] ." ۲۱- متغیری که در دامنه نفوذ یک سور قرار نداشته باشد چه نام دارد؟ ۱. جمله ۲. رابطه .Y . آزاد .Y . مدل
γ«Υ /Υ γ«Υ"ΥΥΔΛ
= نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۳ از ۴

***
WWWy 2pFIL E. ORG . علی دانشحه پیام نو، کارشناسی - :7ץ:/"זריזו W.:*. مر=حا-ز آزمون و سنجش 恭 تعداد سوالات : تستی : ۲۵ تشریحی : ۵ زمان آزمون (دقیقه) : تستی : ۶۰ تشریحی : ۶۰ سری سوال : ۱ یک عن-وان درس : نظریه محاسبات
رشته تحصیلی / کد درس : علوم کامپیوتر، علوم کامپیوتر(چند بخشی ) ۱۱۱۱۱۰۷
۲۲- نماد رتبه ای R در رابطه (IR(x1,x2, x3 چند است؟
Y t * . Y. f Y A . )
۲۳- بررسی درستی یا نادرستی یک عبارت در نظریه اعداد یعنی (* و+ ,N) روی مجموعه جهانی اعداد طبیعی با جمع و ضرب ----- معمولی
۱. تصمیم پذیر است. ۲. کاهش پذیر است. ۳. تصمیم ناپذیر است. ۴. قابل حل است.
۲۴- اگر X یک رشته و (K(A طول توصیف آن باشد، X را فشرده پذیر به مقدار 5 گویند اگر:
K(X) >|X|–5 t K(X) >|X|+5 v K(X) <|X|–5 Y K(X) <| X |+5 .)
----- ۲۵- حداقل تعداد رشته های به طول ۵ که قابل فشرده شدن به طول ۳ نباشد برابر است با
A Y ү . Ү YN . Y የም .\ سوالات تشریحی - ثابت کنید (1 < C = {abick ix j = k , ijk تصمیم پذیر است ؟ ۱،۴۰ نمره ۲- ثابت کنید {A و B هر DFA بوده و (B> | L(A)=L(B وEOpFA = {EQTM = { < M1,M2 > L(M1)=L(M2) 3 se 3: TM 3e,» M29 M1 }
۴- ثابت کنید بعضی از عبارات درست در (*,Th(N, F قابل اثبات نیستند؟ ۱،۴۰ نمره
۵- ثابت کنید {Mیک TM بوده و ETM = { | L(M) = )D تصمیم ناپذیر است. ۱،۴۰ نمره
γ«Υ /Υ γ«Υ"ΥΥΔΛ
نیمسال دوم ۹۴-۱۳۹۳ = صفحه ۴ از ۴
***