سوالات

آخرین رأس انتخاب‌شونده با الگوریتم جستجوی سطح اول (BFS) و نیز با الگوریتم جستجوی عمق اول (DFS) روی گراف زیر و با شروع از S به‌ترتیب از راست به چپ کدام است؟ (هرگاه می‌توان بین چند رأس انتخاب داشت…

الگوریتم جستجوی عمق اول (DFS) را روی یک گراف با n رأس و m یال و با شروع از رأس s اجرا کرده‌ایم. چند بار با یال‌هایی مواجه می‌شویم (سروکار داریم) که یک سر آنها s است؟

عدد طبیعی n و عدد طبیعی a_1, …, a_n داده شده است. قصد داریم بدانیم دو اندیس i و j وجود دارد که 0 < a_i - a_j ≤ 5 یا خیر. زمان متوسط لازم برای این منظور با استفاده از درهم‌سازی (Hashing) از چه…

با اجرای الگوریتم کروسکال روی گراف زیر و با شروع از رأس S وزن چهارمین یال انتخاب شونده در درخت چند است؟

مرتبه زمانی سریع‌ترین الگوریتم برای مسئله زیر، کدام است؟ ورودی: یک گراف G با n رأس و m یال و یک رأس S از G خروجی: تعداد رأس‌هایی از G که فاصله آنها از S برابر با ۲ است.

الگوریتم دایکسترا روی گراف زیر اجرا کرده‌ایم. وزن پنجمین یالی که در الگوریتم در نظر گرفته می‌شود (relax یا به‌روزرسانی می‌شود) کدام است؟

G یک گراف کامل صد رأسی وزن‌دار است. یک پاسخ مسئله فروشنده دوره‌گرد (TSP) را روی آن A می‌نامیم. وزن همه یال‌های G را در ۳ ضرب و سپس با ۵ جمع می‌کنیم. یک پاسخ مسئله فروشنده دوره‌گرد روی گراف حاصل را B…

T یک درخت ریشه‌دار با ریشه r است و هر رأس x به آن یک وزن w(x) دارد. کدام رابطه بازگشتی منجر به یک الگوریتم پویا (dynamic) برای محاسبه وزن مسیری که از r شروع می‌شود که از S شروع می‌شود و مجموع وزن…

مقدار برش کمینه (min cut) میان s و t در گراف زیر، کدام است؟ شبکه‌ی جهت‌دار دارای مبدأ s ، دو رأس میانی چپ a (بالا) و b (پایین)، دو رأس میانی راست c (بالا) و d (پایین)، و مقصد t است، با ظرفیت یال‌ها…

فرض کنیم P ≠ NP . کدام مسئله یا مسائل زیر دارای الگوریتم چندجمله‌ای است؟ الف) ورودی: عدد طبیعی n و اعداد حقیقی مثبت a_1, ⋯, a_n و b_1, ⋯, b_n . خروجی: یک مجموعهٔ I ⊆ 1, ⋯, n به‌طوری که ∑_(i ∈ I) b_i…

کدام گزاره یا گزاره‌ها، درست است؟ الف ـ مسائل تصمیم‌گیری (یعنی مسائلی که جوابشان بله یا خیر است) دارای الگوریتم تقریبی (تخمینی، approximation) با فاکتور (ضریب تقریب) ۲ نیستند. ب ـ اگر مسئله‌ای دارای…

فرض کنیم L زبان منظم عبارت زیر باشد: r = b^()ab^()ab^()ab^() (b^()ab^()ab^()ab^()ab^()ab^()ab^())^() با قرار گرفتن کدام مقدار به‌جای m در عبارت w = b^۷۰۰a^۷۰۰(ab)^۷۰۰ma حاصل در L قرار می‌گیرد؟

عبارت منظم اتوماتون زیر چیست؟ (در شکل، نماد ∘ همان ۰ است.)

