سوالات

حاصل رابطه بازگشتی زیر چیست؟ T(n) = 2T(n/4) + n^(0/51), n > 1 ; T(1) = 1, n = 1

فرض کنیم L یک زبان دارای DFA بر الفبای Σ باشد و a ∈ Σ . کدام مورد درخصوص زبان L' = w ∈ Σ^ : wa ∈ L درست است؟

‏DFA زیر، بر Σ = a, b, c مفروض است. اگر t تعداد رشته‌های به طول ۳ یا کمتر باشد که توسط این DFA پذیرفته می‌شود، کدام مورد درخصوص t درست است؟ خودکار دارای حالت‌های q_1, q_2, q_3, q_4 است. حالت شروع q_1…

اگر L زبان عبارت منظم r=(0+10)^ 1^ باشد و α=1001010110111 و β=0101000110011 ، کدام مورد درست است؟

دو زبان L_1 و L_2 را بر Σ = 0, 1 به‌صورت زیر، درنظر می‌گیریم: L_1 = 0^n 1 0^n 1 0^n : n ≥ 0 L_2 = w : w تعدادی فرد 0 دارد از این دو زبان، کدام منظم است؟

دو زبان L_1 و L_2 روی الفبای Σ = a, b را به‌صورت زیر در نظر می‌گیریم: L_1 = w : n_a(w) = n_b(w) شامل زیررشته‌ی aab نیست L_2 = a^n b^j a^i b^n : n, i, j ≥ 0 از این دو زبان، کدام مستقل از متن است؟

دو زبان L_1 و L_2 را بر Σ = a, b به‌صورت زیر در نظر می‌گیریم: L_1 = a^n b^j a^n b^j : n, j ≥ 0 L_2 = a^n b^j : 0 ≤ n ≤ j^2 از این دو زبان، کدام مستقل از متن است؟

گرامر G با متغیر شروع S بر Σ = a, b, c با قوانین تولید زیر را درنظر می‌گیریم: S → XY W X → aXb ε Y → cY ε W → aWc Z Z → bZ ε با قرار گرفتن کدام‌یک از دو مقدار b یا c به‌جای α در w = a^1402 b^1401 α…

اتوماتای پشته‌ای زیر مفروض است. اگر α = 000011 و β = 000101010 ، کدام‌یک از این دو رشته، توسط این اتوماتا پذیرش می‌شود؟ اتوماتا دارای حالت‌های q_0, q_1, q_2, q_3, q_4 است که q_0 حالت شروع و q_4 تنها…

فرض کنیم زبان‌های L_A ⊆ Σ^() و L_B ⊆ Σ^() توسط DFAهای A=(Q_A,Σ,δ_A,q_0,F_A) و B=(Q_B,Σ,δ_B,q_0',F_B) داده شده‌اند و Σ= 0,1,2 . اتوماتای C را با زبان L_C به‌صورت زیر در نظر می‌گیریم: C=(Q_A× Q_B, Σ…

ماشین تورینگ M با جدول انتقال زیر داده شده است (هر درایه (حالت بعدی، نماد نوشته‌شده، حرکت)؛ نشانگر ابتدای نوار و # نماد تهی است): state symbol 0 1 #…

کدام‌یک از دو استدلال زیر، معتبر است؟ (a) تمام اعداد گویا حقیقی هستند. بعضی اعداد مختلط، گویا نیستند. بنابراین: بعضی اعداد مختلط، حقیقی نیستند. (b) اگر من درس را پاس کرده باشم، آنگاه در میان‌ترم نمره…

از دو فرمول زیر، کدام‌یک در فرم نرمال فصلی (DNF) است؟ ( p_i ها اتم‌اند.) α = p_1 ∧ ¬ p_2 β = p_1 ∨ (¬ p_2 ∨ ¬ p_3)

در زبان L = ≤ شامل یک رابطه دوتایی، فرض کنیم Σ_DLO نظریه ترتیب‌های خطی چگال بدون نقاط انتهایی باشد. از دو مورد زیر، کدام‌یک درست است؟ I ـ اگر u_1 و u_2 ساختارهای شمارا برای Σ_DLO باشند، دراین‌صورت…

فرض کنیم α = (q → p) → r و β = q → (r → p) . کدام مورد درخصوص استلزام منطقی α و β صحیح است؟

فرض کنیم: S : سالم زندگی می‌کنیم K : کمتر از ماشین‌ها استفاده می‌کنیم G : می‌توانیم زندگی خوبی داشته باشیم کدام مورد، بهترین ترجمه برای عبارت زیر است: «اگر سالم زندگی می‌کنیم مگر آنکه کمتر از…

از دو عبارت زیر، کدام صحیح است؟ الف) جملات ∃ x (P(x) ∧ Q(x)) و ∃ x P(x) ∧ ∃ x Q(x) معادل منطقی هستند. ب) جملات ∃ x (P(x) ∨ Q(x)) و ∃ x P(x) ∨ ∃ x Q(x) معادل منطقی هستند.

فرض کنیم φ_n جمله زیر در زبان گراف‌ها باشد: «برای هر زوج (A , B) با مؤلفه اول و دوم زیرمجموعه‌ای از رأس‌ها که A = B = n و A ∩ B = ∅ ، رأس V ∉ A ∪ B وجود دارد که برای هر w ∈ A داریم vEw و برای هر w ∈…

فرض کنیم: K(x) : x کارخانه است C(x) : x خودرو است P(x) : x شخص است H(x) : x پلاک فعال دارد S(x,y,z) : x ، y را به z می‌فروشد کدام مورد، ترجمه صحیح عبارت زیر است: «کارخانه‌ای هست که فقط به افرادی که…

