سوالات

کدام‌یک از ساختار دادههای زیر پیچیدگی زمانی حداقل مشابه با هرم مینیمم برای درج و حذف یک عنصر را دارد؟

فرض کنید می‌خواهیم کمترین تعداد ضرب عددی ممکن برای محاسبه ضرب A_1 × A_2 × ⋯ × A_n را با استفاده از روش برنامه‌نویسی پویا (Dynamic programming) پیدا کنیم. برای این‌کار لازم است از یک جدول n × n…

فرض کنید می‌خواهیم یک آرایه ۱۰ عنصری را با استفاده از الگوریتم مرتب‌سازی ادغامی، مرتب کنیم. چند مورد از موارد زیر صحیح است؟ (I) تعداد فراخوانی تابع merge در این الگوریتم ۱۹ است. (II) تعداد…

الگوریتم زیر برای مرتب‌سازی یک آرایه n عنصری از اعداد ۱، ۰ و ۱- است. به‌جای ...... چه دستوری باید قرار گیرد؟ sort(A) i = ۰ ; j = ۰ ; h = n+۱ ; while(h != j+۱) if(A[j+۱] == -۱) A[j+۱] <-> A[i+۱]…

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

فرض کنید الگوریتم بلمن ـ فورد (Bellman-Ford) برای محاسبه کوتاه‌ترین مسیر تک منبعی در یک گراف وزن‌دار تقریباً کامل استفاده شده است. مرتبه زمانی آن چقدر است؟ (v نشان‌دهنده تعداد گره‌ها و e نشان‌دهنده…

مرتبه زمانی محاسبه رابطه روبه‌رو کدام است؟ ∑_(i=۱)^n frac ۱ i^۲

فرض کنید تمام توابع log در این سؤال بر مبنای ۲ هستند و تعریف تابع log^() به شرح زیر است: log^() n = min i ≥ 0 : log^((i)) n ≤ 1 ترتیب توابع زیر را براساس نرخ رشد (از کمترین نرخ رشد به بیشترین نرخ…

فرض کنید یک متن فارسی به شما داده شده است که فقط ۳۳ کاراکتر در آن ظاهر شده‌اند (۳۲ کاراکتر الفبای فارسی به‌علاوه کاراکتر فاصله). نتیجه شمارش فراوانی این ۳۳ کاراکتر در این متن نشان می‌دهد که فراوانی…

آرایه‌ای به طول n داریم که k − n عنصر آن مرتب و k عنصر آن نامرتب هستند. اگر k خیلی کوچک‌تر از n باشد آنگاه کدام الگوریتم مرتب‌سازی دارای بهترین کارایی برای مرتب کردن آن است؟

اگر هزینه‌ی f(m) و g(m) برابر θ(m) باشد، هزینه‌ی h(n) چقدر است؟ h(n) p = ۱ for(i = ۱ ; i <= n ; i++) f(i) if(i == p) g(n) p = p × ۲

فرض کنید تابعی برای محاسبه‌ی x^n (توان) ندارید و می‌توانید از چهار عنصر اصلی استفاده کنید. x یک عدد دلخواه و n یک عدد طبیعی است. بهترین زمانی که می‌توانید در آن، x^n را محاسبه کنید، کدام است؟

کدام‌یک از مسائل زیر دارای پیچیدگی محاسباتی چند جمله‌ای است؟

متنی شامل حروف f ,a, b, c, d, e با فراوانی‌های زیر داده شده است. اگر این حروف را طبق کد هافمن کدگذاری کنیم تعداد بیت‌های f و a به‌ترتیب از راست به چپ کدام است؟ حروف a b c d e f…

الگوریتم خرد کردن پول با روش حریصانه برای وقتی‌که بخواهیم ۱۴ واحد پول را از طریق سکه‌های ۱۰ ، ۷ ، ۲ ، ۱ واحد خرد کنیم، چند سکه به‌دست می‌دهد؟

در مورد الگوریتم فلوید (برای محاسبه کوتاه‌ترین مسیر در گراف وزن‌دار) کدام گزینه صحیح است؟

فرض کنیم ‎ L_1 ‎ و ‎ L_2 ‎ زبان‌های منظم باشند. کدام مورد برای زبان ‎ L = w : w ∈ L_1, w^R ∈ L_2 ‎ صحیح است؟

کدام عبارت در زبان تولید شده توسط عبارت منظم r = (aa)^() b (bb)^() + a(aa)^() (bb)^() قرار ندارد؟

فرض کنید L = (01^()01^(+))^() و L' = ((0 + 00)1^(+))^() ، کدام گزینه درست است؟

L یک زبان منظم است. کدام‌یک از زبان‌های زیر لزوماً مستقل از متن است؟ L' = ww^Rw w ∈ L L'' = ww^Ru w, u ∈ L

کدام‌یک از زبان‌های زیر مستقل از متن است؟

گرامر G با قوانین تولید S → aSbb aaSbbb λ مفروض است. کدام عبارت در L(G) قرار دارد؟

فرض کنید L زبان همه رشته‌هایی با الفبای ۰ , ۱ است که تعداد صفرهایشان زوج است. زبان کدام‌یک از گرامرهای زیر برابر L است؟ الف- S → ۱S ۰S۰ ε ب- S → ۱S ۰T۰S ε , T → ۱T ε

npda با گراف انتقال زیر را درنظر می‌گیریم، کدام رشته در زبان این اتوماتای پشته‌ای قرار دارد؟ (α , β ; ω یعنی در شرایطی که با نماد بالایی پشته β است و α از ورودی خوانده می‌شود، رشته ω در پشته جایگزین…

دو تغییر زیر را روی هد (head) ماشین‌های تورینگ استاندارد اعمال و دو نوع ماشین جدید تعریف می‌کنیم: نوع اول: در هر حرکت (هر انتقال) مکان هد بتواند ثابت باشد، یک خانه به راست یا یک خانه به چپ حرکت کند.…

L و L' دو زبان هستند. چند تا از گزاره‌های زیر درست است؟ (توضیح نماد ≤ : برای دو زبان A و B می‌نویسیم A ≤ B هرگاه A تقلیل‌پذیر تورینگی به B باشد.) اگر L تصمیم‌پذیر باشد و L ≤ L' آن‌گاه L' تصمیم‌پذیر…

فرض کنید A یک مجموعه ناتهی و R و S دو رابطه هم‌ارزی روی A باشند و R⁻¹ و S⁻¹ نیز به‌ترتیب رابطه‌های وارون R و S باشند. در آن صورت کدام عبارت صحیح است؟

جدول ارزش‌ها را برای [(p → q) → (r → s)] → u تشکیل داده‌ایم. چه تعداد ۱ در ستون آخر آن دیده می‌شود؟

کدام‌یک از مجموعه‌های زیر شمارای نامتناهی است؟

فرض کنید ‏‏ Z ‏ مجموعه اعداد صحیح باشد. آنگاه مجموعه زیرمجموعه‌های متناهی ‏ Z ‏، ...

گزاره‌های زیر را در نظر می‌گیریم: T(a) = x دارای دم است B × y = x ، y را گاز می‌گیرد L(x , y) = x ، y را دوست دارد C(x) = x یک گربه است D(x) = x یک سگ است در آن‌صورت ترجمه فارسی گزاره زیر به‌صورت…

تعداد گزاره‌های ناهم‌ارز که تنها شامل P_1, P_2, P_3 باشد و از نماد منطقی leftrightarrow استفاده شود کدام است؟

اگر α و β و γ اعداد اصلی (cardinal) باشند، آنگاه:

نقیض گزارهٔ ∀ε ~∃δ ∀ x ~∀ y (x^2+y^2 < ε+δ) کدام است؟ (در اینجا ~ نماد نقیض است و ε و δ مقید به اعداد مثبت هستند و x و y اعداد حقیقی می‌باشند.)

کدام‌یک از جملات زیر در منطق مرتبه اول راست می‌باشد؟

چه تعداد از فرمول‌های گزاره‌ای زیر، قضیه‌ای از منطق گزاره‌ای نیستند؟ الف) (~ A → A) → A ب) A → (~ A → B) ج) ((~ B → ~ A) → A) → ((~ B → A) → B) د) (A → B) → A

اگر فرض کنیم A یک مجموعه شمارش‌پذیر نامتناهی باشد. آنگاه P(A) (مجموعه تمام زیرمجموعه‌های A ) .............

کدام‌یک از عبارت‌های زیر درست است؟

فرض کنید Γ مجموعه‌ای از گزاره‌های منطق گزاره‌ای باشد. حداکثر چند تا از احکام زیر با هم معادل‌اند؟ Γ سازگار ماکسیمال است. Γ تنها یک مدل دارد. برای هر گزارهٔ A ، Γ ⊢ A یا Γ ⊢ ¬ A . برای هر گزارهٔ A, B…

با فرض اینکه T_1 و T_2 دو نظریه سازگار در زبان L در منطق مرتبهٔ اول باشند، کدام مورد صحیح است؟