فرض کنیم هر بلوک از صفرهای متوالی در w اندازه زوج داشته باشد (مثلاً ۰۰۰۰۰۱۰۰ در L_1 هست ولی ۰۰۱۱۰ در L_1 نیست.) و L_1 = w ∈ ۰,۱ و L_2 = ۰^(۳^n) n ≥ ۰ . کدام‌یک از دو زبان فوق منظم است؟

گرامر G = (V, ∑, R, S) با مجموعه متغیرهای V = S, W, X, Y, Z ، متغیر شروع S ، ∑ = a, b, c و قوانین زیر مفروض است: S → XY W X → aXb ε Y → cY ε W → aWc Z Z → bZ ε با قرار گرفتن کدام‌یک از دو مقدار b یا…

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

فرض کنید: L_1 = w # x # w^R / w, x ∈ 0,1 ^(), w = x L_2 = x # y / x, y ∈ 0,1 ^(), x = 2 y کدام‌یک از دو زبان فوق مستقل از متن است؟ ( # یک حرف الفباست. همچنین برای هر رشته مانند z تعداد حروف z را با z…

از روی DFAهای D_1 و D_2 بر اساس ضرب دکارتی، DFAای به نام D ساخته می‌شود که: D_1 = ⟨ Q_1, ∑, δ_1, q_1^0, F_1 ⟩ D_2 = ⟨ Q_2, ∑, δ_2, q_2^0, F_2 ⟩ ⇒ D_1 × D_2 = ⟨ Q_1 × Q_2, ∑, δ, ⟨ q_1^0, q_2^0 ⟩, F ⟩…

اگر w = xWz در این‌صورت x را یک قطعه اولیه w و z را یک قطعه انتهایی w می‌گوییم ( x و W و z کاملاً دلخواه هستند بنابراین می‌توانند رشته تهی نیز باشند.) فرض کنید: P(L) = x x قطعه اولیه رشته‌ای مانند w…

فرض کنیم M ماشین تورینگ زیر باشد: ( B یعنی بلانک، که در برخی منابع با λ نشان داده می‌شود. اما b یک حرف الفباست.) اگر L(M) زبان این ماشین تورینگ باشد، کدام‌یک از موارد زیر درست است؟ الف) aaa bb aa bb…

گرامر مقابل را در نظر بگیرید: S → AB A → a A → BaB B → bbA کدام گزینه نادرست است؟

کدام استدلال معتبر است؟ الف) بعضی اعداد گویا، عدد طبیعی نیستند. تمام اعداد طبیعی، عدد صحیح هستند. بنابراین: بعضی اعداد گویا عدد صحیح نیستند. ب) تمام اعداد اول، مثبت هستند. بعضی اعداد منفی، مثبت…

فرض کنیم: α ≡ ¬ p → (q → r) β ≡ q → (p ∨ r) اگر ⇒ نماد استلزام منطقی در منطق گزاره‌ها باشد، کدام گزینه در مورد α و β درست است؟

فرض کنیم: تو در کنکور موفق می‌شوی: p تو تمام تمرین‌ها را حل می‌کنی: q تو در جلسه تمرکز داری: r کدام گزینه بهترین ترجمه برای عبارت زیر است؟ «تو در کنکور موفق می‌شوی فقط اگر تمام تمرین‌ها را حل کنی و…

فرض کنیم: J(x) : x جنگل است A(x) : x حیوان است B(x,y) : x متعلق به y است S(x,y) : x قوی‌تر از y است کدام گزینه بهترین ترجمه برای عبارت زیر است؟ «هر جنگل حیوانی دارد که از تمام حیوانات آن جنگل قوی‌تر…

کدام‌یک از فرمول‌های زیر، راستگو (همیشه درست) نیست؟

فرض کنیم، زبان شامل نماد محمولی دو موضعی A و نماد تابعی یک موضعی f باشد. تعبیری را در نظر می‌گیریم که در آن دامنه مجموعه اعداد طبیعی، A رابطه‌ی < و f تابع 2x است. از دو دنباله‌ی s = ⟨ s_1, s_2, s_3…