فرض کنیم L = P زبان مرتبه اول باشد که P نماد رابطه‌ای دوتایی است. سه عبارت زیر را درنظر بگیرید: ۱) ∀ x ∀ y ∀ z (P(x,y) → (P(y,z) → P(x,z))) ۲) ∀ x ∀ y (P(x,y) → (P(y,x) → x=y)) ۳) ∀ x ∃ y P(x,y) → ∃…

فرض کنیم ⟨ M_n : n ∈ N ⟩ دنباله‌ای از L- ساختارها (L-structure) باشد که M_n زیرساخت مقدماتی M_(n+1) باشد. قرار می‌دهیم M = bigcup_n M_n و ساخت M را با عالم سخن M به‌صورت طبیعی تعریف می‌کنیم. کدام…

فرض کنیم A مجموعه همه توابع از N به N که یک‌به‌یک نیستند، و B مجموعه همه توابع یک‌به‌یک از N به N باشد. از این دو مجموعه، کدام با مجموعه اعداد گویا هم‌توان است؟

فرض کنیم C مجموعه همه زیرمجموعه‌های شمارای 0,1 ^N باشد. در این‌صورت، C با کدام مجموعه هم‌توان است؟

از دو عبارت زیر، کدام مورد درست است؟ الف ـ اگر B ≤ A و A ≠ ∅ ، در این‌صورت، تابع پوشای f : B → A وجود دارد. ب ـ اگر تابع پوشای f : B → A وجود داشته باشد، آنگاه A ≤ B .

دو گزاره زیر درباره مجموعه اعداد طبیعی N را در نظر بگیرید: الف ـ مجموعه اعداد طبیعی N را می‌توان طوری مرتب کرد که نوع ترتیب مجموعه حاصل، اوردینال ω + 2 باشد. ب ـ مجموعه اعداد طبیعی N را می‌توان طوری…

اوردینال ω به‌صورت ω = 0, 1, 2, … تعریف می‌شود. کدام مورد درخصوص ω صحیح است؟ الف ـ ω < 3^ω ب ـ ω < ω^3

فرض کنید x = φ, φ , φ , φ, φ , φ . از دو مورد زیر، کدام عضو P(x) است؟ الف ـ φ, φ , φ ب ـ φ

مجموعه‌های A و B و C را به‌صورت زیر در نظر بگیرید: A = مجموعه همه توابع از N به 0, 1, 2 B = مجموعه همه توابع از N به N C = مجموعه همه توابع از Q به R کدام مورد، درست است؟

فرض کنیم S مجموعه همه دنباله‌های نامتناهی از اعداد طبیعی و P(S) مجموعه توانی S باشد. در این‌صورت تعداد توابع یک‌به‌یک و پوشا از S به P(S) چقدر است؟

فرض کنیم x یک مجموعه است. قرار می‌دهیم: a = β : β یک اوردینال است و تابع پوشای f : β → x وجود دارد . با استفاده از اصول نظریه مجموعه‌ها (ZF) می‌توان دید که a یک مجموعه است. از دو مورد زیر، کدام‌یک در…

از دو نتیجه زیر، کدام‌یک در نظریه مجموعه‌ها بدون اصل انتخاب، اثبات‌پذیر <u>نیست</u>؟ الف ـ اگر k کاردینالی باشد که k ≤ ℵ_0 در این‌صورت k = ℵ_0 یا k = n که n ∈ N . ب ـ اگر A = ℵ_0 در این‌صورت…

به چند طریق می‌توان یک پلکان ۱۱تایی را طی کرد، به‌طوری‌که در هر قدم، یک پله یا دو پله بتوان طی کرد؟

کوچک‌ترین مقدار n چقدر است، به‌طوری‌که هر زیرمجموعه n عضوی از مجموعه 1, 2, …, 49 ، شامل سه عدد صحیح x ، y و z باشد، به‌طوری‌که (x-y)(y-z)(z-x) بر 49 بخش‌پذیر باشد؟

چند رشته ۱۰ رقمی از ارقام ۱، ۲ و ۳ وجود دارد که یا در پنج رقم سمت چپ، هیچ رقمی برابر ۱ نباشد یا در پنج رقم سمت راست، هیچ رقمی برابر ۲ نباشد؟

می‌خواهیم اعداد دورقمی را در 45 دسته متمایز 2 تایی توزیع کنیم، به‌طوری‌که دو عدد 10 و 99 در یک دسته نباشند. به چند طریق، این دسته‌بندی امکان‌پذیر است؟

تعداد دسته جواب‌های معادله زیر در مجموعه اعداد صحیح، چقدر است؟ x_1 + x_2 + ⋯ + x_10 = 1 + 3 + 5 + 7 + ⋯ + 19 x_1 ≥ 1, x_2 ≥ 2, ⋯, x_10 ≥ 10

جواب عمومی رابطه‌ی بازگشتی زیر کدام است؟ a_n = 8a_(n-2) - 16a_(n-4)

تعداد اعضای مجموعه ۱, ۲, …, ۱۰۰ که نسبت به ۴۵ اول هستند، کدام است؟

فرض کنید گراف نابدیهی G ، یال برشی ندارد. کدام گزاره‌های زیر برای این گراف، درست است؟

در کدام‌یک از گراف‌های وزن‌دار و همبند، کوچک‌ترین درخت فراگیر (MST)، یکتا نیست؟