سوالات

در نوشته‌ای تعداد تکرار حروف A، B، C، D، E و F به ترتیب ۲۰۰، ۱۸۰، ۱۵۰، ۴۰، ۳۰ و ۲۰ بار می‌باشد. چنانچه آن نوشته را با استفاده از روش هافمن کد کنیم، طول کد تولید شده چند بیت خواهد بود؟

فرض کنید A و B دو مسئلة تصمیم‌گیری بوده و A ≤_p B باشد ( A در زمان چندجمله‌ای به B کاهش یابد). کدام گزینه درست است؟

درخت جستجوی دودویی بهینه برای نمونه زیر کدام است؟ اعداد ۱ ۲ ۳ ۴ ۵ --- --- --- --- --- --- احتمال جستجو ۰/۲ ۰/۴ ۰/۰۵ ۰/۱ ۰/۲۵

کدام یک از الگوریتم‌های زیر حریصانه می‌باشد؟ a = Fractional knapsack b = Dijkstra c = Bellman − ford d = kruskal

۸۴- در جستجوی عمق اول (Depth First Search) گراف زیر با فرض آنکه گره A گره مبدأ باشد و گره‌های مجاور به یک گره به ترتیب حروف الفبای انگلیسی ملاقات شوند، کدام مورد به ترتیب ملاقات گره‌ها را نمایش…

تابع زیر از چه مرتبه‌ای است؟ T(n) = ۲ T (⌊ √n ⌋) + log n

کدام‌یک از جملات زیر صحیح است؟

فرض کنید یک مجموعه متناهی مانند ∅ ≠ B که شامل اعداد صحیح است داده شده. حال هدف طراحی یک DFA روی الفبای ۰,۱ است به‌طوری که هر رشته مانند x = x_۱,…,x_n که به این DFA داده می‌شود در صورتی پذیرش می‌گیرد…

فرض کنید L_1 و L_2 منظم است. حال زبان‌های زیر را در نظر بگیرید: L'_1 = w w = u_1 v_1 u_2 v_2 … u_n v_n, u_1… u_n ∈ L_1, v_1… v_n ∈ L_2, u_i, v_i ∈ Σ L'_2 = w w = u_1 v_1 u_2 v_2 … u_n v_n, u_1… u_n ∈…

فرض کنید یک زبان روی الفبای Σ= a,b تعریف شده باشد به‌طوری که بین هر جفت a در رشته بتوان تعدادی فرد b یافت. DFA مینیمم روی این زبان شامل چند state است؟

به ازای هر state، k > ۰ و حروف الفبای ۰,۱ ، چه تعداد DFA با State، K می‌توان ارائه کرد؟

زبان معادل با گرامر زیر کدام است؟ S → Ax By A → By Cw B → x Bw C → y

رابطهٔ بازگشتی زیر چه زبانی را توضیح می‌دهد؟ Σ = a, b λ ∈ L ∀ x ∈ L ⇒ axab ∈ L, bx ∈ L

بر اساس چه مقداری از w ، L منظم می‌شود؟ L = a^n w b^n n ≥ ۰

کدام‌یک از زبان‌های زیر بازگشتی است؟

همه جملات زیر صحیح‌اند، به جز:

تعداد T در ستون آخر جدول ارزش گزارهٔ r leftrightarrow (p leftrightarrow q) برابر است با:

چه تعداد از استنتاج‌های زیر معتبر است؟ ¬ p, p ∨ q ⊨ q p ∨ q, ¬ q ∨ r ⊨ p ∨ r p → q, s → t ⊨ (p ∨ s) → (q ∧ t)

فرمول گزاره‌ای زیر، چه تعداد زیرفرمول گزاره‌ای دارد؟ ((p → ¬ q) ∨ ((p ∧ r) → s)) → ¬ r

فرض کنید یک رابط گزاره‌ای ۲ ـ موضعی باشد به‌طوری‌که pq غلط است اگر و تنها اگر p و q ارزش متفاوتی داشته باشند. در ستون آخر جدول ارزش گزارهٔ (pp)(qq) چند T وجود دارد؟

چه تعداد از استنتاج‌های زیر در دستگاه استنتاج طبیعی برقرارند؟ (¬ p) ∨ (q → p) ⊢ ¬ p ∧ q (¬ r) → (p ∨ q), (r ∧ ¬ q) ⊢ r → q p → (q → r) ⊢ p → (r → q)