[توجه به برش: بالای صورت سؤال بریده شده و بخش دیده‌شده از وسط جمله آغاز می‌شود.] ... که در آن دامنه A ، Z ، رابطه ≤ و f تابع x-۱ باشد. کدام‌یک از دو فرمول زیر در این تعبیر، درست هستند؟ α = ∃ x_2 ∀…

کدام یک از دو عبارت زیر منطقاً معتبر (logically valid) هستند؟ ( A نماد محمولی دو موضعی دلخواه است.) الف) ∀ x ∃ y A(x,y) → ∃ y A(y,y) ب) ∃ x ∃ y A(x,y) → ∃ y A(y,y)

فرض کنیم رابط منطقی دوتایی با جدول ارزش زیر باشد. A B A B --- --- --- T T F T F T F T T F F T از دو مورد زیر کدام درست است؟ الف) ¬ A ≡ A A ب) A ∨ B ≡ ((A A) (B B))

استدلال زیر در سیستم استنتاج طبیعی را در نظر بگیرید: ((([P∧ R])/P ∧ E [P→ Q])/Q→ E ([P∧ R])/R ∧ E)/(((Q∧ R)/((P∧ R)→(Q∧ R))→ I)/((P→ Q)→((P∧ R)→(Q∧ R)))→ I) ∧ I چند مورد استفاده اشتباه از قوانین در…

از دو مجموعه زیر کدام شمارا است؟ الف) مجموعه تمام زیردنباله‌های دنباله ۱/n _(n=۱)^(∞) . ب) مجموعه a + b√۲ a, b ∈ Q . ( Q مجموعه اعداد گویا است.)

فرض کنیم A مجموعه همه توابع مانند f : N → ۰,۱ باشد. در این صورت مجموعه A با کدام‌یک از دو مجموعه زیر، هم‌توان (هم‌عدد) است؟ الف) بازه [۰,۱] ب) مجموعه تمام زیرمجموعه‌های مجموعه اعداد گویا

فرض کنیم A یک مجموعه و P(A) مجموعه توانی A باشد. اگر f : A → P(A) یک تابع باشد، کدام مورد صحیح است؟ الف) برای هر x ∈ A ، f(x) ⊆ A . ب) هیچ x ∈ A ای وجود ندارد که f(x) = x ∈ A x ∉ f(x) .

فرض کنیم A = 1, …, 10 و R رابطه شمردن (عاد کردن) بر A باشد. کدام گزینه در مورد زیرمجموعه B = 2, 5, 6 در مجموعه مرتب جزئی (A, R^(-1) - I_A) صحیح است؟ ( I_A یعنی رابطه همانی بر A )

کدام مورد (موارد) صحیح است؟ الف) اگر α و β اوردینال باشند و β subsetneq α آنگاه β ∈ α . ب) اگر α اوردینال باشد آنگاه α ∪ α یک اوردینال است.

p و q و r را سه جمله در زبان محمولات درجهٔ ۱ در نظر می‌گیریم، کدام استنتاج صحیح است؟

کدام مورد زیر، اوردینال حدی است؟ الف) ω + 1 ب) ω + 2

فرض کنیم (A , <) یک مجموعه مرتب خطی ناتهی باشد بهطوری که: I) برای هر a ∈ A یک b ∈ A هست که a < b . II) هر زیرمجموعه ناتهی A دارای کوچکترین عضو است. در اینصورت (A , <) ، با کدام مورد همواره یکریخت…

فرض کنیم F : P(A) → P(A) یک تابع است که از X ⊆ Y ⊆ A نتیجه شود F(X) ⊆ F(Y) . فرض کنیم T = X ⊆ A F(X) ⊆ X . کدام مجموعه عضو T است؟ الف) bigcap T ب) F(bigcap T)