تعداد زیرمجموعه‌های مجموعهٔ توانی مجموعهٔ ∅, ∅ برابر است با:

چه تعداد از ادعاهای زیر در مورد اصل استقرا در نظریهٔ مجموعه‌ها درست است؟ حقیقتی بدیهی در مورد اعداد است. قضیه‌ای در نظریهٔ مجموعه‌هاست. یک تعریف است.

فرض کنید A مجموعهٔ همهٔ دایره‌های در صفحه با مرکز با مختصات گویا و شعاع اصم و B مجموعهٔ همهٔ رابطه‌های هم‌ارزی روی مجموعهٔ اعداد حقیقی باشد. کدام یک از ادعاهای زیر در مورد این دو مجموعه درست است؟

دو جمله A : (∃ x_1)(∀ x_2) R(x_1, x_2) و B : (∃ x_1)(∀ x_2) ¬ R(x_1, x_2) را در نظر بگیرید. فرض کنید M_1 ساختار ⟨ Q ∩ [0,1], <⟩ و M_2 ساختار ⟨ Z, <⟩ باشد. در این‌صورت:

فرمول مرتبهٔ اول زیر به‌ترتیب چه تعداد متغیر آزاد و زیرفرمول دارد؟ (∀ x)(∃ y A(x,y) → ∃ y (B(x,y,z) ∧ D(z)))

چه تعداد از خواص زیر در ساختار حسابی، بیان‌پذیر (تعریف‌پذیر) است؟ اول بودن فرد بودن مربع کامل بودن

مجموعهٔ p ∧ q, p ∨ q, p → q ، چه تعداد زیرمجموعهٔ ناتهی مستقل دارد؟

با دو اتم p و q و دو رابط → و ¬ ، چند گزارهٔ غیر همارز که تناقض یا راستگو نباشند می‌توان ساخت؟

در ستون آخر جدول ارزش گزارهٔ ((p→ p)→ p)→(q→ p) چند مورد T وجود دارد؟

چه تعداد از فرمول‌های زیر منطقاً معتبر است؟ ∀ x (φ(x)leftrightarrowψ(x))leftrightarrow(∀ x φ(x)leftrightarrow∀ x ψ(x)) ∀ x ∃ y (φ(x)∨ψ(y))→(∀ x φ(x)∨∃ y ψ(y)) (¬∀ x ∃ y θ(x,y))→∃ w ∃ z θ(w,z)

به چند طریق می‌توان یک مجموعه n عضوی را به ساختاری برای یک زبان مرتبه اول با یک نماد محمولی ۲ـ موضعی و یک نماد تابعی ۱ـ موضعی تبدیل کرد؟ ( n > ۰ )

چه تعداد از فرمول‌های زیر در یک ساختار مرتبهٔ اول دارای تساوی ارضاءپذیر هستند؟ ∀ x ∀ y (x = y) ∀ x ∀ y (x ≠ y) ∀ x ∃ y (x ≠ y)

جایگزینی ترم t = f(x,g(y)) به جای متغیر y در چه تعداد از فرمول‌های A و B و C زیر، مجاز (آزاد) است؟ A: ∀ x R(x,y) B: ∃ z (∀ x R(x,z) → s(y)) C: ∃ x ∃ z (R(x,y) → s(z))

فرمول (¬∃ z ∀ y z≤ y)∧(∀ x ∀ y ∃ z (x≤ z≤ y∨ y≤ z≤ x)) ، در چه تعداد از ساختارهای ترتیبی اعداد طبیعی، اعداد صحیح، اعداد گویا و اعداد حقیقی درست است؟

Σ یک مجموعهٔ نامتناهی از جملات در یک زبان مرتبهٔ اول است. فرض کنیم به هر زیرمجموعهٔ متناهی Σ ، می‌توان یک جملهٔ دیگر اضافه کرد به‌طوری‌که مجموعهٔ حاصل سازگار باشد. چه تعداد از ادعاهای زیر لزوماً درست…

فرض کنید A = ۱,۲,...,۱۵ . چندتا از زیرمجموعه‌های A شامل دقیقاً سه عدد فرد هستند؟

گراف K_۱۰۰ شامل چند زیرگراف یکریخت با ستاره K_(۱،۴) است؟

مجموع اعداد ۶ رقمی که با رقم‌های ۴ و ۴ و ۴ و ۱ و ۱ و ۱ ساخته می‌شوند، کدام است؟

همه عبارات زیر درباره گراف G صحیح است، به‌جز: